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:
- "optimal curve approximating arbitrary polygon, that is machinable by an end mill of specified radius R"
- "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.
- "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:
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
tools:
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:
#1because 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.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:
search terms:
publications:
educational resources:
simplification might be a good preprocessing step, but doesn't necessarily solve the curvature issue
tools: