Geometry Boost List: Re: [geometry] difference algorithm produces invalid polygon?

Subject: Re: [geometry] difference algorithm produces invalid polygon?
From: Volker Schöch (vschoech_at_[hidden])
Date: 2012-02-21 09:38:04

Hello again,
here is another example of (asymmetric) difference producing output that is invalid as input to itself:

A1: MULTIPOLYGON(((1031 1056,3232 1056,3232 2856,1031 2856)))
B1: MULTIPOLYGON(((1032 1458,1032 1212,2136 2328,3234 2220,3234 2412,2136 2646)))
A1-B1: MULTIPOLYGON(((3232 2220,2136 2328,1032 1212,1032 1458,2136 2646,3232 2412,3232 2856,1031 2856,1031 1056,3232 1056)))

A2: A1-B1
B2: MULTIPOLYGON(((1032 1764,1032 1458,2136 2646,3234 2412,3234 2532,2136 2790)))
A2-B2: MULTIPOLYGON(((3232 2532,3232 2856,1031 2856,1031 1056,3232 1056,3232 2220,2136 2328,1032 1212,1032 1458,1032 1764,2136 2790),(3232 2412,2136 2646)))

A3: A2-B2
B3: MULTIPOLYGON(((1032 2130,1032 1764,2052 2712)),((3234 2580,2558 2690,3234 2532)),((2558 2690,2136 2790,2052 2712,2136 2760)))
A3-B3: MULTIPOLYGON(((2567 2688,3232 2580,3232 2856,1031 2856,1031 1056,3232 1056,3232 2220,2136 2328,1032 1212,1032 1458,1032 1764,1032 2130,2052 2712,1032 1764,2052 2712,2136 2790),(3232 2412,2136 2646),(2952 2597,3232 2532)))

A4: A3-B3
B4: MULTIPOLYGON(((1032 2556,1032 2130,1778 2556)),((3234 2580,2136 2760,1778 2556,3234 2556)))
A4-B4: Boost.Geometry Overlay invalid input exception

As with my other sample, B4 seems to be alright. Taking the difference, e.g, of A1-B4 seems to work flawlessly. Therefore I assume that A4 is the culprit, which is output produced from presumably valid input by boost::geometry::difference.

The problem cannot be fixed by applying boost::geometry::correct on the output from boost::geometry::difference. Actually, in the data above, "A-B" is the result of applying "difference" to A and B and applying "correct" to the result.

I am still using boost 1.48.0, my polygon type is oriented counter-clockwise and not closed, my point type is based on int.

Regards
   Volker

--
Volker Schöch | vschoech_at_[hidden]
Senior Software Engineer
think-cell Software GmbH | Chausseestr. 8/E | 10115 Berlin | Germany
http://www.think-cell.com | phone [phone] | US phone [phone]
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl