Polygon infill algorithm

The approach below will produce a fill pattern that consists of a single path (i.e. the fill nozzle will never be turned off, moved, and turned back on), whenever this is possible.

After your step 4 ("Construct a segments from these points with offset from boundary"), turn each vertical line segment into a 2 or more points: the top and bottom endpoints, plus (imagine your diagram is drawn on a transparent slide; put a piece of paper with horizontal lines on it underneath, and mark where the vertical line segments in your diagram intersect the horizontal lines on the paper).

Now form an edge-weighted graph containing a vertex for each point, with an edge connecting two vertices whenever their corresponding points are less than or equal to one grid unit apart. Also add edges between adjacent topmost points of line segments, and between adjacent bottommost points. Use the Euclidean distance between the points for the edge weight. Finally, the magic part: find a minimum-weight Hamiltonian path on this graph. This is a path that visits each vertex exactly once, and has minimum length. The minimum length constraint guarantees that the path will never cross itself, since if any two lines cross, say the line from a to b and the line from c to d, then it would always be possible to create a shorter overall path by deleting these two lines and creating two new lines using a different combination of endpoints (either a---c and b---d, or a---d and b---c). This is the path that you will fill.

Finding a Hamiltonian path (let alone a minimum-weight Hamiltonian path) is an NP-hard problem that is closely related to the more famous Travelling Salesman Problem. Since many good exact TSP solvers already exist (e.g. Concorde), it would be sensible to instead use one of these to find a travelling salesman tour, and then simply delete one of the edges to produce a short Hamiltonian path. (Even if you delete the heaviest edge, this will not necessarily produce a minimum-length Hamiltonian path, since it may be that there exist shorter paths that don't begin and end at adjacent vertices; but we don't really care about the overall length here, we just want a path that visits all vertices and doesn't cross itself.)

Unfortunately, a graph is not guaranteed to contain either a Hamiltonian path, or a travelling salesman tour. (They obviously can't exist if the graph is disconnected, for example, but even connected graphs can fail to have either or both: e.g. a graph with any vertex of degree 1 cannot have a TSP tour.) In this case, if the TSP solver you are using can find tours that don't visit all vertices, you can just repeat this until all vertices are covered. Failing that, I would fall back on your original algorithm.

After some time of research I've ended at the following algorithm: There are a number of optimizations opportunity, though.

You may want to look at this webpage about algorithms for applying hatching to regions.