Jump to content
  • Advertisement
Sign in to follow this  

Polygon Triangulation

This topic is 3386 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 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

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!