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:

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