CODEWITHSUNDEEP
cgeometrytriangulation
user978281
user978281

Reputation: 477

Triangulation of polygon

Im trying to triangulate a polygon for use in a 3d model. When i try using the ear method on a polygon with points as dotted below, i get triangles where the red lines are. Since there are no other points inside these triangles this is probably correct. But i want it to triangulate the area inside the black lines only. Anyone know of any algorithms that will do this?

enter image description here

Upvotes: 6

Views: 4331

Answers (5)

abenci
abenci

Reputation: 8681

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

Upvotes: 0

sloriot
sloriot

Reputation: 6263

If you can use C++, you can use CGAL and in particular the example given here that can triangulate a set of non-intersected polygons. This example works only if you already know the black segments.

Upvotes: 1

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

There are many algorithms to triangulate a polygon that do not need partitioning into monotone polygons first. One is described in my textbook Computational Geometry in C, which has code associated with it that can be freely downloaded from that link (in C or in Java). You must first have the points in order corresponding to a boundary traversal. My code assumes counterclockwise, but of course that is easy to change. See also the Wikipedia article. Perhaps that is your problem, that you don't have the boundary points consistently organized?

Upvotes: 8

pmr
pmr

Reputation: 59831

The usual approach would be to split your simple polygon into monotone polygon using trapezoid decomposition and then triangulate the monotone polygons. The first part can be achieved with a sweep line algorithm. And speed-ups are possible with the right data-structure (e.g. doubly connected edge list). The best description of this, that I know, can be found in Computational Geometry. This and this also seem helpful.

Upvotes: 2

Soren
Soren

Reputation: 14708

Wikipedia suggest that you break the polygon up into monotone polygons. You check that the polygon is not concave by simply checking for all angles being less than 180 degrees - any corners which has a angle of over 180 is concave, and you need to break it at that corner.

Upvotes: 1

Related Questions