Module segments_2d 

A chain of lines and arcs fitted to a 2D polyline within a tolerance.

The fit has four stages, and the last decides what is returned.

1. The fewest pieces. From every point the fit finds how far one line or one circle holds the polyline within the tolerance: a line exactly as far as any line can, by the narrowest strip about the points, a circle as far as its least-squares fit holds them. A shape holding the points from one start holds those from any later start within its reach, so the reaches never fall as the start moves on, and a walk taking the farthest reach from each run’s end needs no more runs than any split into stretches the reaches cover. A closed loop is walked from every start within one run, one of which is a break of the fewest. The point consecutive runs share is then moved to where their fits leave the least squared residual. A loop one circle holds is that circle.
2. The shapes. A circle run bowing from its chord by no more than min_bow is split into the fewest lines instead. A line within axis_snap of an axis turns onto it about its points’ centroid where it still holds them. A circle run next to lines is refitted tangent to both, or else to one, where the tangent circle still holds it.
3. The joints. Consecutive pieces meet at one point: the tangent point of a tangent pair; with corners, where the two curves cross nearest the input point the runs share, so a corner the polyline rounds off comes back sharp; otherwise midway between the nearest points of the two curves to that shared point. A crossing moves no piece’s end by more than half its run. An open chain starts and ends at the nearest points of its end pieces to the end points.
4. The check. Every input point must lie within the tolerance of the piece whose range holds it, the piece being the line segment or the arc itself, not its whole curve. The point two ranges share may move to any point both pieces hold up to, since a crossing cuts one piece short of points the other then holds. A joint where there is none takes its next choice, the midway point and then the shared input point itself, and a joint out of choices turns the pieces either side into the polylines through their points, which hold them exactly.

The tolerance is therefore a hard bound on what is returned. What is minimal is the count from the first stage: no split into stretches a line holds, or that lie within the reach of a circle fitted from a point at or before them, has fewer pieces, and in particular no split into lines alone. A circle the least-squares fit misses is not found, and the arcs min_bow turns into lines and the polyline fallbacks add pieces to that count.

Each point’s reach is a fit over the run it starts, so the work grows as the number of points times the points in a run.

Structs

Segment2

One piece of a fitted chain.

Segments

How a polyline is split into lines and arcs.

Functions

fit_segments_2d

Fit a chain of lines and arcs to a polyline, every point within the tolerance of its piece, consecutive pieces meeting end to end and, for a closed polyline, the last meeting the first. See the module documentation for how, and for what is minimal.