Data Structures & Algorithms in Python

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