figure out how to simplify map borders into toolpath-friendly curves

[alanbernstein]

this is not a trivial problem, and it should generally be handled by a CNC software package, but it's extremely interesting so i'm researching it.

https://math.stackexchange.com/questions/4025222/how-can-i-approximate-a-complicated-polygon-such-that-the-curvature-never-excee

problem statements:

1. "optimal curve approximating arbitrary polygon, that is machinable by an end mill of specified radius R"
2. "optimal curve approximating arbitrary polygon, with maximum curvature not exceeding specified radius R" - different than #1 because in this case, the curve is allowed to come within <R units of another point on the curve. i believe PH splines are basically designed to solve this problem.
3. "a mediocre approximation of an arbitrary polygon, that is machinable by an end mill of specified radius R". we can probably do this with an ad hoc/heuristic/iterative approach

here, "arbitrary polygon" means something like "a piecewise-linear boundary of a simply-connected planar region, which may have an arbitrarily detailed shape". the arbitrary detail/shape means:

• effective-radius-of-curvature smaller than R (curves that are too sharp and must be replaced by circular segments of radius R)
• feature sizes smaller than R (peninsulas that the bit can not fit inside of). i think this is equivalent to "closest-point-on-curve at a distance less than R"

search terms:

• Pythagorean-Hodograph Curves
• minkowski (minkowski operations implement fillets on simple corners pretty much directly)
• medial axis transform
• clothoid
• fillet algorithm
• continuous fillet algorithm
• two sided fillet polyline algorithm
• rolling ball fillet
• fillet smoothing algorithm
• fillet both interior and exterior
• fillet both for inlay

publications:

• Pythagorean-Hodograph B-Spline Curves - Gudrun Albrecht, 2016 (https://arxiv.org/pdf/1609.07888.pdf)
• Toolpath Smoothing using Clothoids for High Speed CNC Machines - A Shazadeh, 2019 (dissertation, for connecting already-smooth but disjoint curves, i think)
• Blending Operations Using Rolling-Ball Filleting - I Alhashim, 2009 (3d fillets)
• Quintic Pythagorean-Hodograph Curves BasedTrajectory Planning for Delta Robot with a PrescribedGeometrical Constraint - Liang, 2019 (for robotics, but might be useful for understanding PH curves)
• R. T. Farouki, Pythagorean-Hodograph Curves: Algebra and Geometry inseparable, Berlin: Springer, 2008.
• On Rational Minkowski Pythagorean Hodograph Curves - kosinka, 2010 (https://core.ac.uk/download/pdf/204910933.pdf)

educational resources:

• https://demonstrations.wolfram.com/PythagoreanHodographPHCubicCurves/
• http://blancosilva.github.io/post/2014/10/28/Computational-Geometry-in-Python.html? (https://news.ycombinator.com/item?id=8972732)
• https://faculty.engineering.ucdavis.edu/farouki/wp-content/uploads/sites/41/2013/02/Introduction-to-PH-curves.pdf - page 15: "defines center–line tool path, in order to cut a desired profile"
• http://web.mit.edu/hyperbook/Patrikalakis-Maekawa-Cho/ (http://web.mit.edu/hyperbook/Patrikalakis-Maekawa-Cho/)
• https://news.ycombinator.com/item?id=26196470 / https://raphlinus.github.io/curves/2021/02/19/parallel-curves.html
• https://makezine.com/projects/convert-geological-information-into-custom-map-fit-for-3d-printing-and-milling/

In hindsight, I wish I’d spent more time adjusting the borders of states so that they could be cut with a ⅛” bit. I didn’t (I used the actual state borders) so there was a lot of cleanup where sharp corners of states meet so that the whole map fit together decently.

simplification might be a good preprocessing step, but doesn't necessarily solve the curvature issue

• https://github.com/volkerp/fitCurves
• https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

tools:

• shapely (python) uses GEOS (C++), which is a port of JTS (java)
• shapely.simplify uses "topologypreservingsimplifier", which is a slower, higher-quality version of RDP
• https://shapely.readthedocs.io/en/stable/manual.html#object.simplify
• https://github.com/libgeos/geos/blob/65791765e58af02edf6471c4cc7b7fb193abeca7/src/simplify/TopologyPreservingSimplifier.cpp
• http://www.tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/simplify/TopologyPreservingSimplifier.html