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:34:33

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

Is there a method of circular rotation already in Boost.Geometry?  I searched through the sources and docs and couldn't find anything.

John