Boost logo

Geometry :

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
> (...)

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:

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

Geometry list run by mateusz at