Boost logo

Geometry :

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

Geometry list run by mateusz at