#include <SeparableMetricHelper.h>

Inheritance diagram for DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >:

Public Types
enum	Closest { FIRST = 0, SECOND = 1, BOTH = 2 }
typedef TInternalValue	InternalValue
typedef TPoint::Coordinate	Abscissa
typedef TPoint	Point

Public Member Functions
	BOOST_CONCEPT_ASSERT ((CBoundedInteger< Abscissa >))
	BOOST_CONCEPT_ASSERT ((CBoundedInteger< TInternalValue >))
double	getApproxValue (const InternalValue &aInternalValue) const
InternalValue	F (const Abscissa pos, const Abscissa ci, const InternalValue hi) const
InternalValue	reversedF (const Abscissa pos, const Abscissa ci, const InternalValue hi) const
InternalValue	power (const Abscissa pos) const
Abscissa	reversedSep (const Abscissa i, const InternalValue hi, const Abscissa j, const InternalValue hj) const
Abscissa	Sep (const Abscissa i, const InternalValue hi, const Abscissa j, const InternalValue hj) const
Closest	closest (const Point &origin, const Point &first, const Point &second) const
Abscissa	binarySearchHidden (const Abscissa &udim, const Abscissa &vdim, const InternalValue &nu, const InternalValue &nv, const Abscissa &lower, const Abscissa &upper) const
bool	hiddenBy (const Point &u, const Point &v, const Point &w, const Point &startingPoint, const Point &endPoint, const typename Point::UnsignedComponent dim) const

Static Public Attributes
static const DGtal::uint32_t	p = tp

Detailed Description

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>
struct DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >

Aim: Implements basic functions associated to metrics used by separable volumetric algorithms.

Description of template class 'SeparableMetricHelper'

Template Parameters:

TAbscissa	Type used to store the coordinaites of the Domain (model of CBoundedInteger).
TInternalValue	the type used to store the internal numbers for exact computations. More precisely, TInternalValueType must be able to represent numbers of type TAbscissa to the power tp (model of CBoundedInteger).
tp	the order p of the L_p metric.

Warning:: this code is node GMP compliant

Definition at line 75 of file SeparableMetricHelper.h.

Member Typedef Documentation

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

typedef TPoint::Coordinate DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::Abscissa

Definition at line 80 of file SeparableMetricHelper.h.

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

typedef TInternalValue DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::InternalValue

Definition at line 79 of file SeparableMetricHelper.h.

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

typedef TPoint DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::Point

Definition at line 81 of file SeparableMetricHelper.h.

Member Enumeration Documentation

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

enum DGtal::SeparableMetricHelper::Closest

Enumerator:

FIRST
SECOND
BOTH

Definition at line 189 of file SeparableMetricHelper.h.

{ FIRST=0, SECOND=1, BOTH=2};

Member Function Documentation

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

Abscissa DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::binarySearchHidden	(	const Abscissa &	udim,
		const Abscissa &	vdim,
		const InternalValue &	nu,
		const InternalValue &	nv,
		const Abscissa &	lower,
		const Abscissa &	upper
	)		const

inline

Perform a binary search on the interval [lower,upper] to detect the mid-point between u and v according to the l_p distance.

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 Voronoi boundary point coordinates along dimension dim.

Definition at line 241 of file SeparableMetricHelper.h.

Referenced by DGtal::SeparableMetricHelper< Point, IntegerLong, p >::binarySearchHidden(), and DGtal::SeparableMetricHelper< Point, IntegerLong, p >::hiddenBy().

    {   
      ASSERT(  (nu + (InternalValue) std::pow( (double)abs( udim - lower), (double) p)) <=
               (nv + (InternalValue) std::pow( (double)abs( vdim - lower), (double)p)));
      
      //Recurrence stop 
      if ( (upper - lower) <= NumberTraits<Abscissa>::ONE)
        return lower;
      
      Abscissa mid = (lower + upper)/2;
      InternalValue nuUpdated = nu + (InternalValue) std::pow( (double)abs( udim - mid ), (double)p);
      InternalValue nvUpdated = nv + (InternalValue) std::pow( (double)abs( vdim - mid ), (double)p);
      
      //Recursive call
      if ( nuUpdated < nvUpdated)
        return binarySearchHidden(udim,vdim,nu,nv,mid,upper);
      else
        return binarySearchHidden(udim,vdim,nu,nv,lower,mid);
      
    }

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::BOOST_CONCEPT_ASSERT ( (CBoundedInteger< Abscissa >) )

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::BOOST_CONCEPT_ASSERT ( (CBoundedInteger< TInternalValue >) )

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

Closest DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::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 203 of file SeparableMetricHelper.h.

    {
      InternalValue a=NumberTraits<InternalValue>::ZERO,
        b=NumberTraits<InternalValue>::ZERO;
      
      for(typename Point::Dimension i=0; i <  Point::dimension; i++)
        {
          a += power(abs (origin[i] - first[i]));
          b += power(abs (origin[i] - second[i]));
        }
      if (a<b)
        return FIRST;
      else
        if (a>b)
          return SECOND;
        else
          return BOTH;
    }

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

InternalValue DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::F	(	const Abscissa	pos,
		const Abscissa	ci,
		const InternalValue	hi
	)		const

inline

Returns the height at a point pos of a Lp-parabola with center ci and height hi.

Parameters:

pos	an abscissa.
ci	center of the Lp-parabola.
hi	height of the Lp-parabola.

Returns:: the height of the parabola (ci,hi) at pos.

Definition at line 118 of file SeparableMetricHelper.h.

    {
      return std::pow( abs(NumberTraits<Abscissa>::castToDouble(pos - ci)),
                       (double)p) + hi;
    }

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

double DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::getApproxValue ( const InternalValue & aInternalValue ) const

inline

Returns an approximation (double) of the InternalValues associated to the metric.

Parameters:

aInternalValue the internal value to convert

Returns:: the converted value.

Definition at line 102 of file SeparableMetricHelper.h.

    {
      return std::pow( NumberTraits<InternalValue>::castToDouble(aInternalValue),
                       (double) 1.0 / p);
    }

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

bool DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::hiddenBy	(	const Point &	u,
		const Point &	v,
		const Point &	w,
		const Point &	startingPoint,
		const Point &	endPoint,
		const typename Point::UnsignedComponent	dim
	)		const

inline

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

Precondition:: both voronoi cells associated with a and b must intersect the straight line.

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 (a,c) hides b.

Definition at line 285 of file SeparableMetricHelper.h.

    {
      
      //Interval bound for the binary search
      Abscissa lower = startingPoint[dim];
      Abscissa upper = endPoint[dim];
      
      //Partial norm computation
      // (sum_{i!=dim}  |u_i-v_i|^p
      InternalValue nu = NumberTraits<InternalValue>::ZERO;
      InternalValue nv = NumberTraits<InternalValue>::ZERO;
      InternalValue nw = NumberTraits<InternalValue>::ZERO;
      for(Dimension i  = 0 ; i < Point::dimension ; i++)
        if (i != dim)
          {
            nu += ( InternalValue ) std::pow ( (double)abs(u[i] - startingPoint[i] ) , (double)p);
            nv += ( InternalValue ) std::pow ( (double)abs(v[i] - startingPoint[i] ) , (double)p);
            nw += ( InternalValue ) std::pow ( (double)abs(w[i] - startingPoint[i] ) , (double)p);
          }
 
      //Intersection of voronoi boundary
     
      //Optimization if vw lies before starting
      if ((nv + (InternalValue) std::pow( (double)abs( v[dim] - lower), (double) p)) >
          (nw + (InternalValue) std::pow( (double)abs( w[dim] - lower), (double)p)))
        { //trace.endBlock();
          return true;
        }
      //Optimization if vw lies before starting   
      if ((nu + (InternalValue) std::pow( (double)abs( u[dim] - lower), (double) p)) >
          (nv + (InternalValue) std::pow( (double)abs( v[dim] - lower), (double)p)))
        { //trace.endBlock();
          return false;
        }
  
      //Binary search
      Abscissa uv = binarySearchHidden(u[dim],v[dim],nu,nv,lower,upper); 
      Abscissa vw = binarySearchHidden(v[dim],w[dim],nv,nw,lower,upper);
#ifdef DEBUG_VERBOSE
      trace.info() << "Midpoint (u,v) ="<< uv<< " Midpoint (v,w) ="<<vw<<std::endl;
#endif      
      //trace.endBlock();
      if ( uv > vw )
        return true;
      else
        return false;
      
    }

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

InternalValue DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::power ( const Abscissa pos ) const

inline

Returns the InternalValue value of order p for a given position. Basically, its computes pos^p.

Parameters:

pos	the value of type Abscissa

Returns:: the InternaValue value.

Definition at line 148 of file SeparableMetricHelper.h.

Referenced by DGtal::SeparableMetricHelper< Point, IntegerLong, p >::closest().

    {
      return ( InternalValue ) std::pow ( (double)pos, (double)p );
    }

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

InternalValue DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::reversedF	(	const Abscissa	pos,
		const Abscissa	ci,
		const InternalValue	hi
	)		const

inline

Returns the height at a point pos of a reversed Lp-parabola with center ci and height hi.

Parameters:

pos	an abscissa.
ci	center of the Lp-parabola.
hi	height of the Lp-parabola.

Returns:: the height of the reversed parabola (ci,hi) at pos.

Definition at line 134 of file SeparableMetricHelper.h.

    {
      return hi - std::pow( abs((double )pos - ci) , (double)p);
    }

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

Abscissa DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::reversedSep	(	const Abscissa	i,
		const InternalValue	hi,
		const Abscissa	j,
		const InternalValue	hj
	)		const

inline

Returns the abscissa of the intersection point between two reversed Lp-parabolas (ci,hi) and (cj,hj).

Parameters:

ci	center of the first Lp-parabola.
hi	height of the first Lp-parabola power p (hi = real height^p)
cj	center of the first Lp-parabola.
hj	height of the first Lp-parabola power p (hj = real height^p).

Returns:

Definition at line 165 of file SeparableMetricHelper.h.

    {
      ASSERT(false && "Not-Yet-Implemented");
    }

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

Abscissa DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::Sep	(	const Abscissa	i,
		const InternalValue	hi,
		const Abscissa	j,
		const InternalValue	hj
	)		const

inline

Returns the abscissa of the intersection point between two Lp-parabolas (ci,hi) and (cj,hj).

Parameters:

ci	center of the first Lp-parabola.
hi	height of the first Lp-parabola power p (hi = real height^p)
cj	center of the first Lp-parabola.
hj	height of the first Lp-parabola power p (hj = real height^p).

Returns:

Definition at line 182 of file SeparableMetricHelper.h.

    {
      ASSERT(false && "Not-Yet-Implemented");
    }

Field Documentation

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>

const DGtal::uint32_t DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >::p = tp

static

Static constants containing the power p of the Lp-metric.

Definition at line 91 of file SeparableMetricHelper.h.

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

SeparableMetricHelper.h

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp> struct DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >

Member Typedef Documentation

Member Enumeration Documentation

Member Function Documentation

Field Documentation

template<typename TPoint, typename TInternalValue, DGtal::uint32_t tp>
struct DGtal::SeparableMetricHelper< TPoint, TInternalValue, tp >