Programmer's Documentation

Public Types | Public Member Functions | Protected Member Functions | Private Attributes | List of all members
DelaunayCore Class Reference

Detailed Description

Delaunay triangulations.

This class encapsulates some of the core algorithms needed for constructing and refining constrained Delaunay triangulations. DelaunayCore stores the triangulation connectivity data using a butterfly edge data structure kept in a hash table, but no vertex geometry; it is therefore restricted to purely topological operations.

Geometric functions such as an encroachment predicate or a triangle location function must therefore be supplied as function objects.

This class is meant to supersede DnMesh once it supports the same functionality.

See Also
DcEdge, DcFace, DcGeometry

#include <delaunaycore.h>

Collaboration diagram for DelaunayCore:

Public Types

enum  InsertionFlag {
  NotInserted, EdgeSplit, FaceSplit, VertexPresent,
enum  StatusCode {
  StatusOk = 0, ConstraintIntersection, UnhandledMixedConstraint, CannotEnforceEdge,
  InconsistentTopology, InsertPointOutOfDomain, InsertCannotSplitEdge, InsertTriangledNotFound,
  ProtectedConstraintEncroached, NumberOfStatusCodes
typedef std::pair< DcEdge *, uint > EncPair
typedef std::vector< EncPair > FlipStack

Public Member Functions

 DelaunayCore (DcGeometry &geom, size_t reserveEdges=8192)
 empty triangulation
void enableExtension (bool flag)
 enable/disable mesh extension when vertex inserted beyond current mesh
uint addFace (uint a, uint b, uint c)
 add a new face
void addFaces (const Indices &tri)
 add multiple faces, will not check orientation (!)
void fixate ()
 compute edges from faces, update connectivity; call only in initialization
void eraseDetachedEdges ()
 erase edges which are not connected to any faces any more
void triangles (Indices &tri) const
 export triangles
void constrainedEdges (Indices &lns) const
 export constrained line segments
void vertexMap (uint nv, ConnectMap &v2f) const
 compute vertex-to-face connectivity
uint nAllFaces () const
 number of faces, inclusing invalid ones
uint nValidFaces () const
 number of valid faces
const DcFaceface (uint f) const
 access face f
int insertVertex (uint c, bool legalizeEdges=true)
 Vertex insertion. More...
uint insertConstraint (const Indices &c, int flags=DcEdge::Constrained, bool legalizeEdges=true)
 Constraint insertion. More...
void setEdgeFlags (int pattern, int flags)
 change internal treatment of special edges by setting flag bits
void unsetEdgeFlags (int pattern, int flags)
 change internal treatment of special edges by un-setting flag bits
void protectConstraints (bool flag)
 protect constrained edges by ball where insertions are forbidden
bool splitEdge (DcEdge *pab, uint c, bool legalizeEdges=true)
 split edge a-b, insert new vertex c in the middle
bool splitFace (uint f, uint x, bool legalizeEdges=true)
 split face f, insert vertex x
void addExternalVertex (DcEdge *pab, uint c, bool legalizeEdges=true)
 extend triangulation : construct triangle using pab and vertex c
const Indices & verticesOnConstraints () const
 access list of vertices inserted into constrained edges
Indices & verticesOnConstraints ()
 access list of vertices inserted into constrained edges
bool flipEdge (DcEdge *pe)
 flip edge, update connectivity
uint eatHole (uint f)
 eat triangles away, starting at face f, stop at constraints
uint eraseFacesTouching (const Indices &idx)
 erase all faces connected to any of the sorted vertices in idx
DcEdgefindEdge (uint s, uint t) const
 locate edge, return 0 if not found
DcEdgeconstructEdge (uint s, uint t)
 construct edge
bool diamond (DcEdge *pe, uint v[]) const
 collect vertex diamond for edge pe
bool isConvex (const uint v[]) const
 test whether a four-node neighborhood is convex
void constrainedVertices (std::vector< bool > &cvx, int edgeflag=DcEdge::Constrained) const
 mark all constrained vertices
void boundaryVertices (std::vector< bool > &bvx) const
 mark boundary vertices
void clear ()
 remove all contents, release memory
int lastStatusCode () const
 access status code (set when operation not successful)

Protected Member Functions

DcEdgeconstructEdge (const DcEdge &e)
 copy construct edge
void eraseEdge (DcEdge *pe)
 erase edge from set and cache
uint angOpposedVertex (uint t, uint topo) const
 given two adjacent faces, return vertex of topo not in t (Anglada 1997)
uint angOpposedFace (uint t, uint p) const
 return face adjacent to t which does not contain v
void triangulatePolygon (uint bs, uint bt, Indices::const_iterator vbeg, Indices::const_iterator vend)
 triangulate the polygon given by a sorted vertex set (vbeg,vend]
void eraseFace (uint k)
 invalidate face
void detachFace (uint k)
 detach reference to face k from the edges of k
void legalizeEdge (uint src, uint trg, uint v)
 legalize edge pe with respect to vertex v
void legalizeEdge (DcEdge *pe, uint v)
 legalize edge pe with respect to vertex v
DcEdgesearchCacheForFlip (uint s, uint t) const
 search face cache for edge which may be flipped to obtain (s,t)
bool extendCache ()
 extend face cache with immediate neighbor elements
DcEdgeimprintIntersectingEdge (uint csrc, uint ctrg)
 enforce the presence of edge (src,trg) by erasing and retriangulating
DcEdgeimprintOverlappingEdge (uint csrc, uint ctrg)
 enforce the presence of (src,trg) when it overlaps existing edges
void carveAndTriangulate (uint src, uint trg, const Indices &ifaces, Indices &vleft, Indices &vright)
 called by both edge imprinting routines
void legalizeStack (FlipStack &stack)
 process an edge flip stack
void startFaceCaching ()
 start caching new faces
void stopFaceCaching ()
 stop caching new faces

Private Attributes

 geometry evaluator
boost::pool edgePool
 pool allocator for edges
DcEdgeHash edges
DcFaceArray faces
Indices invalidFaces
 list of invalid faces
Indices faceCache
 keeps track of inserted faces
Indices vinConEdges
 vertices inserted on constrained edges
StatusCode status
 code set when error occurs
bool bProtectConstraints
 forbid insertion inside ball around constrained edges?
bool bCacheFaces
 flag indicating whether new faces should be cached
bool bInsertExtend
 is mesh extension by vertex insertion allowed?

Member Function Documentation

uint DelaunayCore::insertConstraint ( const Indices &  c,
int  flags = DcEdge::Constrained,
bool  legalizeEdges = true 

Constraint insertion.

Insert constrained edges along not-yet inserted vertices c. Returns c.size() if operation successfull; returns zero if all vertices could be inserted but an edge enforcement failed, or n < c.size() if vertex n could not be inserted at all (lying on non-splittable edge, outside the domain etc.).

int DelaunayCore::insertVertex ( uint  c,
bool  legalizeEdges = true 

Vertex insertion.

Attempts to insert vertex c, return flag (InsertionFlag) indicating whether edge or face was split or vertex was found present in mesh. Optionally enforce Delaunay property by flipping edges.

The documentation for this class was generated from the following files:
Generated on Fri Sep 29 2023 03:03:15 for libsurf by   doxygen 1.8.5