31 #if defined(QuickHullKernels_RECURSES)
32 #error Recursive header files inclusion detected in QuickHullKernels.h
33 #else // defined(QuickHullKernels_RECURSES)
35 #define QuickHullKernels_RECURSES
37 #if !defined QuickHullKernels_h
39 #define QuickHullKernels_h
47 #include "DGtal/base/Common.h"
48 #include "DGtal/kernel/CInteger.h"
49 #include "DGtal/kernel/NumberTraits.h"
50 #include "DGtal/kernel/PointVector.h"
51 #include "DGtal/kernel/IntegerConverter.h"
52 #include "DGtal/math/linalg/SimpleMatrix.h"
65 template <
typename Po
int >
68 if ( points.empty() )
return Point::zero;
69 Point l = points[ 0 ];
71 for (
const auto& p : points ) {
75 return Point( ( l + u ) / 2 );
106 template <
typename OutputValue,
107 typename ForwardIterator,
108 typename ConversionFct >
109 void transform( std::vector< OutputValue >& output_values,
110 std::vector< std::size_t >& input2output,
111 std::vector< std::size_t >& output2input,
112 ForwardIterator itb, ForwardIterator ite,
113 const ConversionFct& F,
114 bool remove_duplicates )
116 typedef std::size_t
Size;
117 std::vector< OutputValue > input;
118 while ( itb != ite ) {
119 const auto ip = *itb++;
120 input.push_back( F( ip ) );
122 if ( ! remove_duplicates ) {
123 output_values.swap( input );
124 input2output.resize( input.size() );
125 output2input.resize( input.size() );
126 for (
Size i = 0; i < input.size(); ++i )
127 input2output[ i ] = output2input[ i ] = i;
130 output_values.clear();
131 std::vector< std::size_t > i2c_sort( input.size() );
132 input2output.resize( input.size() );
133 for (
Size i = 0; i < input.size(); i++ ) i2c_sort[ i ] = i;
135 std::sort( i2c_sort.begin(), i2c_sort.end(),
136 [&input] (
Size i,
Size j ) { return input[ i ] < input[ j ]; } );
137 output_values.resize( input.size() );
138 output_values[ 0 ] = input[ i2c_sort[ 0 ] ];
139 input2output[ i2c_sort[ 0 ] ] = 0;
141 for (
Size i = 1; i < input.size(); i++ ) {
142 if ( input[ i2c_sort[ i-1 ] ] != input[ i2c_sort[ i ] ] )
143 output_values[ ++j ] = input[ i2c_sort[ i ] ];
144 input2output[ i2c_sort[ i ] ] = j;
146 output_values.resize( j+1 );
147 output2input.resize( output_values.size() );
148 for (
Size i = 0; i < input2output.size(); i++ )
149 output2input[ input2output[ i ] ] = i;
208 :
N( aN ), c( aC ) {}
230 compute(
const std::vector< CoordinatePoint >& vpoints,
234 HalfSpace hs =
compute( vpoints, simplex );
240 if ( nu > hs.c ) { hs.N = -hs.N; hs.c = -hs.c; }
257 compute(
const std::vector< CoordinatePoint >& vpoints,
266 A.setComponent( i-1, j,
268 - vpoints[ simplex[ 0 ] ][ j ] ) );
273 return HalfSpace { N, N.
dot( ip ) };
300 return H1.N.dot( H2.N );
311 bool equal(
const HalfSpace& H1,
const HalfSpace& H2 )
const
313 return H1.c == H2.c && H1.N == H2.N;
341 {
return height(
H, p ) >= 0; }
347 {
return height(
H, p ) == 0; }
453 template <
typename InputPo
int>
454 void makeInput( std::vector< CoordinatePoint >& processed_points,
456 const std::vector< InputPoint >& input_points,
457 bool remove_duplicates )
467 input_points.cbegin(), input_points.cend(),
468 F, remove_duplicates );
473 template <
typename OutputPo
int>
588 template <
typename InputPo
int>
589 void makeInput( std::vector< CoordinatePoint >& processed_points,
591 const std::vector< InputPoint >& input_points,
592 bool remove_duplicates )
607 input_points.cbegin(), input_points.cend(),
608 F, remove_duplicates );
613 template <
typename OutputPo
int>
699 : precision( aPrecision ) {}
747 template <
typename InputPo
int>
748 void makeInput( std::vector< CoordinatePoint >& processed_points,
750 const std::vector< InputPoint >& input_points,
751 bool remove_duplicates )
761 input_points.cbegin(), input_points.cend(),
762 F, remove_duplicates );
781 template <
typename OutputPo
int>
785 out_p[ k ] = ( (
double) p[ k ] ) /
precision;
871 : precision( aPrecision ) {}
923 template <
typename InputPo
int>
924 void makeInput( std::vector< CoordinatePoint >& processed_points,
926 const std::vector< InputPoint >& input_points,
927 bool remove_duplicates )
943 input_points.cbegin(), input_points.cend(),
944 F, remove_duplicates );
966 template <
typename OutputPo
int>
970 out_p[ k ] = ( (
double) p[ k ] ) /
precision;
979 #endif // !defined QuickHullKernels_h
981 #undef QuickHullKernels_RECURSES
982 #endif // else defined(QuickHullKernels_RECURSES)
CoordinateInteger CoordinateScalar
Aim: a geometric kernel to compute the Delaunay triangulation of digital points with integer-only ari...
static Self zero
Static const for zero PointVector.
Aim: a geometric kernel to compute the convex hull of digital points with integer-only arithmetic.
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
void makeInput(std::vector< CoordinatePoint > &processed_points, IndexRange &input2comp, IndexRange &comp2input, const std::vector< InputPoint > &input_points, bool remove_duplicates)
InternalScalar c
the intercept
bool equal(const HalfSpace &H1, const HalfSpace &H2) const
const InternalVector & internalNormal() const
Point center(const std::vector< Point > &points)
CoordinateVector normal(const HalfSpace &H) const
double precision
The precision as the common denominator for all rational points.
ConvexHullCommonKernel< dim+1, TCoordinateInteger, TInternalInteger > Base
InternalVector N
the normal vector
DGtal::PointVector< dim, InternalInteger > InternalVector
void convertPointTo(const CoordinatePoint &p, OutputPoint &out_p) const
Aim: a geometric kernel to compute the Delaunay triangulation of a range of floating points with inte...
DGtal::uint32_t Dimension
void makeInput(std::vector< CoordinatePoint > &processed_points, IndexRange &input2comp, IndexRange &comp2input, const std::vector< InputPoint > &input_points, bool remove_duplicates)
DGtal::PointVector< dim, CoordinateInteger > CoordinateVector
bool hasInfiniteFacets() const
InternalScalar height(const HalfSpace &H, const CoordinatePoint &p) const
double precision
The precision as the common denominator for all rational points.
InternalInteger InternalScalar
bool hasInfiniteFacets() const
unsigned int dim(const Vector &z)
std::vector< Index > IndexRange
ConvexHullIntegralKernel()=default
Default constructor.
bool isHalfSpaceFacetInfinite(const HalfSpace &hs) const
HalfEdgeDataStructure::Size Size
bool above(const HalfSpace &H, const CoordinatePoint &p) const
CoordinateInteger CoordinateScalar
ConvexHullRationalKernel(double aPrecision=1024.)
HalfSpace(const InternalVector &aN, const InternalScalar aC)
DGtal::PointVector< dim, InternalInteger > InternalPoint
DGtal::PointVector< dim, CoordinateInteger > CoordinatePoint
BOOST_CONCEPT_ASSERT((concepts::CInteger< TCoordinateInteger >))
InternalScalar dot(const HalfSpace &H1, const HalfSpace &H2) const
Aim: implements basic MxN Matrix services (M,N>=1).
IntegerConverter< dim, CoordinateInteger > Outer
Converter to outer coordinate integers or lattice points / vector.
void makeInput(std::vector< CoordinatePoint > &processed_points, IndexRange &input2comp, IndexRange &comp2input, const std::vector< InputPoint > &input_points, bool remove_duplicates)
Aim: the common part of all geometric kernels for computing the convex hull or Delaunay triangulation...
IntegerConverter< dim, InternalInteger > Inner
Converter to inner internal integers or lattice points / vector.
ConvexHullCommonKernel< dim+1, TCoordinateInteger, TInternalInteger > Base
Aim: a geometric kernel to compute the convex hull of floating points with integer-only arithmetic....
bool aboveOrOn(const HalfSpace &H, const CoordinatePoint &p) const
DGtal is the top-level namespace which contains all DGtal functions and types.
std::vector< Index > IndexRange
bool hasInfiniteFacets() const
static Integer cast(Integer i)
CoordinateInteger CoordinateScalar
TInternalInteger InternalInteger
HalfSpace compute(const std::vector< CoordinatePoint > &vpoints, const CombinatorialPlaneSimplex &simplex, Index idx_below)
std::array< Index, dim > CombinatorialPlaneSimplex
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)
CoordinateScalar intercept(const HalfSpace &H) const
HalfSpace compute(const std::vector< CoordinatePoint > &vpoints, const CombinatorialPlaneSimplex &simplex)
InternalScalar internalIntercept() const
bool on(const HalfSpace &H, const CoordinatePoint &p) const
std::vector< Index > IndexRange
void convertPointTo(const CoordinatePoint &p, OutputPoint &out_p) const
ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger > Base
void makeInput(std::vector< CoordinatePoint > &processed_points, IndexRange &input2comp, IndexRange &comp2input, const std::vector< InputPoint > &input_points, bool remove_duplicates)
DelaunayIntegralKernel()=default
Default constructor.
bool isHalfSpaceFacetInfinite(const HalfSpace &hs) const
ConvexHullCommonKernel< dim, TCoordinateInteger, TInternalInteger > Base
auto dot(const PointVector< dim, OtherComponent, OtherStorage > &v) const -> decltype(DGtal::dotProduct(*this, v))
Dot product with a PointVector.
void convertPointTo(const CoordinatePoint &p, OutputPoint &out_p) const
Aim: Implements basic operations that will be used in Point and Vector classes.
TCoordinateInteger CoordinateInteger
----------— INTEGER/POINT CONVERSION SERVICES -----------------—
bool isHalfSpaceFacetInfinite(const HalfSpace &hs) const
ConvexHullCommonKernel()=default
Default constructor.
bool hasInfiniteFacets() const
boost::int64_t int64_t
signed 94-bit integer.
std::vector< Index > IndexRange
InternalScalar volume(const HalfSpace &H, const CoordinatePoint &p) const
std::vector< Index > IndexRange
void convertPointTo(const CoordinatePoint &p, OutputPoint &out_p) const
static const Dimension dimension
DelaunayRationalKernel(double aPrecision=1024.)
bool isHalfSpaceFacetInfinite(const HalfSpace &hs) const