Boost logo

Geometry :

Subject: [ggl] intersections and unions
From: Barend Gehrels (Barend.Gehrels)
Date: 2009-06-21 11:08:56

Hi Hartmut,

Hartmut Kaiser wrote:
>> - the "union" has a weird name because it is a reserved word. Other
>> libraries (SQL) do have the same and offer alternatives. We can have:
>> a) union_ (as in MPL)
>> b) st_union (as in SQL) but I reject this, it would require renaming
>> all algorithms for consistency and the st_ prefix is by us the ggl::
>> prefix
>> c) gunion (as in SpatialLite), in Italian (SL is built by italians)
>> this is probably pronounced the same, and "g" probably stands for
>> geometry/geography
>> d) join (cannot remember but some library uses this) sounds good to me
>> e) unite, so take the verb instead of the noun
>> f) Union with a capital
>> I would go for d)
> I know naming issues tend to become bicycle shed discussions, and
> additionally, my vote is probably the least significant here. Nevertheless,
> I'd go for a), because
> - all Boost libraries I know of dealing with this type of name clash resolve
> it by appending an underscore to the reserved name (MPL, Fusion, Phoenix,
> Proto, Spirit, to name a few)
> - a geometry union is - well - a union, and not a join
I appreciate your opinions so yes, significant. It makes sense. I first
also about a) and now I join you, so yes, union_ is consistent.

>> - speaking about performance, the performance is good. I've compared it
>> with other libraries and GGL is faster. More information about this
>> will come.
> What about geometric stability? This is alwys my main concern when it comes
> to geometric algorithms. Speed is fine and necessary, but only as long as
> they converge :-P
Good question. Bruno and I are working on a "numeric adaptor". With
this, library users can choose if they want to have precise types such
as GMP or CLN, or that they want to have plain IEEE arithmetic. I was
quite enthousiastic about this idea but, now we have some measures it
will decrease performance by many factors. Besides that I can hardly
find an example where the result is really better. I mean, the "double"
type is not that bad, I've worked for 15 years without caring about GMP
and never had problems. But I know, if you work in other domains it can
be more important.

So library users can choose between float (fast), double (fast and
precise), CLN (slow and more precise) and GMP (even slower).

The numeric adapter is one of the things we can do, we concentrated on
it now but given the meausures there are also other options (though some
things are only solvable with high precision arithmetic). However, there
is a "merge" process which merges intersection points lying at the same
place. It could be configurable with a sort of measure, or that only
that one is precise, or maybe something else.

There are actually not so many arithmetic steps here:
- the intersection itself, see how and where segments intersect
- merging, gather double intersections
The rest is pure logic and not sensitive for robustness.

>> - ~80% of the process is spent on finding intersections. Without
>> monotonic sections it would be much longer. But it can probably be
>> enhanced with spatial indexing instead
> A simple sorting along the outer edge of one of the polygons already helps a
> lot (using one dimensional indexing). But you're probably doing that
> already.
I think monotonic sections (it is not exactly sorting, but takes order
into account) has about the same effect.

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...

Geometry list run by mateusz at