Algorithm to simplify the path

Question

Given the path, I want to optimize it so that all verticals that are straight on the line can be removed.

For example: Path:

******* * * * * *********** 

It can be optimized for:

 *-----* | \ | \ *---------* 

However, I want to have control over the tilt deviation, so that it does not have to be exactly on the slope.

What algorithm can do this?

thanks

Answer 1

I believe that you can do this with a simple iterative walk along the points along the way. Keep track, at each point, of the last three points that you encounter. If all three of them are collinear, then remove the midpoint from the path, since the selection of a straight line from the first to the third node will go through the middle of the node. You could control how many deviations there are by having some kind of term that controls how close the collinear points should be.

This can be implemented O (n) times with simple data passing if you have points stored in the data structure, for example, a doubly linked list.

Hope this helps!

Answer 2

You should use the convex hull algorithm (it depends on how your polygon is stored in memory), and then clear the points with a minimum angle on both adjacent points. Then you will have a polygon with only a dot at the end.

Here it is: http://en.wikipedia.org/wiki/Convex_hull

There are many possible implementations. It depends on what language you are programming in and with the data you play with.

Edit: I did not know that you already have points in the data. Just iterate over the points and calculate the angle between the one you are at, the preview and the next. if the angle is ~ 180, delete the current point.

Answer 3

This will be a bit abstracted view since I am not a C ++ person, but here goes ...

Let's look at one point right now:

 ******* * * * *<- this one, lets call it X *********** 

What you are going to do is slowly decide if each point is needed. To decide if a point is valid, you need to use other points, points immediately before and immediately after:

 ******* * *<- A * * ***********<- B 

If the angle from A to X is the same (or inside the error you think is accurate enough) as the angle from X to B, then X is not required.

This will not produce the same result as the Convex Hull algorithm. This will simply reduce the resolution of the path. You may get side effects if your permissible error is too large, for example:

  * * * | * | * -> | * | * | * * 

Or, if you are too small, you cannot change the path at all.

Also note that the convex hull can greatly change the path, for example:

  * * *---* * * * * / \ * * * -> * * * * | | ********* *-------* 

Answer 4

 set `D` to a maximum deviance of 10 degrees or so. set `P` to the first point. set `Q` to the point after `P`. set `A` to the angle from `P` to `Q`. while `Q` is not that last point in the list if the angle from `P` to `Q` is within of `A` plus or minus `D` remove `Q` else set `P` to `Q` set `A` to the angle from `P` to `Q`. set `Q` to the point after `P` 

This is a bit more complicated than templatetypedef's answer, but has the advantage of being better suited for large curves.

Answer 5

A more complex solution will include image processing techniques. You can try Hough transform , which allows deviations. Deviations can be included by blurring the parameter space. However, the algorithm is not simple. Also, I don't know how well it handles a large number of lines when the number of points on each line is very different. Since your points are ordered, you can try to look at the parameter space and remove all points that gave a match. If you pick the best matches first, you'll probably be left with a good solution.

Answer 6

I think this page will help you: Simplyfing Polygons (and I also recommend the book ).

Answer 7

I implemented the @templatetypedefdef solution in C++ for a closed polygonal chain described by two vectors x,y . I go along the polygon, and if the point is collinear to the previous and next point, I delete it:

 template<class T> void del_collinear_vanilla(std::vector<T> &x, std::vector<T> &y) { assert(x.size() == y.size()); size_t i = x.size(); size_t im1, ip1 = 0; do { i--; im1 = i ? i - 1 : x.size() - 1; if (are_collinear(x[ip1], y[ip1], x[i], y[i], x[im1], y[im1])) { x.erase(x.begin() + i); y.erase(y.begin() + i); } ip1 = i; } while (i != 0); } 

where the implementation depends on the macro / template are_collinear(x0,y0,x1,y1,x2,y2) .

However, in some cases, I still had some colinear points at the exit. This is an example input with which the algorithm crashes:

In this example, P5 is the same as P0, and P4 has the same ordinate P0 and P1; I slightly changed their coordinates to show all segments. The algorithm should only return a rectangle with vertices P1, P2, P3, P4.

Above, P6 is collinear to P5 and P0. Then, as soon as P6 is removed, P5 and P0 coincide, and both are collinear with P4 and P1.

It turns out that a simple cycle over each point, removing the point, if it is collinear to the previous and next point, does not give the correct result.

(In the example, suppose you start with P0 and you find that it is not collinear with a point before P6 and a point after P1. Then you go to P1, P2, ... until you reach P6. P6 is collinear, you delete it , and the cycle is completed. But now P0 is collinear to P4 and P1, and it had to be deleted!)

The same flaw exists for an open path. The algorithm works fine until the input path is compiled by itself .

The solution is to take a step backward every time you delete a point to make sure that the previous point has become collinear:

 template<class T> void del_collinear(std::vector<T> &x, std::vector<T> &y) { assert(x.size() == y.size()); size_t target = x.size() - 1; size_t i = x.size() - 1; do { size_t im1 = i ? i - 1 : x.size() - 1; size_t ip1 = (i == x.size() - 1) ? 0 : i + 1; if (are_collinear(x[ip1], y[ip1], x[i], y[i], x[im1], y[im1])) { x.erase(x.begin() + i); y.erase(y.begin() + i); // I do not decrease i in this case, as the the previous (alread // processed) point may now be a collinear point that must be // deleted. I mod it because i may now exceed x.size() i = i % x.size(); //Increment the target as well. target = (i + 1 + x.size()) % x.size(); } else //go for the next point. i = i ? i - 1 : x.size() - 1; } while (i != target); }