Search code examples
c++algorithmgeometrypathgeometry

Algorithm to simplify a path

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

Solution

  • 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!