Optimization / simplification of the path

Question

Let's say I have a path with 150 nodes / vertices. How could I simplify if this were so, for example, a straight line with three vertices would remove the middle one, since it does not add anything to the path. And how could I avoid the destruction of sharp corners? And how can I remove tiny variations and have smooth curves.

thanks

Answer 1

A simpler approach. Take 3 vertices a, b and c and the calculus: angle / angle between vertices.

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. 

Answer 2

For each three vertices, select the average and calculate its distance to the line segment between the other two. If the distance is less than the tolerance that you are willing to accept, delete it.

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

Answer 3

How could I simplify if this were so, for example, a straight line with 3 vertices would remove the middle one, since it does not add anything to the path.

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

Also, how could I avoid destroying sharp corners?

If you only delete vertices that fall on a straight line between two others, then you will not have problems with this.

Answer 4

Let A, B, C be some points.

The easiest way to verify that they are on the same line is to count the cross-products of the vectors BA, CA.

If it is zero, they are on the same line:

 // X_ab, Y_ab - coordinates of vector BA. float X_ab = Bx - Ax float Y_ab = By - Ay // X_ac, Y_ac - coordinates of vector CA. float X_ac = Cx - Ax float Y_ac = Cy - Ay 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. } 

Once you know that A, B, C are on the same line, it is easy to see if B is between A and C, the inner product of the vectors BA and CA. If B lies between A and C, then (BA) has the same direction as (CA), and the inner product is> 0, 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 5

Use the Douglas-Peucker method to simplify the path.

epsilon parameter determines the 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); }