DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger > Struct Template Reference

Aim: a geometric kernel to compute the convex hull of digital points with integer-only arithmetic. More...

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

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

Public Types
typedef ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >	Base
typedef DGtal::PointVector< dim, CoordinateInteger >	CoordinatePoint
typedef DGtal::PointVector< dim, CoordinateInteger >	CoordinateVector
typedef CoordinateInteger	CoordinateScalar
typedef DGtal::PointVector< dim, InternalInteger >	InternalPoint
typedef DGtal::PointVector< dim, InternalInteger >	InternalVector
typedef InternalInteger	InternalScalar
typedef std::size_t	Size
typedef Size	Index
typedef std::vector< Index >	IndexRange
typedef std::array< Index, dim >	CombinatorialPlaneSimplex
Public Types inherited from DGtal::ConvexHullCommonKernel< dim, DGtal::int64_t, DGtal::int64_t >
typedef DGtal::int64_t	CoordinateInteger
typedef DGtal::int64_t	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 IntegerConverter< dim, CoordinateInteger >	Outer
	Converter to outer coordinate integers or lattice points / vector. More...
typedef IntegerConverter< dim, InternalInteger >	Inner
	Converter to inner internal integers or lattice points / vector. More...

Public Member Functions
	ConvexHullIntegralKernel ()=default
	Default constructor. More...
bool	hasInfiniteFacets () const
bool	isHalfSpaceFacetInfinite (const HalfSpace &hs) const
template<typename InputPoint >
void	makeInput (std::vector< CoordinatePoint > &processed_points, IndexRange &input2comp, IndexRange &comp2input, const std::vector< InputPoint > &input_points, bool remove_duplicates)
template<typename OutputPoint >
void	convertPointTo (const CoordinatePoint &p, OutputPoint &out_p) const
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
Public Member Functions inherited from DGtal::ConvexHullCommonKernel< dim, DGtal::int64_t, DGtal::int64_t >
	BOOST_CONCEPT_ASSERT ((concepts::CInteger< DGtal::int64_t >))
	BOOST_CONCEPT_ASSERT ((concepts::CInteger< DGtal::int64_t >))
	ConvexHullCommonKernel ()=default
	Default constructor. More...
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
Static Public Attributes inherited from DGtal::ConvexHullCommonKernel< dim, DGtal::int64_t, DGtal::int64_t >
static const Dimension	dimension

Detailed Description

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

Aim: a geometric kernel to compute the convex hull of digital points with integer-only arithmetic.

Description of template class 'ConvexHullIntegralKernel'

See also

QuickHull algorithm in arbitrary dimension for convex hull and Delaunay cell complex computation

Template Parameters

dim	the dimension of the space of processed points.
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.

Examples

geometry/tools/checkLatticeBallQuickHull.cpp, geometry/tools/exampleLatticeBallQuickHull3D.cpp, and geometry/tools/exampleRationalBallQuickHull3D.cpp.

Definition at line 375 of file QuickHullKernels.h.

Member Typedef Documentation

Base

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

typedef ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger > DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >::Base

Definition at line 378 of file QuickHullKernels.h.

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 195 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 188 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 184 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 189 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 193 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 194 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 190 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 185 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 191 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 192 of file QuickHullKernels.h.

Constructor & Destructor Documentation

ConvexHullIntegralKernel()

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

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

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

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 333 of file QuickHullKernels.h.

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

aboveOrOn()

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

bool DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::aboveOrOn

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 339 of file QuickHullKernels.h.

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

compute() [1/2]

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

HalfSpace DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::compute

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 degenrated, 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 257 of file QuickHullKernels.h.

    {
      typedef DGtal::SimpleMatrix< InternalScalar, dimension, dimension > Matrix;
      Matrix A;
      InternalVector N;
      for ( Dimension i = 1; i < dimension; i++ )
        for ( Dimension j = 0; j < dimension; j++ )
          A.setComponent( i-1, j,
                          Inner::cast( vpoints[ simplex[ i ] ][ j ]
                                       - vpoints[ simplex[ 0 ] ][ j ] ) );
      for ( Dimension j = 0; j < dimension; j++ )
        N[ j ] = A.cofactor( dimension-1, j );
      const InternalPoint ip = Inner::cast( vpoints[ simplex[ 0 ] ] );
      // c = N.dot( vpoints[ simplex[ 0 ] ] );
      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

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 230 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;
    }

convertPointTo()

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

template<typename OutputPoint >

void DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >::convertPointTo ( const CoordinatePoint &  p, OutputPoint &  out_p  ) const

inline

Template Parameters

OutputPoint

a model of point such that processing type Point is convertible to it.

Definition at line 473 of file QuickHullKernels.h.

    {
      for ( Dimension k = 0; k < dimension; k++ )
        out_p[ k ] = static_cast<typename OutputPoint::Component>(p[ k ]);
    }

References DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >::dimension.

dot()

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

InternalScalar DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::dot

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 297 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

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 310 of file QuickHullKernels.h.

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

hasInfiniteFacets()

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

bool DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >::hasInfiniteFacets ( ) const

inline

Returns

'true' if a kernel may induce infinite facets. This is typically the case of a Delaunay computation kernel, which casts points in higher dimension.

Definition at line 414 of file QuickHullKernels.h.

    { return false; }

height()

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

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

inline

Parameters

H	the half-space
p	any point

Returns

the (signed) height of p wrt this plane.

Definition at line 318 of file QuickHullKernels.h.

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

intercept()

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

CoordinateScalar DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::intercept

inline

Parameters

H	the half-space

Returns

the intercept of this facet.

Definition at line 284 of file QuickHullKernels.h.

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

isHalfSpaceFacetInfinite()

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

bool DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >::isHalfSpaceFacetInfinite ( const HalfSpace &  hs ) const

inline

Parameters

[in]

hs

an half-space corresponding to a facet.

Returns

'true' if the facet associated to this half-space corresponds to an infinite facet.

Definition at line 421 of file QuickHullKernels.h.

    {
      (void) hs; // unused parameter
      return false;
    }

makeInput()

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

template<typename InputPoint >

void DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >::makeInput ( std::vector< CoordinatePoint > &  processed_points, IndexRange &  input2comp, IndexRange &  comp2input, const std::vector< InputPoint > &  input_points, bool  remove_duplicates  )

inline

Transforms a range input_points of input points to a range processed_points of points adapted to a processing by QuickHull convex hull algorithm. Keep the mapping information between input and processed points.

Template Parameters

InputPoint

any model of point whose components are convertible to Scalar.

Parameters

[out]	processed_points	the range of points prepared for a process by QuickHull.
[out]	input2comp	the surjective mapping between the input_points range and the processed_points range used for computation.
[out]	comp2input	the injective mapping between the processed_points range used for computation and the input_points range.
[in]	input_points	the range of input points.
[in]	remove_duplicates	when 'true', this method removes possible duplicates in input_points and processed_points may thus be of smaller size, otherwise, when 'false', it means that there are no duplicates in input_points.

Definition at line 453 of file QuickHullKernels.h.

    {
      const auto F = [&] ( InputPoint input ) -> CoordinatePoint
      {
        CoordinatePoint p;
        for ( Dimension i = 0; i < dimension; i++ )
          p[ i ] = CoordinateScalar( input[ i ] );
        return p;
      };
      DGtal::detail::transform( processed_points, input2comp, comp2input,
                                input_points.cbegin(), input_points.cend(),
                                F, remove_duplicates );
    }

References DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >::dimension, and DGtal::detail::transform().

normal()

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

CoordinateVector DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::normal

inline

Parameters

H	the half-space

Returns

the normal to this facet.

Definition at line 277 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

inline

Parameters

H	the half-space
p	any point

Returns

'true' iff p lies on this plane.

Definition at line 345 of file QuickHullKernels.h.

    { 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

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 324 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

static

Definition at line 196 of file QuickHullKernels.h.

Referenced by DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >::convertPointTo(), and DGtal::ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >::makeInput().

---

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

• QuickHullKernels.h