Spatial Indexing and Quadtrees

This post is going to be me breaking down and trying t understand this blog post (done by Nick) about Spatial indexing with Quadtrees and Hilbert Curves.  Hopefully I can learn how this algorithm would be useful for terrain and environment representation.  I have a few ideas currently, but I’d like to break down and understand the algorithm first.

Spatial Database’s and Spacial Indices

In order to understand what a spatial index is, we need to know what a spatial database (WIKI) is.  A spatial database is essentially a collection of data that stores points, lines and polygons and any other object data.  Simple terms: databases that store information related to objects in space.  Many databases feature the following functionality:

  • Spatial Measurements: Distance between points
  • Spatial Functionality: Modify existing features while creating new ones
  • Spatial Predicates: Allows for binary/(true/false) queries like, “is there a boss located in that cave 1km from here?”
  • Constructor Functions: Creates new features in the database with an SQL query specifying the vertices (node points) that create lines.  If the first and last vertex are connected (first and last vertex are identical) the feature will be a polygon
  • Observer Functions: Queries that return specific information like the location of the center of a circle

[ASIDE] SQL – Structured Query Language that is designed for managing data in rational database management systems
[ASIDE] SQL Queries – Queries which retrieve data based on specific criteria.  Most important element in SQL

Spatial Queries

Spatial indices are used by the spatial database to make faster queries.
These queries are essentially functions with the following template: functionName (parameter(s)) : return type

Types of queries:

  • Distance(geometry, geometry) : number
  • Equals(geometry, geometry) : boolean
  • Disjoint(geometry, geometry) : boolean
  • Intersects(geometry, geometry) : boolean
  • Touches(geometry, geometry) : boolean
  • Crosses(geometry, geometry) : boolean
  • Overlaps(geometry, geometry) : boolean
  • Contains(geometry, geometry) : boolean
  • Length(geometry) : number
  • Area(geometry) : number

Quadtrees

Trees. OH NO! I personally hated my class on algorithms and data structure’s, except for the part on trees.  Trees were simple to understand and they were related to the more interesting computer animation algorithms (Skeletal Animation, global vs local transformations).  Trees are simply data structures of linked nodes.

So quadtrees are used as a form of spatial indexing.  They are a special type of tree where each internal node has exactly 4 children.  They are heavily used in partitioning 2D space by recursively subdividing it into four quadrants and regions.

This is an example of a 2D quadtree. Ignore the points for now if they confuse you. They are just point data.  This is to show how a quadtree divides an indexed area

Nick describes the quadtree very well on his blog.  Each node in the tree is represented by a bounding box covering a part of the space that in indexed, the root node would be covering the entire area.  Each node is either a leaf node with one or more indexed points, but with no children.  If it is an internal node then it has exactly 4 children, one for each quadrant obtained by diving the area covered in by half on each axes.  This next picture should make things a bit more clear:

Representation of how a quadtree is structured internally

To query a quadtree is very simple.  Since we have a good graphical representation of our quadtree we are essentially dealing with intersecting areas.  We know that the root encompasses the entire area of the quadtree, and each child is a subsection of that.  So to query, we need to examine each child node and see if the area inside that quadrant intersects with our current query.  Once we encounter a leaf node is when we have to search each entry within that area to see if it intersects with the query area.  Then you simply return it if it does.

Geohashing and Hilbert Curves

Both of these are ways of not using the quadtree to recursively look up through the tree, but rather use different methods of querying.

The order in which geohashing visits each quad
The order in which a hilbert curve visits each quad

Summary

Nick goes into a lot more detail in the geohashing and hilbert curve methods, if you are so inclined to learn more about them, click here.  However, as a game developer quadtrees and spatial databases make me think of maps in games.  Ways of representing them (mini-maps) or ways of maybe organizing our scene managers in ogre?  Who knows, but now that I am more familiar with the quadtree data structure I am sure my team an I can think of many ways to implement this useful data structure in our game.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s