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

Subject: Re: [Boost-users] [Boost.Geometry] - Union generates polygon with punctures
From: Olivier Heriveaux (hodevel_at_[hidden])
Date: 2013-07-05 09:05:00

Hi,

Thanks for your support !

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

The toy program has two input polygons and generates the union. Here are
the two input polygons:

    boost::geometry::read_wkt
    (
        "POLYGON(("
            "-0.973360121250153 0.194701105356216,"
            "-0.923463344573975 0.184775948524475,"
            "-0.858578622341156 0.141421362757683,"
            "0.18477588891983 2.07653665542603,"
            "0.141421347856522 2.1414213180542,"
            "-1.18477594852448 -0.076536700129509,"
            "-1.1414213180542 -0.141421377658844,"
            "-0.973360121250153 0.194701105356216"
            "))",
        pa
    );

    boost::geometry::read_wkt
    (
        "POLYGON(("
            "-0.14142133295536 1.8585786819458,"
            "-1.1414213180542 -0.141421377658844,"
            "-1.07653665542603 -0.184775933623314,"
            "-0.076536625623703 1.81522405147552,"
            "-0.14142133295536 1.8585786819458"
            "))",
        pb
    );

And here is the output polygon, printed to stdout:

-0.19351507723331451416 1.5812671184539794922
-0.07653662562370300293 1.8152240514755249023
-0.1414213329553604126 1.8585786819458007812
-0.72200763225555419922 0.69740593433380126953
-1.1847759485244750977 -0.076536700129508972168
-1.1414213180541992188 -0.14142137765884399414    <- A
-0.9733600616455078125 0.19470109045505523682     <- here is the puncture
-1.1414213180541992188 -0.14142137765884399414    <- point equal to A
-1.0765366554260253906 -0.18477593362331390381
-0.89969980716705322266 0.1688976585865020752
-0.85857862234115600586 0.14142136275768280029
0.18477588891983032227 2.0765366554260253906
0.14142134785652160645 2.1414213180541992188
-0.19351507723331451416 1.5812671184539794922

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) :

-0.19351506716472754999 1.5812671771090451855
-0.07653662562370300293 1.8152240514755200174
-0.14142133295535999626 1.8585786819457998931
-0.72200777157880025037 0.69740575279044780821
-1.1847759485244799826 -0.076536700129508999924
-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)
-1.0765366554260300536 -0.18477593362331398708
-0.89969984067827302177 0.16889768269682844948
-0.85857862234115600586 0.14142136275768299458
0.1847758889198299892 2.0765366554260298315
0.14142134785652199502 2.1414213180542001069
-0.19351506716472754999 1.5812671771090451855

With double precision, a kind of hole is created instead of a puncture, but
I don't know if this should be accepted as a good polygon...

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.

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

Regards

On Wed, Jul 3, 2013 at 6:04 PM, Barend Gehrels <barend_at_[hidden]> wrote:

> Hi,
>
>
>
> On 3-7-2013 12:22, Olivier Heriveaux wrote:
>
>> Hello !
>>
>> I'm trying to use Boost.Geometry library to implement Minkowsky
>> algorithm (i.e. polygon convolution). I try to implement it in the
>> same way Boost.Polygon does, but during the algorithm execution, a
>> boost::geometry::overlay_**invalid_input_exception is raised.
>>
>> 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.
>>
>> For info, I attached the SVG file (use inkscape to see it completely
>> since segments are out of the box due to negative coordinates).
>>
>> 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
>>
>
> Thanks for the report - can you give more details, especially WKT of the
> two input polygons? Or the sequence of algorithms you are using? These
> spikes normally never occur in unions, however in difference they might
> occur in some circumstances. Is this also happening with double typed data
> (in case you know)?
>
> Regards, Barend
> ______________________________**_________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/**mailman/listinfo.cgi/boost-**users
>

>