In the approach below, a filling pattern will be created consisting of a single path (i.e. the filling nozzle will never be turned off, moved and turned on again) whenever possible.
After your step 4 (“Build segments from these points off-bound”), rotate each segment of the vertical line 2 or more points: the top and bottom end points plus (imagine your chart is drawn on a transparent place a sheet of paper with horizontal lines on the bottom and mark where the segments of the vertical line in the diagram intersect the horizontal lines on the paper).
Now we form a graph-weighted graph containing a vertex for each point, with an edge connecting two vertices when their corresponding points are less than or equal to one mesh unit. Also add edges between adjacent extreme points of the line segments and between adjacent lower points. Use the Euclidean distance between points for the weight of the edge. Finally, the magic part: find the minimum Hamiltonian weight path on this graph. This is a path that visits each vertex exactly once and has a minimum length. Limiting the minimum length ensures that the path never crosses itself, because if any two lines intersect, say, a line from a to b and a line from c to d, then it will always be possible to create a shorter common path by deleting these two lines and creating two new lines using another combination of endpoints (either --- c, and b --- d, or --- and b --- c). This is the path you fill.
Finding the Hamilton path (not to mention the Hamiltonian path of minimum weight) is an NP-hard problem, which is closely related to the more well-known problem of the salesman commander. Since many good accurate TSP solvers already exist (e.g. Concorde ), it would be wise to use one of them instead to find travel for travelers, and then simply remove one of the edges to create a short Hamiltonian path. (Even if you remove the heaviest edge, this will not necessarily lead to a Hamiltonian path of minimum length, since it may be that there are shorter paths that do not start and end at neighboring peaks, but we don’t really care about the total length here, we you just need a path that visits all the peaks and does not cross itself.)
Unfortunately, the graph does not guarantee the presence of either a Hamiltonian trajectory or a tour of traveling sellers. (Obviously, they cannot exist if the graph is disabled, for example, but even connected graphs may not have one or both: for example, a graph with any vertex of degree 1 cannot have a TSP tour.) In this case, there is a TSP Solver, which you use, you can find tours that do not visit all the peaks, you can simply repeat this until all the peaks are covered. If this does not happen, I will return to the original algorithm.
j_random_hacker
source share