1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
# SPDX-License-Identifier: GPL-2.0-or-later
# <pep8 compliant>
def line_merger(lines, precision=6):
merger = _LineMerger(lines, precision)
return merger.polylines
def _round_point(point, precision):
return tuple(round(c, precision) for c in point)
class _LineMerger:
def __init__(self, lines, precision):
self.segments = set() # single lines as tuples: ((sx, sy[, sz]), (ex, ey[, ez]))
self.used_segments = set()
self.points = dict() # key: point -> value: list of segments with this point as start or end point
self.precision = precision
self.setup(lines)
self.polylines = self.merge_lines() # result of merging process
def setup(self, lines):
for line in lines:
s = _round_point(line.start, self.precision)
e = _round_point(line.end, self.precision)
self.add_segment(s, e)
def add_segment(self, start, end):
if start == end:
return # this is not a segment
if end < start: # order start and end points to detect all doubles
segment = (end, start)
else:
segment = (start, end)
if segment in self.segments:
return # this segment already exist
self.segments.add(segment)
self.add_point(start, segment)
self.add_point(end, segment)
def add_point(self, point, segment):
segments = self.points.get(point)
if segments is None:
segments = list()
self.points[point] = segments
segments.append(segment)
def get_segment_with_point(self, point):
segments = self.points.get(point)
if segments is None:
return None
# Very important: do not return already used segments
for segment in segments:
if segment not in self.used_segments:
return segment
return None
def mark_as_used_segment(self, segment):
self.used_segments.add(segment)
self.segments.discard(segment)
def merge_lines(self):
def get_extension_point(point):
extension = self.get_segment_with_point(point)
if extension is not None:
self.mark_as_used_segment(extension)
if extension[0] == point:
return extension[1]
else:
return extension[0]
return None
polylines = []
while len(self.segments):
segment = self.segments.pop() # take an arbitrary segment
self.mark_as_used_segment(segment)
polyline = list(segment) # start a new polyline
extend_start = True
extend_end = True
while extend_start or extend_end:
if extend_start:
extension_point = get_extension_point(polyline[0]) # extend start of polyline
if extension_point is not None:
polyline.insert(0, extension_point)
else:
extend_start = False
if extend_end:
extension_point = get_extension_point(polyline[-1]) # extend end of polyline
if extension_point is not None:
polyline.append(extension_point)
else:
extend_end = False
polylines.append(polyline)
return polylines
|
