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