Path Simplification Algorithm for use in Cinder C++ Framework

PathSimplify.cpp

//
//  PathSimplify.cpp
//  PathFitter
//
//  Created by Greg Kepler on 4/18/12.
//  Copyright (c) 2012 The Barbarian Group. All rights reserved.
//

#include <iostream>
#include "PathSimplify.h"
#include "cinder/app/AppBasic.h"

vector<Vec2f> PathSimplify::SimplifyPath(const vector<Vec2f> &pts, float tolerance)
{
    vector<Vec2f> simplePath = douglasPeuckerSimplify(pts, tolerance);
    simplePath.push_back(pts[pts.size()-1]);
    return simplePath;
}

vector<Vec2f> PathSimplify::douglasPeuckerSimplify(vector<Vec2f> const &pts, float tolerance)
{
    vector<Vec2f> returnPoints;
    if ( pts.size() <= 2 ) {  
        returnPoints.push_back(pts[0]);
        return returnPoints;
    }
    
    
    // make line from start to end  
    PtLine *line = new PtLine( pts[0], pts[pts.size() - 1] );
    
    // find the largest distance from intermediate poitns to this line
    float maxDistance = 0;
    int maxDistanceIndex = 0;
    Vec2f p;
    
    for ( int i = 1; i <= pts.size() - 2; i++ ) {
        float distance = line->distanceToPoint( pts[i] );
        if ( distance > maxDistance ) {
            maxDistance = distance;
            maxDistanceIndex = i;
        }
    }
    
    
    // check if the max distance is greater than our tollerance allows 
    if ( maxDistance >= tolerance ) {
        p = pts[maxDistanceIndex];
        line->distanceToPoint( p );
        // include this point in the output
        vector<Vec2f> subset1 = getSubset(pts, 0, maxDistanceIndex + 1 );
        vector<Vec2f> simplePath1 = douglasPeuckerSimplify(subset1, tolerance );
        concat(&returnPoints, simplePath1);
        
        vector<Vec2f> subset2 = getSubset(pts, maxDistanceIndex, pts.size() );
        vector<Vec2f> simplePath2 = douglasPeuckerSimplify( subset2, tolerance );
        concat(&returnPoints, simplePath2);
    } 
    else {
        // ditching this point
        p = pts[maxDistanceIndex];
        line->distanceToPoint( p );
        
        returnPoints.push_back(pts[0]);
    }
    
    return returnPoints;
}


vector<Vec2f> PathSimplify::getSubset(const vector<Vec2f> &a, int start, int end) {
    vector<Vec2f> newArr;
    for (int i=start; i<end; i++) {
        newArr.push_back(a[i]);
    }
    return newArr;
}

vector<Vec2f>* PathSimplify::concat(vector<Vec2f> *original, const vector<Vec2f> &newList) {
    for (int i=0; i<newList.size(); i++) {
        original->push_back(newList[i]);
    }
    return original;
}


float PtLine::distanceToPoint(Vec2f pt){
    float m = ( pt2.y - pt1.y ) / ( pt2.x - pt1.x );
    
    // y offset
    float b = pt1.y - ( m * pt1.x );
    double d[3];
    
    // distance to the linear equation
    d[0] = ( abs( pt.y - ( m * pt.x ) - b ) / sqrt( pow( m, 2 ) + 1 ) );
    // distance to p1
    d[1] = pt.distance(pt1);
    // distance to p2
    d[2] = pt.distance(pt2);

    // return the smallest distance
    std::sort(d, d+3, std::less<float>());
    return d[0];
}

PathSimplify.h

//
//  PathSimplify.h
//  PathFitter
//
//  Created by Greg Kepler on 4/18/12.
//  Copyright (c) 2012 The Barbarian Group. All rights reserved.
//

#pragma once
#include <stdio.h>
#include "cinder/app/AppBasic.h"

using namespace cinder;
using namespace ci::app;
using namespace std;

class PathSimplify{
public:
    static vector<Vec2f>    SimplifyPath(vector<Vec2f> const &pts, float tolerance);
    static vector<Vec2f>    getSubset(const vector<Vec2f> &a, int start, int end);
    static vector<Vec2f>*   concat(vector<Vec2f> *original, const vector<Vec2f> &newList);
    
private:
    static vector<Vec2f>    douglasPeuckerSimplify(vector<Vec2f> const &pts, float tolerance);
    
};


class PtLine{
public:
    Vec2f   pt1;
    Vec2f   pt2;
    PtLine(Vec2f p1, Vec2f p2){pt1 = p1, pt2 = p2;};
    float   distanceToPoint(Vec2f pt);
};