Sign in to follow this  

polygon triangulation

Recommended Posts

I am looking for some simple code that deals with convex/concave/polygon with holes triangulation. I would like to simulate the stuff done by GLU's gluNewTess for my simulation environment. although, I find a lot for 2D, I am not able to find a neat one for 3D polygon triangulation. Also, I am not able to compare the existing ones. Could some one throw light onto my needs. ~ Matt

Share this post

Link to post
Share on other sites
Edit: Ah, I assumed you were looking to do triangulation of planar polygons, which appears to not be the case. Ah well, I'll leave this up here in case anyone finds it useful. I should read more carefully next time :).

There are a whole bunch of ways to do tesselation with holes, I'll present a relatively straight-forward and somewhat robust method.

First the easy part: triangulation of concave polygons. You can use a very simple method that goes like this (in pseudo-code):

Vertex FindConvexVertex(Polygon P) {
// Two methods:
// (1) Find the left-most vertex in the polygon, breaking ties by Y value.
// (2) Find a vertex that makes a right turn

Vertex FindIntrudingVertex(Polygon P, Vertex vertex) {
// What we are looking for here is a vertex that intrudes on the triangle formed
// by the vertex (A) it's next neighbor (B) and it's previous neighbor (C).
// So for example:
// A---------------------B
// / __________----
// / #-----
// / \
// C-------*
// The vertex marked # is an intruding vertex, and * is not. Note that you will only
// find intruding vertices in concave polygons.
// The method we can use for finding an intruding vertex is to find any points that lie
// within the triangle formed by ABC. If there are multiple points, we want the one
// that is furthest from the BC edge.

Triangle ABC = Triangle(vertex, vertex.Next, vertex.Prev);

Vertex best = null;

foreach (vertex in P) {
if (vertex in ABC) {
if (best == null) best = vertex;
else if (vertex is further from BC than best) best = vertex;

// best can still be null here, that's fine
return best;

Polygon Split(Vertex first, Vertex last) {
// We want to return a polygon representing the polygon between the vertices first and last
// So for example:
// A------B
// / \
// / \
// F C
// \ /
// \ /
// E------D
// Given A as first and C as last, we return ABC. Give C as first and A as last we return CDEFA.
// Give C as first and F as last wer turn CDEF, etc.
// Note that this is dependent on the winding order of your polygons.

return Polygon(from first to last);

List<Triangle> Triangulate(Polygon P) {
if (P has 3 vertices) return Triangle(P);

Vertex convex = FindConvexVertex(P);
Vertex intruding = FindIntrudingVertex(P, convex);

if (intruding == null) {
// If there is no intruding vertex, we can split the convex vertex and it's two neigbors into
// a seperate triangle and continue onwards.
return Join(Triangulate(Split(convex.Prev, convex.Next)),
Triangulate(Split(convex.Next, convex.PreV)));
} else {
// Otherwise we split the polygon along the intruding vertex, knowing eventually we will end up
// with a convex polygon we can partition into triangles.
return Join(Triangulate(Split(convex, intruding)),
Triangulate(Split(intruding, convex)));

Okay, so that's maybe not so simple :). It would have been much nicer to have images to demonstrate concepts there, but I hope the ascii art is useful.

The basic concept is to find a convex vertex, then using that vertex and the triangle formed by it's two edges, check for an intruding vertex (a vertex within the triangle). If you find an intruding vertex, split the polygon along the convex and intruding vertex and recursively triangle the two polygon halves. If there is no intruding vertex you can split off the convex vertex and it's two edges into a triangle and continue triangulating the rest.

Share this post

Link to post
Share on other sites
I don't know off the top of my head where the algorithm I explained would be found in textbook form. And the reason you are not understanding is because I misunderstood your question and posted a response that is only useful for triangulation of 2D polygons (or planar 3d polygons). I didn't cover handling holes because I realized you wanted something different than what I was providing.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this