Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
Quick Starting Guide

Table of Contents

Choosing a Container

Overview

Spatial C++ Library provides 8 different types of containers, all of which can be used to store elements in multi-dimension. The container's features can be represented in a table:

Container Name Number of dimensions used is a multiple of 2 Ability to Rebalance on insertion or removal Is an associative container
spatial::point_multiset NO YES NO
spatial::idle_point_multiset NO NO NO
spatial::point_multimap NO YES YES
spatial::idle_point_multimap NO NO YES
spatial::box_multiset YES YES NO
spatial::idle_box_multiset YES NO NO
spatial::box_multimap YES YES YES
spatial::idle_box_multimap YES NO YES

As you can see from the table, the idle family of container does not rebalance elements in its tree automatically, contrary to other containers. However they use one less pointer per node, and they can still be rebalanced on demand.

There are no box_map or point_set container in the library. It is currently not provided (it probably will in the future), so in the current containers you can store in one container as many copies of the same object's key as you require. If you wish to store only one key per container, you need to accomplish this by checking first if a given key exists. You can do this with spatial::equal_begin() or by calling find() from the container.

Box and point containers are in fact the same containers, expect that box containers can only store objects in dimensions that are a multiple of two. They are strickly equivalent to point containers otherwise.

Usage of containers

The table below is a naive view provided to guide you in your choice of containers.

I need to remove and insert objects frequently The set of object that I want to store does not change once it's loaded
I need to modify the object's attributes frequently spatial::point_multimap or spatial::box_multimap spatial::idle_point_multimap or spatial::idle_box_multimap
The object is the key itself, I won't modify it's attribute spatial::point_multiset or spatial::box_multiset spatial::idle_point_multiset or spatial::idle_box_multiset

Determining dimension at runtime

By setting the dimension used in the containers to 0, you can define the dimension as a runtime-time parameter, passed to the constructor of the container. All containers are specialized for the dimension 0 and will accept an additional dimension parameter in the constructor:

#include <iostream>
#include <tr1/array> // TR1 array
#include <spatial/point_multiset.hpp>
// Using a rank of 0 for the container, allows you to determine the dimension at
// runtime, as a parameter of the constructor of the conatiner.
int main(int, char**)
{
// Dimension of 0: This container's rank (or dimension) will be determined at
// runtime
typedef spatial::point_multiset<0, std::tr1::array<int, 3> >
runtime_container;
std::cout << "Enter a dimension for container: " << std::flush;
spatial::dimension_type dim;
std::cin >> dim;
// If we are not interested in dealing with ranks larger than 20
if (dim >= 20) throw spatial::invalid_dimension("dim");
runtime_container container(dim); // Note: if dim was equal to 0,
// spatial::invalid_dimension would be
// thrown
std::cout << "container rank is: " << container.dimension() << std::endl;
return 0;
}

Inserting Any Type of Objects

Objects that can be expressed in multi-dimension need to provide a way compare each others on specific dimensions. By default, if an object has overloaded the bracket operator to access each of its dimension, then it can be inserted in spatial::point_multiset, spatial::box_multiset or else, right out of the box.

#include <tr1/array>
#include <iostream>
#include <spatial/point_multiset.hpp>
int main()
{
typedef std::tr1::array<int, 3> point3d;
// Creation of a 3-dimensional container of point3d:
spatial::point_multiset<3, point3d> container;
// Creation of a few points:
point3d origin = { { 0, 0, 0 } };
point3d p1 = { { 432, 65, -32 } };
point3d p2 = { { 84, -2, -35 } };
// insertion of these points in the container
container.insert(origin);
container.insert(p1);
container.insert(p2);
std::cout << "There are " << container.size()
<< " elements in space." << std::endl;
return 0;
}

Spatial supports by default objects with overloaded bracket operator, because the comparator spatial::bracket_less is the default comparator on the containers. In the example above, you can also see how to insert or count elements present in the container.

However, most objects do not overload the bracket operator. Spatial supports 2 others ways of accessing dimensions in an object right out-of-the-box: if you overloaded the parenthesis operator instead, or if you have iterators to access each of your dimensions one by one. To declare a container for both cases, you would use a spatial::paren_less or an spatial::iterator_less comparator.

typedef std::tr1::array<int, 3> point3d;
// Access the dimensions in the point3d through the iterator
spatial::point_multiset<3, point3d, spatial::iterator_less<point3d> > container;
// Create a new type of point with overloaded parenthesis operator
struct other_point3d : point3d
{
// ...
int operator() (const size_t& index) const { return point3d::operator[](index); }
};
// Access the dimension in other_point3d through the parenthesis operator
spatial::point_multiset<3, point3d, spatial::paren_less<point3d> > other_container;

This provides enough flexibility to allow you to use containers such as std::list inside the Spatial container itself.

In some cases this is still not enough: the only way to access your dimensions may be through the use of independent members. In such case, you must use the spatial::accessor_less comparator.

#include <exception>
#include <spatial/point_multiset.hpp>
// A point whose dimensions are accessed directly through it's members:
struct point3d
{
int x;
int y;
int z;
};
// Remedy: define an accessor that takes a dimension_type as a parameter:
struct point3d_accessor
{
int operator() (spatial::dimension_type dim, const point3d p) const
{
switch(dim)
{
case 0: return p.x;
case 1: return p.y;
case 2: return p.z;
default: throw std::out_of_range("dim");
}
}
};
int main ()
{
// Now declare the container with the user-defined accessor
spatial::point_multiset<3, point3d,
spatial::accessor_less<point3d_accessor, point3d>
> point3d_container;
point3d a = { 0, 1, 2 };
point3d b = { 1, 2, 3 };
point3d_container.insert(a);
point3d_container.insert(b);
return 0;
}

Now you start to see that you can use a wide range of objects, inside your container. However, what if your object has different types for each dimension? In this case, you must define your own comparator, as presented below.

// We want to create a library of books, according to several dimensions:
struct book
{
std::string author;
std::string title;
int date;
};
// We define a comparator that compares 2 objects along one dimension
struct compare_book
{
bool operator() (spatial::dimension_type n, const Book& x, const Book& y) const
{
switch(n)
{
case 0: return x.author < y.author;
case 1: return x.title < y.title;
case 2; return x.date < y.date;
default: throw std::out_of_range();
}
}
};
// Now we declare our library
spatial::point_multiset<3, book, compare_book> library;

With this covered, you can now insert any kind of objects, in any number of dimensions, in the containers.

Basic operations on containers

Briefly, at the beginning of the last section, Inserting Any Type of Objects, we showed how to insert elements inside the container. Now let's figure out how to iterate through all the inserted elements, or finding out if the container already contains an particular element.

typedef spatial::point_multiset<3, point3d> container_type;
container_type container;
// ...
// let's suppose that plenty of point3d have been inserted in the container
// ...
for( container_type::const_iterator iter = container.begin();
iter != container.end(); ++iter )
{
// do something with iter
}

Again, it works like any other container from the STL, so finding out if a particular element is present in the container or not, should not surprise you either.

// continued from above...
point3d point_to_find = { { 1, 2, 3 } };
if ( container.find(point_to_find) != container.end() )
{
// point_to_find is in the container!
}
else
{
// humm... point_to_find is not in the container...
}

What about erasing a point then?

// continued from above...
point3d point_to_erase = { { 6, 6, 6 } }; // better erase the beast...
if ( container.erase(point_to_erase) != 0 )
{
// erased all points that matched point_to_erase
}

While most basic operation closely resemble the STL containers, there are a few that are only meaniful for the Spatial containers.

One of them is the inherited spatial::details::Kdtree::rebalance() function that, as its name implies, balances all elements in the container. It makes sense only for containers which do not reblance their elements on insertion, such as spatial::idle_point_multiset, spatial::idle_point_multimap, spatial::idle_box_multiset, or spatial::idle_box_multimap.

Spatial operations on containers

If you have need for a Spatial container, you're probably looking to do one of these operations:

  • find all objects within a certain range,
  • find the nearest neighbor to some point,
  • treat all dimensions as if they where a different way to index each points.

All of these operations are done through the use of external container iterators. Short examples of their usage are given in this section.

Orthogonal range search

Orthogonal range searches are done through the spatial::region_iterator. This iterator lets you go through all elements matching a specific region. By default, a region is defined by a pair of low and high key which bound any x in the container, along every dimension:

\[ \forall _{i = 0 \to n} , low _i \leq x _i < high _i \]

Hence the default behavior for spatial::region_iterator is to act as an half open region search.

using namespace spatial;
typedef point_multiset<3, point3d> container_type;
container_type container;
// ... let's imagine a lot of points have been inserted in the container
// define a region to explore
point3d low = { { -2, -2, -2 } };
point3d high = { { 2, 2, 2 } };
// find all the points between low and high
for (region_iterator<container_type> iter = region_begin(container, low, high);
iter != region_end(container, low, high); ++iter)
{
// do something with elements in the region by deferencing iter...
}

Since it is an iterator which follow's the STL standard, you can also use this in a std::for_each call.

using namespace spatial;
typedef point_multiset<3, point3d> container_type;
container_type container;
// ... let's imagine a lot of points have been inserted in the container
// define a range to explore
point3d low = { { -2, -2, -2 } };
point3d high = { { 2, 2, 2 } };
// create a functor that is doing something with each points
struct functor
{
void operator() (const point3d& p) const
{
// do something with these points...
}
};
std::for_each(region_begin(container, low, high),
region_end(container, low, high),
functor());

Region defined as half-open intervals are the default behavior of spatial::region_iterator, but they are much more versatile than this: we can use them to slice or partition your elements in space. Suppose we are working in 3 dimensions, and we wish to find all points that match the following criterias:

\[ -1 < x _0 < 1, -\infty < x _1 < \infty, -\infty < x _2 < 2 \]

Then we must define a predicate for this particular requirement and use it in the orthogonal range search.

using namespace spatial;
typedef point_multiset<3, point3d> container_type;
container_type container;
// ... let's imagine again that a lot of points have been inserted in the container
// Now we define our predicate, it must return a spatial::relative_order value
struct predicate
{
relative_order
operator()(dimension_type dim, const point3d& x) const
{
switch(dim)
{
// for dimension 0, only the interval ]-1, 1[ matches...
case 0: return x[0] <= -1 ? below : (x[0] >= 1 ? above : matching );
// for dimension 1, it's always a match...
case 1: return matching;
// for dimension 2, matches unless it's equal or above 2...
case 2: return x[2] < 2 ? matching : above;
// else we must be out of range...
default: throw std::out_of_range();
}
}
};
// find all the points that satisfy the predicate
for (region_iterator<container_type, predicate> iter
= region_begin(container, predicate());
iter != region_end(container, predicate()); ++iter)
{
// do something with these points...
}

As you can see, the predicate must return a spatial::relative_order type. spatial::relative_order defines 3 values: below, matching and above. These values tell the algorithm the current postion of the key with regard to the dimension that is being studied: is the key below the interval being studied? Is it above? Or it is matching the region being studied?

While the predicate may not be intuitive to define, it give complete control over the orthogonal range search query on the container.

Spatial comes with a few specialized version of this iterator:

Nearest neighbor search

Another kind of search that is commonly done on multi-dimension containers are nearest neighbor search. spatial::neighbor_iterator allow you to iterate through the k*-nearest points to target, and according to a specific metric.

The container only orders point in a multi-dimensional space, but it has no notion of distances. The metrics provided with Spatial currently include spatial::euclidian, spatial::quadrance or spatial::manhattan (a.k.a. taxicab) representation of distances.

Note
Since the container is independent of the metric, several different metrics can be applied to the same container, without modifying the content of the container.

The use of spatial::neighbor_iterator is presented below:

using namespace spatial;
typedef point_multiset<3, point3d> container_type;
container_type container;
// ... let's imagine that at least 4 points have been inserted in the tree.
// We want to find the closest points to:
point3d target = { { 1, 2, 3 } };
// Print the first 4 closest points (from closest to furthest) with their distances:
neighbor_iterator<container_type> iter = neighbor_begin(container, target);
std::cout << *iter << " is at " << distance(iter) << "metres\n";
std::cout << *++iter << " at " << distance(iter) << "metres\n";
std::cout << *++iter << " at " << distance(iter) << "metres\n";
std::cout << *++iter << " at " << distance(iter) << "metres\n";

This example assumes that the values for each dimension of the type point3d can be accessed via one of the built-in comparators of the library.

Additionally, this example makes use of spatial::neighbor_iterator in its default form, where the euclidian metric is being used and distances are expressed in double.

This is not always what you want. In the example below, we will return distances in int using the spatial::quadrance metric:

using namespace spatial;
typedef point_multiset<3, point3d> container_type;
container_type container;
// ... let's imagine that at least 4 points have been inserted in the tree.
// We want to find the closest points to:
point3d target = { { 1, 2, 3 } };
// Print the first 4 closest points (from closest to furthest) with their distances:
neighbor_iterator<container_type, quadrance<container_type, int> > iter
= neighbor_begin(container, target, quadrance<container_type, int>());
std::cout << *iter << " is at " << distance(iter) << "metres\n";
std::cout << *++iter << " at " << distance(iter) << "metres\n";
std::cout << *++iter << " at " << distance(iter) << "metres\n";
std::cout << *++iter << " at " << distance(iter) << "metres\n";

spatial::quadrance is one of the built-in metrics. Since it should fit most purpose it is also a templated type, based on your container type. It becomes tedious to express, so fortunately, there is a shorter form, more readable:

using namespace spatial;
typedef point_multiset<3, point3d> container_type;
container_type container;
// ... let's imagine that at least 4 points have been inserted in the tree.
// We want to find the closest points to:
point3d target = { { 1, 2, 3 } };
// Print the first 4 closest points (from closest to furthest) with their distances:
quadrance_neighbor_iterator<container_type, int> iter
= quadrance_neighbor_begin(container, target);
std::cout << *iter << " is at " << distance(iter) << "metres\n";
std::cout << *++iter << " at " << distance(iter) << "metres\n";
std::cout << *++iter << " at " << distance(iter) << "metres\n";
std::cout << *++iter << " at " << distance(iter) << "metres\n";

spatial::neighbor_iterator gives you the possibility to search for the k nearest neighor according to your own pre-defined metric. Metric are more complex to write that your average functor, however you have the possibility to compute distances even in a Reimannian metric (e.g. Longitude, Latitude, Altitude corrdinates) if necessary.

Mapping of the container onto a single dimension

Mapping makes your multi-dimension container behave as if it was only a single dimension container, seamlessly tranforming your spatial::point_multiset into a std::set, along one of the dimesion.

Being able to map each of n dimensions of the container independently gives you a simplicity of n STL set containers merged into one, and it starts shifting the perception of the library from a multi-dimension container to a simple in-memory database, where every single field of your records are indexed and can be searched by range of elements.

To illustrate it better, we can start again from the earlier example of the book library:

// We want to create a library of books, according to several dimensions:
struct book
{
std::string author;
std::string title;
int date;
};
// We define a comparator that compares 2 objects along one dimension
struct compare_book
{
bool operator() (spatial::dimension_type n, const Book& x, const Book& y) const
{
switch(n)
{
case 0: return x.author < y.author;
case 1: return x.title < y.title;
case 2; return x.date < y.date;
default: throw std::out_of_range();
}
}
};
using namespace spatial;
// Now we declare our library
typedef point_multiset<3, book, compare_book> library_type;

Now lets start doing a few searches. For example, getting all the books that are written within 1981 to 1993, from the first to the last (the ordering matters here, otherwise we could use a spatial::region_iterator to get that range, but without a specific order).

library_type library;
// Insert several book object in our library
// The "date" information is on the third dimension (or dimension = 2)
mapping_iterator<library_type, 2> iter = mapping_lower_bound(library, 2, 1981);
mapping_iterator<library_type, 2> end = mapping_upper_bound(library, 2, 1993);
for(; iter != end; ++iter)
{
// do something with the books written from 1981 to 1993, in sequence
}
Note
In the example above, the call to spatial::mapping_upper_bound() was not included in the for loop, because the call is not free. So it is better to call it once and save the results.

More similar queries can be done in this way, so you could find the authors in lexicographic order, or the titles in lexicographic order, etc.