Aim: a geometric kernel to compute the Delaunay triangulation of a range of floating points with integer-only arithmetic. Floating points are approximated with rational points with fixed precision (a given number of bits), which are cast in a higher dimensional space and lifted onto the "norm" paraboloid, as classically done when computing a Delaunay triangulation from a convex hull. All remaining computations are exact, as long as there is no overflow. More...
#include <DGtal/geometry/tools/QuickHullKernels.h>
Public Member Functions | |
DelaunayRationalKernel (double aPrecision=1024.) | |
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 |
![]() | |
BOOST_CONCEPT_ASSERT ((concepts::CInteger< DGtal::int64_t >)) | |
BOOST_CONCEPT_ASSERT ((concepts::CInteger< DGtal::int64_t >)) | |
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 |
Data Fields | |
double | precision |
The precision as the common denominator for all rational points. | |
Static Public Attributes | |
static const Dimension | dimension |
![]() | |
static const Dimension | dimension |
Aim: a geometric kernel to compute the Delaunay triangulation of a range of floating points with integer-only arithmetic. Floating points are approximated with rational points with fixed precision (a given number of bits), which are cast in a higher dimensional space and lifted onto the "norm" paraboloid, as classically done when computing a Delaunay triangulation from a convex hull. All remaining computations are exact, as long as there is no overflow.
Description of template class 'DelaunayRationalKernel'
Each floating point input coordinate x
is converted to an integer through the following formula (Integer) round( x * precision )
, where precision
is the floating point value given at instanciation of the kernel.
Each output floating point coordinate is built from integer coordinates a
through the formula ( (double) a ) / precision
, where precision
is the floating point value given at instanciation of the kernel.
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. |
Definition at line 829 of file QuickHullKernels.h.
ConvexHullCommonKernel< dim+1, TCoordinateInteger, TInternalInteger > DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::Base |
Definition at line 832 of file QuickHullKernels.h.
std::array< Index, dim > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::CombinatorialPlaneSimplex |
Definition at line 195 of file QuickHullKernels.h.
DGtal::PointVector< dim, CoordinateInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::CoordinatePoint |
Definition at line 188 of file QuickHullKernels.h.
CoordinateInteger DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::CoordinateScalar |
Definition at line 184 of file QuickHullKernels.h.
DGtal::PointVector< dim, CoordinateInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::CoordinateVector |
Definition at line 189 of file QuickHullKernels.h.
Size DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::Index |
Definition at line 193 of file QuickHullKernels.h.
std::vector< Index > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::IndexRange |
Definition at line 194 of file QuickHullKernels.h.
DGtal::PointVector< dim, InternalInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::InternalPoint |
Definition at line 190 of file QuickHullKernels.h.
InternalInteger DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::InternalScalar |
Definition at line 185 of file QuickHullKernels.h.
DGtal::PointVector< dim, InternalInteger > DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::InternalVector |
Definition at line 191 of file QuickHullKernels.h.
std::size_t DGtal::ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger >::Size |
Definition at line 192 of file QuickHullKernels.h.
|
inline |
Constructor with specified precision
[in] | aPrecision | the chosen precision as the common denominator of all rationals (by defaut, 1024). |
Definition at line 869 of file QuickHullKernels.h.
|
inline |
H | the half-space |
p | any point |
Definition at line 333 of file QuickHullKernels.h.
|
inline |
H | the half-space |
p | any point |
Definition at line 339 of file QuickHullKernels.h.
|
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.
[in] | vpoints | a range of points over which the simplex is defined. |
[in] | simplex | a range of dimension indices of points defining an hyperplane. |
Definition at line 257 of file QuickHullKernels.h.
|
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).
[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. |
Definition at line 230 of file QuickHullKernels.h.
|
inline |
Converts an integral point (as represented internally for QuickHull computations) to its corresponding output point representation.
OutputPoint | a model of point such that processing type Point is convertible to it. |
[in] | p | an integral point (as represented internally for QuickHull computations) |
[out] | out_p | its corresponding output point representation. |
a
through the formula ( (double) a ) / / precision
, where precision
is the floating point value given at instanciation of the kernel. The last coordinate is not used since it was just related to the lifting of the point onto the "norm" paraboloid, as classically done when computing the Delaunay triangulation from a convex hull. Definition at line 966 of file QuickHullKernels.h.
References DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::dimension, and DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::precision.
|
inline |
Equivalent of the dot product of the normals of the half-spaces.
H1 | an half-space |
H2 | an half-space |
Definition at line 297 of file QuickHullKernels.h.
|
inline |
H1 | an half-space |
H2 | an half-space |
H1={{1,0},3}
and H1={{2,0},6}
. Definition at line 310 of file QuickHullKernels.h.
|
inline |
Definition at line 875 of file QuickHullKernels.h.
|
inline |
H | the half-space |
p | any point |
Definition at line 318 of file QuickHullKernels.h.
|
inline |
H | the half-space |
Definition at line 284 of file QuickHullKernels.h.
|
inline |
[in] | hs | an half-space corresponding to a facet. |
Definition at line 882 of file QuickHullKernels.h.
References DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::dimension.
|
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. This kernel transforms dim
-dimensional into dim+1
-dimensional points, where the last coordinate lies on a paraboloid. This is the classical way for computing a Delaunay triangulation as the convex hull of the points onto a paraboloid of higher dimension.
InputPoint | any model of point whose components are convertible to Scalar. |
[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. |
x
is converted to an integer through the following formula (Integer) round( x * / precision )
, where precision
is the floating point value given at instanciation of the kernel. A new coordinate is added so that the point is lifted onto the "norm" paraboloid. Definition at line 923 of file QuickHullKernels.h.
References DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::dimension, and DGtal::detail::transform().
|
inline |
H | the half-space |
Definition at line 277 of file QuickHullKernels.h.
|
inline |
H | the half-space |
p | any point |
Definition at line 345 of file QuickHullKernels.h.
|
inline |
H | the half-space |
p | any point |
Definition at line 324 of file QuickHullKernels.h.
|
static |
Definition at line 196 of file QuickHullKernels.h.
Referenced by DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::convertPointTo(), DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::isHalfSpaceFacetInfinite(), and DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::makeInput().
double DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::precision |
The precision as the common denominator for all rational points.
Definition at line 863 of file QuickHullKernels.h.
Referenced by DGtal::DelaunayRationalKernel< dim, TCoordinateInteger, TInternalInteger >::convertPointTo().