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-12 20:44:37

I realize I posted this question as a response in my thread about unioning polygons, but decided to post it as its own thread (for the sake of search engines and the fact that because Boost.Geometry is fairly new it helps those looking for answers if the thread topics identify the questions being asked).

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

(Disclaimer: I hope the ASCII art I include in this email ends up looking right for those reading.  If not, copy and paste into an editor with a fixed width font or look at the end of the code listing I included)
Suppose I have two rectangles with the following relative size and position
*--------------*
|              |
*--------------*
|              |
|              |
*--------------*

When unioned together to make a square, I would expect it would look like the following without any simplification
*--------------*
|              |
*              *
|              |
|              |
*--------------*

After simplification I would expect it to look like the following
*--------------*
|              |
|              |
|              |
|              |
*--------------*

However, it really looks like the following after simplification
*--------------*
|              |
(*)            |
|              |
|              |
*--------------*
Here the (*) denotes the point that is the start point and end point of the simplified polygon. It seems that the simplification algorithm doesn't realize that there are two co-linear line segments that cross the start/end boundary of the polygon exterior ring.  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.

John Swensen