Geometry Boost List: Re: [geometry] Bounding box checked first?

Subject: Re: [geometry] Bounding box checked first?
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2012-02-08 13:23:48

Barend Gehrels wrote:

On 8-2-2012 11:20, Sebastian wrote:
>> Do the functions "bool within()" (e.g. point in polygon) and "bool 
>> intersects()" (e.g. polygon with polygon) do any bounding box checks?

>No.  Because we use models of a bare point. It can be any point. Same for polygon, can be any (that is: fulfilling the concept). So they don't bear a box with them, the box is not part of the concept.

To clarify, point in polygon check, for example, has the same computational complexity as computing a polygons bounding box.  Therefore the point in polygon check is only sped up if the bounding box of the polygon is pre-computed and cached along with the polygon object.  Since the polygon concept doesn't require a cached bounding box there is no way to use bounding box to speed up the check.  For polygon/polygon intersects the computational complexity is higher so checking if the bounding boxes intersect to check if the polygons could possibly intersect may be profitable, but that is something that should be done in the application.  If you knew in your application that the polygon bounding boxes must intersect because, for example, they were both returned by a point query in a spatial query data structure then you would be unhappy to perform the redundant bounding box check inside intersects().  Only at the application level do you know whether the optimization is desirable.

Regards,
Luke