DGtal  0.9.3beta
Data Structures | Public Types | Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes
DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar > Class Template Reference

#include <DGtal/geometry/surfaces/ChordNaivePlaneComputer.h>

Inheritance diagram for DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >:
[legend]
Collaboration diagram for DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >:
[legend]

Data Structures

struct  State
 

Public Types

typedef TSpace Space
 
typedef TInputPoint InputPoint
 
typedef TInternalScalar InternalScalar
 
typedef InputPoint InputVector
 
typedef InputVector::Component Component
 
typedef InputPoint::Coordinate Coordinate
 
typedef PointVector< 3, InternalScalarInternalVector
 
typedef std::set< InputPointInputPointSet
 
typedef InputPointSet::size_type Size
 
typedef InputPointSet::const_iterator ConstIterator
 
typedef InputPointSet::iterator Iterator
 
typedef Space::Point Point
 
typedef ParallelStrip< Space, true, true > Primitive
 
typedef InputPointSet::const_iterator const_iterator
 
typedef InputPointSet::const_pointer const_pointer
 
typedef InputPointSet::const_reference const_reference
 
typedef InputPointSet::value_type value_type
 
typedef InputPointSet::difference_type difference_type
 
typedef InputPointSet::size_type size_type
 

Public Member Functions

 ~ChordNaivePlaneComputer ()
 
 ChordNaivePlaneComputer ()
 
 ChordNaivePlaneComputer (const ChordNaivePlaneComputer &other)
 
ChordNaivePlaneComputeroperator= (const ChordNaivePlaneComputer &other)
 
void clear ()
 
void init (Dimension axis, InternalScalar widthNumerator=NumberTraits< InternalScalar >::ONE, InternalScalar widthDenominator=NumberTraits< InternalScalar >::ONE)
 
Size size () const
 
bool empty () const
 
ConstIterator begin () const
 
ConstIterator end () const
 
Size max_size () const
 
Size maxSize () const
 
bool operator() (const Point &p) const
 
bool extendAsIs (const InputPoint &p)
 
bool extend (const InputPoint &p)
 
bool isExtendable (const InputPoint &p) const
 
template<typename TInputIterator >
bool extend (TInputIterator itB, TInputIterator itE)
 
template<typename TInputIterator >
bool isExtendable (TInputIterator itB, TInputIterator itE) const
 
template<typename TInputIterator >
bool satisfies (TInputIterator itB, TInputIterator itE) const
 
template<typename TInputIterator >
std::pair< InternalScalar, InternalScalaraxisWidth (TInputIterator itB, TInputIterator itE) const
 
Primitive primitive () const
 
template<typename Vector3D >
void getNormal (Vector3D &normal) const
 
const InternalVectorexactNormal () const
 
template<typename Vector3D >
void getUnitNormal (Vector3D &normal) const
 
void getBounds (double &min, double &max) const
 
const InputPointminimalPoint () const
 
const InputPointmaximalPoint () const
 
void selfDisplay (std::ostream &out) const
 
bool isValid () const
 

Static Public Member Functions

template<typename TInputIterator >
static std::pair< InternalScalar, InternalScalarcomputeAxisWidth (Dimension axis, TInputIterator itB, TInputIterator itE)
 
template<typename TVector1 , typename TVector2 >
static InternalScalar internalDot (const TVector1 &u, const TVector2 &v)
 
template<typename TVector1 , typename TVector2 >
static void internalCross (InternalVector &n, const TVector1 &u, const TVector2 &v)
 

Private Member Functions

 BOOST_CONCEPT_ASSERT ((concepts::CSpace< TSpace >))
 
 BOOST_CONCEPT_ASSERT ((concepts::CSignedNumber< TInternalScalar >))
 
 BOOST_STATIC_ASSERT ((TSpace::dimension==3))
 
 BOOST_STATIC_ASSERT ((TInputPoint::dimension==3))
 
template<typename TInputIterator >
void computeMinMax (State &state, TInputIterator itB, TInputIterator itE) const
 
template<typename TInputIterator >
bool updateMinMax (State &state, TInputIterator itB, TInputIterator itE) const
 
bool checkPlaneWidth (const State &state) const
 
bool setUp1 (const InputPoint &p1)
 
void setUpNormal (State &state) const
 
void setUpNormal1 (State &state) const
 
void setUpNormal2 (State &state) const
 
void setUpNormal3 (State &state) const
 
int signDelta (const InputPoint &A, const InputPoint &B, const InputPoint &C) const
 
int signDelta (const InputPoint &A, const InputPoint &C) const
 
bool newCurrentTriangle (State &state, const InputPoint &M) const
 
template<typename TInputIterator >
unsigned int findTriangle (State &state, TInputIterator itB, TInputIterator itE) const
 
template<typename TInputIterator >
unsigned int findTriangle1 (State &state, TInputIterator itB, TInputIterator itE) const
 
template<typename TInputIterator >
unsigned int findTriangle2 (State &state, TInputIterator itB, TInputIterator itE) const
 
template<typename TInputIterator1 , typename TInputIterator2 >
unsigned int findMixedTriangle (State &state, TInputIterator1 itB1, TInputIterator1 itE1, TInputIterator2 itB2, TInputIterator2 itE2) const
 
bool alignedAlongAxis (const InputPoint &p1, const InputPoint &p2) const
 
void computeHeight (State &state) const
 
void computeNormal (State &state) const
 
template<typename TInputIterator >
bool satisfies (State &state, TInputIterator itB, TInputIterator itE) const
 
template<typename TInputIterator >
std::pair< InternalScalar, InternalScalaraxisWidth (State &state, TInputIterator itB, TInputIterator itE) const
 
bool checkWidth (const State &state) const
 
void selfDisplay (std::ostream &out, const State &state) const
 

Private Attributes

Dimension z
 
Dimension x
 
Dimension y
 
InternalScalar myWidth0
 
InternalScalar myWidth1
 
InputPointSet myPointSet
 
State myState
 
State _state
 
InternalScalar _d
 

Detailed Description

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
class DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >

Aim: A class that contains the chord-based algorithm for recognizing pieces of digital planes of given axis width [ Gerard, Debled-Rennesson, Zimmermann, 2005 ]. When the width is 1, it corresponds to naive planes. The axis is specified at initialization of the object.

Description of template class 'ChordNaivePlaneComputer'.This class is an implementation of Gerard, Debled-Rennesson, Zimmermann, 2005: An elementary digital plane recognition algorithm, [34].

As a (3D) geometric primitive computer, it obeys the concept CAdditivePrimitiveComputer. It is copy constructible, assignable. It has methods extend(), extend( InputIterator, InputIterator) and isExtendable(), isExtendable(InputIterator, InputIterator). The object stores all the distinct points p such that 'extend(p )' was successful. It is thus a model of boost::ForwardContainer (non mutable). It is iterable (inner type ConstIterator, begin(), end()). You may clear() it.

It is also a model of concepts::CPointPredicate (returns 'true' iff a point is within the current bounds).

Note on complexity: According to the paper, the
worst-case complexity is \( O(n^7) \) (in its non-incremental form). However, the observed complexity is quasi-linear.
Note on execution times: The user should favor int32_t or
int64_t instead of BigInteger whenever possible. When the point components are smaller than 14000, int32_t are sufficient. For point components smaller than 440000000, int64_t are sufficient. For greater diameters, it is necessary to use BigInteger.
What is the best algorithm to check if a set of digital points is some (naive) plane ?

We discuss only this question between ChordNaivePlaneComputer (1) and COBANaivePlaneComputer (2) (see also Comparative evaluation of COBA and Chord algorithm):

  1. Complexity: (2) has a better worst time complexity than (1), but neither (1) nor (2) has an easy bound on the number of global recomputation (traversal of all input points to recompute a valid direction).
  2. Big integers: (1) requires (significantly) smaller integers than (2). For instance, int64_t are required for diameter greater than 25 for (2) instead of 14000 for (1).
  3. Practice: both algorithms are very comparable. (1) seems slightly faster than (2) on average (but this was not tested on many architecture).
  4. Exactness: Both algorithms do not return the smallest possible arithmetic parameters for the plane, but only a rational approximation.
  5. Services: Algorithm (1) can be transformed to find the exact axis width of a given set of points, (2) is not suited for that task.

A small example to show how to check if some points form a subset of a naive plane.

//Example. Checks that the following four points does not belong to a naive plane.
typedef SpaceND<3,int> Z3;
typedef ChordNaivePlaneComputer< Z3, Z3::Point, int64_t > NaivePlaneComputer;
plane.init( 2, 1, 1 ); // axis is z, width is 1/1 => naive
plane.extend( Point( 10, 0, 0 ) ); // return 'true'
plane.extend( Point( 0, 8, 0 ) ); // return 'true'
plane.extend( Point( 0, 0, 6 ) ); // return 'true'
plane.extend( Point( 5, 5, 5 ) ); // return 'false'
// There is no naive plane going through the 3 first points and the last one.

Model of boost::DefaultConstructible, boost::CopyConstructible, boost::Assignable, boost::ForwardContainer, concepts::CAdditivePrimitiveComputer, concepts::CPointPredicate.

Template Parameters
TSpacespecifies the digital space (provides dimension and types for the primitive)
TInputPointspecifies the type of the input points (digital or not). Usually, you may choose TInputPoint = TSpace::Point, but this is not compulsory. You may for instance wish to manipulate floating-point value points. This is possible, but you have to choose the type TInternalScalar accordingly.
TInternalScalarspecifies the type of scalar used in internal computations, generally a more precise type than TInputPoint::Component. For instance, for digital points, the type should be able to hold integers of order \((2*D)^2\) if D is the diameter of the set of digital points.
Examples:
io/viewers/viewer3D-7bis-planes.cpp.

Definition at line 157 of file ChordNaivePlaneComputer.h.

Member Typedef Documentation

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputVector::Component DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::Component

Definition at line 171 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPointSet::const_iterator DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::const_iterator

Definition at line 184 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPointSet::const_pointer DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::const_pointer

Definition at line 185 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPointSet::const_reference DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::const_reference

Definition at line 186 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPointSet::const_iterator DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::ConstIterator

Definition at line 177 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPoint::Coordinate DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::Coordinate

Definition at line 172 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPointSet::difference_type DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::difference_type

Definition at line 188 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef TInputPoint DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::InputPoint

Definition at line 168 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef std::set< InputPoint > DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::InputPointSet

Definition at line 175 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPoint DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::InputVector

Definition at line 170 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef TInternalScalar DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::InternalScalar

Definition at line 169 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef PointVector<3,InternalScalar> DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::InternalVector

Definition at line 173 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPointSet::iterator DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::Iterator

Definition at line 178 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef Space::Point DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::Point

Definition at line 179 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef ParallelStrip<Space,true,true> DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::Primitive

Definition at line 180 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPointSet::size_type DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::Size

Definition at line 176 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPointSet::size_type DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::size_type

Definition at line 189 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef TSpace DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::Space

Definition at line 167 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
typedef InputPointSet::value_type DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::value_type

Definition at line 187 of file ChordNaivePlaneComputer.h.

Constructor & Destructor Documentation

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::~ChordNaivePlaneComputer ( )

Destructor.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::ChordNaivePlaneComputer ( )

Constructor. The object is not valid and should be initialized.

See also
init
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::ChordNaivePlaneComputer ( const ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar > &  other)

Copy constructor.

Parameters
otherthe object to clone.

Member Function Documentation

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::alignedAlongAxis ( const InputPoint p1,
const InputPoint p2 
) const
private
Parameters
p1any point.
p2any point.
Returns
'true' iff the two points form a vector aligned with the main axis.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
std::pair<InternalScalar, InternalScalar> DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::axisWidth ( TInputIterator  itB,
TInputIterator  itE 
) const

Useful to compute the axis width of a given range of points (public version).

Template Parameters
TInputIteratorany model of InputIterator on InputPoint.
Parameters
[in]itBan iterator on the first element of the range of 3D points.
[in]itEan iterator after the last element of the range of 3D points.
Returns
the axis width as a pair numerator/denominator.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
std::pair<InternalScalar, InternalScalar> DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::axisWidth ( State state,
TInputIterator  itB,
TInputIterator  itE 
) const
private

Useful to compute the axis width of a given range of points.

Template Parameters
TInputIteratorany model of InputIterator on InputPoint.
Parameters
[out]statethe resulting state, if you need to have a look.
[in]itBan iterator on the first element of the range of 3D points.
[in]itEan iterator after the last element of the range of 3D points.
Returns
the axis width as a pair numerator/denominator.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
ConstIterator DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::begin ( ) const
Returns
a const iterator pointing on the first point stored in the current naive plane.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::BOOST_CONCEPT_ASSERT ( (concepts::CSpace< TSpace >)  )
private
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::BOOST_CONCEPT_ASSERT ( (concepts::CSignedNumber< TInternalScalar >)  )
private
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::BOOST_STATIC_ASSERT ( (TSpace::dimension==3)  )
private
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::BOOST_STATIC_ASSERT ( (TInputPoint::dimension==3)  )
private
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::checkPlaneWidth ( const State state) const
private
Parameters
statethe state where the normal state.N, the scalars state.min and state.max are used in computations.
Returns
'true' if the current width along state.N (computed from the difference of state.max and state.min) is strictly inferior to the maximal specified width (in myWidth), 'false' otherwise.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::checkWidth ( const State state) const
private
Parameters
[in,out]statethe current state of the algorithm (fields state.min, state.max, state.height are used)
Returns
'true' iff the current state indicates that the set of points is included between two planes of axis width smaller than the width specified at initialization. It is the value: state.max - state.min <= state.height.
See also
init
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::clear ( )

Clear the object, free memory. The plane keeps its main axis, diameter and width, but contains no point.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
static std::pair<InternalScalar, InternalScalar> DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::computeAxisWidth ( Dimension  axis,
TInputIterator  itB,
TInputIterator  itE 
)
static

Useful to compute the axis width of a given range of points (public static version).

Template Parameters
TInputIteratorany model of InputIterator on InputPoint.
Parameters
[in]axisthe main axis (0,1,2) for x, y or z.
[in]itBan iterator on the first element of the range of 3D points.
[in]itEan iterator after the last element of the range of 3D points.
Returns
the axis width as a pair numerator/denominator.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::computeHeight ( State state) const
private
Parameters
[in,out]statethe field state.height is updated and contains the main axis height of the current triangle.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::computeMinMax ( State state,
TInputIterator  itB,
TInputIterator  itE 
) const
private

Computes the min and max values/arguments of the scalar product between the normal state.N and the points in the range [itB,itE). Overwrites state.min, state.max at the start.

Template Parameters
TInputIteratorany model of InputIterator.
Parameters
state(modified) the state where the normal N is used in computation and where fields state.min, state.max, state.ptMin, state.ptMax are updated.
itBan input iterator on the first point of the range.
itEan input iterator after the last point of the range.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::computeNormal ( State state) const
private

Computes a new normal according to the given values of state.A, state.B, state.C.

Parameters
[in,out]statethe field state.normal is updated and contains the new normal.
Precondition
state.nbValid >= 2
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::empty ( ) const
Returns
'true' if and only if this object contains no point.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
ConstIterator DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::end ( ) const
Returns
a const iterator pointing after the last point stored in the current naive plane.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
const InternalVector& DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::exactNormal ( ) const
Returns
a reference to the current normal vector (exact form).
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::extend ( const InputPoint p)

Adds the point p and checks if we have still a digital plane of specified width. The plane parameters may be updated so as to include the new point.

Parameters
pany 3D point (in the specified diameter).
Returns
'true' if it is still a plane, 'false' otherwise (the object is then in its original state).
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::extend ( TInputIterator  itB,
TInputIterator  itE 
)

Adds the range of points [it, itE) and checks if we have still a digital plane of specified width. The plane parameters may be updated so as to include all the new points. All points pointed by iterators should be in the diameter of this object.

Template Parameters
TInputIteratorany model of InputIterator on InputPoint.
Parameters
[in]itBan iterator on the first element of the range of 3D points.
[in]itEan iterator after the last element of the range of 3D points.
Returns
'true' if it is still a plane, 'false' otherwise (the object is then in its original state).
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::extendAsIs ( const InputPoint p)

Adds the point p to this plane if it is within the current bounds. The plane parameters are not updated.

Parameters
pany 3D point (in the specified diameter).
Returns
'true' if p is in the plane, 'false' otherwise (the object is then in its original state).
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator1 , typename TInputIterator2 >
unsigned int DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::findMixedTriangle ( State state,
TInputIterator1  itB1,
TInputIterator1  itE1,
TInputIterator2  itB2,
TInputIterator2  itE2 
) const
private
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
unsigned int DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::findTriangle ( State state,
TInputIterator  itB,
TInputIterator  itE 
) const
private
Template Parameters
TInputIteratorany model of boost::InputIterator on InputPoint.

Initializes the Chord algorithm by determining an initial triangle of the convex chord set (S+(-S)) if S is the set of points. If points have special alignment with the main axis, it may not return a triangle.

Parameters
[in]itBthe beginning of the range of input points.
[in]itEthe end of the range of input points.
[out]statecontains the points forming a triangle not containing the main axis (state.A, state.B, state.C) if one was found, otherwise a segment not containing the main axis (state.A, state.B), otherwise the first point (state.A).
Returns
0 if object is initialized and there is no points, 1 when all points are aligned with main axis, 2 when all points form a triangle containing the main axis direction, 3 when there are at least 3 points that form a triangle not aligned with the main axis direction.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
unsigned int DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::findTriangle1 ( State state,
TInputIterator  itB,
TInputIterator  itE 
) const
private
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
unsigned int DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::findTriangle2 ( State state,
TInputIterator  itB,
TInputIterator  itE 
) const
private
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::getBounds ( double &  min,
double &  max 
) const

If n is the unit normal to the current plane, then n.x >= min and n.x <= max are the two half-planes defining it.

Parameters
minthe lower bound (corresponding to the unit vector).
maxthe upper bound (corresponding to the unit vector).
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename Vector3D >
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::getNormal ( Vector3D &  normal) const
Template Parameters
Vector3Dany type T such that T.operator[](int i) returns a reference to a double. i ranges in 0,1,2.
Parameters
[in,out]normalthe current normal vector
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename Vector3D >
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::getUnitNormal ( Vector3D &  normal) const
Template Parameters
Vector3Dany type T such that T.operator[](int i) returns a reference to a double. i ranges in 0,1,2.
Parameters
[in,out]normalthe current unit normal vector
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::init ( Dimension  axis,
InternalScalar  widthNumerator = NumberTraitsInternalScalar >::ONE,
InternalScalar  widthDenominator = NumberTraitsInternalScalar >::ONE 
)

All these parameters cannot be changed during the process. After this call, the object is in a consistent state and can accept new points for recognition. Calls clear so that the object is ready to be extended.

Parameters
axisthe main axis (0,1,2) for x, y or z.
widthNumeratorthe maximal axis-width (x,y,or z) for the plane is defined as the rational number widthNumerator / widthDenominator (default is 1/1, i.e. naive plane).
widthDenominatorthe maximal axis-width (x,y,or z) for the plane is defined as the rational number widthNumerator / widthDenominator (default is 1/1, i.e. naive plane).
Examples:
io/viewers/viewer3D-7bis-planes.cpp.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TVector1 , typename TVector2 >
static void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::internalCross ( InternalVector n,
const TVector1 &  u,
const TVector2 &  v 
)
static

Cross product with potentially better precision.

Parameters
[out]nthe vector that stores the cross product of u and v.
uany vector
vany vector
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TVector1 , typename TVector2 >
static InternalScalar DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::internalDot ( const TVector1 &  u,
const TVector2 &  v 
)
static

Inner product with potentially better precision.

Parameters
uany vector
vany vector
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::isExtendable ( const InputPoint p) const

Checks if we have still a digital plane of specified width when adding point p. The object is left unchanged whatever the returned value. The invariant is 'this->isExtendable( p ) == true <=> this->extend( p ) == true'.

Parameters
pany 3D point (in the specified diameter).
Returns
'true' if this is still a plane, 'false' otherwise.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::isExtendable ( TInputIterator  itB,
TInputIterator  itE 
) const

Checks if we have still a digital plane of specified width when adding the range of points [it, itE). The object is left unchanged whatever the returned value. All points pointed by iterators should be in the diameter of this object. The invariant is 'this->isExtendable( it, itE ) == true <=> this->extend( it, itE ) == true'.

Template Parameters
TInputIteratorany model of InputIterator on InputPoint.
Parameters
[in]itBan iterator on the first element of the range of 3D points.
[in]itEan iterator after the last element of the range of 3D points.
Returns
'true' if this is still a plane, 'false' otherwise.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
Size DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::max_size ( ) const

NB: std version.

Returns
the maximal allowed number of points in the current naive plane.
See also
maxSize
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
const InputPoint& DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::maximalPoint ( ) const
Precondition
! empty()
Returns
the current maximal point of the plane, i.e. the one with the highest scalar product with the current normal vector. Note that other points may also have a maximum value.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
Size DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::maxSize ( ) const

same as max_size

Returns
the maximal allowed number of points in the current naive plane.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
const InputPoint& DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::minimalPoint ( ) const
Precondition
! empty()
Returns
the current minimal point of the plane, i.e. the one with the smallest scalar product with the current normal vector. Note that other points may also have a minimum value.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::newCurrentTriangle ( State state,
const InputPoint M 
) const
private

Puts in (A,B,C) the new current triangle. We choose the triangle of the tetrahedron A,B,C,M having the highest intersection with Oz.

Parameters
statethe current state of the algorithm, state.A, state.B and state.C should represent the current triangle.
Mshould be the vector P2-P1, where P2 is the point maximizing the dot product with the normal and P1 is the point minimizing the same dot product.
Returns
'true' if a consistent new triangle was found, 'false' if error (M was not correct in this case).
Precondition
state.nbValid >= 2
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::operator() ( const Point p) const

Checks if the point p is in the current digital plane. Therefore, a ChordNaivePlaneComputer is a model of concepts::CPointPredicate.

Parameters
pany 3D point.
Returns
'true' if it is in the current plane, false otherwise.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
ChordNaivePlaneComputer& DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::operator= ( const ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar > &  other)

Assignment.

Parameters
otherthe object to copy.
Returns
a reference on 'this'.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
Primitive DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::primitive ( ) const
Returns
the current primitive recognized by this computer, which is a ParallelStrip of axis width smaller than the one specified at instanciation.
Note
The returned primitive has the form \(\mu \le \vec{N} \cdot \vec{X} \le \mu + \epsilon\). It is guaranteed that its axis width is strictly less than the value widthNumerator / widthDenominator specified with method init.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::satisfies ( TInputIterator  itB,
TInputIterator  itE 
) const

Useful to check if a given set of points has a valid axis width (public version).

Template Parameters
TInputIteratorany model of InputIterator on InputPoint.
Parameters
[in]itBan iterator on the first element of the range of 3D points.
[in]itEan iterator after the last element of the range of 3D points.
Returns
'true' iff the set of points given by range [itB,itE) has a valid width.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::satisfies ( State state,
TInputIterator  itB,
TInputIterator  itE 
) const
private

Useful to check if a given set of points has a valid axis width.

Template Parameters
TInputIteratorany model of InputIterator on InputPoint.
Parameters
[out]statethe resulting state, if you need to have a look.
[in]itBan iterator on the first element of the range of 3D points.
[in]itEan iterator after the last element of the range of 3D points.
Returns
'true' iff the set of points given by range [itB,itE) has a valid width.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::selfDisplay ( std::ostream &  out) const

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::selfDisplay ( std::ostream &  out,
const State state 
) const
private

Writes/Displays the object on an output stream (debug purposes).

Parameters
outthe output stream where the object is written.
statea given state for the display.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::setUp1 ( const InputPoint p1)
private

Sets up a consistent state with only one point.

Parameters
p1any point.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::setUpNormal ( State state) const
private

Sets up a consistent initial normal direction given the output of findTriangle (state.nbValid, state.A, state.B, state.C).

Parameters
[in,out]statethe modified state.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::setUpNormal1 ( State state) const
private

Sets up a consistent initial normal direction given the output of findTriangle (state.nbValid == 1).

Parameters
[in,out]statethe modified state.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::setUpNormal2 ( State state) const
private

Sets up a consistent initial normal direction given the output of findTriangle (state.nbValid == 2, state.A).

Parameters
[in,out]statethe modified state.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::setUpNormal3 ( State state) const
private

Sets up a consistent initial normal direction given the output of findTriangle (state.nbValid == 3, state.A, state.B, state.C).

Parameters
[in,out]statethe modified state.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
int DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::signDelta ( const InputPoint A,
const InputPoint B,
const InputPoint C 
) const
private

Computes the orientation of vectors AB and AC viewed from the main axis vector. It is the sign of the 2D determinant of AB and AC.

Parameters
Aany point.
Bany point.
Cany point.
Returns
the sign of det(ab,ac), where a,b,c are the 2d projections of A,B,C along main axis.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
int DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::signDelta ( const InputPoint A,
const InputPoint C 
) const
private

Computes the orientation of vectors AO and AC viewed from the main axis vector. It is the sign of the 2D determinant of AO and AC, where O is the origin.

Parameters
Aany point.
Cany point.
Returns
the sign of det(ao,ac), where a,o,c are the 2d projections of A,O,C along main axis.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
Size DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::size ( ) const
Returns
the number of distinct points in the current naive plane.
template<typename TSpace, typename TInputPoint, typename TInternalScalar>
template<typename TInputIterator >
bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::updateMinMax ( State state,
TInputIterator  itB,
TInputIterator  itE 
) const
private

Updates the min and max values/arguments of the scalar product between the normal state.N and the points in the range [itB,itE). Do not overwrite state.min, state.max at the start.

Template Parameters
TInputIteratorany model of InputIterator.
Parameters
state(modified) the state where the normal N is used in computation and where fields state.min, state.max, state.ptMin, state.ptMax are updated.
itBan input iterator on the first point of the range.
itEan input iterator after the last point of the range.
Returns
'true' if any of the fields state.min, state.max, state.ptMin, state.ptMax have been updated, 'false' otherwise.

Field Documentation

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
InternalScalar DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::_d
mutableprivate

temporary variable used in some computations.

Definition at line 539 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
State DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::_state
mutableprivate

Temporary state used in computations.

Definition at line 538 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
InputPointSet DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::myPointSet
mutableprivate

the set of points within the plane, mutable since its state may temporarily be changed during some computations.

Definition at line 536 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
State DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::myState
private

the current state that defines the plane being recognized.

Definition at line 537 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
InternalScalar DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::myWidth0
private

the plane width as a positive rational number myWidth0/myWidth1

Definition at line 534 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
InternalScalar DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::myWidth1
private

the plane width as a positive rational number myWidth0/myWidth1

Definition at line 535 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
Dimension DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::x
private

Definition at line 533 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
Dimension DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::y
private

the two other axes used in all subsequent computations.

Definition at line 533 of file ChordNaivePlaneComputer.h.

template<typename TSpace, typename TInputPoint, typename TInternalScalar>
Dimension DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::z
private

the main axis used in all subsequent computations.

Definition at line 532 of file ChordNaivePlaneComputer.h.


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