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.