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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

The simpler approach. Take 3 vertecies a, b and c and calcule: The angle/inclination of between vertecies.

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.