Fill underlay inset (#108)

* interim commit

* implement underlay inset

* more refactoring

1 files changed, 46 insertions, 694 deletions

diff --git a/embroider.py b/embroider.py
index eeab5854..804782a9 100644
--- a/embroider.py
+++ b/embroider.py
@@ -36,7 +36,7 @@ from pprint import pformat
 
 import inkstitch
 from inkstitch import _, cache, dbg, param, EmbroideryElement, get_nodes, SVG_POLYLINE_TAG, SVG_GROUP_TAG, PIXELS_PER_MM, get_viewbox_transform
-from inkstitch.stitches import running_stitch
+from inkstitch.stitches import running_stitch, auto_fill, legacy_fill
 from inkstitch.utils import cut_path
 
 class Fill(EmbroideryElement):
@@ -120,257 +120,21 @@ class Fill(EmbroideryElement):
         # print >> sys.stderr, "polygon valid:", polygon.is_valid
         return polygon
 
-    @cache
-    def east(self, angle):
-        # "east" is the name of the direction that is to the right along a row
-        return inkstitch.Point(1, 0).rotate(-angle)
-
-    @cache
-    def north(self, angle):
-        return self.east(angle).rotate(math.pi / 2)
-
-    def row_num(self, point, angle, row_spacing):
-        return round((point * self.north(angle)) / row_spacing)
-
-    def adjust_stagger(self, stitch, angle, row_spacing, max_stitch_length):
-        row_num = self.row_num(stitch, angle, row_spacing)
-        row_stagger = row_num % self.staggers
-        stagger_offset = (float(row_stagger) / self.staggers) * max_stitch_length
-        offset = ((stitch * self.east(angle)) - stagger_offset) % max_stitch_length
-
-        return stitch - offset * self.east(angle)
-
-    def intersect_region_with_grating(self, angle=None, row_spacing=None, end_row_spacing=None):
-        if angle is None:
-            angle = self.angle
-
-        if row_spacing is None:
-            row_spacing = self.row_spacing
-
-        if end_row_spacing is None:
-            end_row_spacing = self.end_row_spacing
-
-        # the max line length I'll need to intersect the whole shape is the diagonal
-        (minx, miny, maxx, maxy) = self.shape.bounds
-        upper_left = inkstitch.Point(minx, miny)
-        lower_right = inkstitch.Point(maxx, maxy)
-        length = (upper_left - lower_right).length()
-        half_length = length / 2.0
-
-        # Now get a unit vector rotated to the requested angle.  I use -angle
-        # because shapely rotates clockwise, but my geometry textbooks taught
-        # me to consider angles as counter-clockwise from the X axis.
-        direction = inkstitch.Point(1, 0).rotate(-angle)
-
-        # and get a normal vector
-        normal = direction.rotate(math.pi / 2)
-
-        # I'll start from the center, move in the normal direction some amount,
-        # and then walk left and right half_length in each direction to create
-        # a line segment in the grating.
-        center = inkstitch.Point((minx + maxx) / 2.0, (miny + maxy) / 2.0)
-
-        # I need to figure out how far I need to go along the normal to get to
-        # the edge of the shape.  To do that, I'll rotate the bounding box
-        # angle degrees clockwise and ask for the new bounding box.  The max
-        # and min y tell me how far to go.
-
-        _, start, _, end = affinity.rotate(self.shape, angle, origin='center', use_radians=True).bounds
-
-        # convert start and end to be relative to center (simplifies things later)
-        start -= center.y
-        end -= center.y
-
-        height = abs(end - start)
-
-        print >> dbg, "grating:", start, end, height, row_spacing, end_row_spacing
-
-        # offset start slightly so that rows are always an even multiple of
-        # row_spacing_px from the origin.  This makes it so that abutting
-        # fill regions at the same angle and spacing always line up nicely.
-        start -= (start + normal * center) % row_spacing
-
-        rows = []
-
-        current_row_y = start
-
-        while current_row_y < end:
-            p0 = center + normal * current_row_y + direction * half_length
-            p1 = center + normal * current_row_y - direction * half_length
-            endpoints = [p0.as_tuple(), p1.as_tuple()]
-            grating_line = shgeo.LineString(endpoints)
-
-            res = grating_line.intersection(self.shape)
-
-            if (isinstance(res, shgeo.MultiLineString)):
-                runs = map(lambda line_string: line_string.coords, res.geoms)
-            else:
-                if res.is_empty or len(res.coords) == 1:
-                    # ignore if we intersected at a single point or no points
-                    runs = []
-                else:
-                    runs = [res.coords]
-
-            if runs:
-                runs.sort(key=lambda seg: (inkstitch.Point(*seg[0]) - upper_left).length())
-
-                if self.flip:
-                    runs.reverse()
-                    runs = map(lambda run: tuple(reversed(run)), runs)
-
-                rows.append(runs)
-
-            if end_row_spacing:
-                current_row_y += row_spacing + (end_row_spacing - row_spacing) * ((current_row_y - start) / height)
-            else:
-                current_row_y += row_spacing
-
-        return rows
-
-    def make_quadrilateral(self, segment1, segment2):
-        return shgeo.Polygon((segment1[0], segment1[1], segment2[1], segment2[0], segment1[0]))
-
-    def is_same_run(self, segment1, segment2):
-        if shgeo.LineString(segment1).distance(shgeo.LineString(segment2)) > self.row_spacing * 1.1:
-            return False
-
-        quad = self.make_quadrilateral(segment1, segment2)
-        quad_area = quad.area
-        intersection_area = self.shape.intersection(quad).area
-
-        return (intersection_area / quad_area) >= 0.9
-
-    def pull_runs(self, rows):
-        # Given a list of rows, each containing a set of line segments,
-        # break the area up into contiguous patches of line segments.
-        #
-        # This is done by repeatedly pulling off the first line segment in
-        # each row and calling that a shape.  We have to be careful to make
-        # sure that the line segments are part of the same shape.  Consider
-        # the letter "H", with an embroidery angle of 45 degrees.  When
-        # we get to the bottom of the lower left leg, the next row will jump
-        # over to midway up the lower right leg.  We want to stop there and
-        # start a new patch.
-
-        # for row in rows:
-        #    print >> sys.stderr, len(row)
-
-        # print >>sys.stderr, "\n".join(str(len(row)) for row in rows)
-
-        runs = []
-        count = 0
-        while (len(rows) > 0):
-            run = []
-            prev = None
-
-            for row_num in xrange(len(rows)):
-                row = rows[row_num]
-                first, rest = row[0], row[1:]
-
-                # TODO: only accept actually adjacent rows here
-                if prev is not None and not self.is_same_run(prev, first):
-                    break
-
-                run.append(first)
-                prev = first
-
-                rows[row_num] = rest
-
-            # print >> sys.stderr, len(run)
-            runs.append(run)
-            rows = [row for row in rows if len(row) > 0]
-
-            count += 1
-
-        return runs
-
-    def stitch_row(self, patch, beg, end, angle, row_spacing, max_stitch_length):
-        # We want our stitches to look like this:
-        #
-        # ---*-----------*-----------
-        # ------*-----------*--------
-        # ---------*-----------*-----
-        # ------------*-----------*--
-        # ---*-----------*-----------
-        #
-        # Each successive row of stitches will be staggered, with
-        # num_staggers rows before the pattern repeats.  A value of
-        # 4 gives a nice fill while hiding the needle holes.  The
-        # first row is offset 0%, the second 25%, the third 50%, and
-        # the fourth 75%.
-        #
-        # Actually, instead of just starting at an offset of 0, we
-        # can calculate a row's offset relative to the origin.  This
-        # way if we have two abutting fill regions, they'll perfectly
-        # tile with each other.  That's important because we often get
-        # abutting fill regions from pull_runs().
-
-
-        beg = inkstitch.Point(*beg)
-        end = inkstitch.Point(*end)
-
-        row_direction = (end - beg).unit()
-        segment_length = (end - beg).length()
-
-        # only stitch the first point if it's a reasonable distance away from the
-        # last stitch
-        if not patch.stitches or (beg - patch.stitches[-1]).length() > 0.5 * PIXELS_PER_MM:
-            patch.add_stitch(beg)
-
-        first_stitch = self.adjust_stagger(beg, angle, row_spacing, max_stitch_length)
-
-        # we might have chosen our first stitch just outside this row, so move back in
-        if (first_stitch - beg) * row_direction < 0:
-            first_stitch += row_direction * max_stitch_length
-
-        offset = (first_stitch - beg).length()
-
-        while offset < segment_length:
-            patch.add_stitch(beg + offset * row_direction)
-            offset += max_stitch_length
-
-        if (end - patch.stitches[-1]).length() > 0.1 * PIXELS_PER_MM:
-            patch.add_stitch(end)
-
-
-    def section_to_patch(self, group_of_segments, angle=None, row_spacing=None, max_stitch_length=None):
-        if max_stitch_length is None:
-            max_stitch_length = self.max_stitch_length
-
-        if row_spacing is None:
-            row_spacing = self.row_spacing
-
-        if angle is None:
-            angle = self.angle
-
-        # print >> sys.stderr, len(groups_of_segments)
-
-        patch = Patch(color=self.color)
-        first_segment = True
-        swap = False
-        last_end = None
-
-        for segment in group_of_segments:
-            (beg, end) = segment
-
-            if (swap):
-                (beg, end) = (end, beg)
-
-            self.stitch_row(patch, beg, end, angle, row_spacing, max_stitch_length)
-
-            swap = not swap
-
-        return patch
-
     def to_patches(self, last_patch):
-        rows_of_segments = self.intersect_region_with_grating()
-        groups_of_segments = self.pull_runs(rows_of_segments)
+        stitch_lists = legacy_fill(self.shape,
+                                   self.angle,
+                                   self.row_spacing,
+                                   self.end_row_spacing,
+                                   self.max_stitch_length,
+                                   self.flip,
+                                   self.staggers)
+        return [Patch(stitches=stitch_list, color=self.color) for stitch_list in stitch_lists]
 
-        return [self.section_to_patch(group) for group in groups_of_segments]
+        rows_of_segments = fill.intersect_region_with_grating(self.shape, self.angle, self.row_spacing, self.end_row_spacing, self.flip)
+        groups_of_segments = fill.pull_runs(rows_of_segments)
 
+        return [fill.section_to_patch(group) for group in groups_of_segments]
 
-class MaxQueueLengthExceeded(Exception):
-    pass
 
 class AutoFill(Fill):
     element_name = _("Auto-Fill")
@@ -427,462 +191,50 @@ class AutoFill(Fill):
     def fill_underlay_max_stitch_length(self):
         return self.get_float_param("fill_underlay_max_stitch_length_mm") or self.max_stitch_length
 
-    def which_outline(self, coords):
-        """return the index of the outline on which the point resides
-
-        Index 0 is the outer boundary of the fill region.  1+ are the
-        outlines of the holes.
-        """
-
-        # I'd use an intersection check, but floating point errors make it
-        # fail sometimes.
-
-        point = shgeo.Point(*coords)
-        outlines = list(enumerate(self.shape.boundary))
-        closest = min(outlines, key=lambda (index, outline): outline.distance(point))
-
-        return closest[0]
-
-    def project(self, coords, outline_index):
-        """project the point onto the specified outline
-
-        This returns the distance along the outline at which the point resides.
-        """
-
-        return self.shape.boundary.project(shgeo.Point(*coords))
-
-    def build_graph(self, segments, angle, row_spacing):
-        """build a graph representation of the grating segments
-
-        This function builds a specialized graph (as in graph theory) that will
-        help us determine a stitching path.  The idea comes from this paper:
-
-        http://www.sciencedirect.com/science/article/pii/S0925772100000158
-
-        The goal is to build a graph that we know must have an Eulerian Path.
-        An Eulerian Path is a path from edge to edge in the graph that visits
-        every edge exactly once and ends at the node it started at.  Algorithms
-        exist to build such a path, and we'll use Hierholzer's algorithm.
-
-        A graph must have an Eulerian Path if every node in the graph has an
-        even number of edges touching it.  Our goal here is to build a graph
-        that will have this property.
-
-        Based on the paper linked above, we'll build the graph as follows:
-
-          * nodes are the endpoints of the grating segments, where they meet
-            with the outer outline of the region the outlines of the interior
-            holes in the region.
-          * edges are:
-            * each section of the outer and inner outlines of the region,
-              between nodes
-            * double every other edge in the outer and inner hole outlines
-
-        Doubling up on some of the edges seems as if it will just mean we have
-        to stitch those spots twice.  This may be true, but it also ensures
-        that every node has 4 edges touching it, ensuring that a valid stitch
-        path must exist.
-        """
-
-        graph = networkx.MultiGraph()
-
-        # First, add the grating segments as edges.  We'll use the coordinates
-        # of the endpoints as nodes, which networkx will add automatically.
-        for segment in segments:
-            # networkx allows us to label nodes with arbitrary data.  We'll
-            # mark this one as a grating segment.
-            graph.add_edge(*segment, key="segment")
-
-        for node in graph.nodes():
-            outline_index = self.which_outline(node)
-            outline_projection = self.project(node, outline_index)
-
-            # Tag each node with its index and projection.
-            graph.add_node(node, index=outline_index, projection=outline_projection)
-
-        nodes = list(graph.nodes(data=True)) # returns a list of tuples: [(node, {data}), (node, {data}) ...]
-        nodes.sort(key=lambda node: (node[1]['index'], node[1]['projection']))
-
-        for outline_index, nodes in groupby(nodes, key=lambda node: node[1]['index']):
-            nodes = [ node for node, data in nodes ]
-
-            # heuristic: change the order I visit the nodes in the outline if necessary.
-            # If the start and endpoints are in the same row, I can't tell which row
-            # I should treat it as being in.
-            for i in xrange(len(nodes)):
-                row0 = self.row_num(inkstitch.Point(*nodes[0]), angle, row_spacing)
-                row1 = self.row_num(inkstitch.Point(*nodes[1]), angle, row_spacing)
-
-                if row0 == row1:
-                    nodes = nodes[1:] + [nodes[0]]
-                else:
-                    break
-
-            # heuristic: it's useful to try to keep the duplicated edges in the same rows.
-            # this prevents the BFS from having to search a ton of edges.
-            row_num = min(row0, row1)
-            if row_num % 2 == 0:
-                edge_set = 0
-            else:
-                edge_set = 1
-
-            #print >> sys.stderr, outline_index, "es", edge_set, "rn", row_num, inkstitch.Point(*nodes[0]) * self.north(angle), inkstitch.Point(*nodes[1]) * self.north(angle)
-
-            # add an edge between each successive node
-            for i, (node1, node2) in enumerate(zip(nodes, nodes[1:] + [nodes[0]])):
-                graph.add_edge(node1, node2, key="outline")
-
-                # duplicate edges contained in every other row (exactly half
-                # will be duplicated)
-                row_num = min(self.row_num(inkstitch.Point(*node1), angle, row_spacing),
-                              self.row_num(inkstitch.Point(*node2), angle, row_spacing))
-
-                # duplicate every other edge around this outline
-                if i % 2 == edge_set:
-                    graph.add_edge(node1, node2, key="extra")
-
-
-        if not networkx.is_eulerian(graph):
-            raise Exception(_("Unable to autofill.  This most often happens because your shape is made up of multiple sections that aren't connected."))
-
-        return graph
-
-    def node_list_to_edge_list(self, node_list):
-        return zip(node_list[:-1], node_list[1:])
-
-    def bfs_for_loop(self, graph, starting_node, max_queue_length=2000):
-        to_search = deque()
-        to_search.appendleft(([starting_node], set(), 0))
-
-        while to_search:
-            if len(to_search) > max_queue_length:
-                raise MaxQueueLengthExceeded()
-
-            path, visited_edges, visited_segments = to_search.pop()
-            ending_node = path[-1]
-
-            # get a list of neighbors paired with the key of the edge I can follow to get there
-            neighbors = [
-                        (node, key)
-                            for node, adj in graph.adj[ending_node].iteritems()
-                            for key in adj
-                    ]
-
-            # heuristic: try grating segments first
-            neighbors.sort(key=lambda (dest, key): key == "segment", reverse=True)
-
-            for next_node, key in neighbors:
-                # skip if I've already followed this edge
-                edge = (tuple(sorted((ending_node, next_node))), key)
-                if edge in visited_edges:
-                    continue
-
-                new_path = path + [next_node]
-
-                if key == "segment":
-                    new_visited_segments = visited_segments + 1
-                else:
-                    new_visited_segments = visited_segments
-
-                if next_node == starting_node:
-                    # ignore trivial loops (down and back a doubled edge)
-                    if len(new_path) > 3:
-                        return self.node_list_to_edge_list(new_path), new_visited_segments
-
-                new_visited_edges = visited_edges.copy()
-                new_visited_edges.add(edge)
-
-                to_search.appendleft((new_path, new_visited_edges, new_visited_segments))
-
-    def find_loop(self, graph, starting_nodes):
-        """find a loop in the graph that is connected to the existing path
-
-        Start at a candidate node and search through edges to find a path
-        back to that node.  We'll use a breadth-first search (BFS) in order to
-        find the shortest available loop.
-
-        In most cases, the BFS should not need to search far to find a loop.
-        The queue should stay relatively short.
-
-        An added heuristic will be used: if the BFS queue's length becomes
-        too long, we'll abort and try a different starting point.  Due to
-        the way we've set up the graph, there's bound to be a better choice
-        somewhere else.
-        """
-
-        #loop = self.simple_loop(graph, starting_nodes[-2])
-
-        #if loop:
-        #    print >> sys.stderr, "simple_loop success"
-        #    starting_nodes.pop()
-        #    starting_nodes.pop()
-        #    return loop
-
-        loop = None
-        retry = []
-        max_queue_length = 2000
-
-        while not loop:
-            while not loop and starting_nodes:
-                starting_node = starting_nodes.pop()
-                #print >> sys.stderr, "find loop from", starting_node
-
-                try:
-                    # Note: if bfs_for_loop() returns None, no loop can be
-                    # constructed from the starting_node (because the
-                    # necessary edges have already been consumed).  In that
-                    # case we discard that node and try the next.
-                    loop = self.bfs_for_loop(graph, starting_node, max_queue_length)
-
-                    if not loop:
-                        print >> dbg, "failed on", starting_node
-                        dbg.flush()
-                except MaxQueueLengthExceeded:
-                    print >> dbg, "gave up on", starting_node
-                    dbg.flush()
-                    # We're giving up on this node for now.  We could try
-                    # this node again later, so add it to the bottm of the
-                    # stack.
-                    retry.append(starting_node)
-
-            # Darn, couldn't find a loop.  Try harder.
-            starting_nodes.extendleft(retry)
-            max_queue_length *= 2
-
-        starting_nodes.extendleft(retry)
-        return loop
-
-    def insert_loop(self, path, loop):
-        """insert a sub-loop into an existing path
-
-        The path will be a series of edges describing a path through the graph
-        that ends where it starts.  The loop will be similar, and its starting
-        point will be somewhere along the path.
-
-        Insert the loop into the path, resulting in a longer path.
-
-        Both the path and the loop will be a list of edges specified as a
-        start and end point.  The points will be specified in order, such
-        that they will look like this:
-
-        ((p1, p2), (p2, p3), (p3, p4) ... (pn, p1))
-
-        path will be modified in place.
-        """
-
-        loop_start = loop[0][0]
-
-        for i, (start, end) in enumerate(path):
-            if start == loop_start:
-                break
-
-        path[i:i] = loop
-
-    def find_stitch_path(self, graph, segments):
-        """find a path that visits every grating segment exactly once
-
-        Theoretically, we just need to find an Eulerian Path in the graph.
-        However, we don't actually care whether every single edge is visited.
-        The edges on the outline of the region are only there to help us get
-        from one grating segment to the next.
-
-        We'll build a "cycle" (a path that ends where it starts) using
-        Hierholzer's algorithm.  We'll stop once we've visited every grating
-        segment.
-
-        Hierholzer's algorithm says to select an arbitrary starting node at
-        each step.  In order to produce a reasonable stitch path, we'll select
-        the vertex carefully such that we get back-and-forth traversal like
-        mowing a lawn.
-
-        To do this, we'll use a simple heuristic: try to start from nodes in
-        the order of most-recently-visited first.
-        """
-
-        original_graph = graph
-        graph = graph.copy()
-        num_segments = len(segments)
-        segments_visited = 0
-        nodes_visited = deque()
-
-        # start with a simple loop: down one segment and then back along the
-        # outer border to the starting point.
-        path = [segments[0], list(reversed(segments[0]))]
-
-        graph.remove_edges_from(path)
-
-        segments_visited += 1
-        nodes_visited.extend(segments[0])
-
-        while segments_visited < num_segments:
-            result = self.find_loop(graph, nodes_visited)
-
-            if not result:
-                print >> sys.stderr, _("Unexpected error while generating fill stitches. Please send your SVG file to lexelby@github.")
-                break
-
-            loop, segments = result
-
-            print >> dbg, "found loop:", loop
-            dbg.flush()
-
-            segments_visited += segments
-            nodes_visited += [edge[0] for edge in loop]
-            graph.remove_edges_from(loop)
-
-            self.insert_loop(path, loop)
-
-            #if segments_visited >= 12:
-            #    break
-
-        # Now we have a loop that covers every grating segment.  It returns to
-        # where it started, which is unnecessary, so we'll snip the last bit off.
-        #while original_graph.has_edge(*path[-1], key="outline"):
-        #    path.pop()
-
-        return path
-
-    def collapse_sequential_outline_edges(self, graph, path):
-        """collapse sequential edges that fall on the same outline
-
-        When the path follows multiple edges along the outline of the region,
-        replace those edges with the starting and ending points.  We'll use
-        these to stitch along the outline later on.
-        """
-
-        start_of_run = None
-        new_path = []
-
-        for edge in path:
-            if graph.has_edge(*edge, key="segment"):
-                if start_of_run:
-                    # close off the last run
-                    new_path.append((start_of_run, edge[0]))
-                    start_of_run = None
-
-                new_path.append(edge)
-            else:
-                if not start_of_run:
-                    start_of_run = edge[0]
-
-        if start_of_run:
-            # if we were still in a run, close it off
-            new_path.append((start_of_run, edge[1]))
-
-        return new_path
-
-    def outline_distance(self, outline, p1, p2):
-        # how far around the outline (and in what direction) do I need to go
-        # to get from p1 to p2?
-
-        p1_projection = outline.project(shgeo.Point(p1))
-        p2_projection = outline.project(shgeo.Point(p2))
-
-        distance = p2_projection - p1_projection
+    @property
+    @param('fill_underlay_inset_mm', _('Inset'), unit='mm', group=_('AutoFill Underlay'), type='float', default=0)
+    def fill_underlay_inset(self):
+        return self.get_float_param('fill_underlay_inset_mm', 0)
 
-        if abs(distance) > self.outline_length / 2.0:
-            # if we'd have to go more than halfway around, it's faster to go
-            # the other way
-            if distance < 0:
-                return distance + self.outline_length
-            elif distance > 0:
-                return distance - self.outline_length
-            else:
-                # this ought not happen, but just for completeness, return 0 if
-                # p1 and p0 are the same point
-                return 0
+    @property
+    def underlay_shape(self):
+        if self.fill_underlay_inset:
+            shape = self.shape.buffer(-self.fill_underlay_inset)
+            if not isinstance(shape, shgeo.MultiPolygon):
+                shape = shgeo.MultiPolygon([shape])
+            return shape
         else:
-            return distance
-
-    def connect_points(self, patch, start, end):
-        outline_index = self.which_outline(start)
-        outline = self.shape.boundary[outline_index]
-
-        pos = outline.project(shgeo.Point(start))
-        distance = self.outline_distance(outline, start, end)
-        stitches = abs(int(distance / self.running_stitch_length))
-
-        direction = math.copysign(1.0, distance)
-        one_stitch = self.running_stitch_length * direction
-
-        print >> dbg, "connect_points:", outline_index, start, end, distance, stitches, direction
-        dbg.flush()
-
-        patch.add_stitch(inkstitch.Point(*start))
-
-        for i in xrange(stitches):
-            pos = (pos + one_stitch) % self.outline_length
-
-            patch.add_stitch(inkstitch.Point(*outline.interpolate(pos).coords[0]))
-
-        end = inkstitch.Point(*end)
-        if (end - patch.stitches[-1]).length() > 0.1 * PIXELS_PER_MM:
-            patch.add_stitch(end)
-
-        print >> dbg, "end connect_points"
-        dbg.flush()
-
-    def path_to_patch(self, graph, path, angle, row_spacing, max_stitch_length):
-        path = self.collapse_sequential_outline_edges(graph, path)
-
-        patch = Patch(color=self.color)
-        #patch.add_stitch(inkstitch.Point(*path[0][0]))
-
-        #for edge in path:
-        #    patch.add_stitch(inkstitch.Point(*edge[1]))
-
-        for edge in path:
-            if graph.has_edge(*edge, key="segment"):
-                self.stitch_row(patch, edge[0], edge[1], angle, row_spacing, max_stitch_length)
-            else:
-                self.connect_points(patch, *edge)
-
-        return patch
-
-    def do_auto_fill(self, angle, row_spacing, max_stitch_length, starting_point=None):
-        patches = []
-
-        print >> dbg, "start do_auto_fill"
-        dbg.flush()
-
-        rows_of_segments = self.intersect_region_with_grating(angle, row_spacing)
-        segments = [segment for row in rows_of_segments for segment in row]
-
-        graph = self.build_graph(segments, angle, row_spacing)
-        path = self.find_stitch_path(graph, segments)
-
-        if starting_point:
-            patch = Patch(self.color)
-            self.connect_points(patch, starting_point, path[0][0])
-            patches.append(patch)
-
-        patches.append(self.path_to_patch(graph, path, angle, row_spacing, max_stitch_length))
-
-        print >> dbg, "end do_auto_fill"
-        dbg.flush()
-
-        return patches
-
+            return self.shape
 
     def to_patches(self, last_patch):
-        patches = []
+        stitches = []
 
         if last_patch is None:
             starting_point = None
         else:
-            nearest_point = self.outline.interpolate(self.outline.project(shgeo.Point(last_patch.stitches[-1])))
-            starting_point = inkstitch.Point(*nearest_point.coords[0])
+            starting_point = last_patch.stitches[-1]
 
         if self.fill_underlay:
-            patches.extend(self.do_auto_fill(self.fill_underlay_angle, self.fill_underlay_row_spacing, self.fill_underlay_max_stitch_length, starting_point))
-            starting_point = patches[-1].stitches[-1]
-
-        patches.extend(self.do_auto_fill(self.angle, self.row_spacing, self.max_stitch_length, starting_point))
-
-        print >> dbg, "end AutoFill.to_patches"
-        dbg.flush()
-
-        return patches
+            stitches.extend(auto_fill(self.underlay_shape,
+                                      self.fill_underlay_angle,
+                                      self.fill_underlay_row_spacing,
+                                      self.fill_underlay_row_spacing,
+                                      self.fill_underlay_max_stitch_length,
+                                      self.running_stitch_length,
+                                      self.staggers,
+                                      starting_point))
+            starting_point = stitches[-1]
+
+        stitches.extend(auto_fill(self.shape,
+                                  self.angle,
+                                  self.row_spacing,
+                                  self.end_row_spacing,
+                                  self.max_stitch_length,
+                                  self.running_stitch_length,
+                                  self.staggers,
+                                  starting_point))
+
+        return [Patch(stitches=stitches, color=self.color)]
 
 
 class Stroke(EmbroideryElement):