
Geometry : 
Subject: [ggl] (spatial_)index::is_overlapping
From: Mateusz Loskot (mateusz)
Date: 20090625 15:56:12
Barend Gehrels wrote:
>>>> 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?
>>>>
>>>>
>>> OK and much better than what I just checked in, and somewhat faster.
>>>
>>
>> Barend,
>>
>> Just a side note, How do we know that?
>
> The speed: In "other/dev" I've my checking program for the polygon
> "touches" algorithm. Not yet moved to "algorithms" (because the project
> didn't go through) but it is working. In that I've done some comparisons
> between spatial indexes / monotonic sections. I will write another mail
> about this later or put it on our Wiki.
> However, I can check the speed of spatial indexes there, and in case of
> errors we (probably) get wrong results there. It is not yet a unit test
> but you see immediately if the index does not work.
>
>
> The correctness: Actually the "intersects", what this function is, is
> just the ! disjoint. The disjoint is already implemented for box/box so
> this is another simpler version.
>
> template <typename Box>
> inline bool is_overlapping(Box const& b1, Box const& b2)
> {
> return ! ggl::disjoint(b1, b2);
> }
Barend,
Thanks for the indepth explanation, thought I think I've misunderstood.
In my question, I assumed you refer to the refactoring work that
"dramatically reduce the numbers of "get".
IOW, I asked why do you say that this refactoring improved speed :)
Anyway, misunderstanding.
Cheers,
 Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Geometry list run by mateusz at loskot.net