Indexing External Spatial Data

When a new geographic feature is inserted into a database, an index value can be requested from GeoBase by providing either a LatLon representing a single point, or a BoundingBox that fully contains the feature. Using this information, GeoBase will return a 64-bit integer value that maps to the specified geographic area on the globe.

Note

The spatial index numbers provided by GeoBase are generated using an algorithm based on 'Hilbert Curves'. This algorithm orders two-dimensional geographic objects such as lines and polygons, placing them along a hypothetical space-filling curve. Using this technique, objects are given a numeric value corresponding with their fixed position on the curve. Similar numbers usually correlate with objects (areas) that are geographically close to one another.

Once a numeric index value for a feature (an object such as a polygon area) has been provided by GeoBase, it can be inserted into a database in an indexed UInt64 column for use as a simple search key. Later, when a query for a specific search area or feature is passed to GeoBase as a BoundingBox or a LatLon, ranges of index values corresponding with the search area are returned.

Note
Indexing of Points, Lines, Rectangles and Polygons is supported. Queries can be performed using Points (LatLon) and Rectangles (BoundingBox). For polygons, we suggest you index using a BoundingBox that fully encloses the polygon.

To request an index value using the HilbertIndex class, pass either a LatLon point or a BoundingBox area, as illustrated in the example below. A 64-bit integer (ulong) will be returned.

// Create a HilbertIndex object
HilbertIndex hilb_index = new HilbertIndex();

// Create a LatLon of the point ..
LatLon lat_lon = new LatLon(33.950335, -118.337890);

// .. or a BoundingBox containing the area ..
BoundingBox b_box = new BoundingBox();
b_box.Add(new LatLon(33.976473, -118.348352));
b_box.Add(new LatLon(33.943459, -118.325526));

// .. then generate a numeric value for the LatLon ..
ulong ll_key = hilb_index.GetKey(lat_lon);
Console.WriteLine("The Hilbert key for the LatLon is: " + ll_key);

// .. or a numeric value for the BoundingBox.
ulong box_key = hilb_index.GetKey(b_box);
Console.WriteLine("The Hilbert key for the BoundingBox is: " + box_key);

In the example above, using a LatLon point of latitude 33.950335 and longitude -118.337890, the value generated by GeoBase is 5129591021377933316. This value should be inserted into the existing spatial database in a UInt64 column, and the column indexed for searching.

To retrieve a number of index ranges associated with a specific search area (suitable for use in a conventional database query), pass a BoundingBox or LatLon to GeoBase. This process uses the HilbertQuery class.

Note
A single LatLon point is treated as a BoundingBox where P1 is equal to P2. In other words, it is the smallest BoundingBox possible located at the specified point.

Our example query will use a BoundingBox and retrieve a maximum of 128 value ranges. This is typically sufficient to accurately locate a feature. Fewer ranges can also be used but may result in the return of more features than necessary, reducing the accuracy of the search. The maximum number of ranges chosen will also be influenced by the indexing method used by the spatial database, as well as hardware factors such as hard drive speed.

Note that any areas (quads) that intersect with one another will be combined into a single range. For this reason the number of ranges returned by a given query will vary.

// Create a HilbertQuery object
HilbertQuery hil_query = hilb_index.Query(b_box, 128);

The array of ranges can be converted into a simple database query, as demonstrated below using the HilbertRange class. For this example we will create a SQL query.

// Start assembling a SQL query.
StringBuilder query = new StringBuilder("SELECT * FROM My_Table");
string join = "WHERE";
double count = 1;

// Use HilbertRange to specify the low and high values of the ranges.
foreach (HilbertRange range in hil_query.Ranges)
{
    query.AppendFormat(" {0} (HilbertKey >= {1} AND HilbertKey <= {2})", join, range.Low, range.High);
    Console.WriteLine("Low for range {0} is {1} and high is {2}.", count, range.Low, range.High);
    count = count + 1;
    join = "OR";
}

// Create the SQL query string.
string sqltest = query.ToString();

// Write the query to the console.
Console.WriteLine("The Hilbert query is: " + sqltest);

Note
Queries generated will always include an initial query range of '32'. This number represents any large features covering the entire globe.

In most cases the SQL query results should be further post-filtered. This is necessary because the ranges used aren't exact, especially when a small number of ranges is used. Without filtering, features may be returned that are outside the search area.

Using the HilbertQueryRenderer class it is also possible to view a graphical representation of the ranges included in the query.

// Create a HilbertQueryRenderer object
HilbertQueryRenderer hilquery_renderer = new HilbertQueryRenderer(hil_query);   
mapCtrl.Renderer = hilquery_renderer;

// Zoom out to show the whole world
mapCtrl.Zoom = ZoomLevel.World;

The BoundingBox search area is represented by a red box. Any areas within the query range but outside the BoundingBox have a white outline, and any areas partially or entirely within the BoundingBox are shown with a black border.

Areas shown in the same color are within a single range of values.