Where the UniformGrid divides a rectangular region of interest into bins, the ImplicitGrid divides each axis of the region of interest into bins. Each UniformGrid bin holds indexes of items that intersect that bin; each ImplicitGrid bin is a bitset that indicates the items intersecting that bin.
The following figure shows a 2D ImplicitGrid indexing a collection of polygons. A query point determines the bin to search for intersecting polygons. The application retrieves that bin's bitset from each axis and computes bitwise AND operator. The code takes that result and tests for query point intersection (possibly an expensive operation) with each of the polygons indicated by bits set "on."
The ImplicitGrid is designed for quick indexing and searching over a static index space in a relatively coarse grid, making it suitable for repeated construction as well as lookup. The following example shows the use of the ImplicitGrid. It is similar to the figure but tests a point against 2D triangles instead of polygons.
../../examples/spin_introduction.cpp
After including the header and setting up types, set up the index.
../../examples/spin_introduction.cpp
Inexpensive queries to the index reduce the number of calls to a (possibly) expensive test routine.
../../examples/spin_introduction.cpp