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. More...

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

Inheritance 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, InternalScalar >	InternalVector

typedef std::set< InputPoint >	InputPointSet

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)

ChordNaivePlaneComputer &	operator= (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, InternalScalar >	axisWidth (TInputIterator itB, TInputIterator itE) const

Primitive	primitive () const

template<typename Vector3D >
void	getNormal (Vector3D &normal) const

const InternalVector &	exactNormal () const

template<typename Vector3D >
void	getUnitNormal (Vector3D &normal) const

void	getBounds (double &min, double &max) const

const InputPoint &	minimalPoint () const

const InputPoint &	maximalPoint () const

void	selfDisplay (std::ostream &out) const

bool	isValid () const

Static Public Member Functions
template<typename TInputIterator >
static std::pair< InternalScalar, InternalScalar >	computeAxisWidth (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, InternalScalar >	axisWidth (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, [61].

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):

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).
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).
Practice: both algorithms are very comparable. (1) seems slightly faster than (2) on average (but this was not tested on many architecture).
Exactness: Both algorithms do not return the smallest possible arithmetic parameters for the plane, but only a rational approximation.
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;
NaivePlaneComputer plane;
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

TSpace	specifies the digital space (provides dimension and types for the primitive)
TInputPoint	specifies 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.
TInternalScalar	specifies 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.

Definition at line 157 of file ChordNaivePlaneComputer.h.

Member Typedef Documentation

◆ Component

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

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

Definition at line 171 of file ChordNaivePlaneComputer.h.

◆ const_iterator

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.

◆ const_pointer

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.

◆ const_reference

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.

◆ ConstIterator

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.

◆ Coordinate

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

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

Definition at line 172 of file ChordNaivePlaneComputer.h.

◆ difference_type

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.

◆ InputPoint

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

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

Definition at line 168 of file ChordNaivePlaneComputer.h.

◆ InputPointSet

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.

◆ InputVector

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

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

Definition at line 170 of file ChordNaivePlaneComputer.h.

◆ InternalScalar

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

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

Definition at line 169 of file ChordNaivePlaneComputer.h.

◆ InternalVector

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.

◆ Iterator

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

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

Definition at line 178 of file ChordNaivePlaneComputer.h.

◆ Point

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

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

Definition at line 179 of file ChordNaivePlaneComputer.h.

◆ Primitive

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.

◆ Size

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.

◆ size_type

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.

◆ Space

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

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

Definition at line 167 of file ChordNaivePlaneComputer.h.

◆ value_type

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

◆ ~ChordNaivePlaneComputer()

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

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

Destructor.

◆ ChordNaivePlaneComputer() [1/2]

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

◆ ChordNaivePlaneComputer() [2/2]

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::ChordNaivePlaneComputer ( const ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar > & other )

Copy constructor.

Parameters

other the object to clone.

Member Function Documentation

◆ alignedAlongAxis()

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::alignedAlongAxis	(	const InputPoint &	p1,
		const InputPoint &	p2
	)		const

private

Parameters

p1	any point.
p2	any point.

Returns: 'true' iff the two points form a vector aligned with the main axis.

◆ axisWidth() [1/2]

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

TInputIterator any model of InputIterator on InputPoint.

Parameters

[out]	state	the resulting state, if you need to have a look.
[in]	itB	an iterator on the first element of the range of 3D points.
[in]	itE	an iterator after the last element of the range of 3D points.

Returns: the axis width as a pair numerator/denominator.

◆ axisWidth() [2/2]

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

TInputIterator any model of InputIterator on InputPoint.

Parameters

[in]	itB	an iterator on the first element of the range of 3D points.
[in]	itE	an iterator after the last element of the range of 3D points.

Returns: the axis width as a pair numerator/denominator.

◆ begin()

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.

◆ BOOST_CONCEPT_ASSERT() [1/2]

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::BOOST_CONCEPT_ASSERT ( (concepts::CSignedNumber< TInternalScalar >) )

private

◆ BOOST_CONCEPT_ASSERT() [2/2]

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::BOOST_CONCEPT_ASSERT ( (concepts::CSpace< TSpace >) )

private

◆ BOOST_STATIC_ASSERT() [1/2]

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::BOOST_STATIC_ASSERT ( (TInputPoint::dimension==3) )

private

◆ BOOST_STATIC_ASSERT() [2/2]

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::BOOST_STATIC_ASSERT ( (TSpace::dimension==3) )

private

◆ checkPlaneWidth()

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::checkPlaneWidth ( const State & state ) const

private

Parameters

state the 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.

◆ checkWidth()

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

bool DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::checkWidth ( const State & state ) const

private

Parameters

[in,out] state the 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

◆ clear()

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.

◆ computeAxisWidth()

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

TInputIterator any model of InputIterator on InputPoint.

Parameters

[in]	axis	the main axis (0,1,2) for x, y or z.
[in]	itB	an iterator on the first element of the range of 3D points.
[in]	itE	an iterator after the last element of the range of 3D points.

Returns: the axis width as a pair numerator/denominator.

◆ computeHeight()

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::computeHeight ( State & state ) const

private

Parameters

[in,out] state the field state.height is updated and contains the main axis height of the current triangle.

◆ computeMinMax()

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

TInputIterator any 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.
itB	an input iterator on the first point of the range.
itE	an input iterator after the last point of the range.

◆ computeNormal()

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] state the field state.normal is updated and contains the new normal.

Precondition: state.nbValid >= 2

◆ empty()

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.

◆ end()

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.

◆ exactNormal()

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).

◆ extend() [1/2]

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

p	any 3D point (in the specified diameter).

Returns: 'true' if it is still a plane, 'false' otherwise (the object is then in its original state).

◆ extend() [2/2]

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

TInputIterator any model of InputIterator on InputPoint.

Parameters

[in]	itB	an iterator on the first element of the range of 3D points.
[in]	itE	an 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).

◆ extendAsIs()

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

p	any 3D point (in the specified diameter).

Returns: 'true' if p is in the plane, 'false' otherwise (the object is then in its original state).

◆ findMixedTriangle()

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

◆ findTriangle()

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

TInputIterator any 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]	itB	the beginning of the range of input points.
[in]	itE	the end of the range of input points.
[out]	state	contains 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.

◆ findTriangle1()

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

◆ findTriangle2()

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

◆ getBounds()

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

min	the lower bound (corresponding to the unit vector).
max	the upper bound (corresponding to the unit vector).

◆ getNormal()

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

template<typename Vector3D >

void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::getNormal ( Vector3D & normal ) const

Template Parameters

Vector3D any type T such that T.operator[](int i) returns a reference to a double. i ranges in 0,1,2.

Parameters

[in,out] normal the current normal vector

◆ getUnitNormal()

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

template<typename Vector3D >

void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::getUnitNormal ( Vector3D & normal ) const

Template Parameters

Vector3D any type T such that T.operator[](int i) returns a reference to a double. i ranges in 0,1,2.

Parameters

[in,out] normal the current unit normal vector

◆ init()

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

void DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::init	(	Dimension	axis,
		InternalScalar	widthNumerator = `NumberTraits< InternalScalar >::ONE`,
		InternalScalar	widthDenominator = `NumberTraits< InternalScalar >::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

axis	the main axis (0,1,2) for x, y or z.
widthNumerator	the 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).
widthDenominator	the 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).

Referenced by main().

◆ internalCross()

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]	n	the vector that stores the cross product of u and v.
	u	any vector
	v	any vector

◆ internalDot()

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

u	any vector
v	any vector

◆ isExtendable() [1/2]

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

p	any 3D point (in the specified diameter).

Returns: 'true' if this is still a plane, 'false' otherwise.

◆ isExtendable() [2/2]

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

TInputIterator any model of InputIterator on InputPoint.

Parameters

[in]	itB	an iterator on the first element of the range of 3D points.
[in]	itE	an iterator after the last element of the range of 3D points.

Returns: 'true' if this is still a plane, 'false' otherwise.

◆ isValid()

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.

◆ max_size()

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

◆ maximalPoint()

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.

◆ maxSize()

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.

◆ minimalPoint()

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.

◆ newCurrentTriangle()

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

state	the current state of the algorithm, state.A, state.B and state.C should represent the current triangle.
M	should 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

◆ operator()()

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

p	any 3D point.

Returns: 'true' if it is in the current plane, false otherwise.

◆ operator=()

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

ChordNaivePlaneComputer& DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::operator= ( const ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar > & other )

Assignment.

Parameters

other the object to copy.

Returns: a reference on 'this'.

◆ primitive()

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.

◆ satisfies() [1/2]

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

TInputIterator any model of InputIterator on InputPoint.

Parameters

[out]	state	the resulting state, if you need to have a look.
[in]	itB	an iterator on the first element of the range of 3D points.
[in]	itE	an 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.

◆ satisfies() [2/2]

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

TInputIterator any model of InputIterator on InputPoint.

Parameters

[in]	itB	an iterator on the first element of the range of 3D points.
[in]	itE	an 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.

◆ selfDisplay() [1/2]

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

out	the output stream where the object is written.

◆ selfDisplay() [2/2]

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

out	the output stream where the object is written.
state	a given state for the display.

◆ setUp1()

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

p1	any point.

◆ setUpNormal()

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] state the modified state.

◆ setUpNormal1()

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] state the modified state.

◆ setUpNormal2()

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] state the modified state.

◆ setUpNormal3()

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] state the modified state.

◆ signDelta() [1/2]

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

A	any point.
B	any point.
C	any point.

Returns: the sign of det(ab,ac), where a,b,c are the 2d projections of A,B,C along main axis.

◆ signDelta() [2/2]

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

A	any point.
C	any point.

Returns: the sign of det(ao,ac), where a,o,c are the 2d projections of A,O,C along main axis.

◆ size()

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.

◆ updateMinMax()

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

TInputIterator any 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.
itB	an input iterator on the first point of the range.
itE	an 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

◆ _d

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.

◆ _state

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.

◆ myPointSet

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.

◆ myState

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.

◆ myWidth0

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.

◆ myWidth1

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.

◆ x

template<typename TSpace , typename TInputPoint , typename TInternalScalar >

Dimension DGtal::ChordNaivePlaneComputer< TSpace, TInputPoint, TInternalScalar >::x

private

Definition at line 533 of file ChordNaivePlaneComputer.h.

◆ y

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.

◆ z

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:

ChordNaivePlaneComputer.h

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

◆ Component

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ ConstIterator

◆ Coordinate

◆ difference_type

◆ InputPoint

◆ InputPointSet

◆ InputVector

◆ InternalScalar

◆ InternalVector

◆ Iterator

◆ Point

◆ Primitive

◆ Size

◆ size_type

◆ Space

◆ value_type

Constructor & Destructor Documentation

◆ ~ChordNaivePlaneComputer()

◆ ChordNaivePlaneComputer() [1/2]

◆ ChordNaivePlaneComputer() [2/2]

Member Function Documentation

◆ alignedAlongAxis()

◆ axisWidth() [1/2]

◆ axisWidth() [2/2]

◆ begin()

◆ BOOST_CONCEPT_ASSERT() [1/2]

◆ BOOST_CONCEPT_ASSERT() [2/2]

◆ BOOST_STATIC_ASSERT() [1/2]

◆ BOOST_STATIC_ASSERT() [2/2]

◆ checkPlaneWidth()

◆ checkWidth()

◆ clear()

◆ computeAxisWidth()

◆ computeHeight()

◆ computeMinMax()

◆ computeNormal()

◆ empty()

◆ end()

◆ exactNormal()

◆ extend() [1/2]

◆ extend() [2/2]

◆ extendAsIs()

◆ findMixedTriangle()

◆ findTriangle()

◆ findTriangle1()

◆ findTriangle2()

◆ getBounds()

◆ getNormal()

◆ getUnitNormal()

◆ init()

◆ internalCross()

◆ internalDot()

◆ isExtendable() [1/2]

◆ isExtendable() [2/2]

◆ isValid()

◆ max_size()

◆ maximalPoint()

◆ maxSize()

◆ minimalPoint()

◆ newCurrentTriangle()

◆ operator()()

◆ operator=()

◆ primitive()

◆ satisfies() [1/2]

◆ satisfies() [2/2]

◆ selfDisplay() [1/2]

◆ selfDisplay() [2/2]

◆ setUp1()

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