Wednesday, October 29, 2008

CGLA: Abusing merge_edge

The CGAL arrangement_2 operation "merge_edge" takes two connected half-edges (connected by a vertex of degree 2) and makes them one. Useful! But there is some fine print:

merge_edge is only meant to be used when the new combined curve covers the exact same path as the old curve. If you are using line segments as your curves, this means the three vertices involved (the middle vertex is the one to be deleted) are collinear.

Can merge_edge be abused to remove edges that bend? Yes, sort of, if you are very careful:
  1. You must verify that the new combined edge does not cross any other edges, and will be in the same face as the existing two edges. This limits how much you can move an edge by combining. Basically merge_edge can't change topology!
  2. The two half-edges being merged must go in the same direction! Otherwise, the half-edge direction flag could be wrong after the merge.
None of this is very safe - safer (but slower) is to simply add the new edge and delete the two old ones.

No comments:

Post a Comment