Aim: a geometric kernel to compute the convex hull of floating points with integer-only arithmetic. Floating points are approximated with rational points with fixed precision (a given number of bits). All remaining computations are exact, as long as there is no overflow.
More...
|
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 |
|
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 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...
|
|
|
| ConvexHullRationalKernel (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< 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 |
|
template<
Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>
struct DGtal::ConvexHullRationalKernel< dim, TCoordinateInteger, TInternalInteger >
Aim: a geometric kernel to compute the convex hull of floating points with integer-only arithmetic. Floating points are approximated with rational points with fixed precision (a given number of bits). All remaining computations are exact, as long as there is no overflow.
Description of template class 'ConvexHullRationalKernel'
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.
- 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/exampleRationalBallQuickHull3D.cpp.
Definition at line 658 of file QuickHullKernels.h.
template<
Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>
template<typename OutputPoint >
template<
Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>
template<typename InputPoint >
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. |
- Note
- 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.
Definition at line 748 of file QuickHullKernels.h.
752 {
754 {
758 return p;
759 };
761 input_points.cbegin(), input_points.cend(),
762 F, remove_duplicates );
763 }
void transform(std::vector< OutputValue > &output_values, std::vector< std::size_t > &input2output, std::vector< std::size_t > &output2input, ForwardIterator itb, ForwardIterator ite, const ConversionFct &F, bool remove_duplicates)
CoordinateInteger CoordinateScalar
DGtal::PointVector< dim, CoordinateInteger > CoordinatePoint
References DGtal::ConvexHullRationalKernel< dim, TCoordinateInteger, TInternalInteger >::dimension, and DGtal::detail::transform().