io_import_dxf/dxfimport/line_merger.py

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