Looking for an efficient algorithm to find the boundary of a swept 2d shape

Question

I have piecewise curve defining a generator (think brush) and a piecewise curve representing the path the brush follows. I wish to generate the boundary that the generator curve creates as it is swept across the path.

This is for an engineering CAD like application. I am looking for a general algorithm or code samples in any language.

Answer 1

The actual answer we used is too complex to post in full but in summary.

1. Sample the curve at regular intervals along the transformed path
2. Build a triangular mesh by joining the vertices from each sample to the next and previous sample
3. Identify candidate silhouette edge by whose neighboring triangles normals point in opposite directions
4. Split all edges at intersections using a sweepline algorithm. This is the tricky part as we found we had to do this with a BigRational algorithm or subtle numerical errors crept in which broke the topology.
5. Convert the split edges into a planar graph
6. Find the closest of the split edges to some external test point

7. Walk around the outside of the graph. ( again all tests are done using big rational )

   The performance of the algorithm is not brilliant due to the BigRational calculations. However we tried many ways to do this in floating point and we always got numerical edges cases where the resulting graph was not planar. If the graph is not planar then you can't walk around the outside of it.

Answer 2

I suggest the following papers:

• "Approximate General Sweep Boundary of a 2D Curved Object" by Jae-Woo Ahn, Myung-Soo Kim and Soon-Bum Lim
• "Real Time Fitting of Pressure Brushstrokes" by Thierry Pudet
• "The Brush-Trajectory Approach to Figure Specification: Some Algebraic-Solutions"

Answer 3

If your have an arbitrarily complex shape translating and rotating along an arbitrary path, figuring out the area swept (and its boundary) using an exact method is going to be a really tough problem.

You might consider instead using a rendering-based approach:

1. start with a black canvas
2. densely sample the path of your moving shape
3. for each sample position and rotation, render the shape as white
4. you now have a canvas with a fairly good estimate of the swept shape

You can follow this up with these steps:

• (optional) do some image processing to try to fix up any artifacts introduced by too-sparsely sampling the path of the shape
• (optional) pass the canvas through an edge-finding filter to get the boundary of the swept shape