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-08-01 03:02:16

Hi Enrico, List,

>> 1)
>> 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.
> I will check it in the next few days (the pc used to run the tests is
> located at my workplace).

Thanks.

In the meantime I thought about this define. I think I will move the 
check to another point in the sources. Actually I don't like this 
define, people have to define something to get the full (original) 
speed, while in most cases they will be unaware of this.

Actually Boost.Geometry *can* do overlays on two input geometries which 
are invalid. It is just that, if the input polygons are too messy or 
interact in a non-ambiguous way, that the path traversal which we do 
internally does not produce a meaningful output. For example, these 
polygons:

do both have self-intersections but they do not influence the overlay. 
Self-intersections are not even detected. These two polygons can 
perfectly be intersected or unioned (the union will include the two 
artefacts).

While this overlay:

might be a bit more problematic (didn't try yet).

I think I will move the check to the point where a problem is detected. 
This changes the original pre-condition "invalid polygons cannot be 
overlayed" to "invalid polygons might, depending on the artefacts, give 
problems or raise exceptions when overlayed", but it will get the 
original speed back (without a define).

So, for the current benchmark, the define will do, and for the longer 
term it is better to avoid this slowy check.

Alternatively we could reverse the define (so only check if defined) or 
give an optional boolean parameter with the intersection function. But 
the last option is not scalable (if there are more versions, we have to 
repeat it, etc). Also it might be part of a strategy (currently the 
intersection does not take a strategy).

Finally the reverse define could be kept with the move of the check, so 
then users can choose to check invalidity before, or it is detected in 
case a of traversal problem.

>> 4)
>> 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.
> With SqlGeometry (and probably GEOS ... while CGAL has some problems
> when compiled with the /clr flag) I think I will close with this
> benchmark ... also I think it should be at least refactored / refined
> (to keep the myth of the VB programmer I did a lot of copy and paste),
> and the wrappers should be created using P/Invoke (maybe with the help
> of SWIG) for portability (Mono under Unix). This is more work than I'm
> willing to do. However, if someone is interested, my code is available
> and can be taken and used without problems.

I understand. Great you consider adding SqlGeometry/GEOS. If you want, I 
can put your sources (when you're ready with them) there, I've an 
account, so they are saved, at a central place, and waiting for a future 
someone continuing the research.

Regards, Barend

-------------- next part --------------
Skipped content of type multipart/related