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

Subject: [ggl] (spatial_)index::is_overlapping
From: Mateusz Loskot (mateusz)
Date: 2009-06-25 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 in-depth 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