#include <DGtal/geometry/tools/determinant/InGeneralizedDiskOfGivenRadius.h>

Collaboration diagram for DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >:

Public Types
typedef TPoint	Point

typedef std::array< Point, 2 >	PointArray

typedef PointArray::size_type	SizeArray

typedef TDetComputer	DetComputer

typedef DetComputer::ArgumentInteger	Integer

typedef DetComputer::ResultInteger	Value

typedef Simple2x2DetComputer< Integer >	AreaFunctor

Public Member Functions
	BOOST_CONCEPT_ASSERT ((C2x2DetComputer< DetComputer >))

	InGeneralizedDiskOfGivenRadius (bool isPositive=true, const Integer &aNum2=NumberTraits< Integer >::ONE, const Integer &aDen2=NumberTraits< Integer >::ZERO)

	InGeneralizedDiskOfGivenRadius (const InGeneralizedDiskOfGivenRadius &other)

InGeneralizedDiskOfGivenRadius &	operator= (const InGeneralizedDiskOfGivenRadius &other)

void	init (const Point &aP, const Point &aQ)

void	init (const PointArray &aA)

Value	operator() (const Point &aR) const

void	selfDisplay (std::ostream &out) const

bool	lengthIsValid (const Integer &aL2) const

bool	isValid () const

void	finalizeComputation () const

Static Public Attributes
static const SizeArray	size = 2

Private Attributes
Integer	myNum2

Integer	myDen2

bool	myIsPositive

DetComputer	myDetComputer

Point	myP

Point	myQ

Point	myR

Integer	myComputedNum2

Integer	myComputedDen2

Integer	myPQ0

Integer	myPQ1

Integer	myPQnorm

Integer	myQR0

Integer	myQR1

Integer	myQRnorm

Integer	myRP0

Integer	myRP1

Integer	myRPnorm

Integer	myArea

AreaFunctor	myAreaFunctor

Detailed Description

template<typename TPoint, typename TDetComputer>
class DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >

Aim: This class implements an orientation functor that provides a way to determine the position of a given point with respect to the unique circle passing by the same two given points and whose radius and orientation is given.

This class is useful for some geometric algorithm involving disks of given radius, such as alpha-hull and alpha-shape computations.

The radius is given at construction. It is described by a pair of integers myNum2 and myDen2 that stands for the numerator and denominator of the squared radius. The orientation is also given at construction. It is described by a boolean equal to 'true' (resp. 'false') if the center C of the circle of squared radius myNum2 / myDen2 and passing by myP and myQ is located on the left side (resp. right side) of the oriented line myP myQ, ie. if myP , myQ , C are counter-clockwise oriented (resp. clockwise oriented).

The test is done in two steps. After an initialization step that memorizes the two points that uniquely defines the circle whose radius and orientation is given, we can test the position of a third point myR with respect to this circle. Note that the distance between myP and myR is assumed to be greater than the distance between myP and myQ and between myQ and myR.

If the third point lies on the same side of the oriented line passing by myP myQ than the circle center, the return value is:
- zero if the third point belongs to the circle
- strictly positive if it does not lie in the interior or on the boundary of the circle
- strictly negative if it lies in the interior of the circle
otherwise, the return value is strictly negative. This case is discarded because segment myP myR is assumed to be the longest side of the triangle myP , myQ , myR.

The test is reduced to the computation of the determinant of a 2x2 matrix of integral entries, the implementation of which is delegated to a determinant computer. The reduction involves many multiplications and additions so that temporary integers must be coded with at least \( 6b + 9 \) bits for point coordinates coded with \( b \) bits. That's why it is a best practice to use BigInteger to avoid any overflows. You can use however 64 bits integers together with a smart determinant computer, like AvnaimEtAl2x2DetSignComputer, for small domains where point coordinates range within ]-2^9; 2^9[.

Basic usage:

...
typedef Z2i::Point Point; 
typedef Simple2x2DetComputer<Z2i::BigInteger> DeterminantComputer; 
typedef InGeneralizedDiskOfGivenRadius<Point, DeterminantComputer> Functor; 
Functor functor(true, 25, 1); //circles of radius 5, directly oriented 
functor.init( Point(5,0), Point(0,5) ); 
return functor( Point(-4,1) ); 
//a strictly positive value is returned because (-4,1) lies in the interior
//of the circle of center (0,0) and radius 5. 

Note that since a substantial part of the execution time comes from the allocation/desallocation of integers, we follow the same strategy used in IntegerComputer: the user instantiates once this object and performs several tests with it.

Template Parameters

TPoint	a model of point
TDetComputer	a model of C2x2DetComputer

Examples:: geometry/tools/exampleAlphaShape.cpp.

Definition at line 125 of file InGeneralizedDiskOfGivenRadius.h.

Member Typedef Documentation

template<typename TPoint , typename TDetComputer >

typedef Simple2x2DetComputer<Integer> DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::AreaFunctor

Type of functor returning the area of a parallelogram based on two vectors. Used to compute the radius of a circle passing by 3 points.

Definition at line 165 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

typedef TDetComputer DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::DetComputer

Type of determinant computer

Definition at line 150 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

typedef DetComputer::ArgumentInteger DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::Integer

Type of integers used during the computation

Definition at line 155 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

typedef TPoint DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::Point

Type of input points

Definition at line 132 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

typedef std::array<Point,2> DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::PointArray

Type of point array

Definition at line 137 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

typedef PointArray::size_type DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::SizeArray

Type used to represent the size of the array

Definition at line 141 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

typedef DetComputer::ResultInteger DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::Value

Type of returned value

Definition at line 159 of file InGeneralizedDiskOfGivenRadius.h.

Constructor & Destructor Documentation

template<typename TPoint , typename TDetComputer >

DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::InGeneralizedDiskOfGivenRadius	(	bool	isPositive = `true`,
		const Integer &	aNum2 = `NumberTraits< Integer >::ONE`,
		const Integer &	aDen2 = `NumberTraits< Integer >::ZERO`
	)

Constructor of the functor from a given radius.

Parameters

isPositive	bool equal to 'true' (resp. 'false') if the center C of the circle of squared radius myNum2 / myDen2 and passing by myP and myQ is located on the left side (resp. right side) of the oriented line myP myQ, ie. myP , myQ , C are counter-clockwise oriented (resp. clockwise oriented).
aNum2	squared numerator of the radius (0 by default)
aDen2	squared denominator of the radius (1 by default)

Precondition: aNum2 should be not zero; the object is not valid.

Warning: aNum2 and aDen2 should be both positive. If they are negative, we take their opposite. It aDen2 is zero, the radius is assumed to tend to infinite.

template<typename TPoint , typename TDetComputer >

DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::InGeneralizedDiskOfGivenRadius ( const InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer > & other )

Copy constructor.

Parameters

other the object to clone.

Member Function Documentation

template<typename TPoint , typename TDetComputer >

DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::BOOST_CONCEPT_ASSERT ( (C2x2DetComputer< DetComputer >) )

template<typename TPoint , typename TDetComputer >

void DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::finalizeComputation ( ) const

Update myComputedNum2 and myComputedDen2 from other private datas.

template<typename TPoint , typename TDetComputer >

void DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::init	(	const Point &	aP,
		const Point &	aQ
	)

Initialization from two points.

Parameters

aP	a first point
aQ	a second point

Precondition: the distance between aP and aQ must be greater than the circle diameter

template<typename TPoint , typename TDetComputer >

void DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::init ( const PointArray & aA )

Initialisation from two points.

Parameters

aA	array of two points

See also: InGeneralizedDiskOfGivenRadiusBy2x2DetComputer::init()

template<typename TPoint , typename TDetComputer >

bool DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::isValid ( ) const

Checks the validity/consistency of the object. More precisely, myNum2 and myDen2 must be positive, myNum2 must not be zero (only strictly positive radius are valid)

Returns: 'true' if the object is valid, 'false' otherwise.

template<typename TPoint , typename TDetComputer >

bool DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::lengthIsValid ( const Integer & aL2 ) const

Compares the length of two consecutive input points to the diameter of the circle.

Parameters

aL2	any squared length between two points

Returns: 'true' if either myDen2 equals zero or the given (squared) length is shorter than the (squared) diameter of the circle

template<typename TPoint , typename TDetComputer >

Value DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::operator() ( const Point & aR ) const

Main operator.

Warning: InGeneralizedDiskOfGivenRadiusBy2x2DetComputer::init() should be called before

Parameters

aR	any point to test

Returns

orientation of the third point myR with respect to the circle of squared radius myNum2 / myDen2 and oriented by myPositive passing by myP and myQ.

if the third point lies on the same side of the oriented line passing by myP myQ than the circle center, the return value is:
- zero if the third point belongs to the circle
- strictly positive if it does not lie in the interior or on the boundary of the circle
- strictly negative if it lies in the interior of the circle
otherwise, the return value is strictly negative.

Precondition: the distance between myQ and aR must be greater than the circle diameter and segment myP aR is assumed to be the longest side of the triangle myP , myQ , aR.

template<typename TPoint , typename TDetComputer >

InGeneralizedDiskOfGivenRadius& DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::operator= ( const InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer > & other )

Assignment.

Parameters

other the object to copy.

Returns: a reference on 'this'.

template<typename TPoint , typename TDetComputer >

void DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::selfDisplay ( std::ostream & out ) const

Writes/Displays the object on an output stream.

Parameters

out	the output stream where the object is written.

Field Documentation

template<typename TPoint , typename TDetComputer >

Integer DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::myArea

mutableprivate

area of triangle myP myQ myR

Definition at line 362 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

AreaFunctor DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::myAreaFunctor

mutableprivate

Functor returning the area of a parallelogram based on two vectors.

Definition at line 367 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

Integer DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::myComputedDen2

mutableprivate

Denominator of the squared radius of the circle myP , myQ , myR

Definition at line 322 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

Integer DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::myComputedNum2

mutableprivate

Numerator of the squared radius of the circle myP , myQ , myR

Definition at line 318 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

Integer DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::myDen2

private

Denominator of the given squared radius

Definition at line 285 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

DetComputer DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::myDetComputer

private

Determinant computer used to compare the given (squared) radius myNum2 / myDen2 to the (squared) radius of the circle passing by myP , myQ , myR , ie. myComputedNum2 / myComputedDen2

Definition at line 301 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

bool DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::myIsPositive

private

boolean equal to 'true' (resp. 'false') if the center C of the circle of squared radius myNum2 / myDen2 and passing by myP and myQ is located on the left side (resp. right side) of the oriented line myP myQ, ie. if myP , myQ , C are counter-clockwise oriented (resp. clockwise oriented).

Definition at line 294 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

Integer DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::myNum2

private

Numerator of the given squared radius

Definition at line 281 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >

Point DGtal::InGeneralizedDiskOfGivenRadius< TPoint, TDetComputer >::myP

mutableprivate

First point

Definition at line 306 of file InGeneralizedDiskOfGivenRadius.h.

template<typename TPoint , typename TDetComputer >