12. Spatial Data Structures

In This Chapter

Spatial Data

Computing Distances Between Points

Circles and Bounding Boxes

Searching Spatial Data

Lists of Points

Grids

Quadtrees

Theoretical Performance and Optimizations

Practical Considerations

Further Extensions

So far, all our data structures have stored records containing a key to identify them. That’s perfect when you want to find a record that exactly matches a key. What about when you want to identify items by position—for example, finding all the grocery stores within a certain distance of a particular location? For that task, you need a structure that uses two separate numeric keys to identify the location of records that correspond to points in space.

Although this pair ...

Get Data Structures & Algorithms in Python now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.