Menu
I'm using Delaunay to triangulate a concave polygon, but it fills in the concavities. How do I automatically remove the triangles that are outside the polygon boundaries?
509
The most straightforward way of efficiently computing the Delaunay triangulation is to repeatedly add one vertex at a time, retriangulating the affected parts of the graph. When a vertex v is added, we split in three the triangle that contains v, then we apply the flip algorithm.
There exists a Delaunay triangulation for any set of points in two dimensions. It is always unique as long as no four points in the point set are co-circular. Because it minimizes small angles and circumscribed circles, the Delaunay triangulation is geometrically nice and, in general, pleasing to the eye.
While the Delaunay property is well defined, the topology of the triangulation is not unique in the presence of degenerate point sets. In two dimensions, degeneracies arise when four or more unique points lie on the same circle. The vertices of a square, for example, have a nonunique Delaunay triangulation.
Self-answer: in some cases, this is impossible. I needed to use a constrained Delaunay algorithm: http://www.cs.cmu.edu/~quake/triangle.delaunay.html
91
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
