Re: [Boost-users] [Boost.Geometry] - Union generates polygon with punctures

Subject: Re: [Boost-users] [Boost.Geometry] - Union generates polygon with punctures
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-07-12 17:40:41

Hi Olivier,

The policy of this list is: don't top-post. I reordered your mail to 
read from top to bottom, my answers in between.

>
>         It seems that one of the input polygons to the union_ function is
>         invalid. To understand my mistake, I outputed the operand
>         polygons to
>         SVG files and I discovered punctures in one of them. I believe
>         Boost.Geometry thinks my polygon is self-intersecting (may be
>         due to
>         precision error with floats ?) - but this polygon itself is
>         the result
>         of a previous union operation.
>
>         I don't know if solutions to this problem exists or if the
>         library is
>         faulty (the bad polygon is the result of an union operation). One
>         workaround would be to detect punctures and remove them, but
>         it's kind
>         of ugly imho...
>
>         Some more details:
>         - point coordinates type is float,
>         - I use custom class instead of point_xy model,
>         - polygon winding is counter-clockwise.
>
>         Thank you in advance for any help,
>         Olivier
>
>
>

On 5-7-2013 15:05, Olivier Heriveaux wrote:
>
> I exported the two inputs which produce the error during the algorithm 
> execution and I wrote a simple program appart with thoose polygons. I 
> also simplified a little the inputs and i was able to reproduce the 
> problem (see attached source file main.cpp).

Thanks for your sample program and your tests.

>
>
> I'll attach the generated SVG for inputs and output.
> As you suggested, I also tried to use double instead of float. The 
> result is different (note: not all digits printed for doubles) :
>
> -1.1414213180542001069 -0.14142137765884399414    <- A
> -0.97336012125015303198 0.19470110535621598657    <- one new extra-point
> -0.97336008742385127235 0.19470109862769818809    <-
> -1.1414213180542001069 -0.14142137765884399414    <- point equal to A 
> (I checked till last digit, not shown here)
>

My version with high precision (ttmath):
-1.1414213180542 -0.141421377658844 (point of both pa and pb)
-0.973360121250153 0.194701105356216 (point of pa)
-0.9733600874238512128115932867815276942 
0.19470109862769819504261957771496882692 (generated point)
-1.1414213180542 -0.141421377658844 (point of both pa and pb)

>
> One more thing I forgot to mention: I'm using boost 1.53 - I see 
> another version has been released very recently and I think i'll give 
> a try with it asap.

This behaviour is not changed.

>
> I'm not very familiar with Boost.Geometry, so maybe I'm doing 
> something wrong or maybe I'm expecting too much.

I tried it with float, double and ttmath and can reproduce your case 
with all of them. ttmath is expected to be high precision so it is 
(probably) not really a floating point error. I also tried to make the 
union with both SQL Server and PostGIS and both give a similar output, 
including the pseudo-spike. SQL Server makes it one polygon, PostGIS 
makes it a polygon with a hole. So this case is indeed quite 
interesting. They both report the output polygon to be valid. A polygon 
may contain a self-tangency.

The whole-like triangle has an area of 
-0.000000006250291651472502798247346743117038847 so it is in fact not a 
spike, at least not in ttmath (and according to your report, not in double).

So only in float we have the real spike. The output is indeed not 
checked on these cases. They should not be generated but in float they 
apparently are, because of the lower resolution.

Did you try the complete program (so including the steps after this 
union) with double? Is it then also reporting the self-intersection? You 
probably cannot use float for this case... We can filter out the spike 
in a post-process, as you suggest, but it is (at least not now) the 
intention to do this by default.

Regards, Barend