Geometry Boost List: [ggl] Problems with the difference between two polygons

Subject: [ggl] Problems with the difference between two polygons
From: Barend Gehrels (barend)
Date: 2011-07-29 14:44:31

Hi Enrico,

On 26-7-2011 21:01, Enrico Leoni wrote:
> On Sun, Jul 24, 2011 at 11:36 AM, Barend Gehrels<barend_at_[hidden]>  wrote:
>
>> I'm curious to the results of your benchmarks.
> See this link: http://preview.tinyurl.com/4378lyp
>

Thanks for including Boost.Geometry in your benchmark. I was able to 
reproduce your benchmark, thanks for the sources, and played with it. A 
few remarks on it.

It points to here:
<http://rogue-modron.blogspot.com/2011/04/polygon-clipping-wrapper-benchmark.html>

1) I was a bit surprised why Boost.Geometry was sometimes faster, 
sometimes slower than some other libraries. Especially in the first 
benchmark, Boost.Geometry is quite slow. I figured out that the culprit 
was the check on self-intersections. This check was added last april, to 
avoid many bug-reports on intersections, caused by invalid input.

If I turn off this check, the output of the first benchmark is 
completely different. A piece of the output:

With check on self-intersections:
TS Ggl        l 002 ms/l 0003953 PS 00157 VS 00024488 PR 006000 VR 
000041999
TS Ggl        l 002 ms/l 0009678 PS 00221 VS 00049060 PR 012000 VR 
000083569
TS Ggl        l 002 ms/l 0015297 PS 00271 VS 00073166 PR 018000 VR 
000124425
TS Ggl        l 002 ms/l 0021849 PS 00311 VS 00097030 PR 024000 VR 
000168057
TS Ggl        l 002 ms/l 0028331 PS 00349 VS 00121448 PR 030000 VR 
000208851

Without check on self-intersections:
TS Ggl        l 002 ms/l 0000120 PS 00157 VS 00024488 PR 006000 VR 
000041889
TS Ggl        l 002 ms/l 0000263 PS 00221 VS 00049060 PR 012000 VR 
000083679
TS Ggl        l 002 ms/l 0000517 PS 00271 VS 00073166 PR 018000 VR 
000125374
TS Ggl        l 002 ms/l 0000650 PS 00311 VS 00097030 PR 024000 VR 
000167179
TS Ggl        l 002 ms/l 0000831 PS 00349 VS 00121448 PR 030000 VR 
000209737

(For other readers: the value after ms/l, is the milliseconds per loop, 
so 831 for the last line). In this piece it is faster now by a factor 
~33. I yet have to figure out why self-intersection check is so slow 
here, because a factor 2 or 3 I would understand, but 33 times slower is 
unexpected. Anyway, it can now be turned off with the define 
BOOST_GEOMETRY_OVERLAY_SKIP_CHECK_SELF_INTERSECTIONS. This might be 
considered as cheating, but if you know the input is certainly valid, 
its use is justified. We used Boost.Geometry intersections for three 
years without it, and added this check only a few months before release...

So my question is: can you check it with this define? It is in the Trunk 
now (so it is just added/committed, and skips two lines of code). I'm 
curious to the new results (I didn't run all tests for all libraries on 
my machine, and I didn't compare or create graphs). I will check on our 
self-intersection-check later, that will take some time.

2) It would be great if you could add Microsoft's SqlGeometry to your 
benchmark. SqlGeometry is the heart of SQL Server spatial. I've good 
experience with it, it is fast and good. It is a library can be used in 
.NET very easily, also without SQL Server installed. See for example 
this page on my blog for a short introduction:
<http://barendgehrels.blogspot.com/2011/04/sqlgeometry-types-and-linq.html> 
(first two paragraphs).

3) It would also be great if you could add GEOS to your benchmark. This 
would require adding another C++ wrapper.

4) As you probably know I've done some benchmarks in the past, 
originally they were in the GGL repository. However, I considered myself 
as not an objective observer, so finished with that part. The sources 
are moved to another OSGEO repository, here 
<http://svn.osgeo.org/osgeo/foss4g/benchmarking/geometry_libraries/> . 
That site is referred to on your blog. You might consider to add your 
benchmark sources to that repository. It is nice to have a benchmark 
both in pure C++, and in .NET, available. You also might see how I did 
e.g. GEOS.

Regards, Barend