Circular fill (#2053)

5 files changed, 215 insertions, 34 deletions

diff --git a/lib/elements/fill_stitch.py b/lib/elements/fill_stitch.py
index c6762ad1..1897c8bf 100644
--- a/lib/elements/fill_stitch.py
+++ b/lib/elements/fill_stitch.py
@@ -9,22 +9,25 @@ import re
 import sys
 import traceback
 
+from inkex import Transform
 from shapely import geometry as shgeo
 from shapely.errors import TopologicalError
 from shapely.validation import explain_validity, make_valid
 
+from .. import tiles
 from ..i18n import _
 from ..marker import get_marker_elements
 from ..stitch_plan import StitchGroup
-from ..stitches import auto_fill, contour_fill, guided_fill, legacy_fill
+from ..stitches import (auto_fill, circular_fill, contour_fill, guided_fill,
+                        legacy_fill)
 from ..stitches.meander_fill import meander_fill
-from ..svg import PIXELS_PER_MM
+from ..svg import PIXELS_PER_MM, get_node_transform
 from ..svg.tags import INKSCAPE_LABEL
-from .. import tiles
 from ..utils import cache, version
+from ..utils.param import ParamOption
+from ..utils.threading import ExitThread
 from .element import EmbroideryElement, param
 from .validation import ValidationError, ValidationWarning
-from ..utils.threading import ExitThread
 
 
 class SmallShapeWarning(ValidationWarning):
@@ -107,15 +110,33 @@ class FillStitch(EmbroideryElement):
     def auto_fill(self):
         return self.get_boolean_param('auto_fill', True)
 
+    _fill_methods = [ParamOption('auto_fill', _("Auto Fill"), 0),
+                     ParamOption('contour_fill', _("Contour Fill"), 1),
+                     ParamOption('guided_fill', _("Guided Fill"), 2),
+                     ParamOption('meander_fill', _("Meander Fill")),
+                     ParamOption('circular_fill', _("Circular Fill")),
+                     ParamOption('legacy_fill', _("Legacy Fill"), 3)]
+
     @property
-    @param('fill_method', _('Fill method'), type='dropdown', default=0,
-           options=[_("Auto Fill"), _("Contour Fill"), _("Guided Fill"), _("Legacy Fill"), _("Meander Fill")], sort_index=2)
+    @param('fill_method',
+           _('Fill method'),
+           type='combo',
+           default=0,
+           options=_fill_methods,
+           sort_index=2)
     def fill_method(self):
-        return self.get_int_param('fill_method', 0)
+        # convert legacy values
+        legacy_method = self.get_int_param('fill_method', None)
+        if legacy_method in range(0, 4):
+            method = [method.id for method in self._fill_methods if method.legacy == legacy_method][0]
+            self.set_param('fill_method', method)
+            return method
+
+        return self.get_param('fill_method', 'auto_fill')
 
     @property
     @param('guided_fill_strategy', _('Guided Fill Strategy'), type='dropdown', default=0,
-           options=[_("Copy"), _("Parallel Offset")], select_items=[('fill_method', 2)], sort_index=3,
+           options=[_("Copy"), _("Parallel Offset")], select_items=[('fill_method', 'guided_fill')], sort_index=3,
            tooltip=_('Copy (the default) will fill the shape with shifted copies of the line. '
                      'Parallel offset will ensure that each line is always a consistent distance from its neighbor. '
                      'Sharp corners may be introduced.'))
@@ -124,18 +145,23 @@ class FillStitch(EmbroideryElement):
 
     @property
     @param('contour_strategy', _('Contour Fill Strategy'), type='dropdown', default=0,
-           options=[_("Inner to Outer"), _("Single spiral"), _("Double spiral")], select_items=[('fill_method', 1)], sort_index=3)
+           options=[_("Inner to Outer"), _("Single spiral"), _("Double spiral")], select_items=[('fill_method', 'contour_fill')], sort_index=3)
     def contour_strategy(self):
         return self.get_int_param('contour_strategy', 0)
 
     @property
     @param('join_style', _('Join Style'), type='dropdown', default=0,
-           options=[_("Round"), _("Mitered"), _("Beveled")], select_items=[('fill_method', 1)], sort_index=4)
+           options=[_("Round"), _("Mitered"), _("Beveled")], select_items=[('fill_method', 'contour_fill')], sort_index=4)
     def join_style(self):
         return self.get_int_param('join_style', 0)
 
     @property
-    @param('avoid_self_crossing', _('Avoid self-crossing'), type='boolean', default=False, select_items=[('fill_method', 1)], sort_index=5)
+    @param('avoid_self_crossing',
+           _('Avoid self-crossing'),
+           type='boolean',
+           default=False,
+           select_items=[('fill_method', 'contour_fill')],
+           sort_index=5)
     def avoid_self_crossing(self):
         return self.get_boolean_param('avoid_self_crossing', False)
 
@@ -149,24 +175,29 @@ class FillStitch(EmbroideryElement):
            type='integer',
            unit='mm',
            default=0,
-           select_items=[('fill_method', 1), ('fill_method', 4)],
+           select_items=[('fill_method', 'contour_fill'), ('fill_method', 'meander_fill')],
            sort_index=5)
     def smoothness(self):
         return self.get_float_param('smoothness_mm', 0)
 
     @property
-    @param('clockwise', _('Clockwise'), type='boolean', default=True, select_items=[('fill_method', 1)], sort_index=5)
+    @param('clockwise', _('Clockwise'), type='boolean', default=True, select_items=[('fill_method', 'contour_fill')], sort_index=5)
     def clockwise(self):
         return self.get_boolean_param('clockwise', True)
 
     @property
     @param('meander_pattern', _('Meander Pattern'), type='combo', default=0,
-           options=sorted(tiles.all_tiles()), select_items=[('fill_method', 4)], sort_index=3)
+           options=sorted(tiles.all_tiles()), select_items=[('fill_method', 'meander_fill')], sort_index=3)
     def meander_pattern(self):
         return self.get_param('meander_pattern', None)
 
     @property
-    @param('meander_scale_percent', _('Meander pattern scale'), type='float', unit="%", default=100, select_items=[('fill_method', 4)], sort_index=4)
+    @param('meander_scale_percent',
+           _('Meander pattern scale'),
+           type='float', unit="%",
+           default=100,
+           select_items=[('fill_method', 'meander_fill')],
+           sort_index=4)
     def meander_scale(self):
         return self.get_split_float_param('meander_scale_percent', (100, 100)) / 100
 
@@ -177,7 +208,7 @@ class FillStitch(EmbroideryElement):
            unit='deg',
            type='float',
            sort_index=6,
-           select_items=[('fill_method', 0), ('fill_method', 3)],
+           select_items=[('fill_method', 'auto_fill'), ('fill_method', 'legacy_fill')],
            default=0)
     @cache
     def angle(self):
@@ -196,8 +227,8 @@ class FillStitch(EmbroideryElement):
                   'Skipping it decreases stitch count and density.'),
         type='boolean',
         sort_index=6,
-        select_items=[('fill_method', 0), ('fill_method', 2),
-                      ('fill_method', 3)],
+        select_items=[('fill_method', 'auto_fill'), ('fill_method', 'guided_fill'),
+                      ('fill_method', 'legacy_fill')],
         default=False)
     def skip_last(self):
         return self.get_boolean_param("skip_last", False)
@@ -210,7 +241,7 @@ class FillStitch(EmbroideryElement):
                   'When you enable flip, stitching goes from right-to-left instead of left-to-right.'),
         type='boolean',
         sort_index=7,
-        select_items=[('fill_method', 3)],
+        select_items=[('fill_method', 'legacy_fill')],
         default=False)
     def flip(self):
         return self.get_boolean_param("flip", False)
@@ -222,7 +253,10 @@ class FillStitch(EmbroideryElement):
            unit='mm',
            sort_index=6,
            type='float',
-           select_items=[('fill_method', 0), ('fill_method', 1), ('fill_method', 2), ('fill_method', 3)],
+           select_items=[('fill_method', 'auto_fill'),
+                         ('fill_method', 'contour_fill'),
+                         ('fill_method', 'guided_fill'),
+                         ('fill_method', 'legacy_fill')],
            default=0.25)
     def row_spacing(self):
         return max(self.get_float_param("row_spacing_mm", 0.25), 0.1 * PIXELS_PER_MM)
@@ -239,7 +273,10 @@ class FillStitch(EmbroideryElement):
            unit='mm',
            sort_index=6,
            type='float',
-           select_items=[('fill_method', 0), ('fill_method', 1), ('fill_method', 2), ('fill_method', 3)],
+           select_items=[('fill_method', 'auto_fill'),
+                         ('fill_method', 'contour_fill'),
+                         ('fill_method', 'guided_fill'),
+                         ('fill_method', 'legacy_fill')],
            default=3.0)
     def max_stitch_length(self):
         return max(self.get_float_param("max_stitch_length_mm", 3.0), 0.1 * PIXELS_PER_MM)
@@ -251,7 +288,7 @@ class FillStitch(EmbroideryElement):
                      'Fractional values are allowed and can have less visible diagonals than integer values.'),
            type='int',
            sort_index=6,
-           select_items=[('fill_method', 0), ('fill_method', 2), ('fill_method', 3)],
+           select_items=[('fill_method', 'auto_fill'), ('fill_method', 'guided_fill'), ('fill_method', 'legacy_fill')],
            default=4)
     def staggers(self):
         return self.get_float_param("staggers", 4)
@@ -380,7 +417,7 @@ class FillStitch(EmbroideryElement):
                 yield UnderlayInsetWarning(shape.centroid)
 
         # guided fill warnings
-        if self.fill_method == 2:
+        if self.fill_method == 'guided_fill':
             guide_lines = self._get_guide_lines(True)
             if not guide_lines or guide_lines[0].is_empty:
                 yield MissingGuideLineWarning(self.shape.centroid)
@@ -406,12 +443,15 @@ class FillStitch(EmbroideryElement):
     @property
     @param('running_stitch_length_mm',
            _('Running stitch length'),
-           tooltip=_(
-               'Length of stitches around the outline of the fill region used when moving from section to section.  Also used for meander fill.'),
+           tooltip=_('Length of stitches around the outline of the fill region used when moving from section to section. '
+                     'Also used for meander and circular fill.'),
            unit='mm',
            type='float',
            default=1.5,
-           select_items=[('fill_method', 0), ('fill_method', 2), ('fill_method', 4)],
+           select_items=[('fill_method', 'auto_fill'),
+                         ('fill_method', 'guided_fill'),
+                         ('fill_method', 'meander_fill'),
+                         ('fill_method', 'circular_fill')],
            sort_index=6)
     def running_stitch_length(self):
         return max(self.get_float_param("running_stitch_length_mm", 1.5), 0.01)
@@ -511,7 +551,10 @@ class FillStitch(EmbroideryElement):
            type='float',
            default=0,
            sort_index=5,
-           select_items=[('fill_method', 0), ('fill_method', 2), ('fill_method', 4)])
+           select_items=[('fill_method', 'auto_fill'),
+                         ('fill_method', 'guided_fill'),
+                         ('fill_method', 'meander_fill'),
+                         ('fill_method', 'circular_fill')])
     def expand(self):
         return self.get_float_param('expand_mm', 0)
 
@@ -523,7 +566,7 @@ class FillStitch(EmbroideryElement):
                      'are not visible.  This gives them a jagged appearance.'),
            type='boolean',
            default=True,
-           select_items=[('fill_method', 0), ('fill_method', 2)],
+           select_items=[('fill_method', 'auto_fill'), ('fill_method', 'guided_fill'), ('fill_method', 'circular_fill')],
            sort_index=6)
     def underpath(self):
         return self.get_boolean_param('underpath', True)
@@ -586,7 +629,7 @@ class FillStitch(EmbroideryElement):
 
     def to_stitch_groups(self, previous_stitch_group):  # noqa: C901
         # backwards compatibility: legacy_fill used to be inkstitch:auto_fill == False
-        if not self.auto_fill or self.fill_method == 3:
+        if not self.auto_fill or self.fill_method == 'legacy_fill':
             return self.do_legacy_fill()
         else:
             stitch_groups = []
@@ -603,14 +646,16 @@ class FillStitch(EmbroideryElement):
 
                     fill_shapes = self.fill_shape(shape)
                     for i, fill_shape in enumerate(fill_shapes.geoms):
-                        if self.fill_method == 0:
+                        if self.fill_method == 'auto_fill':
                             stitch_groups.extend(self.do_auto_fill(fill_shape, previous_stitch_group, start, end))
-                        if self.fill_method == 1:
+                        elif self.fill_method == 'contour_fill':
                             stitch_groups.extend(self.do_contour_fill(fill_shape, previous_stitch_group, start))
-                        elif self.fill_method == 2:
+                        elif self.fill_method == 'guided_fill':
                             stitch_groups.extend(self.do_guided_fill(fill_shape, previous_stitch_group, start, end))
-                        elif self.fill_method == 4:
+                        elif self.fill_method == 'meander_fill':
                             stitch_groups.extend(self.do_meander_fill(fill_shape, i, start, end))
+                        elif self.fill_method == 'circular_fill':
+                            stitch_groups.extend(self.do_circular_fill(fill_shape, previous_stitch_group, start, end))
                 except ExitThread:
                     raise
                 except Exception:
@@ -782,3 +827,33 @@ class FillStitch(EmbroideryElement):
         message += traceback.format_exc()
 
         self.fatal(message)
+
+    def do_circular_fill(self, shape, last_patch, starting_point, ending_point):
+        # get target position
+        command = self.get_command('ripple_target')
+        if command:
+            pos = [float(command.use.get("x", 0)), float(command.use.get("y", 0))]
+            transform = get_node_transform(command.use)
+            pos = Transform(transform).apply_to_point(pos)
+            target = shgeo.Point(*pos)
+        else:
+            target = shape.centroid
+        stitches = circular_fill(
+                                 shape,
+                                 self.angle,
+                                 self.row_spacing,
+                                 self.staggers,
+                                 self.running_stitch_length,
+                                 self.running_stitch_tolerance,
+                                 self.skip_last,
+                                 starting_point,
+                                 ending_point,
+                                 self.underpath,
+                                 target
+                                )
+
+        stitch_group = StitchGroup(
+            color=self.color,
+            tags=("circular_fill", "auto_fill_top"),
+            stitches=stitches)
+        return [stitch_group]
diff --git a/lib/extensions/params.py b/lib/extensions/params.py
index e342c592..4b6780ee 100644
--- a/lib/extensions/params.py
+++ b/lib/extensions/params.py
@@ -24,8 +24,9 @@ from ..gui import PresetsPanel, SimulatorPreview, WarningPanel
 from ..i18n import _
 from ..svg.tags import SVG_POLYLINE_TAG
 from ..utils import get_resource_dir
-from .base import InkstitchExtension
+from ..utils.param import ParamOption
 from ..utils.threading import ExitThread, check_stop_flag
+from .base import InkstitchExtension
 
 
 def grouper(iterable_obj, count, fillvalue=None):
@@ -404,6 +405,8 @@ class ParamsTab(ScrolledPanel):
                 input = wx.ComboBox(self, wx.ID_ANY, choices=[], style=wx.CB_READONLY)
                 for option in param.options:
                     input.Append(option.name, option)
+                if not param.options:
+                    input.Append(_('No options available'), ParamOption('not_available'))
                 value = self.get_combo_value_index(param.values[0], param.options)
                 input.SetSelection(value)
                 input.Bind(wx.EVT_COMBOBOX, self.changed)
diff --git a/lib/stitches/__init__.py b/lib/stitches/__init__.py
index cfa05e51..f77f16e7 100644
--- a/lib/stitches/__init__.py
+++ b/lib/stitches/__init__.py
@@ -4,6 +4,7 @@
 # Licensed under the GNU GPL version 3.0 or later.  See the file LICENSE for details.
 
 from .auto_fill import auto_fill
+from .circular_fill import circular_fill
 from .fill import legacy_fill
 from .guided_fill import guided_fill
 
diff --git a/lib/stitches/circular_fill.py b/lib/stitches/circular_fill.py
new file mode 100644
index 00000000..91943b90
--- /dev/null
+++ b/lib/stitches/circular_fill.py
@@ -0,0 +1,94 @@
+from shapely import geometry as shgeo
+
+from ..stitch_plan import Stitch
+from ..utils.geometry import reverse_line_string
+from .auto_fill import (build_fill_stitch_graph, build_travel_graph,
+                        collapse_sequential_outline_edges, fallback,
+                        find_stitch_path, graph_is_valid, travel)
+from .contour_fill import _make_fermat_spiral
+from .running_stitch import running_stitch
+
+
+def circular_fill(shape,
+                  angle,
+                  row_spacing,
+                  num_staggers,
+                  running_stitch_length,
+                  running_stitch_tolerance,
+                  skip_last,
+                  starting_point,
+                  ending_point,
+                  underpath,
+                  target
+                  ):
+
+    # get furthest distance of the target point to a shape border
+    # so we know how many circles we will need
+    distance = shape.hausdorff_distance(target) + 1
+    radius = row_spacing
+    center = shgeo.Point(target)
+
+    circles = []
+    # add a small inner circle to make sure that the spiral ends close to the center
+    circles.append(shgeo.LineString(center.buffer(0.1).exterior.coords))
+    while distance > radius:
+        circles.append(shgeo.LineString(center.buffer(radius).exterior.coords))
+        radius += row_spacing
+    circles.reverse()
+
+    # Use double spiral from contour fill (we don't want to get stuck in the middle of the spiral)
+    double_spiral = _make_fermat_spiral(circles, running_stitch_length, circles[0].coords[0])
+    double_spiral = shgeo.LineString(list(double_spiral))
+    intersection = double_spiral.intersection(shape)
+
+    segments = []
+    for line in intersection.geoms:
+        if isinstance(line, shgeo.LineString):
+            segments.append(line.coords[:])
+
+    fill_stitch_graph = build_fill_stitch_graph(shape, segments, starting_point, ending_point)
+    if not graph_is_valid(fill_stitch_graph, shape, running_stitch_length):
+        return fallback(shape, running_stitch_length, running_stitch_tolerance)
+
+    travel_graph = build_travel_graph(fill_stitch_graph, shape, angle, underpath)
+    path = find_stitch_path(fill_stitch_graph, travel_graph, starting_point, ending_point)
+    result = path_to_stitches(path, travel_graph, fill_stitch_graph, running_stitch_length, running_stitch_tolerance, skip_last)
+
+    # use running stitch to adjust the stitch length
+    result = running_stitch(result,
+                            running_stitch_length,
+                            running_stitch_tolerance)
+
+    return result
+
+
+def path_to_stitches(path, travel_graph, fill_stitch_graph, running_stitch_length, running_stitch_tolerance, skip_last):
+    path = collapse_sequential_outline_edges(path)
+
+    stitches = []
+
+    # If the very first stitch is travel, we'll omit it in travel(), so add it here.
+    if not path[0].is_segment():
+        stitches.append(Stitch(*path[0].nodes[0]))
+
+    for edge in path:
+        if edge.is_segment():
+            current_edge = fill_stitch_graph[edge[0]][edge[-1]]['segment']
+            path_geometry = current_edge['geometry']
+
+            if edge[0] != path_geometry.coords[0]:
+                path_geometry = reverse_line_string(path_geometry)
+
+            new_stitches = [Stitch(*point) for point in path_geometry.coords]
+
+            # need to tag stitches
+            if skip_last:
+                del new_stitches[-1]
+
+            stitches.extend(new_stitches)
+
+            travel_graph.remove_edges_from(fill_stitch_graph[edge[0]][edge[1]]['segment'].get('underpath_edges', []))
+        else:
+            stitches.extend(travel(travel_graph, edge[0], edge[1], running_stitch_length, running_stitch_tolerance, skip_last))
+
+    return stitches
diff --git a/lib/utils/param.py b/lib/utils/param.py
new file mode 100644
index 00000000..c7dfdab0
--- /dev/null
+++ b/lib/utils/param.py
@@ -0,0 +1,8 @@
+class ParamOption:
+    def __init__(self, param_id=None, name=None, legacy=None):
+        self.id: str = param_id
+        self.name: str = name
+        self.legacy: int = legacy
+
+    def __repr__(self):
+        return "ParamOption(%s, %s, %s)" % (self.id, self.name, self.legacy)