CODEWITHSUNDEEP
algorithmpath
jmasterx
jmasterx

Reputation: 54103

Optimizing / simplifying a path

Say I have a path with 150 nodes / verticies. How could I simplify if so that for example a straight line with 3 verticies, would remove the middle one since it does nothing to add to the path. Also how could I avoid destroying sharp corners? And how could I remove tiny variations and have smooth curves remaining.

Thanks

Upvotes: 6

Views: 3177

Answers (5)

user347594
user347594

Reputation: 1296

The simpler approach. Take 3 verticies a, b and c and calculate the angle/inclination between verticies.

std::vector<VERTEX> path;
//fill path
std::vector<int> removeList;
//Assure that the value is in the same unit as the return of angleOf function.
double maxTinyVariation = SOMETHING; 

for (int i = 0; i < quantity-2; ++i) {
  double a = path[i], b = path[i + 1] , c = path[i + 2]
  double abAngle = angleOf(a, b);
  double bcAngle = angleOf(b, c);
  
  if (abs(ab - bc) <= maxTinyVariation) {
      //a, b and c are colinear
      //remove b later
      removeList.push_back(i+1);
  }
}
//Remove vertecies from path using removeList.

Upvotes: 3

Roman
Roman

Reputation: 3833

Use Douglas-Peucker method to simplify a Path.

epsilon parameter defines level of "simplicity":

private List<Point> douglasPeucker (List<Point> points, float epsilon){
    int count = points.size();
    if(count < 3) {
        return points;
    }

    //Find the point with the maximum distance
    float dmax = 0;
    int index = 0;
    for(int i = 1; i < count - 1; i++) {
        Point point = points.get(i);
        Point lineA = points.get(0);
        Point lineB = points.get(count-1);
        float d = perpendicularDistance(point, lineA, lineB);
        if(d > dmax) {
            index = i;
            dmax = d;
        }
    }

    //If max distance is greater than epsilon, recursively simplify
    List<Point> resultList;
    if(dmax > epsilon) {
        List<Point> recResults1 = douglasPeucker(points.subList(0,index+1), epsilon);

        List<Point> recResults2 = douglasPeucker(points.subList(index, count), epsilon);

        List<Point> tmpList = new ArrayList<Point>();
        tmpList.addAll(recResults1);
        tmpList.remove(tmpList.size()-1);
        tmpList.addAll(recResults2);
        resultList = tmpList;
    } else {
        resultList = new ArrayList<Point>();
        resultList.add(points.get(0));
        resultList.add(points.get(count-1));
    }

    return resultList;
}

private float perpendicularDistance(Point point, Point lineA, Point lineB){
    Point v1 = new Point(lineB.x - lineA.x, lineB.y - lineA.y);
    Point v2 = new Point(point.x - lineA.x, point.y - lineA.y);
    float lenV1 = (float)Math.sqrt(v1.x * v1.x + v1.y * v1.y);
    float lenV2 = (float)Math.sqrt(v2.x * v2.x + v2.y * v2.y);
    float angle = (float)Math.acos((v1.x * v2.x + v1.y * v2.y) / (lenV1 * lenV2));
    return (float)(Math.sin(angle) * lenV2);
}

Upvotes: 2

Max
Max

Reputation: 4932

Let A, B, C be some points.

The easiest way to check they lie on the same line is to count crossproduct of vectors B-A, C-A.

If it equals zero, they lie on the same line:

// X_ab, Y_ab - coordinates of vector B-A.
float X_ab = B.x - A.x
float Y_ab = B.y - A.y
// X_ac, Y_ac - coordinates of vector C-A.
float X_ac = C.x - A.x
float Y_ac = C.y - A.y
float crossproduct = Y_ab * X_ac - X_ab * Y_ac
if (crossproduct < EPS) // if crossprudct == 0
{
   // on the same line.
} else {
   // not on the same line.
}

After you know that A, B, C lie on the same line it is easy to know whether B lies between A and C throw innerproduct of vectors B-A and C-A. If B lies between A and C, then (B-A) has the same direction as (C-A), and innerproduct > 0, otherwise < 0:

float innerproduct = X_ab * X_ac + Y_ab * Y_ac;
if (innerproduct > 0) {
  // B is between A and C.
} else {
  // B is not between A and C.
}

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308101

For every 3 vertices, pick the middle one and calculate its distance to the line segment between the other two. If the distance is less than the tolerance you're willing to accept, remove it.

If the middle vertex is very close to one of the endpoints, you should tighten the tolerance to avoid removing rounded corners for instance.

Upvotes: 4

James McNellis
James McNellis

Reputation: 354969

How could I simplify if so that for example a straight line with 3 verticies, would remove the middle one since it does nothing to add to the path.

For each set of three consecutive vertices, test whether they are all in a straight line. If they are, remove the middle vertex.

Also how could I avoid destroying sharp corners?

If you're only removing vertices that fall on a straight line between two others, then you won't have a problem with this.

Upvotes: 3

Related Questions