CUGL 2.3
Cornell University Game Library

#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 
Poly2 *  getPolygon (Poly2 *buffer) const 
std::vector< Uint32 >  getMap () const 
size_t  getMap (std::vector< Uint32 > &buffer) const 
Poly2  getMapPolygon () const 
Poly2 *  getMapPolygon (Poly2 *buffer) const 
std::vector< Poly2 >  getVoronoi () const 
Poly2  getVoronoiCell (size_t index) const 
Poly2 *  getVoronoiCell (size_t index, Poly2 *buffer) const 
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 selfcrossings). All triangles produced are guaranteed to be counterclockwise.
Note that poly2tri uses a sweepline algorithm described in
https://www.tandfonline.com/doi/abs/10.1080/13658810701492241
While most sweepline algorithms have O(n^2) time, this algorithm experimentally outperforms an O(n log n) algorithm. However, no worstcase 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 midcalculation.
cugl::DelaunayTriangulator::DelaunayTriangulator  (  ) 
Creates a triangulator with no vertex data.
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.
points  The vertices to triangulate 
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.
path  The vertices to triangulate 
cugl::DelaunayTriangulator::~DelaunayTriangulator  (  ) 
Deletes this triangulator, releasing all resources.
void cugl::DelaunayTriangulator::addHole  (  const Path2 &  path  ) 
Adds the given hole to the triangulation.
The hole path should be a closed path with no selfcrossings. 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..n1, 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.
path  The hole path 
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 selfcrossings. 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..n1, 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.
points  The hole vertices 
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 selfcrossings. 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..n1, 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.
points  The hole vertices 
size  The number of vertices 
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.
point  The Steiner point 
void cugl::DelaunayTriangulator::calculate  (  ) 
Performs a triangulation of the current vertex data.
This only calculates the triangulation. It does not compute the Voronoi dual.
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.
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.
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.
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.
buffer  The buffer to store the extended triangulation map 
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.
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.
buffer  The buffer to store the triangulated polygon 
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.
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.
buffer  The buffer to store the triangulated polygon 
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.
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.
buffer  The buffer to store the triangulation indices 
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.
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
index  The index of the vertex generating the cell 
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.
index  The index of the vertex generating the cell 
buffer  The buffer to store the Voronoi cell 
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.
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 counterclockwise 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 readd any lost data and reperform the calucation.
path  The vertices to triangulate 
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 counterclockwise 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 readd any lost data and reperform the calucation.
points  The vertices to triangulate 
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 counterclockwise 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 readd any lost data and reperform the calucation.
points  The vertices to triangulate 
size  The number of vertices 