Aim: the common part of all geometric kernels for computing the convex hull or Delaunay triangulation of a range of points. More...

#include <DGtal/geometry/tools/QuickHullKernels.h>

Inheritance diagram for DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >:

[legend]

Data Structures
class	HalfSpace

Public Types
typedef TCoordinateInteger	CoordinateInteger
typedef TInternalInteger	InternalInteger
typedef CoordinateInteger	CoordinateScalar
typedef InternalInteger	InternalScalar
typedef DGtal::PointVector< dim, CoordinateInteger >	CoordinatePoint
typedef DGtal::PointVector< dim, CoordinateInteger >	CoordinateVector
typedef DGtal::PointVector< dim, InternalInteger >	InternalPoint
typedef DGtal::PointVector< dim, InternalInteger >	InternalVector
typedef std::size_t	Size
typedef Size	Index
typedef std::vector< Index >	IndexRange
typedef std::array< Index, dim >	CombinatorialPlaneSimplex
typedef ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >	Self
typedef ConvexHullCommonKernel< dim-1, TCoordinateInteger, TInternalInteger >	LowerSelf
typedef IntegerConverter< dim, CoordinateInteger >	Outer
	Converter to outer coordinate integers or lattice points / vector.
typedef IntegerConverter< dim, InternalInteger >	Inner
	Converter to inner internal integers or lattice points / vector.

Public Member Functions
	BOOST_CONCEPT_ASSERT ((concepts::CInteger< TCoordinateInteger >))
	BOOST_CONCEPT_ASSERT ((concepts::CInteger< TInternalInteger >))
	ConvexHullCommonKernel ()=default
	Default constructor.
HalfSpace	compute (const std::vector< CoordinatePoint > &vpoints, const CombinatorialPlaneSimplex &simplex, Index idx_below)
HalfSpace	compute (const std::vector< CoordinatePoint > &vpoints, const CombinatorialPlaneSimplex &simplex)
CoordinateVector	normal (const HalfSpace &H) const
CoordinateScalar	intercept (const HalfSpace &H) const
InternalScalar	dot (const HalfSpace &H1, const HalfSpace &H2) const
bool	equal (const HalfSpace &H1, const HalfSpace &H2) const
InternalScalar	height (const HalfSpace &H, const CoordinatePoint &p) const
InternalScalar	volume (const HalfSpace &H, const CoordinatePoint &p) const
bool	above (const HalfSpace &H, const CoordinatePoint &p) const
bool	aboveOrOn (const HalfSpace &H, const CoordinatePoint &p) const
bool	on (const HalfSpace &H, const CoordinatePoint &p) const

Static Public Attributes
static const Dimension	dimension = dim

Detailed Description

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>
struct DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >

Aim: the common part of all geometric kernels for computing the convex hull or Delaunay triangulation of a range of points.

Description of template class 'ConvexHullCommonKernel'

Template Parameters

dim	the dimension of the space that is used for computing the convex hull (either the same as input points for convex hull, or one more than input points for Delaunay triangulation)
TCoordinateInteger	the integer type that represents coordinates of lattice points, a model of concepts::CInteger.
TInternalInteger	the integer type that is used for internal computations of above/below plane tests, a model of concepts::CInteger. Must be at least as precise as TCoordinateInteger.

Definition at line 180 of file QuickHullKernels.h.

Member Typedef Documentation

◆ CombinatorialPlaneSimplex

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef std::array< Index, dim > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::CombinatorialPlaneSimplex

Definition at line 197 of file QuickHullKernels.h.

◆ CoordinateInteger

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef TCoordinateInteger DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::CoordinateInteger

Definition at line 183 of file QuickHullKernels.h.

◆ CoordinatePoint

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef DGtal::PointVector< dim, CoordinateInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::CoordinatePoint

Definition at line 190 of file QuickHullKernels.h.

◆ CoordinateScalar

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef CoordinateInteger DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::CoordinateScalar

Definition at line 186 of file QuickHullKernels.h.

◆ CoordinateVector

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef DGtal::PointVector< dim, CoordinateInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::CoordinateVector

Definition at line 191 of file QuickHullKernels.h.

◆ Index

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef Size DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::Index

Definition at line 195 of file QuickHullKernels.h.

◆ IndexRange

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef std::vector< Index > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::IndexRange

Definition at line 196 of file QuickHullKernels.h.

◆ Inner

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef IntegerConverter< dim, InternalInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::Inner

Converter to inner internal integers or lattice points / vector.

Definition at line 205 of file QuickHullKernels.h.

◆ InternalInteger

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef TInternalInteger DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::InternalInteger

Definition at line 184 of file QuickHullKernels.h.

◆ InternalPoint

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef DGtal::PointVector< dim, InternalInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::InternalPoint

Definition at line 192 of file QuickHullKernels.h.

◆ InternalScalar

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef InternalInteger DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::InternalScalar

Definition at line 187 of file QuickHullKernels.h.

◆ InternalVector

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef DGtal::PointVector< dim, InternalInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::InternalVector

Definition at line 193 of file QuickHullKernels.h.

◆ LowerSelf

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef ConvexHullCommonKernel< dim-1, TCoordinateInteger, TInternalInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::LowerSelf

Definition at line 201 of file QuickHullKernels.h.

◆ Outer

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef IntegerConverter< dim, CoordinateInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::Outer

Converter to outer coordinate integers or lattice points / vector.

Definition at line 203 of file QuickHullKernels.h.

◆ Self

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::Self

Definition at line 200 of file QuickHullKernels.h.

◆ Size

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef std::size_t DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::Size

Definition at line 194 of file QuickHullKernels.h.

Constructor & Destructor Documentation

◆ ConvexHullCommonKernel()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::ConvexHullCommonKernel ( )

default

Default constructor.

Member Function Documentation

◆ above()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

bool DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::above	(	const HalfSpace &	H,
		const CoordinatePoint &	p ) const

inline

Parameters

H	the half-space
p	any point

Returns: 'true' iff p is strictly above this plane (so in direction N ).

Definition at line 329 of file QuickHullKernels.h.

330 { return height( H, p ) > 0; }

DGtal::ConvexHullCommonKernel

Aim: the common part of all geometric kernels for computing the convex hull or Delaunay triangulation...

Definition QuickHullKernels.h:180

DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::height

InternalScalar height(const HalfSpace &H, const CoordinatePoint &p) const

Definition QuickHullKernels.h:314

◆ aboveOrOn()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

bool DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::aboveOrOn	(	const HalfSpace &	H,
		const CoordinatePoint &	p ) const

inline

Parameters

H	the half-space
p	any point

Returns: 'true' iff p is above or lies on this plane (so in direction N ).

Definition at line 335 of file QuickHullKernels.h.

336 { return height( H, p ) >= 0; }

◆ BOOST_CONCEPT_ASSERT() [1/2]

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< TCoordinateInteger >) )

◆ BOOST_CONCEPT_ASSERT() [2/2]

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< TInternalInteger >) )

◆ compute() [1/2]

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

HalfSpace DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::compute	(	const std::vector< CoordinatePoint > &	vpoints,
		const CombinatorialPlaneSimplex &	simplex )

inline

Computes an halfspace from dimension points specified by simplex with vertices in a range vpoints of Point. Orientation is induced by the order of the points. If the simplex is degenerated, the half-space is invalid and has null normal.

Parameters

[in]	vpoints	a range of points over which the simplex is defined.
[in]	simplex	a range of dimension indices of points defining an hyperplane.

Returns: the corresponding halfspace (has null normal vector if simplex was not full dimensional)

Definition at line 261 of file QuickHullKernels.h.

    {
      // More robust method than SimpleMatrix::cofactor and faster for higher dimension.
      InternalVector N; // null normal
      const InternalPoint ip = Inner::cast( vpoints[ simplex[ 0 ] ] );
      functions::getOrthogonalVector( N, vpoints, simplex );
      return HalfSpace { N, N.dot( ip ) };
    }

◆ compute() [2/2]

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

HalfSpace DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::compute	(	const std::vector< CoordinatePoint > &	vpoints,
		const CombinatorialPlaneSimplex &	simplex,
		Index	idx_below )

inline

Computes an halfspace from dimension points specified by simplex with vertices in a range vpoints of Point. It is oriented such that the point of index idx_below is included in the half-space (i.e. below).

Parameters

[in]	vpoints	a range of points over which the simplex is defined.
[in]	simplex	a range of dimension indices of points defining an hyperplane.
[in]	idx_below	the index of a p-oint that is below the hyperplane.

Returns: the corresponding halfspace (has null normal vector if simplex was not full dimensional)

Definition at line 234 of file QuickHullKernels.h.

    {
      HalfSpace hs = compute( vpoints, simplex );
      if ( hs.N != InternalVector::zero ) 
        {
          const InternalPoint  ip = Inner::cast( vpoints[ idx_below ] );
          const InternalScalar nu = hs.N.dot( ip );
          //const Scalar nu = hs.N.dot( vpoints[ idx_below ] );
          if ( nu > hs.c ) { hs.N = -hs.N; hs.c = -hs.c; }
        }
      return hs;
    }

Referenced by compute().

◆ dot()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

InternalScalar DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::dot	(	const HalfSpace &	H1,
		const HalfSpace &	H2 ) const

inline

Equivalent of the dot product of the normals of the half-spaces.

Parameters

H1	an half-space
H2	an half-space

Returns: a positive scalar if both half-spaces points to to the same hemisphere, a negative scalar if they point to opposite hemispheres, and zero if they are orthogonal.

Definition at line 293 of file QuickHullKernels.h.

    {
      return H1.N.dot( H2.N );
    }

◆ equal()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

bool DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::equal	(	const HalfSpace &	H1,
		const HalfSpace &	H2 ) const

inline

Parameters

H1	an half-space
H2	an half-space

Returns: 'true' if the half-spaces have the smae members.

Note: two half-spaces may be not equal but may represent the same set of points. For instance H1={{1,0},3} and H1={{2,0},6}.

Definition at line 306 of file QuickHullKernels.h.

    {
      return H1.c == H2.c && H1.N == H2.N;
    }

◆ height()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

InternalScalar DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::height	(	const HalfSpace &	H,
		const CoordinatePoint &	p ) const

inline

Parameters

H	the half-space
p	any point

Returns: the (signed) height of p wrt this plane.

Definition at line 314 of file QuickHullKernels.h.

315 { return H.N.dot( Inner::cast( p ) ) - H.c; }

Referenced by above(), aboveOrOn(), DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::HalfSpace::ConvexHullCommonKernel< dim, CoordinateInteger, InternalInteger >, and volume().

◆ intercept()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

CoordinateScalar DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::intercept ( const HalfSpace & H ) const

inline

Parameters

H	the half-space

Returns: the intercept of this facet.

Definition at line 280 of file QuickHullKernels.h.

    {
      return Outer::cast( H.c );
    }

◆ normal()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

CoordinateVector DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::normal ( const HalfSpace & H ) const

inline

Parameters

H	the half-space

Returns: the normal to this facet.

Definition at line 273 of file QuickHullKernels.h.

    {
      return Outer::cast( H.N );
    }

◆ on()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

bool DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::on	(	const HalfSpace &	H,
		const CoordinatePoint &	p ) const

inline

Parameters

H	the half-space
p	any point

Returns: 'true' iff p lies on this plane.

Definition at line 341 of file QuickHullKernels.h.

342 { return height( H, p ) == 0; }

◆ volume()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

InternalScalar DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::volume	(	const HalfSpace &	H,
		const CoordinatePoint &	p ) const

inline

Parameters

H	the half-space
p	any point

Returns: the volume of the vectors spanned by the simplex and this point.

Definition at line 320 of file QuickHullKernels.h.

    {
      InternalScalar v = height( H, p );
      return v < InternalScalar( 0 ) ? -v : v;
    }

Field Documentation

◆ dimension

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

const Dimension DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::dimension = dim

static

Definition at line 198 of file QuickHullKernels.h.

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

QuickHullKernels.h

Data Structures

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ CombinatorialPlaneSimplex

◆ CoordinateInteger

◆ CoordinatePoint

◆ CoordinateScalar

◆ CoordinateVector

◆ Index

◆ IndexRange

◆ Inner

◆ InternalInteger

◆ InternalPoint

◆ InternalScalar

◆ InternalVector

◆ LowerSelf

◆ Outer

◆ Self

◆ Size

Constructor & Destructor Documentation

◆ ConvexHullCommonKernel()

Member Function Documentation

◆ above()

◆ aboveOrOn()

◆ BOOST_CONCEPT_ASSERT() [1/2]

◆ BOOST_CONCEPT_ASSERT() [2/2]

◆ compute() [1/2]

◆ compute() [2/2]

◆ dot()

◆ equal()

◆ height()

◆ intercept()

◆ normal()

◆ on()

◆ volume()

Field Documentation

◆ dimension