Geometry Boost List: [ggl] (spatial_)index::is_overlapping

Subject: [ggl] (spatial_)index::is_overlapping
From: Barend Gehrels (Barend.Gehrels)
Date: 2009-06-18 05:38:21

Hi Chris,

> Do we agree the only difference between the index::is_overlapping vs. 
> ggl::overlaps is that ggl considers common edges as NOT overlapping 
> while spatial_index considers they are?
That had indeed to be sorted out :-) You will be right here. The OGC 
definition for "overlaps" is that there should be an overlap in the 
interior. While "intersects" is the inverse of disjoint, so anything 
which touches or overlaps. So this one should be the "intersects" for 
boxes, which is not yet there but should be there soon, it is good to 
clean this up.

>
> spatial_index' function is not very efficient, and that is noticeable 
> in a drawing loop.
>
There is much to optimize here. As the list will have noticed, Federico 
is there again and he's very welcome. We will work on optimize it. I did 
a test some months ago about the difference between spatial index and 
"monotonic sections" for relating polygon segments to each other.

The summarized result is that the monotonic sections (MS) about twice as 
fast as a spatial index (SI) over segment index, while for MS there are 
6 times more comparisons than for SI. So SI should be faster

This is actually really good news because if we succeed in enhance the 
performance, many things will be (even) faster than they are now. For 
example 84% of the time for clipping is spent on finding intersections, 
this can be much less.

> Obviously, "else-ing" the X and Y if's would already be a nice 
> optimization ;-)
Thanks. Done. So it will harmonized later / moved to "intersects" for 
box. I'll do that soon.
But this will not solve everything...

Regards, Barend