Fade_2D is the Delaunay triangulation main class. More...
#include <Fade_2D.h>
Public Member Functions  
Fade_2D (unsigned numExpectedVertices=3)  
Constructor of the main triangulation class. More...  
~Fade_2D ()  
Destructor.  
void  exportTriangulation (FadeExport &fadeExport, bool bWithCustomIndices, bool bClear) 
Export triangulation data from Fade. More...  
bool  checkValidity (bool bCheckEmptyCircleProperty, const char *msg) const 
Checks if a triangulation is valid. More...  
int  setNumCPU (int numCPU) 
Set the number CPU cores for multithreading. More...  
void  setFastMode (bool bFast) 
Set fast mode. More...  
void  statistics (const char *s) const 
Statistics. More...  
void  show (const char *postscriptFilename, bool bWithConstraints=true) const 
Draws the triangulation as postscript file. More...  
void  show (Visualizer2 *pVis, bool bWithConstraints=true) const 
Draws the triangulation as postscript file using an existing Visualizer2 object. More...  
void  remove (Point2 *pVertex) 
Remove a single vertex. More...  
void  getConvexHull (bool bAllVertices, std::vector< Point2 * > &vConvexHullPointsOut) 
Compute the convex hull. More...  
Point2 *  insert (const Point2 &p) 
Insert a single point. More...  
void  insert (const std::vector< Point2 > &vInputPoints) 
Insert a vector of points. More...  
void  insert (const std::vector< Point2 > &vInputPoints, std::vector< Point2 * > &vHandles) 
Insert points from a std::vector and store pointers in vHandles. More...  
void  insert (int numPoints, double *aCoordinates, Point2 **aHandles) 
Insert points from an array. More...  
double  measureTriangulationTime (std::vector< Point2 > &vPoints) 
Measure the Delaunay triangulation time. More...  
Triangle2 *  locate (const Point2 &p) 
Locate a triangle which contains p. More...  
void  refine (Zone2 *pZone, double minAngleDegree, double minEdgeLength, double maxEdgeLength, bool bAllowConstraintSplitting) 
Delaunay refinement. More...  
void  refineAdvanced (MeshGenParams *pParameters) 
Delaunay refinement and grid meshing. More...  
size_t  numberOfPoints () const 
Number of points. More...  
size_t  numberOfTriangles () const 
Number of triangles. More...  
void  getTrianglePointers (std::vector< Triangle2 * > &vAllTriangles) const 
Get pointers to all triangles. More...  
void  getVertexPointers (std::vector< Point2 * > &vAllPoints) const 
Get pointers to all vertices. More...  
Triangle2 *  getAdjacentTriangle (Point2 *p0, Point2 *p1) const 
Get adjacent triangle. More...  
bool  hasArea () const 
Check if the triangulation contains triangles (which is the case if at least 3 noncollinear points exist in the triangulation. More...  
ConstraintGraph2 *  createConstraint (std::vector< Segment2 > &vSegments, ConstraintInsertionStrategy cis, bool bOrientedSegments=false) 
Add constraint edges (edges, polyline, polygon) More...  
Zone2 *  createZone (ConstraintGraph2 *pConstraintGraph, ZoneLocation zoneLoc, bool bVerbose=true) 
Create a zone. More...  
Zone2 *  createZone (const std::vector< ConstraintGraph2 * > &vConstraintGraphs, ZoneLocation zoneLoc, const Point2 &startPoint, bool bVerbose=true) 
Create a zone limited by multiple ConstraintGraph2 objects by growing from a start point. More...  
Zone2 *  createZone (ConstraintGraph2 *pConstraintGraph, ZoneLocation zoneLoc, const Point2 &startPoint, bool bVerbose=true) 
Create a zone limited by a ConstraintGraph by growing from a start point. More...  
Zone2 *  createZone (std::vector< Triangle2 * > &vTriangles, bool bVerbose=true) 
Create a zone defined by a vector of triangles. More...  
void  deleteZone (Zone2 *pZone) 
Delete a Zone2 object. More...  
void  applyConstraintsAndZones () 
Apply conforming constraints and zones (deprecated!) More...  
Bbox2  computeBoundingBox () const 
Compute the axisaligned bounding box of the points. More...  
bool  isConstraint (Triangle2 *pT, int ith) const 
Check if an edge is a constraint edge. More...  
void  getAliveConstraintSegments (std::vector< ConstraintSegment2 * > &vAliveConstraintSegments) const 
Get active (alive) constraint segments.  
void  getAliveAndDeadConstraintSegments (std::vector< ConstraintSegment2 * > &vAllConstraintSegments) const 
Get all (alive and dead) constraint segments.  
ConstraintSegment2 *  getConstraintSegment (Point2 *p0, Point2 *p1) const 
Retrieve a ConstraintSegment2. More...  
void  getIncidentTriangles (Point2 *pVtx, std::vector< Triangle2 * > &vIncidentT) const 
Get incident triangles. More...  
void  getIncidentVertices (Point2 *pVtx, std::vector< Point2 * > &vIncidentVertices) const 
Get incident vertices. More...  
void  writeObj (const char *filename) const 
Write the current triangulation to an *.obj file. More...  
void  writeObj (const char *filename, Zone2 *pZone) const 
Write a zone to an *.obj file. More...  
void  writeWebScene (const char *path) const 
Write the current triangulation to an *.obj file. More...  
void  writeWebScene (const char *path, Zone2 *pZone) const 
Write a zone to an *.obj file. More...  
void  subscribe (MsgType msgType, MsgBase *pMsg) 
Register a message receiver. More...  
void  unsubscribe (MsgType msgType, MsgBase *pMsg) 
Unregister a message receiver. More...  
bool  isConstraint (Point2 *p0, Point2 *p1) const 
Check if an edge is a constraint edge. More...  
bool  isConstraint (Point2 *pVtx) const 
Check if a vertex is a constraint vertex. More...  
void  printLicense () const 
Prints license information.  
Zone2 *  importTriangles (std::vector< Point2 > &vPoints, bool bReorientIfNeeded, bool bCreateExtendedBoundingBox) 
Import triangles. More...  
Orientation2  getOrientation (const Point2 &p0, const Point2 &p1, const Point2 &p2) 
Compute the orientation of 3 points. More...  
void  cutTriangles (const Point2 &knifeStart, const Point2 &knifeEnd, bool bTurnEdgesIntoConstraints) 
Cut through a triangulation. More...  
void  cutTriangles (std::vector< Segment2 > &vSegments, bool bTurnEdgesIntoConstraints) 
Cut through a triangulation. More...  
Zone2 *  createZone_cookieCutter (std::vector< Segment2 > &vSegments, bool bProtectEdges) 
Cookie Cutter The Cookie Cutter cuts out a part of a triangulation and returns it as a Zone2 object. More...  
bool  drape (std::vector< Segment2 > &vSegmentsIn, std::vector< Segment2 > &vSegmentsOut) const 
Drape segments along a surface. More...  
void  enableMultithreading () 
Enable multithreading (deprecated) More...  
Fade_2D is the Delaunay triangulation main class.
Fade_2D represents a Delaunay triangulation in 2D or 2.5D (depends on the used namespace)

inlineexplicit 
Constructor of the main triangulation class.
numExpectedVertices  specifies the number of points that will be inserted. This is a default parameter that does not need to be specified. 
void Fade_2D::applyConstraintsAndZones  (  ) 
Apply conforming constraints and zones (deprecated!)
This method establishes conforming constraint segments and zones which depend on them. For technical reasons conforming constraint segments are not immediately established but inserted at the end of the triangulation process. This step must be triggered manually i.e., it is up to the user to call applyConstraintsAndZones() before the resulting triangulation is used. If afterwards the triangulation is changed in any way, applyConstraintsAndZones() must be called again.
bool Fade_2D::checkValidity  (  bool  bCheckEmptyCircleProperty, 
const char *  msg  
)  const 
Checks if a triangulation is valid.
Checks the validity of the data structure.
bCheckEmptyCircleProperty  specifies if (slow!) multiprecision arithmetic shall be used to recheck the empty circle property 
msg  is a debug string that will be shown in terminal output so that you know which checkValidity call currently runs. 
This method is thought for development purposes. Don't call it method unless you assume that something is wrong with the code.
Bbox2 Fade_2D::computeBoundingBox  (  )  const 
Compute the axisaligned bounding box of the points.
If no points have been inserted yet, then the returned Bbox2 object is invalid and its member function Bbox2::isValid() returns false.
ConstraintGraph2* Fade_2D::createConstraint  (  std::vector< Segment2 > &  vSegments, 
ConstraintInsertionStrategy  cis,  
bool  bOrientedSegments = false 

) 
Add constraint edges (edges, polyline, polygon)
vSegments  are segments which shall appear as edges of the triangulation. The segments may be automatically reordered and reoriented, see bOrientedSegments below. 
cis  is the ConstraintInsertionStrategy. Use always CIS_CONSTRAINED_DELAUNAY. This mode inserts the constraint segments at their original level (no projection onto the surface) and without subdivision unless existing vertices or existing constraint segments are crossed. When subdivision (e.g., to achieve better triangle shapes) is desired then use ConstraintGraph2::makeDelaunay() after insertion. When the segments shall be adapted to the elevation of the existing surface then use Fade_2D::drape(). See the example code in examples_25D/terrain.cpp 
bOrientedSegments  specifies whether the segments in vSegments are oriented (oriented, not ordered!). To maintain backwards compatibility bOrientedSegments is a default parameter and it defaults to false. Fade will maintain the orientation of the segments only when bOrientedSegments=true . This regards functions like ConstraintGraph2::getPolygonVertices() when the order of the returned vertices is important. Another consequence is when later a Zone2 object shall be constructed from this ConstraintGraph2. This is only possible if either this value is true (then the algorithm will assume that all segments exist in counterclockwise orientation) or when the value is false and the segments can be automatically reoriented and reordered such that they form one closed polygon. 
Zone2* Fade_2D::createZone  (  const std::vector< ConstraintGraph2 * > &  vConstraintGraphs, 
ZoneLocation  zoneLoc,  
const Point2 &  startPoint,  
bool  bVerbose = true 

) 
Create a zone limited by multiple ConstraintGraph2 objects by growing from a start point.
A Zone2 object is an area of the traingulation, see createZone
vConstraintGraphs  is a vector of ConstraintGraph objects 
zoneLoc  must be ZL_GROW 
startPoint  is the point from which the area is grown until the borders specified in vConstraintGraphs are reached 
bVerbose  is by default true and causes a warning if NULL is returned. 
Zone2* Fade_2D::createZone  (  ConstraintGraph2 *  pConstraintGraph, 
ZoneLocation  zoneLoc,  
bool  bVerbose = true 

) 
Create a zone.
A Zone2 object is an area of a triangulation, possibly bounded by a ConstraintGraph.
zoneLoc  is ZL_INSIDE, ZL_OUTSIDE or ZL_GLOBAL. 
pConstraintGraph  points to a formerly created ConstraintGraph2 object (which must be oriented and contain a simple polygon) or is NULL in case of zoneLoc==ZL_GLOBAL. 
bVerbose  is by default true and causes a warning if NULL is returned. 
Zone2* Fade_2D::createZone  (  ConstraintGraph2 *  pConstraintGraph, 
ZoneLocation  zoneLoc,  
const Point2 &  startPoint,  
bool  bVerbose = true 

) 
Create a zone limited by a ConstraintGraph by growing from a start point.
A Zone2 object is an area of the traingulation, see createZone
pConstraintGraph  is a constraint whose edges specify the area's border 
zoneLoc  must be ZL_GROW 
startPoint  is the point from which the area is grown until the borders specified in pConstraint are reached 
bVerbose  is by default true and causes a warning if NULL is returned. 
Create a zone defined by a vector of triangles.
A Zone2 object is an area of the traingulation, see createZone
vTriangles  
bVerbose  is by default true and causes a warning if NULL is returned. 
Cookie Cutter The Cookie Cutter cuts out a part of a triangulation and returns it as a Zone2 object.
[in]  vSegments  specifies a simple polygon. 
[in]  bProtectEdges  specifies if existing triangles shall be protected with constraint segments. 
Properties: The input polygon ( vSegments
) does not need to have certain height values, the zcoordinates are computed automatically. The input polygon is automatically trimmed when it is outside the convex hull of the triangulation. Insertion of intersection points may flip existing edges in the triangulation but this can be avoided using bProtectEdges=true. In this case new constraint edges may be created.
void Fade_2D::cutTriangles  (  const Point2 &  knifeStart, 
const Point2 &  knifeEnd,  
bool  bTurnEdgesIntoConstraints  
) 
Cut through a triangulation.
knifeStart  is one point of the knife segment 
knifeEnd  is the second point of the knife segment 
bTurnEdgesIntoConstraints  turns all 3 edges of each intersected triangle into constraint segments. 
This method inserts a constraint edge knife(knifeStart,knifeEnd). If existing edges E are intersected by knife, then knife is subdivided at the intersection points P.
In any case knife will exist (in a possibly subdivided form) in the result. But a consequence of the insertion of the points P is that the edges E and even edges which are not intersected by knife may be flipped. Use bTurnEdgesIntoConstraints=true to avoid that.
void Fade_2D::cutTriangles  (  std::vector< Segment2 > &  vSegments, 
bool  bTurnEdgesIntoConstraints  
) 
Cut through a triangulation.
vSegments  are the knife segments 
bTurnEdgesIntoConstraints  specifies if intersected edges shall automatically be turned into constraints 
Same method as void cutTriangles(const Point2& knifeStart,const Point2& knifeEnd,bool bTurnEdgesIntoConstraints) but it takes a vector of segments instead of a single segment. This is the recommended method to cut through a triangulation when more than one knife segment exists.
void Fade_2D::deleteZone  (  Zone2 *  pZone  ) 
Delete a Zone2 object.
Zone2 objects are automatically destroyed with their Fade_2D objects. In addition this method provides the possibility to eliminate Zone2 objects earlier.
bool Fade_2D::drape  (  std::vector< Segment2 > &  vSegmentsIn, 
std::vector< Segment2 > &  vSegmentsOut  
)  const 
Drape segments along a surface.
Projects the segments from vSegmentsIn
onto the triangulation. Thereby the segments are subdivided where they intersect edges of the triangulation. Segment parts outside the triangulation are cut off and ignored. Degenerate input segments are also ignored.
The heights (zvalues) of the result segments are adapted to the surface.
[in]  zTolerance  is used to avoid excessive subdivision of segments. Use some positive value to define the acceptable geometric error or use zTolerance=1.0 to split the segments at all intersections with triangulationedges. 
[in]  zTolerance  defines the acceptable zerror 
[in]  vSegmentsIn  Input segments 
[out]  vSegmentsOut  Output segments 
void Fade_2D::enableMultithreading  (  ) 
Enable multithreading (deprecated)
Deprecated: Use setNumCPU() instead. This method is kept for compatibility with existing applications. Internally it calls setNumCPU(0) to automatically determine and use the number of available CPU cores.
void Fade_2D::exportTriangulation  (  FadeExport &  fadeExport, 
bool  bWithCustomIndices,  
bool  bClear  
) 
Export triangulation data from Fade.
fadeExport  is a struct that will hold the requested triangulation data 
bWithCustomIndices  determines whether the custom indices of the points are also stored 
bClear  determines whether the Fade instance is cleared during the export operation to save memory 
Get adjacent triangle.
ConstraintSegment2* Fade_2D::getConstraintSegment  (  Point2 *  p0, 
Point2 *  p1  
)  const 
Retrieve a ConstraintSegment2.
void Fade_2D::getConvexHull  (  bool  bAllVertices, 
std::vector< Point2 * > &  vConvexHullPointsOut  
) 
Compute the convex hull.
bAllVertices  determines if all convex hull points are returned or if collinear ones shall be removed.  
[out]  vConvexHullPointsOut  is used to return the convex hull vertices in counterclockwise order. The start vertex is the leftmost vertex. If more than one leftmost vertex exists, the bottommost of them is the start vertex. 
Get incident triangles.
Stores pointers to all triangles around pVtx into vIncidentT
void Fade_2D::getIncidentVertices  (  Point2 *  pVtx, 
std::vector< Point2 * > &  vIncidentVertices  
)  const 
Get incident vertices.
Stores pointers to all vertices around pVtx into vIncidentVertices
Compute the orientation of 3 points.
void Fade_2D::getTrianglePointers  (  std::vector< Triangle2 * > &  vAllTriangles  )  const 
Get pointers to all triangles.
This command fetches the existing triangles
[out]  vAllTriangles  is used to return the triangles 
void Fade_2D::getVertexPointers  (  std::vector< Point2 * > &  vAllPoints  )  const 
Get pointers to all vertices.
vAllPoints  is an empty vector of Point2 pointers. 
Stores pointers to all vertices of the triangulation in vAllPoints. The order in which the points are stored is not necessarily the insertion order. For geometrically identical points which have been inserted multiple times, only one pointer exists. Thus vAllPoints.size() can be smaller than the number of inserted points.
bool Fade_2D::hasArea  (  )  const 
Check if the triangulation contains triangles (which is the case if at least 3 noncollinear points exist in the triangulation.
As long as all inserted points are collinear the triangulation does not contain triangles. This is clearly the case as long as less than three input points are present but it may also be the case when 3 or more points have been inserted when all these points are collinear. These points are then in a pending state, i.e. they will be triangulated as soon as the first noncollinear point is inserted.
Zone2* Fade_2D::importTriangles  (  std::vector< Point2 > &  vPoints, 
bool  bReorientIfNeeded,  
bool  bCreateExtendedBoundingBox  
) 
Import triangles.
This method imports triangles into an empty Fade object. The triangles do not need to satisfy the empty circle property.
vPoints  contains the input vertices (3 subsequent ones per triangle) 
bReorientIfNeeded  specifies if the orientations of the point triples shall be checked and corrected. If the point triples are certainly oriented in counterclockwise order then the orientation test can be skipped. 
bCreateExtendedBoundingBox  can be used to insert 4 dummy points of an extended bounding box. This is convenient in some cases. Use false if you are unsure. 
Insert a single point.
p  is the point to be inserted. 
The triangulation keeps a copy of p. The return value is a pointer to this copy. If duplicate points are inserted, the triangulation does not create new copies but returns a pointer to the copy of the very first insertion.
void Fade_2D::insert  (  const std::vector< Point2 > &  vInputPoints  ) 
Insert a vector of points.
vInputPoints  contains the points to be inserted. 
void Fade_2D::insert  (  const std::vector< Point2 > &  vInputPoints, 
std::vector< Point2 * > &  vHandles  
) 
Insert points from a std::vector and store pointers in vHandles.
vInputPoints  contains the points to be inserted. 
vHandles  (empty) is used by Fade to return Point2 pointers 
Internally, the triangulation keeps copies of the inserted points which are returned in vHandles (in the same order). If duplicate points are contained in vInputPoints then only one copy will be made and a pointer to this unique copy will be stored in vHandles for every occurance.
void Fade_2D::insert  (  int  numPoints, 
double *  aCoordinates,  
Point2 **  aHandles  
) 
Insert points from an array.
numPoints  is the number of points to be inserted 
aCoordinates  is an array of 2n double values, e.g. {x0,y0,x1,y1,...,xn,yn} 
aHandles  is an empty array with size n where pointers to the inserted points will be stored by Fade 
Check if an edge is a constraint edge.
Returns whether the edge (p0,p1) is a constraint edge.
bool Fade_2D::isConstraint  (  Point2 *  pVtx  )  const 
Check if a vertex is a constraint vertex.
Returns whether the vertex pVtx
belongs to a constraint edge.
bool Fade_2D::isConstraint  (  Triangle2 *  pT, 
int  ith  
)  const 
Check if an edge is a constraint edge.
Returns whether the edge in triangle pT which is opposite to the ith vertex is a constraint edge.
Locate a triangle which contains p.
The Fade_2D class can be used as a data structure for point location. This method returns a pointer to a triangle which contains p.
p  is the query point 
double Fade_2D::measureTriangulationTime  (  std::vector< Point2 > &  vPoints  ) 
Measure the Delaunay triangulation time.
This method evaluates the performance of single and multithreaded point insertion into a Delaunay triangulation.
[in]  vPoints  are the points to be inserted 
size_t Fade_2D::numberOfPoints  (  )  const 
Number of points.
size_t Fade_2D::numberOfTriangles  (  )  const 
Number of triangles.
void Fade_2D::refine  (  Zone2 *  pZone, 
double  minAngleDegree,  
double  minEdgeLength,  
double  maxEdgeLength,  
bool  bAllowConstraintSplitting  
) 
Delaunay refinement.
Creates a mesh inside the area given by a Zone2 object.
pZone  is the zone whose triangles are refined. Allowed zoneLocation values are ZL_INSIDE and ZL_BOUNDED. 
minAngleDegree  (up to 30) is the minimum interior triangle angle 
minEdgeLength  is a lower threshold on the edge length. Triangles with smaller edges are not refined. 
maxEdgeLength  is an upper threshold on the edge length. Triangles with larger edges are always refined. 
bAllowConstraintSplitting  specifies if constraint edges may be splitted 
void Fade_2D::refineAdvanced  (  MeshGenParams *  pParameters  ) 
Delaunay refinement and grid meshing.
This method calls an advanced Delaunay mesh generator and grid mesher. The parameters are encapsulated in the MeshGenParams class. This class provides default parameters that can be used as is. Alternatively client code can derive from MeshGenParams and overwrite the methods and parameters to gain full control over the mesh generation process.
void Fade_2D::remove  (  Point2 *  pVertex  ) 
Remove a single vertex.
pVertex  shall be removed. 
pVertex
must not be a vertex of a ConstraintGraph2 or ConstraintSegment2 object. If this is the case, the vertex is not removed and a warning is issued. void Fade_2D::setFastMode  (  bool  bFast  ) 
Set fast mode.
By default, numerically perfect calculations are performed to compute a 100% perfect Delaunay triangulation. However, the difference is hardly noticeable and only relevant in scientific applications, while practical applications may want to skip the computationally expensive calculations.
Depending on the position of the input points, the effect of the FastMode is between zero and a quite considerable acceleration.
bFast  is true when exact tests shall be avoided in favor of better performance. 
int Fade_2D::setNumCPU  (  int  numCPU  ) 
Set the number CPU cores for multithreading.
numCPU  is the number of CPU cores to be used. The special value numCPU=0 means: autodetect and use the number of available CPU cores. 
Characteristics:
void Fade_2D::show  (  const char *  postscriptFilename, 
bool  bWithConstraints = true 

)  const 
Draws the triangulation as postscript file.
show() is a convenience function for quick outputs with a default look. It is also possible to use the Visualizer2 class directly to draw arbitrary circles, line segments, vertices and labels with custom colors.
postscriptFilename  is the output name, i.e. "myFile.ps" 
bWithConstraints  specifies if constraint segments shall be shown (default: true) 
void Fade_2D::show  (  Visualizer2 *  pVis, 
bool  bWithConstraints = true 

)  const 
Draws the triangulation as postscript file using an existing Visualizer2 object.
This overload of the show() method allows to add further geometric primitives to the Visualizer2 object before it is finally written.
pVis  is the pointer of a Visualizer2 object that may already contain geometric primitives or that may later be used to draw further elements 
bWithConstraints  specifies if constraint segments shall be shown (default: true) 
void Fade_2D::statistics  (  const char *  s  )  const 
Statistics.
Prints mesh statistics to stdout.
void Fade_2D::subscribe  (  MsgType  msgType, 
MsgBase *  pMsg  
) 
Register a message receiver.
msgType  is the type of message the subscriber shall receive, e.g. MSG_PROGRESS or MSG_WARNING 
pMsg  is a pointer to a custom class derived from MsgBase 
void Fade_2D::unsubscribe  (  MsgType  msgType, 
MsgBase *  pMsg  
) 
Unregister a message receiver.
msgType  is the type of message the subscriber shall not receive anymore 
pMsg  is a pointer to a custom class derived from MsgBase 
void Fade_2D::writeObj  (  const char *  filename  )  const 
Write the current triangulation to an *.obj file.
Visualizes the current triangulation. The *.obj format represents a 3D scene.
void Fade_2D::writeObj  (  const char *  filename, 
Zone2 *  pZone  
)  const 
Write a zone to an *.obj file.
Visualizes a certain Zone2 object of the present triangulation. The *.obj format represents a 3D scene.
void Fade_2D::writeWebScene  (  const char *  path  )  const 
Write the current triangulation to an *.obj file.
Made for terrain visualizations in 2.5D but will work also for 2D.
void Fade_2D::writeWebScene  (  const char *  path, 
Zone2 *  pZone  
)  const 
Write a zone to an *.obj file.
Made for terrain visualizations in 2.5D but will work also for 2D.