• Advertisement
Sign in to follow this  

Polygon Triangulation

This topic is 3087 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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 this post

Link to post
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 this post

Link to post
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);
Wm4::Vector2<Real> vec3(0,-1);
Wm4::Vector2<Real> vec4(1,-1);
Wm4::Vector2<Real> vec5(0,1);

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]

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement