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

Subject: [ggl] (spatial_)index::is_overlapping
From: Chris Browet (cbro)
Date: 2009-06-18 05:47:56

I've simplified the function to this:

template <typename Box>
> inline bool is_overlapping(Box const& b1, Box const& b2)
> {
>     if (ggl::get<min_corner, 0>(b1) > ggl::get<max_corner, 0>(b2))
>         return false
>
>     if (ggl::get<max_corner, 0>(b1) < ggl::get<min_corner, 0>(b2))
>         return false;
>
>     if (ggl::get<min_corner, 1>(b1) > ggl::get<max_corner, 1>(b2))
>         return false;
>
>     if (ggl::get<max_corner, 1>(b1) < ggl::get<min_corner, 1>(b2))
>         return false;
>
>     return true;
> }
>

This should dramatically reduce the numbers of "get". Do you see an obvious
flaw?

- Chris -

2009/6/18 Barend Gehrels <Barend.Gehrels_at_[hidden]>

> 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
>
>
>
>
>
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20090618/010af0a4/attachment.html