# Polygon Triangulation

## Recommended Posts

I need to be able to triangulate 2d polygons taking into account any holes. I am thinking of trying to put together an algorithm to do it, nothing too fancy. Google hasn't been of much help though. Does anyone know any articles on the subject? Any code or known library is welcome too. Thanks.

##### Share on other sites
I would build a 2D BSP tree of the polygon and simply triangulate the convex areas at the leafs.
I found quite a lot of information with Google.
Try searching for 'polygon triangulation with holes', or 'ear clipping triangulation holes'. For example the following seems to give a lot of information: http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf.

##### Share on other sites
The GLUT library has a power triangulator for 3D that you can cut down to 2D. http://glprogramming.com/red/chapter11.html

##### Share on other sites
I decided to give geometrictools a go(thanks by the way) but I am having trouble with something in particular.

When I try calling the triangulation function I get a vector iterator outside of range error message.

When I check the value of simplePolygon with the debugger just before calling the function for some reason(even after pushing all those values into it) it remains at [0]().

I was thinking it could have something to do with variable types, me setting some of them wrong.

Vector2 seems to be a small 2 element vector, I am not really sure how it works.

    // Convenient typedefs.    typedef std::vector<Vector2<Real>> Positions;    typedef std::vector<int> Indices;    typedef std::vector<Indices*> IndicesArray;    typedef std::map<int,int> IndexMap;

	Wm4::TriangulateEC<Real>::Positions simplePolygon;	Wm4::Vector2<Real> vec2(0,0);	simplePolygon.push_back(vec2);	Wm4::Vector2<Real> vec3(0,-1);	simplePolygon.push_back(vec3);	Wm4::Vector2<Real> vec4(1,-1);	simplePolygon.push_back(vec4);	Wm4::Vector2<Real> vec5(0,1);	simplePolygon.push_back(vec5);	Wm4::TriangulateEC<Real>::Indices tIndices;	Wm4::TriangulateEC<Real> triangulate(simplePolygon,Wm4::Query::QT_RATIONAL,0,tIndices);

Edit: I had already tried geometric tools before and now I remember why I gave up on it. For some reason it gets a wild hair up its butt and gives me a 'vector iterator outside of range' error when it tries to resize a member variable.

The value of iPEQuantity at the moment of error is 4(size of rkPositions which although not showing the values added to it as mentioned previously does seem to contain them, I did a check).
void TriangulateEC<Real>::InitializePositions (const Positions& rkPositions,    Query::Type eQueryType, Real fEpsilon, int iExtraElements){    int iPQuantity = (int)rkPositions.size();    assert(iPQuantity >= 3);    int iPEQuantity = iPQuantity + iExtraElements;	m_kSPositions.resize(iPEQuantity);//ERROR AT THIS LINE OF CODE    if (eQueryType == Query::QT_FILTERED)    {        assert((Real)0.0 <= fEpsilon && fEpsilon <= (Real)1.0);    }//More code

Edit: Using the debugger I've come across something odd, by the end of the whole resize procedure it seems to want to add about a thousand elements.

[Edited by - Antonym on September 9, 2009 3:36:21 AM]

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628383
• Total Posts
2982378

• 10
• 9
• 15
• 24
• 11