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

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.

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: