lti::delaunayTriangulation< T > Class Template Reference

This class performs a delaunay triangulation on a given std::vector<tpoint<T> >. More...

#include <ltiDelaunayTriangulation.h>

Inheritance diagram for lti::delaunayTriangulation< T >:

[legend]

Collaboration diagram for lti::delaunayTriangulation< T >:

[legend]

List of all members.

Classes
class	parameters
	the parameters for the class delaunayTriangulation More...
Public Member Functions
	delaunayTriangulation ()
	delaunayTriangulation (const parameters &par)
	delaunayTriangulation (const delaunayTriangulation &other)
virtual	~delaunayTriangulation ()
virtual const char *	getTypeName () const
bool	apply (const std::vector< tpoint< T > > &src, std::vector< int > &triangles)
delaunayTriangulation &	copy (const delaunayTriangulation &other)
delaunayTriangulation &	operator= (const delaunayTriangulation &other)
virtual functor *	clone () const
const parameters &	getParameters () const

---

Detailed Description

template<class T>
class lti::delaunayTriangulation< T >

This class performs a delaunay triangulation on a given std::vector<tpoint<T> >.

A triangulation T of a given set of points P is called Delaunay if the circumcircle of any triangle of T does not contain a point of P. The triangulation is therefore angle-optimal. A triangulation T is angle-optimal if the sorted vector of angles A(T)=(alpha_1,alpha_2,...,alpha_3m) is the largest angle-vector. An angle vector A(T) is larger then A(T') if there exists an i so that alpha_j = alpha'_j for every j < i and alpha_i > alpha'_i. Optimal triangulations avoid "skinny" triangles. The implemented algorithm is in O(n*log(n)) where n is the number of points. The discription of the algorithm can be found in: de Berg, van Krefeld: Computational Geometry (Chapter 9: Delaunay Triangulations).

Note: Depending on the supplied data this algorithm may fail due to numerical and implementation issues. It usually works well for points that correspond to pixel positions in a image. For other uses adjusting the parameters::epsilon and parameters::specialPointsFactor will probably lead to a satisfactory result.

This failure can manifest itself in two ways:

• An assertion (l != 4) is thrown in debug mode (a segmentation fault in release). Probably need higher value for parameters::specialPointsFactor
• There are edges missing on the convex hull, solve as above.

---

Constructor & Destructor Documentation

template<class T >

lti::delaunayTriangulation< T >::delaunayTriangulation

(

)

default constructor

template<class T >

lti::delaunayTriangulation< T >::delaunayTriangulation

(

const parameters &

par

)

Construct a functor using the given parameters.

template<class T >

lti::delaunayTriangulation< T >::delaunayTriangulation

(

const delaunayTriangulation< T > &

other

)

copy constructor

Parameters:

other

the object to be copied

template<class T >

virtual lti::delaunayTriangulation< T >::~delaunayTriangulation

(

)

[virtual]

destructor

---

Member Function Documentation

template<class T >

bool lti::delaunayTriangulation< T >::apply	(	const std::vector< tpoint< T > > &	src,
		std::vector< int > &	triangles
	)

Performing a delaunay triangulation on the given set of points and storing the result in 'triangles'.

Parameters:

	src	the source data.
	triangles	a std::vector containing the triangles as a result of the delaunay triangulation. the indices 0..2 belong to the first triangle, 3..5 to the second, and so on.

Returns:

true if successful or false otherwise.

template<class T >

virtual functor* lti::delaunayTriangulation< T >::clone

(

)

const [virtual]

returns a pointer to a clone of this functor.

Implements lti::functor.

template<class T >

delaunayTriangulation& lti::delaunayTriangulation< T >::copy

(

const delaunayTriangulation< T > &

other

)

copy data of "other" functor.

Parameters:

other

the functor to be copied

Returns:

a reference to this functor object

Reimplemented from lti::functor.

template<class T >

const parameters& lti::delaunayTriangulation< T >::getParameters

(

)

const

returns used parameters

Reimplemented from lti::functor.

template<class T >

virtual const char* lti::delaunayTriangulation< T >::getTypeName

(

)

const [virtual]

returns the name of this type ("delaunayTriangulation")

Reimplemented from lti::functor.

template<class T >

delaunayTriangulation& lti::delaunayTriangulation< T >::operator=

(

const delaunayTriangulation< T > &

other

)

alias for copy member

Parameters:

other

the functor to be copied

Returns:

a reference to this functor object

Reimplemented from lti::functor.

---

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

• ltiDelaunayTriangulation.h