Boost logo

Geometry :

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).


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

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

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

Geometry list run by mateusz at