3 ms·

This is a tangentially related question, but seems like a good opportunity to ask: I recently found myself trying to figure out how to implement "parallel curv

This is a tangentially related question, but seems like a good opportunity to ask: I recently found myself trying to figure out how to implement "parallel curves" to arbitrary polyline shapes with small (relative to the offset), complicated details (world map borders from shapefiles). Eventually I found a way to accomplish my goal with existing software, so gave up on implementing it myself, but I'm still curious how it might be done. Parallel curves are conceptually straightforward when you're working with shapes defined by some sort of splines. I'm not sure if the problem is even well-defined when working with complicated polylines. It doesn't seem that Minkowski operations or PH curves are quite enough to solve this problem. Is there solid math that addresses it? Do existing CAD tools use proprietary heuristics? Is there a simple solution that I missed?

raphlinus 6y ago
Tangentially, huh? So the underlying operation of finding a parallel "curve" is trivial when the curve is a line, as it's just another line. That doesn't mean the problems is simple, though. One challenge (which I didn't address in the post, nor do I have code yet) is dealing with corners, as there are the usual choices of round, miter, and bevel. Of these, only round represents a true Minkowski sum. The others are generally more commonly used. Btw, see "Polar Stroking" [1] for more details on this. I came very close to linking it. The second detail is the "trimming" as the parallel curve paths generally have self-intersections, and very often you don't want those. So in the general case you have to do something similar to, say, Skia path ops. It's very difficult to make those operations completely numerically robust, and I think most implementations have gone through some pain as more test cases pop up which break. It is a fascinating area. I'm glad you're curious. [1]: https://arxiv.org/abs/2007.00308 https://arxiv.org/abs/2007.00308

raphlinus 6y ago

Tangentially, huh? So the underlying operation of finding a parallel "curve" is trivial when the curve is a line, as it's just another line. That doesn't mean the problems is simple, though. One challenge (which I didn't address in the post, nor do I have code yet) is dealing with corners, as there are the usual choices of round, miter, and bevel. Of these, only round represents a true Minkowski sum. The others are generally more commonly used. Btw, see "Polar Stroking" [1] for more details on this. I came very close to linking it. The second detail is the "trimming" as the parallel curve paths generally have self-intersections, and very often you don't want those. So in the general case you have to do something similar to, say, Skia path ops. It's very difficult to make those operations completely numerically robust, and I think most implementations have gone through some pain as more test cases pop up which break. It is a fascinating area. I'm glad you're curious. [1]: https://arxiv.org/abs/2007.00308 https://arxiv.org/abs/2007.00308