Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
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|
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
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.
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|
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:
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.
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.
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
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.
With this covered, you can now insert any kind of objects, in any number of dimensions, in the 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.
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.
What about erasing a point then?
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.
If you have need for a Spatial container, you're probably looking to do one of these operations:
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 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
high key which bound any
x in the container, along every dimension:
Hence the default behavior for spatial::region_iterator is to act as an half open region search.
Since it is an iterator which follow's the STL standard, you can also use this in a
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:
Then we must define a predicate for this particular requirement and use it in the orthogonal range search.
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:
highare included in the search,
highare included in the 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.
The use of spatial::neighbor_iterator is presented below:
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
This is not always what you want. In the example below, we will return distances in
int using the spatial::quadrance metric:
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:
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 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:
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).
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.