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 20:59:05

On Oct 12, 2011, at 5:34 PM, Barend Gehrels wrote:

> On 12-10-2011 22:25, John Swensen wrote:
>> 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.
> 
> Sure, good idea Luke!
> 
> Thanks, Barend

His is my attempt at a patch that implements the modification suggested by Luke.  I don't know exactly why, but I could not get the original ref_candidates to work with std::rotate.  I don't know if it is because it was created from the const reference to the input Range, but it simply wouldn't work.  It compiled fine and ran fine, it just didn't actually rotate.  Instead, I created a copy of the range, rotated the range, then created a new std::vector<dp_point_type> from the rotated Range.  Then I run DP as normal.  I realize this might slow things down and use more memory for very large geometries because a std::vector<dp_point_type> is created twice.  If you can tell me how to get the original std::vector created in the line
std::vector<dp_point_type> ref_candidates(boost::begin(range), boost::end(range));
to rotate properly then I can avoid this and submit an updated patch.

John Swensen

-------------- next part --------------
A non-text attachment was scrubbed...
Name: DP_straight_line_crossing_startend.patch
Type: application/octet-stream
Size: 2245 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/ggl/attachments/20111013/3a55a7e8/DP_straight_line_crossing_startend-0001.obj
-------------- next part --------------