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

Subject: Re: [geometry] Bounding box checked first?
From: Bruno Lalande (bruno.lalande_at_[hidden])
Date: 2012-02-08 17:42:37

Hi,

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.

Correct.

Approximated geometries (among which bounding boxes) and maybe caching of
those is an area I'm thinking about currently, while reading a book which
is entirely about collision detection (in 3D). But whatever which form it
will take, the library should only be responsible for providing ways to
generate those approximated geometries from the more accurate ones
(generating, re-generating after rotation occurred, etc), and algorithms
that work on them. It shouldn't decide for the user whether they should be
used as pretests.

> 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.

Or, at the very most, the user has to be able to decide whether he wants
this step or not, as it can be very inefficient in some cases (as you
mentioned).

Regards
Bruno