Spatial C++ Library
Generic MultiDimensional 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:
Signature/Typedef  Description  
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:
The details of the MyMetric
type are as follow:
distance:
the quantity that separates two points origin
and key
in the current metric space.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
.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 readymade models of Metric such as spatial::euclidian, spatial::quadrance and spatial::manhattan.