CUGL 2.1
Cornell University Game Library
Public Member Functions | List of all members
cugl::DelaunayTriangulator Class Reference

#include <CUDelaunayTriangulator.h>

Public Member Functions

 DelaunayTriangulator ()
 
 DelaunayTriangulator (const std::vector< Vec2 > &points)
 
 DelaunayTriangulator (const Path2 &path)
 
 ~DelaunayTriangulator ()
 
void set (const std::vector< Vec2 > &points)
 
void set (const Vec2 *points, size_t size)
 
void set (const Path2 &path)
 
void addHole (const std::vector< Vec2 > &points)
 
void addHole (const Vec2 *points, size_t size)
 
void addHole (const Path2 &path)
 
void addSteiner (Vec2 point)
 
void reset ()
 
void clear ()
 
void calculate ()
 
void calculateDual ()
 
std::vector< Uint32 > getTriangulation () const
 
size_t getTriangulation (std::vector< Uint32 > &buffer) const
 
Poly2 getPolygon () const
 
Poly2getPolygon (Poly2 *buffer) const
 
std::vector< Uint32 > getMap () const
 
size_t getMap (std::vector< Uint32 > &buffer) const
 
Poly2 getMapPolygon () const
 
Poly2getMapPolygon (Poly2 *buffer) const
 
std::vector< Poly2getVoronoi () const
 
Poly2 getVoronoiCell (size_t index) const
 
Poly2getVoronoiCell (size_t index, Poly2 *buffer) const
 

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 triangulator uses the poly2tri library to perform a Constrained Delaunay triangulation. This library supports complex polygons, namely those with interior holes (but not self-crossings). All triangles produced are guaranteed to be counter-clockwise.

Note that poly2tri uses a sweep-line algorithm described in

https://www.tandfonline.com/doi/abs/10.1080/13658810701492241

While most sweep-line algorithms have O(n^2) time, this algorithm experimentally outperforms an O(n log n) algorithm. However, no worst-case analysis on this algorithm is available.

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 single polygon (for each point) or a collection of polygons. Each polygon is a solid Poly2 representing a region.

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. Unlike the other triangulators, you cannot simply get this triangulation as a set of indices. That is because the triangulation may have added additional vertices.

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

Creates a triangulator with no vertex data.

◆ DelaunayTriangulator() [2/3]

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

Creates a triangulator with the given vertex data.

The vertices are assumed to be the outer hull, and do not include any holes (which may be specified later). The vertex data is copied. The triangulator does not retain any references to the original data.

Parameters
pointsThe vertices to triangulate

◆ DelaunayTriangulator() [3/3]

cugl::DelaunayTriangulator::DelaunayTriangulator ( const Path2 path)

Creates a triangulator with the given vertex data.

The path is assumed to be the outer hull, and does not include any holes (which may be specified later). The vertex data is copied. The triangulator does not retain any references to the original data.

Parameters
pathThe vertices to triangulate

◆ ~DelaunayTriangulator()

cugl::DelaunayTriangulator::~DelaunayTriangulator ( )

Deletes this triangulator, releasing all resources.

Member Function Documentation

◆ addHole() [1/3]

void cugl::DelaunayTriangulator::addHole ( const Path2 path)

Adds the given hole to the triangulation.

The hole path should be a closed path with no self-crossings. In addition, it is assumed to be inside the polygon outer hull, with vertices ordered in clockwise traversal. If any of these is not true, the results are undefined.

The vertex data is copied. The triangulator does not retain any references to the original data. Hole points are added after the hull points, in order. That is, when the triangulation is computed, if the hull is size n, then the hull points are indices 0..n-1, while n is the index of a hole point.

Any holes added to the triangulator will be lost if the exterior polygon is changed via the set method.

Parameters
pathThe hole path

◆ addHole() [2/3]

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

Adds the given hole to the triangulation.

The hole is assumed to be a closed path with no self-crossings. In addition, it is assumed to be inside the polygon outer hull, with vertices ordered in clockwise traversal. If any of these is not true, the results are undefined.

The vertex data is copied. The triangulator does not retain any references to the original data. Hole points are added after the hull points, in order. That is, when the triangulation is computed, if the hull is size n, then the hull points are indices 0..n-1, while n is the index of a hole point.

Any holes added to the triangulator will be lost if the exterior polygon is changed via the set method.

Parameters
pointsThe hole vertices

◆ addHole() [3/3]

void cugl::DelaunayTriangulator::addHole ( const Vec2 points,
size_t  size 
)

Adds the given hole to the triangulation.

The hole is assumed to be a closed path with no self-crossings. In addition, it is assumed to be inside the polygon outer hull, with vertices ordered in clockwise traversal. If any of these is not true, the results are undefined.

The vertex data is copied. The triangulator does not retain any references to the original data. Hole points are added after the hull points, in order. That is, when the triangulation is computed, if the hull is size n, then the hull points are indices 0..n-1, while n is the index of a hole point.

Any holes added to the triangulator will be lost if the exterior polygon is changed via the set method.

Parameters
pointsThe hole vertices
sizeThe number of vertices

◆ addSteiner()

void cugl::DelaunayTriangulator::addSteiner ( Vec2  point)

Adds the given Steiner point to the triangulation.

A Steiner point may be included in the triangulation results, but it does not have to be. Any Steiner points added to the triangulator will be lost if the exterior polygon is changed via the set method.

The vertex data is copied. The triangulator does not retain any references to the original data. Steiner points are added last. That is, when the triangulation is computed, the highest indices all refer to these points, in the order that they were provided.

Parameters
pointThe Steiner point

◆ calculate()

void cugl::DelaunayTriangulator::calculate ( )

Performs a triangulation of the current vertex data.

This only calculates the triangulation. It does not compute the Voronoi dual.

◆ calculateDual()

void cugl::DelaunayTriangulator::calculateDual ( )

Calculates the Voronoi diagram.

This will force a triangulation if one has not been computed already. In cases where triangles are missing to fully define the Voronoi diagram (such as on the boundary of the diagram), the missing triangles are interpolated.

◆ clear()

void cugl::DelaunayTriangulator::clear ( )

Clears all internal data, including the initial vertex data.

When this method is called, you will need to set a new vertices before calling calculate. In addition, any holes or Steiner points will be lost as well.

◆ getMap() [1/2]

std::vector<Uint32> cugl::DelaunayTriangulator::getMap ( ) const

Returns a list of indices representing the extended triangulation map.

The indices represent positions in the original vertex list, which included both holes and Steiner points. Positions are ordered as follows: first the exterior hull, then all holes in order, and finally the Steiner points. As these indices represent the extended triangulation, they may include triangles outside of the exterior hull.

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.

◆ getMap() [2/2]

size_t cugl::DelaunayTriangulator::getMap ( std::vector< Uint32 > &  buffer) const

Stores the extended triangulation map indices in the given buffer.

The indices represent positions in the original vertex list, which included both holes and Steiner points. Positions are ordered as follows: first the exterior hull, then all holes in order, and finally the Steiner points. As these indices represent the extended triangulation, they may include triangles outside of the exterior hull.

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.

Parameters
bufferThe buffer to store the extended triangulation map
Returns
the number of elements added to the buffer

◆ getMapPolygon() [1/2]

Poly2 cugl::DelaunayTriangulator::getMapPolygon ( ) const

Returns a polygon representing the extended triangulation map.

This polygon is the extended triangulation, which may include triangles outside of the polygon hull. It may or many not include any Steiner points that were specified.

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.

◆ getMapPolygon() [2/2]

Poly2* cugl::DelaunayTriangulator::getMapPolygon ( Poly2 buffer) const

Stores the extended triangulation map in the given buffer.

This polygon is the extended triangulation, which may include triangles outside of the polygon hull. It may or many not include any Steiner points that were specified.

This method will append the vertices to the given polygon. 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
bufferThe buffer to store the triangulated polygon
Returns
a reference to the buffer for chaining.

◆ getPolygon() [1/2]

Poly2 cugl::DelaunayTriangulator::getPolygon ( ) const

Returns a polygon representing the triangulation.

This polygon is the proper triangulation, constrained to the interior of the polygon hull. It contains the vertices of the exterior polygon, as well as any holes. It may or many not include any Steiner points that were specified.

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.

The polygon produced is the proper triangulation, constrained to the interior of the polygon hull. It contains the vertices of the exterior polygon, as well as any holes. It may or many not include any Steiner points that were specified.

This method will append the vertices to the given polygon. 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
bufferThe buffer to store the triangulated polygon
Returns
a reference to the buffer for chaining.

◆ getTriangulation() [1/2]

std::vector<Uint32> cugl::DelaunayTriangulator::getTriangulation ( ) const

Returns a list of indices representing the triangulation.

The indices represent positions in the original vertex list, which included both holes and Steiner points. Positions are ordered as follows: first the exterior hull, then all holes in order, and finally the Steiner points.

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< Uint32 > &  buffer) const

Stores the triangulation indices in the given buffer.

The indices represent positions in the original vertex list, which included both holes and Steiner points. Positions are ordered as follows: first the exterior hull, then all holes in order, and finally the Steiner points.

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.

Parameters
bufferThe buffer to store the triangulation indices
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. Each Voronoi cell corresponds to a vertex in the original triangulation.

The cells are returned in the same order as the vertices. For each cell, the Poly2 object is triangulated as a fan with the associated vertex point at its center.

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 index corresponds to the vertex in the original triangulation. The returns Poly2 object is triangulated as a fan with the associated vertex point at its center.

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

Parameters
indexThe 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. The index corresponds to the vertex in the original triangulation. The returns Poly2 object is triangulated as a fan with the associated vertex point at its center.

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

Parameters
indexThe index of the vertex generating the cell
bufferThe buffer to store the Voronoi cell
Returns
a reference to the buffer for chaining.

◆ reset()

void cugl::DelaunayTriangulator::reset ( )

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

This method also retains any holes or Steiner points. It only clears the triangulation results.

◆ set() [1/3]

void cugl::DelaunayTriangulator::set ( const Path2 path)

Sets the exterior vertex data for this triangulator.

The path is assumed to be the outer hull, and does not include any holes (which may be specified later). The path should define the hull in a counter-clockwise traversal.

The vertex data is copied. The triangulator does not retain any references to the original data. Hull points are added first. That is, when the triangulation is computed, the lowest indices all refer to these points, in the order that they were provided.

This method resets all interal data. The triangulation is lost, as well as any previously added holes or Steiner points. You will need to re-add any lost data and reperform the calucation.

Parameters
pathThe vertices to triangulate

◆ set() [2/3]

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

Sets the exterior vertex data for this triangulator.

The vertices are assumed to be the outer hull, and do not include any holes (which may be specified later). The vertices should define the hull in a counter-clockwise traversal.

The vertex data is copied. The triangulator does not retain any references to the original data. Hull points are added first. That is, when the triangulation is computed, the lowest indices all refer to these points, in the order that they were provided.

This method resets all interal data. The triangulation is lost, as well as any previously added holes or Steiner points. You will need to re-add any lost data and reperform the calucation.

Parameters
pointsThe vertices to triangulate

◆ set() [3/3]

void cugl::DelaunayTriangulator::set ( const Vec2 points,
size_t  size 
)

Sets the exterior vertex data for this triangulator.

The vertices are assumed to be the outer hull, and do not include any holes (which may be specified later). The vertices should define the hull in a counter-clockwise traversal.

The vertex data is copied. The triangulator does not retain any references to the original data. Hull points are added first. That is, when the triangulation is computed, the lowest indices all refer to these points, in the order that they were provided.

This method resets all interal data. The triangulation is lost, as well as any previously added holes or Steiner points. You will need to re-add any lost data and reperform the calucation.

Parameters
pointsThe vertices to triangulate
sizeThe number of vertices

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