Kamaelia.Support.Particles.SpatialIndexer

• Fast spatial indexing of entities
  • Example Usage
  • How does it work?

Fast spatial indexing of entities

A SpatialIndexer object is an index of entities that provides fast lookups of entities whose coordinates are within a specified radius of a specified point. You can have as many, or few, spatial dimensions as you like.

This is particularly useful for computationally intensive tasks such as calculating interactions between particles as performed, for example, by the Particle and ParticleSystem classes.

Example Usage

Creating and index and registering two entities with it at (1,2) and (12,34). We also tell the SpatialIndexer that the 'usual' radius we'll be searching over is 5 units:

>>> class Entity:
...   def __init__(self, coords):
...     self.coords = coords
...   def getLoc(self):
...     return self.coords
...
>>> index = SpatialIndexer(proxDist=5.0)
>>> a = Entity((1.0, 2.0))
>>> b = Entity((12.0, 34.0))
>>> index.add(a,b)

Only 'a' is within 10 units of (0,0):

>>> index.withinRadius((0,0), 10.0) == [(a,5.0)]
True

The returned tuples are of the form: (entity, distance-squared)

Neither point is within 1 unit of (0,0):

>>> index.withinRadius((0,0), 1.0)
[]

Both 'a' and 'b' are within 50 units of (0,0):

>>> index.withinRadius((0,0), 50.0) == [(a,5.0), (b,1300)]
True

We can ask the same, but request that 'a' be excluded:

>>> filter = lambda particle : particle != a
>>> index.withinRadius((0,0), 50.0, filter) == [(b,1300)]
True

If we remove 'a' then only 'b' will be found:

>>> index.remove(a)
>>> index.withinRadius((0,0), 50.0) == [(b, 1300.0)]
True

If we change the position of b we must notify the SpatialIndexer:

>>> index.withinRadius((0,0), 10.0) == []
True
>>> b.coords=(5.0,6.0)
>>> index.withinRadius((0,0), 10.0) == [(b, 61.0)]
False
>>> index.updateLoc(b)
>>> index.withinRadius((0,0), 10.0) == [(b, 61.0)]
True

How does it work?

SpatialIndexer stores entities in an associative data structure, indexed by their spatial location. Simply put, it breaks space into a grid of cells. The coordinates of that cell index into a dictionary. All particles that fall within a given cell are stored in a list in that dictionary entry.

It can then rapidly search for cells overlapping the area we want to search and return those entities that fall within that area.

The size of the cells is specified during initialisation. Choose a size roughly equal to the radius you'll most often be searching over. Too small a value will case SpatialIndexer to spend too long enumerating through cells. To big a cell size and far more entities will be searched that necessary.

Entities must provide a getLoc() method that returns a tuple of the coordinates of that entity.

Use the add(...) and remove(...) methods to register and deregister entities from the spatial index.

If you change the coordinates of an entity, the SpatialIndexer must be notified by calling its updateLoc(...) method.

---