Aim: implements separable l_p metrics with exact predicates. More...

#include <DGtal/geometry/volumes/distance/ExactPredicateLpSeparableMetric.h>

Public Types
typedef TSpace	Space
	Copy the space type. More...

typedef Space::Point	Point
	Type for points. More...

typedef Point::Coordinate	Abscissa
	Type for points. More...

typedef Space::Vector	Vector
	Type for vectors. More...

typedef TRawValue	RawValue
	Type for internal distance values. More...

typedef double	Value
	Type for distance values. More...

typedef ExactPredicateLpSeparableMetric< TSpace, p, RawValue >	Self
	Self type. More...

Public Member Functions
	BOOST_CONCEPT_ASSERT ((concepts::CSpace< TSpace >))

	BOOST_CONCEPT_ASSERT ((concepts::CInteger< RawValue >))

	ExactPredicateLpSeparableMetric ()

	~ExactPredicateLpSeparableMetric ()

	ExactPredicateLpSeparableMetric (const Self &other)

Self &	operator= (const Self &other)

Value	operator() (const Point &aP, const Point &aQ) const

Closest	closest (const Point &origin, const Point &first, const Point &second) const

RawValue	rawDistance (const Point &aP, const Point &aQ) const

bool	hiddenBy (const Point &u, const Point &v, const Point &w, const Point &startingPoint, const Point &endPoint, const typename Point::UnsignedComponent dim) const

void	selfDisplay (std::ostream &out) const

bool	isValid () const

Abscissa	binarySearchHidden (const Abscissa &udim, const Abscissa &vdim, const RawValue &nu, const RawValue &nv, const Abscissa &lower, const Abscissa &upper) const

Detailed Description

template<typename TSpace, DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>
class DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >

Aim: implements separable l_p metrics with exact predicates.

Description of template class 'ExactPredicateLpSeparableMetric'

Given a template parameter p, the class implement classical l_p metric as a model of CSeparableMetric. Hence, given two points \( x=(x_0...x_{n-1})\), \( y=(y_0...y_{n-1})\) in the given digital space (see below), we define a metric such that:

\( distance(x,y)= \left( \sum_{i=0}^{n-1} |x_i-y_i|^p\right)^{1/p}\)

This class is said to be exact in the sense that the power p is computed without approximation (exponentiation by squaring in \( O(log(p))\) per computation, see functions::power). As a consequence, hiddenBy and closest methods are error free if the capacity of the template type TPromoted allows to store sums of \( |x_i-y_i|^p\) quantities.

Template Parameters

TSpace	the model of CSpace on which the metric is defined.
p	the exponent of the metric (static DGtal::uint32_t)
TRawValue	model of CSignedInteger used to store power p sums (default: DGtal::int64_t)

Definition at line 87 of file ExactPredicateLpSeparableMetric.h.

Member Typedef Documentation

◆ Abscissa

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

typedef Point::Coordinate DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::Abscissa

Type for points.

Definition at line 98 of file ExactPredicateLpSeparableMetric.h.

◆ Point

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

typedef Space::Point DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::Point

Type for points.

Definition at line 96 of file ExactPredicateLpSeparableMetric.h.

◆ RawValue

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

typedef TRawValue DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::RawValue

Type for internal distance values.

Definition at line 103 of file ExactPredicateLpSeparableMetric.h.

◆ Self

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

typedef ExactPredicateLpSeparableMetric<TSpace,p,RawValue> DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::Self

Self type.

Definition at line 110 of file ExactPredicateLpSeparableMetric.h.

◆ Space

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

typedef TSpace DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::Space

Copy the space type.

Definition at line 92 of file ExactPredicateLpSeparableMetric.h.

◆ Value

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

typedef double DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::Value

Type for distance values.

Definition at line 107 of file ExactPredicateLpSeparableMetric.h.

◆ Vector

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

typedef Space::Vector DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::Vector

Type for vectors.

Definition at line 100 of file ExactPredicateLpSeparableMetric.h.

Constructor & Destructor Documentation

◆ ExactPredicateLpSeparableMetric() [1/2]

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::ExactPredicateLpSeparableMetric ( )

Constructor.

◆ ~ExactPredicateLpSeparableMetric()

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::~ExactPredicateLpSeparableMetric ( )

Destructor.

◆ ExactPredicateLpSeparableMetric() [2/2]

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::ExactPredicateLpSeparableMetric ( const Self & other )

inline

Copy constructor.

Parameters

other the object to clone (not used).

Definition at line 127 of file ExactPredicateLpSeparableMetric.h.

     {
       boost::ignore_unused_variable_warning( other );
     }

Member Function Documentation

◆ binarySearchHidden()

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

Abscissa DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::binarySearchHidden	(	const Abscissa &	udim,
		const Abscissa &	vdim,
		const RawValue &	nu,
		const RawValue &	nv,
		const Abscissa &	lower,
		const Abscissa &	upper
	)		const

Perform a binary search on the interval [lower,upper] to detect the mid-point between u and v according to the l_p distance. It returns the abscissa q such that q belongs to the power cell of u (strictly) but not q-1.

Precondition: udim < vdim

Parameters

udim	coordinate of u along dimension dim
vdim	coordinate of v along dimension dim
nu	partial distance of u (sum of \|xj-x_i\|^p) discarding the term along the dimension dim
nv	partial distance of v (sum of \|xj-x_i\|^p) discarding the term along the dimension dim
lower	interval lower bound
upper	interval upper bound

Returns: the u Voronoi cell greatest point coordinates along dimension dim.

Referenced by testBinarySearch().

◆ BOOST_CONCEPT_ASSERT() [1/2]

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< RawValue >) )

◆ BOOST_CONCEPT_ASSERT() [2/2]

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::BOOST_CONCEPT_ASSERT ( (concepts::CSpace< TSpace >) )

◆ closest()

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

Closest DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::closest	(	const Point &	origin,
		const Point &	first,
		const Point &	second
	)		const

Given an origin and two points, this method decides which one is closest to the origin. This method should be faster than comparing distance values.

Parameters

origin	the origin
first	the first point
second	the second point

Returns: a Closest enum: FIRST, SECOND or BOTH.

Referenced by testMetrics().

◆ hiddenBy()

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

bool DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::hiddenBy	(	const Point &	u,
		const Point &	v,
		const Point &	w,
		const Point &	startingPoint,
		const Point &	endPoint,
		const typename Point::UnsignedComponent	dim
	)		const

Given three sites (u,v,w) and a straight segment [startingPoint,endPoint] along dimension dim, we detect if the voronoi cells of u and w strictly hide the voronoi cell of v on the straight line.

This method is in \( O(log(n))\) if n is the size of the straight segment. For \( l_2\) metric (p=2), the method is in \( O(1)\).

Precondition: u,v and w must be such that u[dim] < v[dim] < w[dim]

Parameters

u	a site
v	a site
w	a site
startingPoint	starting point of the segment
endPoint	end point of the segment
dim	direction of the straight line

Returns: true if (u,w) hides v (strictly).

Referenced by testMetrics(), testSpecialCasesL2(), and testSpecialCasesLp().

◆ isValid()

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

bool DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::isValid ( ) const

Checks the validity/consistency of the object.

Returns: 'true' if the object is valid, 'false' otherwise.

◆ operator()()

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

Value DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::operator()	(	const Point &	aP,
		const Point &	aQ
	)		const

Compute the distance between aP and aQ.

Parameters

aP	a first point.
aQ	a second point.

Returns: the distance between aP and aQ.

◆ operator=()

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

Self& DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::operator= ( const Self & other )

inline

Assignment.

Parameters

other other the object to copy (not used).

Returns: a reference on 'this'.

Definition at line 137 of file ExactPredicateLpSeparableMetric.h.

     {
       boost::ignore_unused_variable_warning( other );
       return *this;
     }

◆ rawDistance()

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

RawValue DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::rawDistance	(	const Point &	aP,
		const Point &	aQ
	)		const

Compute the raw distance between aP and aQ. (i.e. \( \sum_{i=1}^n |x_i-y_i |^p\)).

Parameters

aP	a first point.
aQ	a second point.

Returns: the distance between aP and aQ.

◆ selfDisplay()

template<typename TSpace , DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>

void DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >::selfDisplay ( std::ostream & out ) const

Writes/Displays the object on an output stream.

Parameters

out	the output stream where the object is written.

The documentation for this class was generated from the following file:

ExactPredicateLpSeparableMetric.h

Public Types

Public Member Functions

Detailed Description

template<typename TSpace, DGtal::uint32_t p, typename TRawValue = DGtal::int64_t> class DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >

Member Typedef Documentation

◆ Abscissa

◆ Point

◆ RawValue

◆ Self

◆ Space

◆ Value

◆ Vector

Constructor & Destructor Documentation

◆ ExactPredicateLpSeparableMetric() [1/2]

◆ ~ExactPredicateLpSeparableMetric()

◆ ExactPredicateLpSeparableMetric() [2/2]

Member Function Documentation

◆ binarySearchHidden()

◆ BOOST_CONCEPT_ASSERT() [1/2]

◆ BOOST_CONCEPT_ASSERT() [2/2]

◆ closest()

◆ hiddenBy()

◆ isValid()

◆ operator()()

◆ operator=()

◆ rawDistance()

◆ selfDisplay()

template<typename TSpace, DGtal::uint32_t p, typename TRawValue = DGtal::int64_t>
class DGtal::ExactPredicateLpSeparableMetric< TSpace, p, TRawValue >