Region Predicate

This concept defines the requirements for a predicate to be used in region queries.

Region queries are used for orthogonal searches in sets of point and overlaping or enclosing orthogonal searches in set of boxes. The models of RegionPredicate are used to match points and boxes in the spatial containers against predefined intervals along each dimensions.

The models of region predicate shall publicly provide the following interfaces:

	Signature/Typedef	Description
Legend	P	A model of Region Predicate
Legend	V	The key of a spatial container. E.g. in
Require	spatial::relative_order P::operator()(spatial::dimension_type dim, const V& key, spatial::dimension_type rank) const	Returns spatial::below if key is below the interval considered along dim; spatial::above if key is above the interval being considered along dim; spatial::matching if key matches the interval being considered along dim. For a more complete explanation read the detailed description.

The definition of a region predicate functor is generally not required. Before you define such predicate, consider using spatial::bounds, spatial::open_bounds, spatial::closed_bounds, spatial::overlap_bounds, or spatial::enclosed_bounds.

A model of region predicate generally represents a multi-dimension continuous interval which is going to be used for orthogonal search. In order to provide a generic model of iteration over an interval, Spatial provides a tribool value spatial::relative_order to represent whether any value of the container is situated above, below or in the interval, for a given dimension.

For example, if you are storing integers in 1 dimension, and are interested in finding all values between 0 and 10 included, you could write the following predicate:

struct MySimplePredicate
{
  spatial::relative_order
  operator()(dimension_type, const int& key, dimension_type)
  {
    return key < 0 ? spatial::below
      : ( key > 10 ? spatial::above : spatial::matching );
  }
};

In this very simple example, there is no more than one dimension being considered, so the first and last parameters are not used. As can be seen from the implementation of the predicate, any value between 0 and 10 included would result in the return value equal to spatial::matching. If the value of key is less than 0, the lower bound of the interval, then the return value is equal to spatial::below. If the value of key is more than 10, the return value is spatial::above.

There are several limitation, by design, for a model a Region Predicate:

• Comparison are made along the axes of your space, you can't compare keys against a complicated polygon or a circle: i.e. for an euclidian space of rank 2, then the shape of the interval will be a box.

• The interval of comparison must be continuous. There cannot be "holes" in in the interval. If you must have a non-continuous predicate with, you have no choice but to split this predicate in several different predicate which have no holes, and make separated queries.

Let's look at a more complex example, probably closer to reality. This predicate will work on any key that is a std::vector<double>, and matches only values that are within the slice [-1, 1] of the highest dimension:

struct HigherSlice
{
  typedef std::vector<double> key_type;

  spatial::relative_order
  operator()(dimension_type dim, const key_type& key, dimension_type rank)
  {
    return rank - 1 == dim
      ? (key[dim] < -1.0 ? spatial::below
         : (key[dim] > 1.0 ? spatial::above : spatial::matching))
      : spatial::matching;
  }
};

The value of rank is equal to the rank of the container used for the orthogonal search. The value of dim is the current dimension being considered. It is always in the interval [0, rank).

More examples of predicates can be found in the example and the tutorial.

Class spatial::bounds< Key, Compare >

This object is a model of Region Predicate

Class spatial::closed_bounds< Key, Compare >

This object is a model of Region Predicate

Class spatial::enclosed_bounds< Key, Compare, Layout >

This object is a model of Region Predicate

Class spatial::open_bounds< Key, Compare >

This object is a model of Region Predicate

Class spatial::overlap_bounds< Key, Compare, Layout >

This object is a model of Region Predicate