Jump to content
  • Advertisement
Sign in to follow this  
thecoast47

Ramer–Douglas–Peucker algorithm help

This topic is 2071 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 recently implemented a marching squares algorithm to generate a polygon for an arbitrary image.

 

Here is an example of my marching squares implementation:  

Berlet2D2013-01-1813-41-17-41_zpsb86872e

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

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites

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

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!