Geometry Boost List: [ggl] intersections and unions

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...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20090621/4957a197/attachment.html