4 replies to this topic

[thecoast47]

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.

[dayman]

I don't know this particular algorithm, but iterating over the whole vertexList in smoothCurve() doesn't feel right. It looks like you should only iterate over the Particles between p0 and p1.

Also, vector<>.resize() accepts a default value, so you can use outPut.resize( vertexList.size(), NULL ) and get rid of the initialization loop.

[thecoast47]

I don't know this particular algorithm, but iterating over the whole vertexList in smoothCurve() doesn't feel right. It looks like you should only iterate over the Particles between p0 and p1.

Also, vector<>.resize() accepts a default value, so you can use outPut.resize( vertexList.size(), NULL ) and get rid of the initialization loop.

thanks for the input.

Do you know any popular line/polygon simplification algorithms? 

 

*EDIT*

 

 

 

It looks like you should only iterate over the Particles between p0 and p1.

I changed it so that I only iterate through p0 and p1 and now it works completely.

Now I feel really,REALLY stupid.

Edited by thecoast47, 20 January 2013 - 09:03 PM.

[dayman]

Do you know any popular line/polygon simplification algorithms? 

Sorry, no. But this RDP-algorithm doesn't seem so bad. The biggest downside might be

that it removes points on both sides of the curve, so if you want to map the image as a texture onto the polygon, there will be some parts missing.

Can you elaborate what the problem with RDP is or what properties the final polygon should have?

[eppo]

An Edge contraction algorithm may have a better way of preserving the shape of a mesh/curve in that those try to incorporate some of a deleted point's features into the remaining points, whereas RDP completely discards points.

Edited by eppo, 21 January 2013 - 09:27 AM.