I recently implemented a marching squares algorithm to generate a polygon for an arbitrary image.

Here is an example of my marching squares implementation:

As you can see it works,however, the marching squares algorithm gives me more data than I really need for a polygon. So a polygon simplification algorithm would be needed.

I'm currently trying to implement the Ramer–Douglas–Peucker algorithm. The problem is that I don't know what condition's to set to end the recursion. Currently, the either the algorithm runs in an infinite loop or terminates without correctly simplifying the line/polygon.

My interpretation of the algorithm is as followed:

-for the current line segment compute the vertex with the farthest perpendicular distance.

-if the farthest perpendicular distance is greater than the user defined "tolerance" do recursion, otherwise terminate recursion.

Can someone point out what i'm doing wrong here?

Here's my flawed code:

void smoothCurve(Particle* p0, Particle* p1,float tolerance,std::vector<Particle*>& vertexList,std::vector<Particle*>& outPut , std::vector<bool>& isRejected){ Vector2 displacement; Vector2 projectionArm; Vector2 projectedPoint; Vector2 pointToLineDisp; Vector2& x0 = p0->curPos; Vector2& x1 = p1->curPos; float dot; float currentDist = 0; float maxDist = 0; unsigned int maxIndex = 0; displacement = x1- x0; //calculates maximum distance from the line segment for(unsigned int I = 1; I < vertexList.size()-1;I++){ Particle*& currentVertex = vertexList[I]; Vector2& curVertexPos= currentVertex->curPos; projectionArm = curVertexPos - x0; dot = (projectionArm*displacement)/(displacement*displacement); projectedPoint = x0 + (displacement * dot); pointToLineDisp = projectedPoint - curVertexPos; currentDist = pointToLineDisp.getMagnitude(); if(currentDist > maxDist){ maxDist = currentDist; maxIndex = I; } } if(maxDist >= tolerance && outPut[maxIndex] == NULL ){ Particle* criticalParticle = vertexList[maxIndex]; outPut[maxIndex] = criticalParticle; smoothCurve(p0,criticalParticle,tolerance,vertexList,outPut,isRejected); smoothCurve(criticalParticle,p1,tolerance,vertexList,outPut,isRejected); } } void simplifyPolygon(float tolerance,std::vector<Particle*>& vertexList){ std::vector<Particle*> outPut; std::vector<bool> isRejected; outPut.resize(vertexList.size()); isRejected.resize(vertexList.size()); for(unsigned int I = 0; I < vertexList.size();I++){ outPut[I] = NULL; isRejected[I] = false; } Particle* x0 = vertexList[0]; Particle* x1 = vertexList[vertexList.size()-1]; outPut[0] = x0; outPut[vertexList.size()-1] = x1; smoothCurve(x0,x1,10.0f,vertexList,outPut,isRejected); for(unsigned int I = 0; I < outPut.size();I++){ Particle * cp = outPut[I]; if(cp == NULL){ delete vertexList[I]; } } vertexList.clear(); for(unsigned int I = 0; I < outPut.size();I++){ Particle * cp = outPut[I]; if(cp != NULL){ vertexList.push_back(cp); } } }

**Edited by thecoast47, 20 January 2013 - 06:11 PM.**