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 02:31:50

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