Reputation: 47

How to triangulate a polygon with and without vertices and holes inside - delaunay triangulation possible?

I got the following problem: I'm working on an algorithm and the output will be an arbitrary polygon. The polygon can be concave, have holes in it and also have vertices with edges that have an angle of 180 degree.

I need to triangulate said polygon with and without additional vertices inside it. Can the delaunay triangulation handle this, especially if I only have the polygon without vertices inside? I might be able to avoid holes inside the polygon, if that eases things.

Thanks for reading

Upvotes: 1

Answers (3)

Alex

Reputation: 1132

You can use Triangle.

Running Triangle via the command line, you create an ASCII .poly file that specifies the vertices and edges of the input (i.e., your polygon) as well as any holes in the domain. Each hole is defined by its xyz location. For example, if I have a square domain with a triangular hole inside it, my input could look like:

7 2 0 0  # 7 vertices
1 1 -1
2 1 1
3 -1 1
4 -1 -1
5 -.5 -.5
6 .5 -.5
7 0 .5
7 0      # 7 segments: four for the square and three for the hole
1 1 2
2 2 3
3 3 4
4 4 1
5 5 6
6 6 7
7 7 5
1      # 1 hole
1 0.0 0.0

If you want to refine the mesh (i.e., add vertices inside), you can use either the -a option (limiting the maximum area of a triangle) or the -q option (controlling the quality of the triangles produced but not directly limiting the size). The documentation on command line switches is here.

Upvotes: 0