Delaunay triangulation  the main class. More...
#include <Fade_2D.h>
Public Member Functions  
Fade_2D (unsigned numExpectedVertices=3)  
Constructor of the main triangulation class. More...  
bool  checkValidity (bool bCheckEmptyCircleProperty, const std::string &msg) const 
Checks if a triangulation is valid. More...  
int  setNumCPU (int numCPU) 
Set the number CPU cores for multithreading. More...  
void  statistics (const std::string &s) const 
Statistics. More...  
void  show (const std::string &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  showGeomview (const std::string &filename) 
Draws the triangulation in 3D. More...  
void  showGeomview (Visualizer3 *pVis) 
Draws the triangulation in 3D. 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  measureTrianguluationTime (std::vector< Point2 > &vPoints) 
Measure the Delaunay triangulation time. More...  
Triangle2 *  locate (const Point2 &p) 
Locate a triangle which contains p. More...  
bool  getHeight (double x, double y, double &heightOut, Triangle2 *pApproxT=NULL, double tolerance=0) const 
Compute the height of a certain point. 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  is2D () 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 formerly defined conforming constraints and zones. 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 std::string &filename) const 
Write the current triangulation to an *.obj file. More...  
void  writeObj (const std::string &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 
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...  
void  enableMultithreading () 
Enable multithreading (deprecated) More...  
Fade_2D represents a Delaunay triangulation in 2D or 2.5D (depends on the used namespace)

inlineexplicit 
numExpectedVertices  specifies the number of points that will probably be inserted. 
This is a default parameter that does not need to be specified. By default the internal data structures are initialized for 3 points and they are automatically reconfigured later if necessary.
void GEOM_FADE25D::Fade_2D::applyConstraintsAndZones  (  ) 
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 GEOM_FADE25D::Fade_2D::checkValidity  (  bool  bCheckEmptyCircleProperty, 
const std::string &  msg  
)  const 
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 GEOM_FADE25D::Fade_2D::computeBoundingBox  (  )  const 
If no points have been inserted yet, then the returned Bbox2 object is invalid and its member function Bbox2::isValid() returns false.
ConstraintGraph2* GEOM_FADE25D::Fade_2D::createConstraint  (  std::vector< Segment2 > &  vSegments, 
ConstraintInsertionStrategy  cis,  
bool  bOrientedSegments = false 

) 
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 Constraint Insertion Strategy (please compare the images):

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* GEOM_FADE25D::Fade_2D::createZone  (  ConstraintGraph2 *  pConstraintGraph, 
ZoneLocation  zoneLoc,  
bool  bVerbose = true 

) 
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 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* GEOM_FADE25D::Fade_2D::createZone  (  const std::vector< ConstraintGraph2 *> &  vConstraintGraphs, 
ZoneLocation  zoneLoc,  
const Point2 &  startPoint,  
bool  bVerbose = true 

) 
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* GEOM_FADE25D::Fade_2D::createZone  (  ConstraintGraph2 *  pConstraintGraph, 
ZoneLocation  zoneLoc,  
const Point2 &  startPoint,  
bool  bVerbose = true 

) 
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. 
Zone2* GEOM_FADE25D::Fade_2D::createZone  (  std::vector< Triangle2 *> &  vTriangles, 
bool  bVerbose = true 

) 
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. 
Zone2* GEOM_FADE25D::Fade_2D::createZone_cookieCutter  (  std::vector< Segment2 > &  vSegments, 
bool  bProtectEdges  
) 
[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 could flip existing edges in the triangulation, this can be avoided using bProtectEdges=true. The operation may create constraint segments.
void GEOM_FADE25D::Fade_2D::cutTriangles  (  const Point2 &  knifeStart, 
const Point2 &  knifeEnd,  
bool  bTurnEdgesIntoConstraints  
) 
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 GEOM_FADE25D::Fade_2D::cutTriangles  (  std::vector< Segment2 > &  vSegments, 
bool  bTurnEdgesIntoConstraints  
) 
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 GEOM_FADE25D::Fade_2D::deleteZone  (  Zone2 *  pZone  ) 
Zone2 objects are automatically destroyed with their Fade_2D objects. In addition this method provides the possibility to eliminate Zone2 objects earlier.
void GEOM_FADE25D::Fade_2D::enableMultithreading  (  ) 
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.
ConstraintSegment2* GEOM_FADE25D::Fade_2D::getConstraintSegment  (  Point2 *  p0, 
Point2 *  p1  
)  const 
void GEOM_FADE25D::Fade_2D::getConvexHull  (  bool  bAllVertices, 
std::vector< Point2 *> &  vConvexHullPointsOut  
) 
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. 
bool GEOM_FADE25D::Fade_2D::getHeight  (  double  x, 
double  y,  
double &  heightOut,  
Triangle2 *  pApproxT = NULL , 

double  tolerance = 0 

)  const 
Computes the height (z) at the coordinates x
and y
, assigns it to heightOut and returns true if successful.
[in]  x,y  are the input coordinates 
[out]  heightOut  is the computed height 
[in]  pApproxT  can be set to a nearby triangle. If unknown, use NULL. 
[in]  tolerance  is by default 0, see below 
tolerance
parameter (default: 0): If your query point is not farther outside the convex hull than tolerance
then the height of the closest point of the convex hull is returned. void GEOM_FADE25D::Fade_2D::getIncidentTriangles  (  Point2 *  pVtx, 
std::vector< Triangle2 *> &  vIncidentT  
)  const 
Stores pointers to all triangles around pVtx into vIncidentT
void GEOM_FADE25D::Fade_2D::getIncidentVertices  (  Point2 *  pVtx, 
std::vector< Point2 *> &  vIncidentVertices  
)  const 
Stores pointers to all vertices around pVtx into vIncidentVertices
Orientation2 GEOM_FADE25D::Fade_2D::getOrientation  (  const Point2 &  p0, 
const Point2 &  p1,  
const Point2 &  p2  
) 
void GEOM_FADE25D::Fade_2D::getTrianglePointers  (  std::vector< Triangle2 *> &  vAllTriangles  )  const 
This command fetches the existing triangles
[out]  vAllTriangles  is used to return the triangles 
void GEOM_FADE25D::Fade_2D::getVertexPointers  (  std::vector< Point2 *> &  vAllPoints  )  const 
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.
Zone2* GEOM_FADE25D::Fade_2D::importTriangles  (  std::vector< Point2 > &  vPoints, 
bool  bReorientIfNeeded,  
bool  bCreateExtendedBoundingBox  
) 
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. 
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 GEOM_FADE25D::Fade_2D::insert  (  const std::vector< Point2 > &  vInputPoints  ) 
vInputPoints  contains the points to be inserted. 
void GEOM_FADE25D::Fade_2D::insert  (  const std::vector< Point2 > &  vInputPoints, 
std::vector< Point2 *> &  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 GEOM_FADE25D::Fade_2D::insert  (  int  numPoints, 
double *  aCoordinates,  
Point2 **  aHandles  
) 
numPoints  is the number of points to be inserted 
aCoordinates  is an array of 3n double values, e.g. {x0,y0,z0,x1,y1,z1,...,xn,yn,zn} 
aHandles  is an array with size n where pointers to the inserted points will be stored 
bool GEOM_FADE25D::Fade_2D::is2D  (  )  const 
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.
bool GEOM_FADE25D::Fade_2D::isConstraint  (  Triangle2 *  pT, 
int  ith  
)  const 
Returns whether the edge in triangle pT which is opposite to the ith vertex is a constraint edge.
Returns whether the edge (p0,p1) is a constraint edge.
bool GEOM_FADE25D::Fade_2D::isConstraint  (  Point2 *  pVtx  )  const 
Returns whether the vertex pVtx
belongs to a constraint edge.
double GEOM_FADE25D::Fade_2D::measureTrianguluationTime  (  std::vector< Point2 > &  vPoints  ) 
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 GEOM_FADE25D::Fade_2D::numberOfPoints  (  )  const 
size_t GEOM_FADE25D::Fade_2D::numberOfTriangles  (  )  const 
void GEOM_FADE25D::Fade_2D::printLicense  (  )  const 
Prints informations about the currently used license
void GEOM_FADE25D::Fade_2D::refine  (  Zone2 *  pZone, 
double  minAngleDegree,  
double  minEdgeLength,  
double  maxEdgeLength,  
bool  bAllowConstraintSplitting  
) 
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 GEOM_FADE25D::Fade_2D::refineAdvanced  (  MeshGenParams *  pParameters  ) 
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 GEOM_FADE25D::Fade_2D::remove  (  Point2 *  pVertex  ) 
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. int GEOM_FADE25D::Fade_2D::setNumCPU  (  int  numCPU  ) 
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 GEOM_FADE25D::Fade_2D::show  (  const std::string &  postscriptFilename, 
bool  bWithConstraints = true 

)  const 
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 GEOM_FADE25D::Fade_2D::show  (  Visualizer2 *  pVis, 
bool  bWithConstraints = true 

)  const 
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 GEOM_FADE25D::Fade_2D::showGeomview  (  const std::string &  filename  ) 
void GEOM_FADE25D::Fade_2D::showGeomview  (  Visualizer3 *  pVis  ) 
void GEOM_FADE25D::Fade_2D::statistics  (  const std::string &  s  )  const 
Prints mesh statistics to stdout.
void GEOM_FADE25D::Fade_2D::subscribe  (  MsgType  msgType, 
MsgBase *  pMsg  
) 
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 GEOM_FADE25D::Fade_2D::unsubscribe  (  MsgType  msgType, 
MsgBase *  pMsg  
) 
msgType  is the type of message the subscriber shall not receive anymore 
pMsg  is a pointer to a custom class derived from MsgBase 
void GEOM_FADE25D::Fade_2D::writeObj  (  const std::string &  filename  )  const 
Visualizes the current triangulation. The *.obj format represents a 3D scene but can also be used with 2D triangles (all zvalues are zero then).
void GEOM_FADE25D::Fade_2D::writeObj  (  const std::string &  filename, 
Zone2 *  pZone  
)  const 
Visualizes a Zone2 object. The *.obj format represents a 3D scene but can also be used with 2D triangles (all zvalues are zero then).
void GEOM_FADE25D::Fade_2D::writeWebScene  (  const char *  path  )  const 
Made for terrain visualizations in 2.5D but will work also for 2D.
void GEOM_FADE25D::Fade_2D::writeWebScene  (  const char *  path, 
Zone2 *  pZone  
)  const 
Made for terrain visualizations in 2.5D but will work also for 2D.