Delaunay Triangulation
Author
I need a 2D polygon triangulator which will create a low number of triangles uniformly over the surface of a polygon (which may have one or more holes). From what I can tell, a Delaunay Triangulation does this for a set of points, and a Constrained Delaunay Triangulation could be used to constrain the output to the polygon.
I've found a few open-source implementations which I could probably port to C++/C# (which I'm using) but a lot of these seem to be quite old (i.e. no longer updated), and I'd rather not make a start until I'm sure I've chosen the 'best' implementation.
So, I'm looking for opinions from anyone who has used these implementations before. As I say, I need the resultant triangles to be relatively evenly spaced out (with few skinny polygons) and for it to support holes.
Also, if anyone would like to suggest any other alternate algorithms, your opinions would be welcome also.
Thanks in advance!
FYI, the implementations I've found include poly2tri and Triangle.
Quote:FYI, the implementations I've found include poly2tri and Triangle.Triangle is what I would have suggested. Does it not meet your needs?
Quote:Original post by Barguast
FYI, the implementations I've found include poly2tri and Triangle.
You should also specify the kind of license you're looking for, because some of those Delaunay libs won't let you use it commercially.
Author
This is just for an independent project so any free implementations.
I've considered Triangle but after looking on this website:
http://www.vterrain.org/Implementation/Libs/triangulate.html
And this comment:
"One small drawback: You can't just tell it which segments are the edges of your hole. Instead, you must supply some point that lies within the hole. Triangle triangulate the hole, then does some kind of "flood fill" to empty it. It's inefficient, but what's worse is it requires the caller to compute a point-in-polygon for the hole. This is a non-trivial algorithm for an arbitrary complex polygon."
I immediately went off the idea. That said, I'm not sure if it's up to date. Somehow, I never came across CGAL during my research so I'm glad I asked!
I'll have a play with CGAL, and see if it suits my needs. Any other suggestion would be nice in the meantime. :)
Thanks!
I've considered Triangle but after looking on this website:
http://www.vterrain.org/Implementation/Libs/triangulate.html
And this comment:
"One small drawback: You can't just tell it which segments are the edges of your hole. Instead, you must supply some point that lies within the hole. Triangle triangulate the hole, then does some kind of "flood fill" to empty it. It's inefficient, but what's worse is it requires the caller to compute a point-in-polygon for the hole. This is a non-trivial algorithm for an arbitrary complex polygon."
I immediately went off the idea. That said, I'm not sure if it's up to date. Somehow, I never came across CGAL during my research so I'm glad I asked!
I'll have a play with CGAL, and see if it suits my needs. Any other suggestion would be nice in the meantime. :)
Thanks!
If your goal is triangulating a polygon with holes, Constrained Delaunay Triangulation (CDT) and the Triangle program (which contains CDT) are probably overkill. Even if you use CDT, the vertices of the polygon are triangulated with Delaunay. Then you modify the triangulation by inserting a polygon edge one-at-a-time. It is a bit challenging to get this to work robustly with floating-point arithmetic, but it is possible. However, in the case of polygon triangulation, you will need to trim away those triangles that are outside the polygon.
You might consider using instead an ear-clipping algorithm that handles holes. For example, Triangulation.
You mentioned a constraint of "low number of triangles uniformly over the surface of a polygon". Polygon triangulation uses only the polygon vertices. Straightforward ear clipping tends to produce some skinny triangles, but so does CDT. You can use a Delaunay-like condition for selecting which ear to clip. That said, you might not like the triangulation. You might have to insert a set of uniformly spaced points into the triangulation and subdivide to get a finer resolution mesh with some uniformity.
You might consider using instead an ear-clipping algorithm that handles holes. For example, Triangulation.
You mentioned a constraint of "low number of triangles uniformly over the surface of a polygon". Polygon triangulation uses only the polygon vertices. Straightforward ear clipping tends to produce some skinny triangles, but so does CDT. You can use a Delaunay-like condition for selecting which ear to clip. That said, you might not like the triangulation. You might have to insert a set of uniformly spaced points into the triangulation and subdivide to get a finer resolution mesh with some uniformity.
Author
Thanks Dave.
The more I think about this, I actually need two types of triangulation. One to triangulate polygons with holes - the link you posted is ideal - and another to uniformly triangulate a simple 2D 'terrain' type mesh. For the layer, Delaunay would be ideal I think, but at least now I know I don't require that to handle holes which should make it a lot easier to implement.
I'll set about converting the polygon triangulator. Are there any good tutorials or learning resources on 'basic' Delaunay which anyone can provide? I've already done ear-clipping to death (minus the holes support) but any materials on that would be welcome too.
Thanks again.
The more I think about this, I actually need two types of triangulation. One to triangulate polygons with holes - the link you posted is ideal - and another to uniformly triangulate a simple 2D 'terrain' type mesh. For the layer, Delaunay would be ideal I think, but at least now I know I don't require that to handle holes which should make it a lot easier to implement.
I'll set about converting the polygon triangulator. Are there any good tutorials or learning resources on 'basic' Delaunay which anyone can provide? I've already done ear-clipping to death (minus the holes support) but any materials on that would be welcome too.
Thanks again.
I also have a Delaunay implementation at my web site. I have used this for generating terrain data sets for games. A Constrained Delaunay Triangulation is useful for terrains when you want to "stencil" in roads or "cutout" portions of the terrain to insert world objects. This avoids having the artists do the work manually (such as building road lofts and world objects and then having to stitch them into the terrain manually). I have not yet posted my CDT implementation.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
