cugl::DelaunayTriangulator Class Reference

#include <CUDelaunayTriangulator.h>

Public Member Functions
	DelaunayTriangulator ()
	DelaunayTriangulator (const std::vector< Vec2 > &points)
	DelaunayTriangulator (const Poly2 &poly)
	~DelaunayTriangulator ()
void	set (const Poly2 &poly)
void	set (const std::vector< Vec2 > &points)
void	reset ()
void	clear ()
void	calculate ()
void	calculateDual ()
std::vector< unsigned short >	getTriangulation () const
size_t	getTriangulation (std::vector< unsigned short > &buffer) const
Poly2	getPolygon () const
Poly2 *	getPolygon (Poly2 *buffer) const
std::vector< Poly2 >	getVoronoi () const
Poly2	getVoronoiCell (size_t index) const
Poly2 *	getVoronoiCell (size_t index, Poly2 *buffer) const
Poly2	getVoronoiFrame () const
Poly2 *	getVoronoiFrame (Poly2 *buffer) const
Rect	getBoundingBox () const
void	computeDelaunay (const Rect &rect)
void	computeVoronoi (const Rect &rect)
void	sortCell (size_t index, const Rect &rect)

Detailed Description

This class is a factory for producing solid Poly2 objects from a set of vertices.

For all but the simplist of shapes, it is important to have a triangulator that can divide up the polygon into triangles for drawing. This is triangulator uses the Bowyer-Watson algorithm to perform a Delaunay triangulation. This triangulation minimizes sliver triangles, which are common with ear clipping algorithms {

See also

SimpleTriangulator}.

Because the Voronoi diagram is the dual of the Delaunay triangulation, this factory can be used to extract this diagram. The Voronoi diagram can be extracted as either a wireframe or a collection of regions.

As with all factories, the methods are broken up into three phases: initialization, calculation, and materialization. To use the factory, you first set the data (in this case a set of vertices or another Poly2) with the initialization methods. You then call the calculation method. Finally, you use the materialization methods to access the data in several different ways.

This division allows us to support multithreaded calculation if the data generation takes too long. However, note that this factory is not thread safe in that you cannot access data while it is still in mid-calculation.

Constructor & Destructor Documentation

DelaunayTriangulator() [1/3]

cugl::DelaunayTriangulator::DelaunayTriangulator ( )

inline

Creates a triangulator with no vertex data.

DelaunayTriangulator() [2/3]

cugl::DelaunayTriangulator::DelaunayTriangulator ( const std::vector< Vec2 > &  points )

inline

Creates a triangulator with the given vertex data.

The vertex data is copied. The triangulator does not retain any references to the original data.

Parameters

points

The vertices to triangulate

DelaunayTriangulator() [3/3]

cugl::DelaunayTriangulator::DelaunayTriangulator ( const Poly2 &  poly )

inline

Creates a triangulator with the given vertex data.

The triangulator only uses the vertex data from the polygon. It ignores any existing indices.

The vertex data is copied. The triangulator does not retain any references to the original data.

Parameters

poly	The vertices to triangulate

~DelaunayTriangulator()

cugl::DelaunayTriangulator::~DelaunayTriangulator ( )

inline

Deletes this triangulator, releasing all resources.

Member Function Documentation

calculate()

void cugl::DelaunayTriangulator::calculate

(

)

Performs a triangulation of the current vertex data.

This method does not automatically calculate the Voronoi diagram. Call calculateDual() to do that.

calculateDual()

void cugl::DelaunayTriangulator::calculateDual

(

)

Creates a Voronoi diagram from the current vertex data.

If the method calculate() has not been called, this method will call that first. Then it will construct the Voronoi diagram.

clear()

void cugl::DelaunayTriangulator::clear ( )

inline

Clears all internal data, the initial vertex data.

When this method is called, you will need to set a new vertices before calling calculate.

computeDelaunay()

void cugl::DelaunayTriangulator::computeDelaunay

(

const Rect &

rect

)

Calculates the Delaunay triangulation.

The provided bounding box guides the initial super triangle.

Parameters

rect	the bounding box for the input vertices

computeVoronoi()

void cugl::DelaunayTriangulator::computeVoronoi

(

const Rect &

rect

)

Calculates the Voronoi diagram.

The provided bounding box guides the boundary edges.

Parameters

rect	the bounding box for the input vertices

getBoundingBox()

Rect cugl::DelaunayTriangulator::getBoundingBox

(

)

const

Returns the bounding box for the input vertices

Returns

the bounding box for the input vertices

getPolygon() [1/2]

Poly2 cugl::DelaunayTriangulator::getPolygon

(

)

const

Returns a polygon representing the triangulation.

The polygon contains the original vertices together with the new indices defining a solid shape. The triangulator does not maintain references to this polygon and it is safe to modify it.

If the calculation is not yet performed, this method will return the empty polygon.

Returns

a polygon representing the triangulation.

getPolygon() [2/2]

Poly2* cugl::DelaunayTriangulator::getPolygon

(

Poly2 *

buffer

)

const

Stores the triangulation in the given buffer.

This method will add both the original vertices, and the corresponding indices to the new buffer. If the buffer is not empty, the indices will be adjusted accordingly. You should clear the buffer first if you do not want to preserve the original data.

If the calculation is not yet performed, this method will do nothing.

Parameters

buffer

The buffer to store the triangulated polygon

Returns

a reference to the buffer for chaining.

getTriangulation() [1/2]

std::vector<unsigned short> cugl::DelaunayTriangulator::getTriangulation

(

)

const

Returns a list of indices representing the triangulation.

The indices represent positions in the original vertex list. If you have modified that list, these indices may no longer be valid.

The triangulator does not retain a reference to the returned list; it is safe to modify it.

If the calculation is not yet performed, this method will return the empty list.

Returns

a list of indices representing the triangulation.

getTriangulation() [2/2]

size_t cugl::DelaunayTriangulator::getTriangulation

(

std::vector< unsigned short > &

buffer

)

const

Stores the triangulation indices in the given buffer.

The indices represent positions in the original vertex list. If you have modified that list, these indices may no longer be valid.

The indices will be appended to the provided vector. You should clear the vector first if you do not want to preserve the original data.

If the calculation is not yet performed, this method will do nothing.

Returns

the number of elements added to the buffer

getVoronoi()

std::vector<Poly2> cugl::DelaunayTriangulator::getVoronoi

(

)

const

Returns the Voronoi diagram as a list of polygons

Each polygon represents a single Voronoi cell. A Voronoi cell is a polygon whose vertices are the boundary of the cell. The returned Poly2 object does not have indices and is free to be triangulated later. The triangulator does not maintain references to these polygons and it is safe to modify them.

Each Voronoi cell corresponds to a vertex in the original triangulation. The cells are returned in the same order as the vertices.

If the Voronoi diagram is not calculated, this method will do nothing.

Returns

the Voronoi diagram as a list of polygons

getVoronoiCell() [1/2]

Poly2 cugl::DelaunayTriangulator::getVoronoiCell

(

size_t

index

)

const

Returns the Voronoi cell for the given index

A Voronoi cell is a polygon whose vertices are the boundary of the cell. The returned Poly2 object does not have indices and is free to be triangulated later. The triangulator does not maintain references to this polygon and it is safe to modify it.

The index corresponds to the vertex in the original triangulation. If the Voronoi diagram is not calculated, this method will do nothing.

Parameters

index

The index of the vertex generating the cell

Returns

he Voronoi cell for the given index

getVoronoiCell() [2/2]

Poly2* cugl::DelaunayTriangulator::getVoronoiCell	(	size_t	index,
		Poly2 *	buffer
	)		const

Stores the Voronoi cell in the given buffer.

A Voronoi cell is a polygon whose vertices are the boundary of the cell. This method will theses vertices to the new buffer. You should clear the buffer first if you do not want to preserve the original data. No indices will be added to the buffer, and it is free to be triangulated later.

The index corresponds to the vertex in the original triangulation. If the Voronoi diagram is not calculated, this method will do nothing.

Parameters

index	The index of the vertex generating the cell
buffer	The buffer to store the Voronoi cell

Returns

a reference to the buffer for chaining.

getVoronoiFrame() [1/2]

Poly2 cugl::DelaunayTriangulator::getVoronoiFrame

(

)

const

Returns a polygon with a wireframe of the Voronoi diagram.

The polygon contains the vertices of the Voronoi diagram together with the new indices connecting the vertices as edges. The triangulator does not maintain references to this polygon and it is safe to modify it.

If the Voronoi diagram is not calculated, this method will return the empty polygon.

Returns

a polygon with a wireframe of the Voronoi diagram.

getVoronoiFrame() [2/2]

Poly2* cugl::DelaunayTriangulator::getVoronoiFrame

(

Poly2 *

buffer

)

const

Stores a wireframe of the Voronoi diagram in the given buffer.

This method will add both the Voronoi vertices, and the corresponding indices to the new buffer. If the buffer is not empty, the indices will be adjusted accordingly. You should clear the buffer first if you do not want to preserve the original data.

If the Voronoi diagram is not calculated, this method will return the empty polygon.

Parameters

buffer

The buffer to store the wireframe of the Voronoi diagram

Returns

a reference to the buffer for chaining.

reset()

void cugl::DelaunayTriangulator::reset ( )

inline

Clears all internal data, but still maintains the initial vertex data.

set() [1/2]

void cugl::DelaunayTriangulator::set ( const Poly2 &  poly )

inline

Sets the vertex data for this triangulator..

The triangulator only uses the vertex data from the polygon. It ignores any existing indices.

The vertex data is copied. The triangulator does not retain any references to the original data.

This method resets all interal data. You will need to reperform the calculation before accessing data.

Parameters

poly	The vertices to triangulate

set() [2/2]

void cugl::DelaunayTriangulator::set ( const std::vector< Vec2 > &  points )

inline

Sets the vertex data for this triangulator..

The vertex data is copied. The triangulator does not retain any references to the original data.

This method resets all interal data. You will need to reperform the calculation before accessing data.

Parameters

points

The vertices to triangulate

sortCell()

void cugl::DelaunayTriangulator::sortCell	(	size_t	index,
		const Rect &	rect
	)

Sorts the edges of the Voronoi cell so that they are adjacent.

In addition to sorting the edges, this method fills in any missing edges on the outside of the bounding box.

&

Parameters

index	the index of the Voronoi cell
rect	the bounding box for the input vertices

---

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

• include/cugl/math/polygon/CUDelaunayTriangulator.h