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 02:46:53

On Oct 12, 2011, at 3:19 PM, Barend Gehrels wrote:

> Hi John,
> 
> Thanks for your message. I snipped most of it to make a concise answer.
> 
> On 12-10-2011 15:50, John Swensen wrote:
>> (...)
>> I am having the problem that after unioning polygons and simplifying the resulting multi_polygon that it doesn't simplify as much as I thought it would.  The following code snippet illustrates the problem
>> http://pastie.org/2683011
>> (...)
> 
> I run your program and get (slightly indented to be viewed correctly in fixed width):
> poly_union:                           ((((0, 8.5), (0, 10), (10, 10), (10, 8.5), (10, 0), (0, 0), (0, 8.5))))
> poly_union (correct,unique):          ((((0, 8.5), (0, 10), (10, 10), (10, 8.5), (10, 0), (0, 0), (0, 8.5))))
> poly_union (correct,unique,simplify): ((((0, 8.5), (0, 10), (10, 10),            (10, 0), (0, 0), (0, 8.5))))
> 
> So yes, simplify omits only one point which is not necessary, and in this case you would have wanted that it also had omitted the start/end point. Because that point is also unnecessary.
> 
> However, that is not that easy, it is on the fact of open problems on geometry, by O'Rourke: http://maven.smith.edu/~orourke/TOPP/P24.html#Problem.24 <http://maven.smith.edu/%7Eorourke/TOPP/P24.html#Problem.24>
> 
> The problem is that it is not known beforehand where to start. For linestrings it is easy of course, but for polygons it can be any point. You know that after running the algorithm. I knew that this was an open problem, didn't do my own research, and therefore Boost.Geometry just takes the naive approach and for a polygon, the starting/ending point are always kept...
> 
>> I have tried sifting through the Boost.Geometry source code but can't find exactly where this simplification process is executed.  From reading the docs, it seems that in order to create my own simplify routine I will need to learn a lot more about how the Concept/Algorithm pattern is implemented.  If I could get some guidance on the best way to go about this, it would be greatly appreciated.
> 
> Yeah, if you want to work on it, the algorithm itself is in the simplify_douglas_peucker.hpp file, and you can provide your own. I believe that modifying it or revising it completely should be possible, the calling file (simplify.hpp) does not make the assumption to keep the start/end point itself. You might do several (or a few, or only one) circular rotation and take the output with the smallest point. However, to fully solve it, I predict quadratic performance (or worse) based on O'Rourke ;-)
> 
> Regards, Barend
> 

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.

Do you want this contributed back?  If so, do you have a preference on what I call it?

John Swensen