DGtal  1.3.beta
Data Structures | Public Types | Public Member Functions | Static Public Attributes
DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger > Struct Template Reference

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, CoordinateIntegerCoordinatePoint
 
typedef DGtal::PointVector< dim, CoordinateIntegerCoordinateVector
 
typedef DGtal::PointVector< dim, InternalIntegerInternalPoint
 
typedef DGtal::PointVector< dim, InternalIntegerInternalVector
 
typedef std::size_t Size
 
typedef Size Index
 
typedef std::vector< IndexIndexRange
 
typedef std::array< Index, dimCombinatorialPlaneSimplex
 
typedef IntegerConverter< dim, CoordinateIntegerOuter
 Converter to outer coordinate integers or lattice points / vector. More...
 
typedef IntegerConverter< dim, InternalIntegerInner
 Converter to inner internal integers or lattice points / vector. More...
 

Public Member Functions

 BOOST_CONCEPT_ASSERT ((concepts::CInteger< TCoordinateInteger >))
 
 BOOST_CONCEPT_ASSERT ((concepts::CInteger< TInternalInteger >))
 
 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 = 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
dimthe 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)
TCoordinateIntegerthe integer type that represents coordinates of lattice points, a model of concepts::CInteger.
TInternalIntegerthe 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 178 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 195 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 181 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.

◆ 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 201 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 182 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.

◆ 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 199 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

◆ 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
Hthe half-space
pany point
Returns
'true' iff p is strictly above this plane (so in direction N ).

Definition at line 334 of file QuickHullKernels.h.

335  { 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 ( const HalfSpace H,
const CoordinatePoint p 
) const
inline
Parameters
Hthe half-space
pany point
Returns
'true' iff p is above or lies on this plane (so in direction N ).

Definition at line 340 of file QuickHullKernels.h.

341  { 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 degenrated, the half-space is invalid and has null normal.

Parameters
[in]vpointsa range of points over which the simplex is defined.
[in]simplexa 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.

259  {
261  Matrix A;
262  InternalVector N;
263  InternalScalar c;
264  for ( Dimension i = 1; i < dimension; i++ )
265  for ( Dimension j = 0; j < dimension; j++ )
266  A.setComponent( i-1, j,
267  Inner::cast( vpoints[ simplex[ i ] ][ j ]
268  - vpoints[ simplex[ 0 ] ][ j ] ) );
269  for ( Dimension j = 0; j < dimension; j++ )
270  N[ j ] = A.cofactor( dimension-1, j );
271  const InternalPoint ip = Inner::cast( vpoints[ simplex[ 0 ] ] );
272  // c = N.dot( vpoints[ simplex[ 0 ] ] );
273  return HalfSpace { N, N.dot( ip ) };
274  }

◆ 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]vpointsa range of points over which the simplex is defined.
[in]simplexa range of dimension indices of points defining an hyperplane.
[in]idx_belowthe 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.

233  {
234  HalfSpace hs = compute( vpoints, simplex );
235  if ( hs.N != InternalVector::zero )
236  {
237  const InternalPoint ip = Inner::cast( vpoints[ idx_below ] );
238  const InternalScalar nu = hs.N.dot( ip );
239  //const Scalar nu = hs.N.dot( vpoints[ idx_below ] );
240  if ( nu > hs.c ) { hs.N = -hs.N; hs.c = -hs.c; }
241  }
242  return hs;
243  }

Referenced by DGtal::ConvexHullCommonKernel< dim, DGtal::int64_t, DGtal::int64_t >::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
H1an half-space
H2an 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 298 of file QuickHullKernels.h.

299  {
300  return H1.N.dot( H2.N );
301  }

◆ 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
H1an half-space
H2an 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 311 of file QuickHullKernels.h.

312  {
313  return H1.c == H2.c && H1.N == H2.N;
314  }

◆ 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

◆ 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
Hthe half-space
Returns
the intercept of this facet.

Definition at line 285 of file QuickHullKernels.h.

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

◆ 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
Hthe half-space
Returns
the normal to this facet.

Definition at line 278 of file QuickHullKernels.h.

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

◆ 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
Hthe half-space
pany point
Returns
'true' iff p lies on this plane.

Definition at line 346 of file QuickHullKernels.h.

347  { 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
Hthe half-space
pany point
Returns
the volume of the vectors spanned by the simplex and this point.

Definition at line 325 of file QuickHullKernels.h.

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

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

The documentation for this struct was generated from the following file:
DGtal::PointVector< dim, InternalInteger >::zero
static Self zero
Static const for zero PointVector.
Definition: PointVector.h:1595
DGtal::ConvexHullCommonKernel::InternalVector
DGtal::PointVector< dim, InternalInteger > InternalVector
Definition: QuickHullKernels.h:191
DGtal::Dimension
DGtal::uint32_t Dimension
Definition: Common.h:137
DGtal::ConvexHullCommonKernel::height
InternalScalar height(const HalfSpace &H, const CoordinatePoint &p) const
Definition: QuickHullKernels.h:319
DGtal::ConvexHullCommonKernel::InternalScalar
InternalInteger InternalScalar
Definition: QuickHullKernels.h:185
DGtal::ConvexHullCommonKernel::InternalPoint
DGtal::PointVector< dim, InternalInteger > InternalPoint
Definition: QuickHullKernels.h:190
DGtal::SimpleMatrix
Aim: implements basic MxN Matrix services (M,N>=1).
Definition: SimpleMatrix.h:75
DGtal::IntegerConverter::cast
static Integer cast(Integer i)
Definition: IntegerConverter.h:123
DGtal::ConvexHullCommonKernel::compute
HalfSpace compute(const std::vector< CoordinatePoint > &vpoints, const CombinatorialPlaneSimplex &simplex, Index idx_below)
Definition: QuickHullKernels.h:230
DGtal::ConvexHullCommonKernel::dimension
static const Dimension dimension
Definition: QuickHullKernels.h:196
DGtal::ProbingMode::H
@ H