Aim: implements a model of CSeparableMetric for Chamfer and path based norms. More...

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

Data Structures
struct	LessOrEqThanAngular

struct	LessThanAngular

Public Types
typedef TSpace	Space
	Underlying Space.

typedef Space::Vector	Vector
	Type for vectors.

typedef Space::Point	Point
	Type for points.

typedef std::vector< Vector >	Directions
	Container for set of directions.

typedef Directions::const_iterator	ConstIterator

typedef double	Value
	Value type for embedded distance evaluation.

typedef Space::Integer	RawValue
	Value type for exact distance evaluation.

typedef Vector::Component	Abscissa
	Vector components type.

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

	BOOST_STATIC_ASSERT (TSpace::dimension==2)

	ChamferNorm2D (const unsigned int aN)

	ChamferNorm2D (const Directions &aDirectionSet, const Directions &aNormalDirectionSet, const Value norm=1.0)

	~ChamferNorm2D ()

ConstIterator	getCone (const Vector &aDirection, ConstIterator aBegin, ConstIterator aEnd) const

ConstIterator	getCone (const Vector &aDirection) const

Vector	getNormalFromCone (ConstIterator aCone) const

Vector	canonicalRay (const Vector &aRay) const

Value	operator() (const Point &P, const Point &Q) const

RawValue	rawDistance (const Point &P, const Point &Q) const

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

	ChamferNorm2D (const ChamferNorm2D &other)

ChamferNorm2D< Space > &	operator= (const ChamferNorm2D< Space > &other)

Abscissa	getLowerRayIntersection (const Vector &aP, const Vector &aQ, const Point &Lmin, const Point &Lmax, const Dimension aDimension) const

Abscissa	getUpperRayIntersection (const Vector &aP, const Vector &aQ, const Point &Lmin, const Point &Lmax, const Dimension aDimension) const

ConstIterator	shrinkPSubMask (ConstIterator aBegin, ConstIterator aEnd, const Point &aP, const Point &aQ, const Point &Lmin, const Point &Lmax, const Dimension aDimension, Point &midPoint, Point &nextMidPoint) const

ConstIterator	shrinkP (ConstIterator aBegin, ConstIterator aEnd, const Point &aP, const Point &aQ, const Point &Lmin, const Point &Lmax, const Dimension aDimension, Point &midPoint, Point &nextMidPoint) const

Abscissa	getLowerVoronoiEdgeAbscissa (const Point &u, const Point &v, const Point &startingPoint, const Point &endPoint, const Dimension dim) const

bool	hiddenBy (const Point &u, const Point &v, const Point &w, const Point &startingPoint, const Point &endPoint, const Dimension dim) const

ConstIterator	begin ()

ConstIterator	end ()

unsigned int	size () const

void	selfDisplay (std::ostream &out) const

bool	isValid () const

Protected Member Functions
	ChamferNorm2D ()

Private Member Functions
	BOOST_STATIC_CONSTANT (Abscissa, myInfinity=32562)
	Static constant.

Private Attributes
Directions	myDirections
	Mask container.

Directions	myNormals
	Normal to cone container.

LessThanAngular	myLessThanAngular
	Instance of comparator functor.

Value	myNorm
	Normalization factor.

Detailed Description

template<typename TSpace>
class DGtal::experimental::ChamferNorm2D< TSpace >

Aim: implements a model of CSeparableMetric for Chamfer and path based norms.

Description of template class 'ChamferNorm2D'

This is a proof-of-concept which implements a path-based norm (here chamfer mask) in a separable way in dimension 2. Hence, this metric can be used in all separable volumetric tools like DistanceTransformation or VoronoiMap.

The metric is constructed from a set of directions that defines a set of cones, and weights associated with each cone. Alternatively, to check the computational efficiency of the methods, user can specify a number of cones and a fake chamfer mask will be constructed.

Note that the mask must satisfy norm conditions with axis symmetric unit ball.

As discussed in [36] and in nD Volumetric Analysis using Separable Processes, we have the following properties:

distance between two points is in \( O(log(n))\)
hiddenBy predicate is in \( O(log^2(n))\)
closest predicate is in \( O(log(n))\)

Template Parameters

TSpace a model CSpace of dimension 2.

Definition at line 86 of file ChamferNorm2D.h.

Member Typedef Documentation

◆ Abscissa

template<typename TSpace >

Vector::Component DGtal::experimental::ChamferNorm2D< TSpace >::Abscissa

Vector components type.

Definition at line 112 of file ChamferNorm2D.h.

◆ ConstIterator

template<typename TSpace >

Directions::const_iterator DGtal::experimental::ChamferNorm2D< TSpace >::ConstIterator

Definition at line 104 of file ChamferNorm2D.h.

◆ Directions

template<typename TSpace >

std::vector< Vector > DGtal::experimental::ChamferNorm2D< TSpace >::Directions

Container for set of directions.

Definition at line 103 of file ChamferNorm2D.h.

◆ Point

template<typename TSpace >

Space::Point DGtal::experimental::ChamferNorm2D< TSpace >::Point

Type for points.

Definition at line 100 of file ChamferNorm2D.h.

◆ RawValue

template<typename TSpace >

Space::Integer DGtal::experimental::ChamferNorm2D< TSpace >::RawValue

Value type for exact distance evaluation.

Definition at line 109 of file ChamferNorm2D.h.

◆ Space

template<typename TSpace >

TSpace DGtal::experimental::ChamferNorm2D< TSpace >::Space

Underlying Space.

Definition at line 95 of file ChamferNorm2D.h.

◆ Value

template<typename TSpace >

double DGtal::experimental::ChamferNorm2D< TSpace >::Value

Value type for embedded distance evaluation.

Definition at line 107 of file ChamferNorm2D.h.

◆ Vector

template<typename TSpace >

Space::Vector DGtal::experimental::ChamferNorm2D< TSpace >::Vector

Type for vectors.

Definition at line 98 of file ChamferNorm2D.h.

Constructor & Destructor Documentation

◆ ChamferNorm2D() [1/4]

template<typename TSpace >

DGtal::experimental::ChamferNorm2D< TSpace >::ChamferNorm2D ( const unsigned int aN )

Constructor from a number N. Will generate a partial mask with aN directions (from Farey fractions). Weights are set to satisfy the norm condition using the 3-4-mask weights. Hence, increasing aN does not improve the metric. This constructor is just used to compute efficiency statistics when aN increases.

◆ ChamferNorm2D() [2/4]

template<typename TSpace >

DGtal::experimental::ChamferNorm2D< TSpace >::ChamferNorm2D	(	const Directions &	aDirectionSet,
		const Directions &	aNormalDirectionSet,
		const Value	norm = 1.0 )

Constructor from direction and noraml vector sets.

Parameters

	aDirectionSet	the set of vectors of the chamfer norm mask. This set should correspond to the vectors of the chamfer mask with positive abscissa. Internally, this set will be symmetrized w.r.t. y-axis to make it complete.
	aNormalDirectionSet	for each cone, the associated normal vector.
[in]	norm	the normalization factor associated with th mask (default is 1.0)

◆ ~ChamferNorm2D()

template<typename TSpace >

DGtal::experimental::ChamferNorm2D< TSpace >::~ChamferNorm2D ( )

Destructor.

◆ ChamferNorm2D() [3/4]

template<typename TSpace >

DGtal::experimental::ChamferNorm2D< TSpace >::ChamferNorm2D ( const ChamferNorm2D< TSpace > & other )

inline

Copy constructor.

Parameters

other the object to clone.

Definition at line 290 of file ChamferNorm2D.h.

      {
        this->myDirections = other.myDirections;
        this->myNormals = other.myNormals;
      }

References DGtal::experimental::ChamferNorm2D< TSpace >::myDirections, and DGtal::experimental::ChamferNorm2D< TSpace >::myNormals.

◆ ChamferNorm2D() [4/4]

template<typename TSpace >

DGtal::experimental::ChamferNorm2D< TSpace >::ChamferNorm2D ( )

protected

Constructor. Forbidden by default (protected to avoid g++ warnings).

Member Function Documentation

◆ begin()

template<typename TSpace >

ConstIterator DGtal::experimental::ChamferNorm2D< TSpace >::begin ( )

inline

Returns: the begin iterator to the mask direction set

Definition at line 466 of file ChamferNorm2D.h.

      {
        return myDirections.begin();
      }

References DGtal::experimental::ChamferNorm2D< TSpace >::myDirections.

Referenced by testChamferSimple().

◆ BOOST_CONCEPT_ASSERT()

template<typename TSpace >

DGtal::experimental::ChamferNorm2D< TSpace >::BOOST_CONCEPT_ASSERT ( (concepts::CSpace< TSpace >) )

◆ BOOST_STATIC_ASSERT()

template<typename TSpace >

DGtal::experimental::ChamferNorm2D< TSpace >::BOOST_STATIC_ASSERT ( TSpace::dimension = =2 )

◆ BOOST_STATIC_CONSTANT()

template<typename TSpace >

DGtal::experimental::ChamferNorm2D< TSpace >::BOOST_STATIC_CONSTANT	(	Abscissa	,
		myInfinity	= 32562 )

private

Static constant.

◆ canonicalRay()

template<typename TSpace >

Vector DGtal::experimental::ChamferNorm2D< TSpace >::canonicalRay ( const Vector & aRay ) const

Return the canonical ray for a given ray.

This method construct a vector in the first quadrant corresponding to aRay.

Returns: Vector |aRay[i]|

Referenced by testChamferSimple().

◆ closest()

template<typename TSpace >

DGtal::Closest DGtal::experimental::ChamferNorm2D< TSpace >::closest	(	const Point &	origin,
		const Point &	first,
		const Point &	second ) const

inline

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.

Definition at line 271 of file ChamferNorm2D.h.

      {
        Value a = this->operator()(origin,first),
          b = this->operator()(origin,second);
        if (a<b)
          return ClosestFIRST;
        else
          if (a>b)
            return ClosestSECOND;
          else
            return ClosestBOTH;
      }

References DGtal::ClosestBOTH, DGtal::ClosestFIRST, DGtal::ClosestSECOND, and DGtal::experimental::ChamferNorm2D< TSpace >::operator()().

◆ end()

template<typename TSpace >

ConstIterator DGtal::experimental::ChamferNorm2D< TSpace >::end ( )

inline

Returns: the end iterator to the mask direction set

Definition at line 474 of file ChamferNorm2D.h.

      {
        return myDirections.end();
      }

References DGtal::experimental::ChamferNorm2D< TSpace >::myDirections.

Referenced by testChamferSimple().

◆ getCone() [1/2]

template<typename TSpace >

ConstIterator DGtal::experimental::ChamferNorm2D< TSpace >::getCone ( const Vector & aDirection ) const

inline

Returns the cone associated to a direction (iterator it) in the whole mask.

The cone is given by [it, it+1):

(*it) <= aDirection < (*(it+1)) (For the angular comparator).

Precondition: We have *aBegin <= aDirection < *aEnd

Parameters

aDirection the direction to probe

Returns: a const iterator to the cone the direction belongs to.

Definition at line 213 of file ChamferNorm2D.h.

      {
        return getCone(aDirection, myDirections.begin(), myDirections.end());
      }

References DGtal::experimental::ChamferNorm2D< TSpace >::getCone(), and DGtal::experimental::ChamferNorm2D< TSpace >::myDirections.

◆ getCone() [2/2]

template<typename TSpace >

ConstIterator DGtal::experimental::ChamferNorm2D< TSpace >::getCone	(	const Vector &	aDirection,
		ConstIterator	aBegin,
		ConstIterator	aEnd ) const

Returns the cone associated to a direction (iterator it) in the range [aBegin, eEnd).

The cone is given by [it, it+1):

(*it) <= aDirection < (*(it+1)) (For the angular comparator).

Precondition: We have *aBegin <= aDirection < *aEnd

Parameters

[in]	aDirection	the direction to probe
[in]	aBegin	the begin of the range in which the search is performed.
[in]	aEnd	the end of the range in which the search is performed.

Returns: a ConstIterator to the cone the direction belongs to.

Referenced by DGtal::experimental::ChamferNorm2D< TSpace >::getCone(), testBasicMasks(), and testChamferSimple().

◆ getLowerRayIntersection()

template<typename TSpace >

Abscissa DGtal::experimental::ChamferNorm2D< TSpace >::getLowerRayIntersection	(	const Vector &	aP,
		const Vector &	aQ,
		const Point &	Lmin,
		const Point &	Lmax,
		const Dimension	aDimension ) const

Compute the intersection between (aP,aQ) and (Lmin, Lmax). More precisely, if we suppose that

Precondition: We have \( Lmin[aDimension] < Lmax[aDimension]\); We have \( Lmin[(aDimension+1)%2] == Lmax[(aDimension+1)%2]\); We have \( (aP,aQ) \cap (Lmin,Lmax) \)

this method returns the lower rounding abscissa of the rational intersection point.

Parameters

aP	first extremity point
aQ	second extremity point
Lmin	first extremity point of the L segment
Lmax	second extremity point of the L segment
aDimension	a dimension

Returns: the lowest rounding intersection point.

◆ getLowerVoronoiEdgeAbscissa()

template<typename TSpace >

Abscissa DGtal::experimental::ChamferNorm2D< TSpace >::getLowerVoronoiEdgeAbscissa	(	const Point &	u,
		const Point &	v,
		const Point &	startingPoint,
		const Point &	endPoint,
		const Dimension	dim ) const

Returns the lower abscissa of the Voronoi edge between u and v along the span (startingPoint,endPoint).

Parameters

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

Returns: the abscissa on (startingPoint,endPoint) of the Voronoi cell.

◆ getNormalFromCone()

template<typename TSpace >

Vector DGtal::experimental::ChamferNorm2D< TSpace >::getNormalFromCone ( ConstIterator aCone ) const

Parameters

aCone the input cone

Returns: the normal associated with a cone (aCone, aCone+1)

Referenced by testChamferSimple().

◆ getUpperRayIntersection()

template<typename TSpace >

Abscissa DGtal::experimental::ChamferNorm2D< TSpace >::getUpperRayIntersection	(	const Vector &	aP,
		const Vector &	aQ,
		const Point &	Lmin,
		const Point &	Lmax,
		const Dimension	aDimension ) const

Compute the intersection between (aP,aQ) and (Lmin, Lmax). More precisely, if we suppose that

Precondition: We have \( Lmin[aDimension] < Lmax[aDimension]\); We have \( Lmin[(aDimension+1)%2] == Lmax[(aDimension+1)%2]\); We have \( (aP,aQ) \cap (Lmin,Lmax) \)

this method returns the upper rounding abscissa of the rational intersection point.

Parameters

aP	first extremity point
aQ	second extremity point
Lmin	first extremity point of the L segment
Lmax	second extremity point of the L segment
aDimension	a dimension

Returns: the lowest rounding intersection point.

◆ hiddenBy()

template<typename TSpace >

bool DGtal::experimental::ChamferNorm2D< TSpace >::hiddenBy	(	const Point &	u,
		const Point &	v,
		const Point &	w,
		const Point &	startingPoint,
		const Point &	endPoint,
		const Dimension	dim ) const

The main hiddenBy predicate. (in \( O(log^2(n))\)).

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).

◆ isValid()

template<typename TSpace >

bool DGtal::experimental::ChamferNorm2D< TSpace >::isValid ( ) const

Checks the validity/consistency of the object.

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

◆ operator()()

template<typename TSpace >

Value DGtal::experimental::ChamferNorm2D< TSpace >::operator()	(	const Point &	P,
		const Point &	Q ) const

Returns the distance for the chamfer norm between P and Q.

Parameters

P	a point
Q	a point

Returns: the distance between P and Q.

Referenced by DGtal::experimental::ChamferNorm2D< TSpace >::closest().

◆ operator=()

template<typename TSpace >

ChamferNorm2D< Space > & DGtal::experimental::ChamferNorm2D< TSpace >::operator= ( const ChamferNorm2D< Space > & other )

inline

Assignment.

Parameters

other the object to copy.

Returns: a reference on 'this'.

Definition at line 302 of file ChamferNorm2D.h.

      {
        this->myDirections = other.myDirections;
        this->myNormals = other.myNormals;
        return *this;
      }

References DGtal::experimental::ChamferNorm2D< TSpace >::myDirections, and DGtal::experimental::ChamferNorm2D< TSpace >::myNormals.

◆ rawDistance()

template<typename TSpace >

RawValue DGtal::experimental::ChamferNorm2D< TSpace >::rawDistance	(	const Point &	P,
		const Point &	Q ) const

Returns the raw distance for the chamfer norm between P and Q. For chamfer norm, it corresponds to un-normalized distance value.

Parameters

P	a point
Q	a point

Returns: the distance between P and Q.

◆ selfDisplay()

template<typename TSpace >

void DGtal::experimental::ChamferNorm2D< TSpace >::selfDisplay ( std::ostream & out ) const

Writes/Displays the object on an output stream.

Parameters

out	the output stream where the object is written.

◆ shrinkP()

template<typename TSpace >

ConstIterator DGtal::experimental::ChamferNorm2D< TSpace >::shrinkP	(	ConstIterator	aBegin,
		ConstIterator	aEnd,
		const Point &	aP,
		const Point &	aQ,
		const Point &	Lmin,
		const Point &	Lmax,
		const Dimension	aDimension,
		Point &	midPoint,
		Point &	nextMidPoint ) const

This method returns the cone (ConstIterator, ConstIterator+1) at P which contains

Parameters

[in]	aBegin	begin iterator on the current set of directions at P
[in]	aEnd	end iterator on the current set of directions at P
[in]	aP	center of the ball we are shrinking
[in]	aQ	center of the second ball
[in]	Lmin	first extremity point of the L segment
[in]	Lmax	first extremity point of the L segment
[in]	aDimension	direction of the (Lmin,LMax segment)
[out]	midPoint	the point, on the segment, corresponding to the intersection of the the first cone direction and the segment
[out]	nextMidPoint	the point, on the segment, corresponding to the intersection of the second cone direction and the segment

Returns: the ConstIterator to the cone direction the Voronoi Edge belongs to

◆ shrinkPSubMask()

template<typename TSpace >

ConstIterator DGtal::experimental::ChamferNorm2D< TSpace >::shrinkPSubMask	(	ConstIterator	aBegin,
		ConstIterator	aEnd,
		const Point &	aP,
		const Point &	aQ,
		const Point &	Lmin,
		const Point &	Lmax,
		const Dimension	aDimension,
		Point &	midPoint,
		Point &	nextMidPoint ) const

Considering a vertical configuration (aDimension == 1, P[!dimension]<= Lmin[!dimension]), This method returns the cone (ConstIterator, ConstIterator+1) at P which contains the Voronoi Edge of P and Q.

Precondition: We have aP[aDimension] != aQ[aDimension (no alignement)

This method runs in O(log^2(n)), n being the number of directions in the mask.

Parameters

[in]	aBegin	begin iterator on the current set of directions at P
[in]	aEnd	end iterator on the current set of directions at P
[in]	aP	center of the ball we are shrinking
[in]	aQ	center of the second ball
[in]	Lmin	first extremity point of the L segment
[in]	Lmax	first extremity point of the L segment
[in]	aDimension	direction of the (Lmin,LMax segment)
[out]	midPoint	the point, on the segment, corresponding to the intersection of the the first cone direction and the segment
[out]	nextMidPoint	the point, on the segment, corresponding to the intersection of the second cone direction and the segment

Returns: the ConstIterator to the cone direction the Voronoi Edge belongs to

◆ size()

template<typename TSpace >

unsigned int DGtal::experimental::ChamferNorm2D< TSpace >::size ( ) const

inline

Returns: the mask size

Definition at line 483 of file ChamferNorm2D.h.

      {
        return myDirections.size();
      }

References DGtal::experimental::ChamferNorm2D< TSpace >::myDirections.

Field Documentation

◆ myDirections

template<typename TSpace >

Directions DGtal::experimental::ChamferNorm2D< TSpace >::myDirections

private

Mask container.

Definition at line 515 of file ChamferNorm2D.h.

Referenced by DGtal::experimental::ChamferNorm2D< TSpace >::begin(), DGtal::experimental::ChamferNorm2D< TSpace >::ChamferNorm2D(), DGtal::experimental::ChamferNorm2D< TSpace >::end(), DGtal::experimental::ChamferNorm2D< TSpace >::getCone(), DGtal::experimental::ChamferNorm2D< TSpace >::operator=(), and DGtal::experimental::ChamferNorm2D< TSpace >::size().

◆ myLessThanAngular

template<typename TSpace >

LessThanAngular DGtal::experimental::ChamferNorm2D< TSpace >::myLessThanAngular

private

Instance of comparator functor.

Definition at line 521 of file ChamferNorm2D.h.

◆ myNorm

template<typename TSpace >

Value DGtal::experimental::ChamferNorm2D< TSpace >::myNorm

private

Normalization factor.

Definition at line 527 of file ChamferNorm2D.h.

◆ myNormals

template<typename TSpace >

Directions DGtal::experimental::ChamferNorm2D< TSpace >::myNormals

private

Normal to cone container.

Definition at line 518 of file ChamferNorm2D.h.

Referenced by DGtal::experimental::ChamferNorm2D< TSpace >::ChamferNorm2D(), and DGtal::experimental::ChamferNorm2D< TSpace >::operator=().

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

ChamferNorm2D.h

Data Structures

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Abscissa

◆ ConstIterator

◆ Directions

◆ Point

◆ RawValue

◆ Space

◆ Value

◆ Vector

Constructor & Destructor Documentation

◆ ChamferNorm2D() [1/4]

◆ ChamferNorm2D() [2/4]

◆ ~ChamferNorm2D()

◆ ChamferNorm2D() [3/4]

◆ ChamferNorm2D() [4/4]

Member Function Documentation

◆ begin()

◆ BOOST_CONCEPT_ASSERT()

◆ BOOST_STATIC_ASSERT()

◆ BOOST_STATIC_CONSTANT()

◆ canonicalRay()

◆ closest()

◆ end()

◆ getCone() [1/2]

◆ getCone() [2/2]

◆ getLowerRayIntersection()

◆ getLowerVoronoiEdgeAbscissa()

◆ getNormalFromCone()

◆ getUpperRayIntersection()

◆ hiddenBy()

◆ isValid()

◆ operator()()

◆ operator=()

◆ rawDistance()

◆ selfDisplay()

◆ shrinkP()

◆ shrinkPSubMask()

◆ size()

Field Documentation

◆ myDirections

◆ myLessThanAngular

◆ myNorm

◆ myNormals