Algorithm to simplify a path

Question

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

For example: Path:

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

Could be optimized to:

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

However I want to have control over the deviation from the slope so that it doesnt have to be exactly on the slope.

What sort of algorithm can do this?

Thanks

Answer 1

I believe that you can do this with a simple iterative walk across the points on the path. Keep track, at each point, of the last three points you've encountered. If all three of them are collinear, then remove the middle point from the path, since taking a straight-line path from the first to the third node will pass through the middle node. You could control how much of a deviation there is by having some term that controls how close to collinear the points would have to be.

This can be implemented in O(n) time with a simple pass over the data if you have the points stored in a data structure like a doubly-linked list.

Hope this helps!

Answer 2

You should use the convex hull algorithm (it depends on how is your polygon stocked in memory) and then clean the points with a min angle on both neighbour point. Then you'll have a polygon with only the point at the extremity.

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

They are many possible implementation.It depends on what language you're programing in, and the data you play with..

Edit: I didn't know at time that you had already the points in data.. Just iterate thrue the points and calculate the angle between the one you're on, the prev and the next. if the angle is ~= 180 erase the current point.

Answer 3

This is going to be a bit of an abstracted view since I'm not much of a C++ person, but here goes...

Let's take a look at one point right now:

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

What you're going to do is slowly decide if each point is necessary. To decide if a point is valid, other points must be used, the points immediately before and immediately after:

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

If the angle from A to X is the same (or within an error you deem accurate enough) as the angle from X to B, then X is unnecessary.

This will NOT result in the same outcome as the Convex Hull algorithm. This will simply reduce the resolution of the path. You can get side affects if your allowed error is too great such as this:

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

Or if you're error is too small you may not change the path at all.

Also note that convex hull can greatly change the path, 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 slightly more complicated than the templatetypedef's answer, but has the advantage that it forms a better fit on large curves.

Answer 5

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

Answer 6

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

Answer 7

I've implemented @templatetypedef's solution in C++, for a closed polygonal chain, described by two x,y vectors. I walk the polygon, and if a point is collinear with the previous and the 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 a macro/template are_collinear(x0,y0,x1,y1,x2,y2).

However, in some cases I still had some collinear points in the output. This is a sample input with which the algorithm fails:

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

Above, P6 is collinear with P5 and P0. Then, once P6 is eliminated, P5 and P0 coincide, and they are both collinear with P4 and P1.

It turns out that a simple loop over each point, deleting a point if it is collinear with the previous and the next point, does not provide the correct result.

(In the example, let's say you start with P0, and you find that it is not collinear with the point before P6 and the point after P1. Then you move to P1,P2,... until you reach P6. P6 is collinear, you delete it, and the loop is finished. But now P0 is collinear with P4 and P1, and it should have been deleted!)

The same flaw exists for an open path. The algorithm works fine as long as the input path has not collapsed on itself, in a way.

The solution is to take a step back every time you delete a point, to verify if the previous point has now 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);
}