Geometry Boost List: [ggl] Simplifying polygons with co-linear points

Subject: [ggl] Simplifying polygons with co-linear points
From: John Swensen (jpswensen)
Date: 2011-10-13 03:40:43

On Oct 12, 2011, at 4:15 PM, Simonson, Lucanus J wrote:

> 
>> On 12-10-2011 15:50, John Swensen wrote:
> 
>> I should have gone and looked at the code before I responded earlier. This actually looks fairly easy to modify for my >needs.  I think I will make another class (not sure what to call it because the mod definitely wouldn't merit adding my >name to the class/algorithm).  I am going to run the standard Douglas-Peucker algorithm as it is now and then rotate >until the start point is not co-linear with the point in front and behind, then simplify again.  This naive approach >will still be O (2*n*log(n) + n), if I computed right.  O(n*log(n)) for the first simplify, O(n) for the maximum >possible number of rotations, and O(n*log(n)) for the second simplify.  I don't think a full simplify is required the 
>> second time around, but it is the "easy" way to do it.
> 
> A simple alternative is to scan the polygon for the point with the max distance from the line segment that joins the two points on either side of it (including the wrap around case) and rotate the polygon so that point is first.  It solves the original problem since a collinear point would never be chosen, but it also generalizes it because nearly collinear points will also not be chosen.  It requires one pass instead of two of the Douglas-Peucker and it is built out of the same building blocks as Douglas-Peucker so should be simple to implement.  We ought to be able modify the original DP implementation to work this way rather than creating a new interface because it is arguably still doing DP and not a new algorithm.
> 
> Regards,
> Luke
> 

This sound quite reasonable and not that hard for me to implement.  I will try to implement it this way since you seem to know Boost.Geometry and geometry in general much better than I.  I will still put it in a separate class so I can use it in the meantime, but will also generate a diff patch against the official DP class so you can apply it easily.

John