Alex Rivera | Logout

Polygon Triangulation with Holes

Asked 2009-01-02T08:31:59.780
32

I am looking for an algorithm or library (better) to break down a polygon into triangles. I will be using these triangles in a Direct3D application. What are the best available options?

Here is what I have found so far:

  1. Ben Discoe's notes
  2. FIST: Fast Industrial-Strength Triangulation of Polygons
  3. I know that CGAL provides triangulation but am not sure if it supports holes.

I would really appreciate some opinions from people with prior experience in this area.

Edit: This is a 2D polygon.

graphics geometry direct3d triangulation cgal
Edit
Report

2 Answers

2

You can add the holes relatively easily yourself. Basically triangulate to the convex hull of the input points, as per CGAL, and then delete any triangle whose incentre lies inside any of the hole polygons (or outside any of the external boundaries). When dealing with lots of holes in a large dataset, masking techniques may be used to significantly speed this process up.

edit: A common extension to this technique is to weed weak triangles on the hull, where the longest edge or smallest internal angle exceeds a given value. This will form a better concave hull.

answered 2009-01-02T09:08:18.800
1

This is a common problem in finite element analysis. It's called "automatic mesh generation". Google found this site with links to commercial and open source software. They usually presume some kind of CAD representation of the geometry to start.

answered 2009-01-02T14:04:37.303

Your Answer