#include <VoronoiMap.h>

Collaboration diagram for DGtal::VoronoiMap< TSpace, TPointPredicate, p >:

Public Types
typedef TSpace	Space
typedef TPointPredicate	PointPredicate
typedef HyperRectDomain< Space >	Domain
typedef DGtal::int64_t	IntegerLong
typedef Space::Vector	Vector
typedef Space::Point	Point
typedef Space::Dimension	Dimension
typedef Space::Size	Size
typedef Space::Point::Coordinate	Abscissa
typedef SeparableMetricHelper < Point, IntegerLong, p >	SeparableMetric
typedef ImageContainerBySTLVector < Domain, Point >	OutputImage

Public Member Functions
	BOOST_CONCEPT_ASSERT ((CSpace< TSpace >))
	BOOST_CONCEPT_ASSERT ((CPointPredicate< TPointPredicate >))
	BOOST_STATIC_ASSERT ((boost::is_same< typename TSpace::Point, typename TPointPredicate::Point >::value))
	VoronoiMap (const Domain &aDomain, const PointPredicate &predicate)
	~VoronoiMap ()
OutputImage	compute ()

Protected Member Functions
	VoronoiMap ()

Private Member Functions
void	computeOtherSteps (OutputImage &output, const Dimension dim) const
void	computeOtherStep1D (OutputImage &output, const Point &row, const Size dim, std::vector< Point > &Sites) const

Private Attributes
SeparableMetric	myMetric
const Domain &	myDomain
const PointPredicate &	myPointPredicate
Point	myLowerBoundCopy
Point	myUpperBoundCopy
Point	myInfinity

Detailed Description

template<typename TSpace, typename TPointPredicate, DGtal::uint32_t p>
class DGtal::VoronoiMap< TSpace, TPointPredicate, p >

Aim: Implementation of the linear in time Voronoi map construction.

Description of template class 'VoronoiMap'

The algorithm uses a sperable process to construct partial Voronoi maps which has been described in:

Maurer, C., Qi, R., & Raghavan, V. (2003). A Linear Time Algorithm
 for Computing Exact Euclidean Distance Transforms of Binary Images in
 Arbitrary Dimensions. IEEE Trans. Pattern Analysis and Machine
 Intelligence, 25pp265-270.

and

 Coeurjolly, D. (2002). Algorithmique et géométrie discrète pour
 la caractérisation des courbes et des surfaces. PhD Thesis,
 Université Lumière Lyon 2.

Given a domain and a point predicate, the compute() method returns, for each point in the domain, the closest point for which the predicate if false. Following Computational Geometry terminoliogy, points for which the predicate is false are "sites" for the Voronoi map construction.

The metric is specified by the p template parameter which defines a l_p separable metric.

If a point is equi-distant to two sites (e.g. if the digital point belong to a Voronoi cell boundary in the Euclidean space), this Voronoi map construction will only keep one of them.

Hence, the result is given as a map (point from the domain, closest site) implemented using an ImageContainerBySTLVector whose value type is the type of Point of the predicate.

Template Parameters:

TSpace	type of Digital Space (model of CSpace).
TPointPredicate	point predicate returning true for points from which we compute the distance (model of CPointPredicate)
p	the static integer value to define the l_p metric.
IntegerLong	(optional) type used to represent exact distance value according to p (default: DGtal::uint64_t)

Definition at line 109 of file VoronoiMap.h.