Geometry Boost List: Re: [geometry] "Overlay invalid input exception" (fixed)

Subject: Re: [geometry] "Overlay invalid input exception" (fixed)
From: Barend Gehrels (barend_at_[hidden])
Date: 2012-07-22 10:28:35

Hi Volker,

I looked in detail to your polygons. Attached my version of a complete 
program.

On 17-7-2012 16:17, Volker Schöch wrote:
> 2. I tried 1.50.0 and applied your patch. The step where it previously 
> failed in 1.50.0 did work after the patch was applied, but the step 
> that originally failed in 1.48.0 still fails in 1.50.0 with your 
> patch. Please find three reproductions below that all fail with 
> "Overlay invalid input exception" in the last step, with 1.50.0, with 
> your patch applied. The definitions of the operators can be found 
> below the reproductions.
>
> **
>
> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>
> _intPolygon polygon( "MULTIPOLYGON(((1031 1056,3232 1056,3232 
> 2856,1031 2856)))");
>
> polygon -= _intPolygon( "MULTIPOLYGON(((1032 1458,1032 1212,2136 
> 2328,3234 2220,3234 2412,2136 2646)))");
>
> polygon -= _intPolygon( "MULTIPOLYGON(((1032 1764,1032 1458,2136 
> 2646,3234 2412,3234 2532,2136 2790)))");
>
> polygon -= _intPolygon( "MULTIPOLYGON(((1032 2130,1032 1764,2052 
> 2712)),((3234 2580,2558 2690,3234 2532)),((2558 2690,2136 2790,2052 
> 2712,2136 2760)))");
>
> polygon -= _intPolygon( "MULTIPOLYGON(((1032 2556,1032 2130,1778 
> 2556)),((3234 2580,2136 2760,1778 2556,3234 2556)))");
>

(what I call 6A)
I can reproduce this. With double no exception. What is happening, in 
integer, is that a spike is generated by difference. In the next step 
this spike is hindering the intersection process and causes the invalid 
input exception.

There was an issue with double too, because a hole with only two points 
was generated. That did not give an exception in this case, but it might 
give exceptions in other cases depending on the configuration, so it is 
potentially problematic. That is fixed now (for double and integer).

I have to avoid spikes being generated. It is now for integer, but 
potentially also for double. It is probably only possible with 
difference, but I have to do some more research for this.

An workaround is to remove spikes from the output, before next step. 
There is already an algorithm, but in extensions and not released, and 
it is not yet working perfectly.

A third solution is that spikes can be processed in the intersection 
process without problems, and that is what you referred to in your 
recent mail too.

> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>
> _intPolygon polygon( "MULTIPOLYGON(((807 152,3958 152,3958 576,807 
> 576)))");
>
> polygon -= _intPolygon( "MULTIPOLYGON(((813 277,813 235,1341 
> 235)),((3963 277,3441 235,3963 235)))");
>
> polygon -= _intPolygon( "MULTIPOLYGON(((3963 277,3441 319,2913 
> 235,3441 235)),((2391 403,1863 235,1341 319,813 277,1341 235,1863 
> 151))) ");
>
> polygon -= _intPolygon( "MULTIPOLYGON(((3441 319,2913 361,2391 
> 403,2913 235)),((2391 403,1863 361,1341 319,1863 235)))");
>
> polygon -= _intPolygon( "MULTIPOLYGON(((2913 361,2391 571,1863 
> 361,2391 403)))");
>
> _intPolygon constpolygonB = _intPolygon("MULTIPOLYGON(((813 277,1341 
> 319,1863 361,2391 571,2913 361,3441 319,3963 277,3963 32767,813 
> 32767)))") ^ _intPolygon("MULTIPOLYGON(((813 277,1341 319,1863 
> 571,2391 571,2913 571,3441 319,3963 277,3963 32767,813 32767)))");
>
> polygon -= polygonB;
>

(what I call 6B): I cannot reproduce this, not with integer, not with 
double, not counter clockwise or open, etc. See attachment.

> >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>
> _intPolygon polygon( "MULTIPOLYGON(((971 1402,5395 1402,5395 3353,971 
> 3353)))");
>
> {
>
> _intPolygon constpolygonB = _intPolygon("MULTIPOLYGON(((966 2862,1704 
> 3348,2442 3186,3180 2376,3912 1722,4650 1398,5388 1560,5388 32767,966 
> 32767)))") ^ _intPolygon("MULTIPOLYGON(((966 2700,1704 3348,2442 
> 3186,3180 2376,3912 1884,4650 1398,5388 1560,5388 32767,966 32767)))");
>
> polygon -= polygonB;
>
> }
>
> {
>
> _intPolygon constpolygonB = _intPolygon("MULTIPOLYGON(((966 2700,1704 
> 3348,2442 3186,3180 2376,3912 1884,4650 1398,5388 1560,5388 32767,966 
> 32767)))") ^ _intPolygon("MULTIPOLYGON(((966 2700,1704 3024,2442 
> 3186,3180 2376,3912 1884,4650 1722,5388 1560,5388 32767,966 32767)))");
>
> polygon -= polygonB;
>
> }
>
> {
>
> _intPolygon constpolygonB = _intPolygon("MULTIPOLYGON(((966 2700,1704 
> 3024,2442 3186,3180 2376,3912 1884,4650 1722,5388 1560,5388 32767,966 
> 32767)))") ^ _intPolygon("MULTIPOLYGON(((966 2208,1704 3024,2442 
> 3186,3180 2376,3912 2376,4650 1722,5388 1560,5388 32767,966 32767)))");
>
> polygon -= polygonB;
>
> }
>

(what I call 6C): I can reproduce this. It throws the invalid input 
exception for counter-clockwise open integer polygons. For clockwise 
open integer, or counter-clockwise closed integer, it is no problem and 
for double it is never a problem. I do not yet know why, more research 
is necessary.

So in summary:
A: needs a fix for spikes
B: cannot reproduce
C: needs a closer look for ccw/open/integer polygons in this case

Attached the reproduction program (I made it quite close to your input). 
For the list, it's also a nice sample using a wkt-constructor, operators 
for (sym)difference and a geometry-registration,

Again, thanks for your reports.

Barend