• Create Account

### #Actualthecoast47

Posted 20 January 2013 - 06:11 PM

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


### #1thecoast47

Posted 20 January 2013 - 06:10 PM

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

PARTNERS