Polygon Triangulation

Question

Im trying to triangulate a polygon for use in a 3d model. When I try to use the ear method on the polygon with the points indicated below, I get triangles where the red lines are. Since there are no other points in these triangles, this is probably correct. But I want him to triangulate the area inside the black lines. Does anyone know any algorithms that will do this?

Answer 1

There are many algorithms for triangulating a polygon that does not need to be split into monotone polygons. One of them is described in my textbook Computational Geometry in C , which has code associated with it that can be freely downloaded from this link (in C or Java). You must first have the points in the order corresponding to the border bypass. My code assumes counterclockwise, but of course it is easy to change. See Also Wikipedia article. Perhaps it is your problem that you do not have agreed border points?

Answer 2

The usual approach would be to split your simple polygon into a monotone polygon using trapezoidal decomposition, and then triangulate the monotone polygons. The first part can be achieved using the sweep line algorithm. And accelerations are possible with the correct data structure (for example, a doubly linked list of edges). The best description of this that I know can be found in Computational Geometry . This and this also seems useful.

Answer 3

Wikipedia suggests that you split a polygon into monotonous polygons. You check that the polygon is not concave, just checking that all angles are less than 180 degrees - any angles with an angle greater than 180 are concave, and you need to break it in this corner.

Answer 4

If you can use C ++, you can use CGAL and, in particular, the example below, which can triangulate a lot of disjoint polygons. This example only works if you already know the black segments.

Answer 5

You need to use the EarClipping algorithm, not Delaunay. See the following white paper: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf