2

I have a set of polygons, which may share common edges and nodes. All these polygons are strictly non-overlapping, although they can share a common vertex or edge.

I want to triangulate all these polygons in batch, as such, the solution I can think of is constraint delaunay triangulation. But the output of Constraint Delaunay Triangulation will generate triangles that are not in the original polygons.

Is there a way to identify these out-of-polygon triangles?

Edit: Matlab has a way to do it via the inOutStatus; I am looking for such an algorithm independent of the language.

1
  • Are the polygons all convex? If so, it's fairly easy to triangulate each polygon as a fan (choose one vertex and split into triangles from that vertex.)
    – Dan Bryant
    Nov 30, 2011 at 15:36

1 Answer 1

0

Many Delaunay triangulation packages (such as Triangle, which I would recommend) generally include the option to remove the "outer" triangles from the triangulation auto-magically. Check out the documentation.

If this is not the case for your algorithm, you should be able to prune off the outer triangles by testing whether the centroid of each triangle lies within the polygon(s) that you've specified as constraints, via a point-in polygon test for instance. This should always work since a constrained Delaunay triangulation will ensure that no triangle edges cross the polygonal constraint edges (there's no chance of a partially in/out triangle).

Another consideration for your problem is the batch processing you describe. The complexity of most (if not all) Delaunay triangulation algorithms is non-linear (Triangle achieves O(n*log(n))), so I would think you would actually achieve a speed-up by processing the polygons one-by-one rather than all at once.

1
  • you should be able to prune off the outer triangles by testing whether the centroid of each triangle lies within the polygon(s) that you've specified as constraints, via a point-in polygon test for instance. I think there is a performance hit here; the runtime is O(m*n), where m is the number of triangle elements, n is the number of original polygon
    – Graviton
    Dec 6, 2011 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.