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@xs4all.nl> 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@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users