Boost logo

Geometry :

Subject: [ggl] RE: incorrect result for an intersection
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-04-16 19:10:38

Vishnu wrote:
> Luke,
> What does Boost.Polygon use for independently validating its boolean
> operations?

Since boost.polygon has three implementations, one for manhattan, one for 45 and one for general case the first step was to compare with itself. 45 was validated against manhattan for manhattan inputs and general was validated against manhattan and 45. Manhattan was extensively tested and compared with four other known correct (but slower) internal implementations. The 45 was validated against commercially available software. The general booleans have been in use by quite a few different people since 2009 and have not have any bugs found in that time. Because I assembled the general booleans out of three different algorithms (line intersection, general sweep and polygon formation) I validated each of these sub algorithms in a thorough way before I integrated them. I tested on large scale data sets for my benchmark comparisons presented at boostcon 2009. There was a validation of output of the benchmarks including XOR test with area check on the result of the XOR, any suspciously large polygons were in
spected visually to make sure they could be explained by rounding error.


Geometry list run by mateusz at