Sign in to follow this  
Antonym

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 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);
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]

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