Optimizing / simplifying a path

Question

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

Least Squares, i guess. Remove those nodes with least contribution to overall "shape". You need to be more specific what "path" you have and why it would be OK to remove nodes. Are you talking about a geometric path? — zerm, Jun 13 '10 at 14:55
possible duplicate of [Shortest distance between a point and a line segment](http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment) — Pratik, Sep 26 '11 at 10:07

score 4 · Answer 1 · edited May 23 '17 at 12:16

4

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.

edited May 23 '17 at 12:16

Community

1
1

answered Jun 13 '10 at 14:57

Mark Ransom

299,747
42
398
622

score 3 · Answer 2 · answered Jun 13 '10 at 14:55

3

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.

answered Jun 13 '10 at 14:55

James McNellis

348,265
75
913
977

1

You may also want to make sure that the "middle" (second) vertex of the three is actually between the two "endpoints". It may never happen if you can guarantee you're starting with a valid polygon, but if it ever does, removing the second vertex will usually give you a different-looking shape than you started with. – cHao Jun 13 '10 at 15:14

score 3 · Accepted Answer · edited Jan 27 '22 at 15:00

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.

Shouldn't you take into account situations like when `abAngle = 359` and `bcAngle = 1`? (in degrees, that is). They are close but on opposite sides of zero. — noio, Oct 10 '11 at 14:57

score 2 · Answer 4 · answered May 05 '15 at 13:59

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

Max · Answer 5 · 2010-06-13T15:21:57.807

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.
}

Optimizing / simplifying a path

5 Answers5

Linked