Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations

This concept defines the requirements for a Metric to be used with spatial::neighbor_iterator.

spatial::neighbor_iterator provide iterative nearest neighbor search algorithms on the container. Initializing the iterator to its begining makes it stop at the nearest neighbor of the given point of origin. In order for the spatial::neighbor_iterator to compute distances, a Metric type must be provided.

The models of Metric shall publicly provide the following interfaces:

Legend P A type that is a model of Metric
Legend V A type that is the key of the spatial container.
Legend D A type that is the distance used for calculation. D must have the same interface as arithmetic types (it must be comparable, it must support addition, substraction, multiplication, division, etc).
Require typedef D distance_type The type used to express the distance between 2 element of the container.
Require distance_type A::distance_to_key(dimension_type rank, const V& origin, const V& key) const Compute the distance between origin and key in a space of dimension rank.
Require distance_type A::distance_to_plane(dimension_type rank, dimension_type dim, const V& origin, const V& key) const Compute the distance between key and the plane orthogonal to the axis along dimension dim and containing origin, in a space of dimension rank.

The purpose of the Metric itself is to represent the metric space in which the metric calculation in between elements of the container take place. With this concept you have the freedom to create any metric space that is a continous space topology. And so, it is possible to write a Metric where calculations for distance_to_key and distance_to_plane take place in a Manifold, and not just a regular Euclidean space.

If you were to write a Metric on your own, you would start from the stub below, that is following the interface of this concept:

struct MyMetric
typedef my_distance_type distance_type; // [1]
distance_to_key(dimension_type rank,
const Key& origin, const Key& key) const; // [2]&[4]
distance_to_plane(dimension_type rank, dimension_type dim,
const Key& origin, const Key& key) const; // [3]&[4]

The details of the MyMetric type are as follow:

  • [1] is the definition of the type used for the computation of the distance, often defined as double.
  • [2] is the general understanding of a distance: the quantity that separates two points origin and key in the current metric space.
  • [3] represents the shortest possible distance between a point named origin and the plane that is orthogonal to the axis along the dimension dim and that contains the point key. While this may seem difficult to understand, in euclidian space, this operation is equivalent to computing the difference in coordinates of origin and key along the dimension dim.
  • [4] for any 2 points origin and key, [3] must always return a result that is lower or equal to [2], regardless of the dimension being considered. If rule [4] is not enforced in the metric (For example, due to errors in approximations during the calculation), then the iterator would not work properly and would skip some items in the container. When writing Metrics for Manifolds or Riemanean spaces, you must pay special attention to this rule, since the shortest distance between the key and the plane is not always easy to represent mentally.

Spatial provides ready-made models of Metric such as spatial::euclidian, spatial::quadrance and spatial::manhattan.

Class spatial::euclidian< Ct, DistanceType, Diff >
This object is a model of Metric
Class spatial::manhattan< Ct, DistanceType, Diff >
This object is a model of Metric.
Class spatial::quadrance< Ct, DistanceType, Diff >
This object is a model of Metric