1

I want to triangulate a polygon (without selfintersection, but with holes and the polygon can also be concav). In this question (e.g.): Delaunay triangulating the 2d polygon with holes a Constrained Delaunay Triangulation is proposed. What I was wondering about: is this the best way to do so or is it like "using a sledge-hammer to crack a nut"? An alternativ would be to use an algorithm for creating a "normal" triangulation (eg splitting the polygon in y-monoton parts and triangulate these parts) and flipping the edges afterwards. But it seams that (nearly) nobody takes this solution. Is there a reason? What are the pros and cons for one of these solutions? (the polygons can have an arbitrary size)

Community
  • 1
  • 1
Infinity
  • 11
  • 1
  • All you need is EarClipping, please check [this link](http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf). – abenci Apr 09 '15 at 06:35
  • Thanks. But I thought, that the complexity of ear-clipping is O(n^2)? Sorry, I am a little bit confiused which is the best way to solve my problem. – Infinity Apr 09 '15 at 06:53
  • And after the ear clipping I just legalize the edges to match the delaunay property? – Infinity Apr 09 '15 at 07:16
  • Ear clipping can triangulate any polygon with any number of holes, the only requirement is that polygons don't overlap. There is no reason to use Delaunay if as input you only have contours. – abenci Apr 10 '15 at 06:49

2 Answers2

1

There are a few reasons to prefer (constrained) Delaunay triangulations to other approaches:

  1. In R^2 it can be proven that such a triangulation is the "best" way to triangulate a given geometry -- resulting in a triangulation that maximises the minimum angle. This is equivalent to producing triangles of optimal quality, without any "skinny" elements.

  2. Forming the Delaunay triangulation is efficient (i.e. O(n*log(n)) in R^2).

  3. Delaunay triangulation algorithms are robust and efficient in practice. A number of very high quality implementations exist, such as Triangle and CGAL.

  4. Delaunay triangulations generalise to higher-dimensional problems (i.e. tetrahedrons in R^3 and general simplexes in R^d).

  5. Delaunay triangulations induce an orthogonal dual complex (i.e. the Voronoi diagram). This can be important for certain classes of numerical methods.

Depending on what exactly you're looking to achieve, you might find one or more of these criteria persuasive. Other options, such as ear-clipping or monotone slab triangulation, can be competitive in some areas, but don't, IMO, exhibit the same kind of overall performance.

Darren Engwirda
  • 6,915
  • 4
  • 26
  • 42
0

You can try alpha shapes. It is defined as a delaunay triangulation without edges exceeding alpha.

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • 1
    Could you please explain me how I can realize this using alpha shapes? I thought alpha shapes are good, if I have a point cloud and want to get the shape of these points. But in my case I have points (the vertices of the polygon) and the edges. Thus I thought I have to use Constrained Delaunay or an algorithm to triangulate a polygon and legalize the edges afterwards. And for an arbitrary polygon, isn't it difficult to find the right alpha? (Some edges of the polygon may be quite short, others quiete long) – Infinity Apr 08 '15 at 19:36
  • @Infinity:Maybe you can delete edges inside the holes and approximate? – Micromega Apr 09 '15 at 00:08
  • You mean using alpha-shapes for deleting edges? But how would you start to get a first triangulation? Using Constrained Delaunay Triangulation? – Infinity Apr 09 '15 at 06:03