break apart loops (#690)

1 files changed, 116 insertions, 38 deletions

diff --git a/lib/extensions/break_apart.py b/lib/extensions/break_apart.py
index 625ace55..32f548f6 100644
--- a/lib/extensions/break_apart.py
+++ b/lib/extensions/break_apart.py
@@ -1,68 +1,146 @@
-from copy import deepcopy
+import logging
+from copy import copy
 
-from shapely.geometry import Polygon
+from shapely.geometry import LineString, MultiPolygon, Polygon
+from shapely.ops import polygonize, unary_union
 
 import inkex
 
-from ..elements import AutoFill, Fill
+from ..elements import EmbroideryElement
 from ..i18n import _
 from ..svg import get_correction_transform
+from ..svg.tags import SVG_PATH_TAG
 from .base import InkstitchExtension
 
 
 class BreakApart(InkstitchExtension):
-    def effect(self):  # noqa: C901
-        if not self.get_elements():
-            return
+    '''
+    This will break apart fill areas into separate elements.
+    '''
+    def __init__(self, *args, **kwargs):
+        InkstitchExtension.__init__(self, *args, **kwargs)
+        self.OptionParser.add_option("-m", "--method", type="int", default=1, dest="method")
 
+    def effect(self):
         if not self.selected:
             inkex.errormsg(_("Please select one or more fill areas to break apart."))
             return
 
-        for element in self.elements:
-            if not isinstance(element, AutoFill) and not isinstance(element, Fill):
+        elements = []
+        nodes = self.get_nodes()
+        for node in nodes:
+            if node.tag in SVG_PATH_TAG:
+                elements.append(EmbroideryElement(node))
+
+        for element in elements:
+            if not element.get_style("fill", "black"):
                 continue
-            if len(element.paths) <= 1:
+
+            # we don't want to touch valid elements
+            paths = element.flatten(element.parse_path())
+            paths.sort(key=lambda point_list: Polygon(point_list).area, reverse=True)
+            polygon = MultiPolygon([(paths[0], paths[1:])])
+            if self.geom_is_valid(polygon):
                 continue
 
-            polygons = []
-            multipolygons = []
-            holes = []
+            polygons = self.break_apart_paths(paths)
+            polygons = self.ensure_minimum_size(polygons, 5)
+            if self.options.method == 1:
+                polygons = self.combine_overlapping_polygons(polygons)
+            polygons = self.recombine_polygons(polygons)
+            if polygons:
+                self.polygons_to_nodes(polygons, element)
 
-            for path in element.paths:
-                polygons.append(Polygon(path))
+    def break_apart_paths(self, paths):
+        polygons = []
+        for path in paths:
+            linestring = LineString(path)
+            polygon = Polygon(path).buffer(0)
+            if not linestring.is_simple:
+                linestring = unary_union(linestring)
+                for polygon in polygonize(linestring):
+                    polygons.append(polygon)
+            else:
+                polygons.append(polygon)
+        return polygons
+
+    def combine_overlapping_polygons(self, polygons):
+        for polygon in polygons:
+            for other in polygons:
+                if polygon == other:
+                    continue
+                if polygon.overlaps(other):
+                    diff = polygon.symmetric_difference(other)
+                    if diff.geom_type == 'MultiPolygon':
+                        polygons.remove(other)
+                        polygons.remove(polygon)
+                        for p in diff:
+                            polygons.append(p)
+                        # it is possible, that a polygons overlap with multiple
+                        # polygons, this means, we need to start all over again
+                        polygons = self.combine_overlapping_polygons(polygons)
+                        return polygons
+        return polygons
 
-            # sort paths by size and convert to polygons
-            polygons.sort(key=lambda polygon: polygon.area, reverse=True)
+    def geom_is_valid(self, geom):
+        # Don't complain about invalid shapes, we just want to know
+        logger = logging.getLogger('shapely.geos')
+        level = logger.level
+        logger.setLevel(logging.CRITICAL)
+        valid = geom.is_valid
+        logger.setLevel(level)
+        return valid
 
-            for shape in polygons:
-                if shape in holes:
+    def ensure_minimum_size(self, polygons, size):
+        for polygon in polygons:
+            if polygon.area < size:
+                polygons.remove(polygon)
+        return polygons
+
+    def recombine_polygons(self, polygons):
+        polygons.sort(key=lambda polygon: polygon.area, reverse=True)
+        multipolygons = []
+        holes = []
+        for polygon in polygons:
+            if polygon in holes:
+                continue
+            polygon_list = [polygon]
+            for other in polygons:
+                if polygon == other:
                     continue
-                polygon_list = [shape]
-
-                for other in polygons:
-                    if shape != other and shape.contains(other) and other not in holes:
-                        # check if "other" is inside a hole, before we add it to the list
-                        if any(p.contains(other) for p in polygon_list[1:]):
-                            continue
-                        polygon_list.append(other)
-                        holes.append(other)
-                multipolygons.append(polygon_list)
-            self.element_to_nodes(multipolygons, element)
-
-    def element_to_nodes(self, multipolygons, element):
-        for polygons in multipolygons:
-            el = deepcopy(element)
+                if polygon.contains(other) and other not in holes:
+                    if any(p.contains(other) or p.intersects(other) for p in polygon_list[1:]):
+                        continue
+                    holes.append(other)
+                    # if possible let's make the hole a tiny little bit smaller, just in case, it hits the edge
+                    # and would lead therefore to an invalid shape
+                    o = other.buffer(-0.01)
+                    if not o.is_empty and o.geom_type == 'Polygon':
+                        other = o
+                    polygon_list.append(other)
+            multipolygons.append(polygon_list)
+        return multipolygons
+
+    def polygons_to_nodes(self, polygon_list, element):
+        # reverse the list of polygons, we don't want to cover smaller shapes
+        polygon_list = polygon_list[::-1]
+        index = element.node.getparent().index(element.node)
+        for polygons in polygon_list:
+            if polygons[0].area < 5:
+                continue
+            el = copy(element.node)
             d = ""
             for polygon in polygons:
-                # copy element and replace path
-                el.node.set('id', self.uniqueId(element.node.get('id') + "_"))
+                # update element id
+                if len(polygon_list) > 1:
+                    node_id = self.uniqueId(el.get('id') + '_')
+                    el.set('id', node_id)
                 d += "M"
                 for x, y in polygon.exterior.coords:
                     d += "%s,%s " % (x, y)
                     d += " "
                 d += "Z"
-            el.node.set('d', d)
-            el.node.set('transform', get_correction_transform(element.node))
-            element.node.getparent().insert(0, el.node)
+            el.set('d', d)
+            el.set('transform', get_correction_transform(element.node))
+            element.node.getparent().insert(index, el)
         element.node.getparent().remove(element.node)