break apart loops (#690)

9 files changed, 142 insertions, 55 deletions

diff --git a/lib/elements/fill.py b/lib/elements/fill.py
index 59b7414b..923bf726 100644
--- a/lib/elements/fill.py
+++ b/lib/elements/fill.py
@@ -19,7 +19,7 @@ class UnconnectedError(ValidationError):
                     "Ink/Stitch doesn't know what order to stitch them in.  Please break this "
                     "object up into separate shapes.")
     steps_to_solve = [
-        _('* Extensions > Ink/Stitch > Fill Tools > Break Apart and Retain Holes.')
+        _('* Extensions > Ink/Stitch > Fill Tools > Break Apart Fill Objects'),
     ]
 
 
@@ -27,15 +27,7 @@ class InvalidShapeError(ValidationError):
     name = _("Border crosses itself")
     description = _("Fill: Shape is not valid.  This can happen if the border crosses over itself.")
     steps_to_solve = [
-        _("1. Inkscape has a limit to how far it lets you zoom in.  Sometimes there can be a little loop, "
-          "that's so small, you can't see it, but Ink/Stitch can. It's especially common for Inkscape's "
-          "Trace Bitmap to produce those tiny loops."),
-        _("* Delete the node"),
-        _("* Or try to adjust it's handles"),
-        _("2. If you can actually see a loop, run the following commands to seperate the crossing shapes:"),
-        _("* Path > Union (Ctrl++)"),
-        _("* Path > Break apart (Shift+Ctrl+K)"),
-        _("* (Optional) Recombine shapes with holes (Ctrl+K).")
+        _('* Extensions > Ink/Stitch > Fill Tools > Break Apart Fill Objects')
     ]
 
 
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)
diff --git a/templates/break_apart.inx b/templates/break_apart.inx
index 2580ddc3..83333ad1 100644
--- a/templates/break_apart.inx
+++ b/templates/break_apart.inx
@@ -1,6 +1,6 @@
 <?xml version="1.0" encoding="UTF-8"?>
 <inkscape-extension xmlns="http://www.inkscape.org/namespace/inkscape/extension">
-    <name>{% trans %}Break Apart and Retain Holes{% endtrans %}</name>
+    <name>{% trans %}Break Apart Fill Objects{% endtrans %}</name>
     <id>org.inkstitch.break_apart.{{ locale }}</id>
     <param name="extension" type="string" gui-hidden="true">break_apart</param>
     <effect>
@@ -11,6 +11,13 @@
             </submenu>
         </effects-menu>
     </effect>
+    <param name="description" type="description">
+        {% trans %}This extension will try to repair fill shapes and break them apart if necessary. Holes will be retained. Use on simple or overlapping shapes.{% endtrans %}
+    </param>
+    <param name="method" type="optiongroup" _gui-text="Method">
+       <option value="0">Simple</option>
+       <option value="1">Complex</option>
+    </param>
     <script>
         {{ command_tag | safe }}
     </script>
diff --git a/templates/embroider.inx b/templates/embroider.inx
index ea062aa4..b79c2f5f 100644
--- a/templates/embroider.inx
+++ b/templates/embroider.inx
@@ -17,7 +17,9 @@
     <effect>
         <object-type>all</object-type>
         <effects-menu>
-            <submenu name="Ink/Stitch" />
+            <submenu name="Ink/Stitch">
+                <submenu name="{% trans %}Visualise and Export{% endtrans %}" />
+            </submenu>
         </effects-menu>
     </effect>
     <script>
diff --git a/templates/print.inx b/templates/print.inx
index 2aec826b..33d8b25c 100644
--- a/templates/print.inx
+++ b/templates/print.inx
@@ -1,12 +1,14 @@
 <?xml version="1.0" encoding="UTF-8"?>
 <inkscape-extension xmlns="http://www.inkscape.org/namespace/inkscape/extension">
-    <name>{% trans %}Print / Realistic Preview{% endtrans %}</name>
+    <name>{% trans %}PDF Export{% endtrans %}</name>
     <id>org.inkstitch.print.{{ locale }}</id>
     <param name="extension" type="string" gui-hidden="true">print</param>
     <effect>
         <object-type>all</object-type>
         <effects-menu>
-            <submenu name="Ink/Stitch" />
+            <submenu name="Ink/Stitch">
+                <submenu name="{% trans %}Visualise and Export{% endtrans %}" />
+            </submenu>
         </effects-menu>
     </effect>
     <script>
diff --git a/templates/remove_embroidery_settings.inx b/templates/remove_embroidery_settings.inx
index 44b34ded..c83cc1b8 100644
--- a/templates/remove_embroidery_settings.inx
+++ b/templates/remove_embroidery_settings.inx
@@ -13,6 +13,7 @@
         <object-type>all</object-type>
         <effects-menu>
             <submenu name="Ink/Stitch">
+                <submenu name="{% trans %}Troubleshoot{% endtrans %}" />
             </submenu>
         </effects-menu>
     </effect>
diff --git a/templates/simulator.inx b/templates/simulator.inx
index 53bec56a..dfa6b34a 100644
--- a/templates/simulator.inx
+++ b/templates/simulator.inx
@@ -1,12 +1,14 @@
 <?xml version="1.0" encoding="UTF-8"?>
 <inkscape-extension xmlns="http://www.inkscape.org/namespace/inkscape/extension">
-    <name>{% trans %}Simulator{% endtrans %}</name>
+    <name>{% trans %}Simulator / Realistic Preview{% endtrans %}</name>
     <id>org.inkstitch.simulator.{{ locale }}</id>
     <param name="extension" type="string" gui-hidden="true">simulator</param>
     <effect>
         <object-type>all</object-type>
         <effects-menu>
-            <submenu name="Ink/Stitch" />
+            <submenu name="Ink/Stitch">
+                <submenu name="{% trans %}Visualise and Export{% endtrans %}" />
+            </submenu>
         </effects-menu>
     </effect>
     <script>
diff --git a/templates/stitch_plan_preview.inx b/templates/stitch_plan_preview.inx
index e047af10..72ea7f04 100644
--- a/templates/stitch_plan_preview.inx
+++ b/templates/stitch_plan_preview.inx
@@ -6,7 +6,9 @@
     <effect>
         <object-type>all</object-type>
         <effects-menu>
-            <submenu name="Ink/Stitch" />
+            <submenu name="Ink/Stitch">
+                <submenu name="{% trans %}Visualise and Export{% endtrans %}" />
+            </submenu>
         </effects-menu>
     </effect>
     <script>
diff --git a/templates/troubleshoot.inx b/templates/troubleshoot.inx
index 64f4ebb0..02df8ddc 100644
--- a/templates/troubleshoot.inx
+++ b/templates/troubleshoot.inx
@@ -7,6 +7,7 @@
         <object-type>all</object-type>
         <effects-menu>
             <submenu name="Ink/Stitch">
+                <submenu name="{% trans %}Troubleshoot{% endtrans %}" />
             </submenu>
         </effects-menu>
     </effect>