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

Subject: [ggl] Simplifying polygons with co-linear points
From: Barend Gehrels (barend)
Date: 2011-10-13 03:09:57

On 12-10-2011 21:34, John Swensen wrote:
> 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.

Sounds good! Yes, that will be sufficient for most cases and fast 
enough. Probably is it not guaranteed right (otherwise it would not be 
on the list of open problems) but for 99% of the cases it will be 
satisfactory or perfect.

>
> Do you want this contributed back?

Yes!

>    If so, do you have a preference on what I call it?

Currently I've no concrete idea.  So no, no preference yet.

Regards, Barend