Programmer's Documentation

Classes | Public Types | Public Member Functions | Private Attributes | List of all members
DcEdge Class Reference

Detailed Description

Butterfly edge for Delaunay algorithms.

DcEdge is the main data structure for the algorithms implemented in class DelaunayCore. It stores source and target vertex indices along with two face indices which reference a face array in DelaunayCore.

Pointers to DcEdge are stored in a hash map (boost::unordered_set), hashed by source and target vertex indices.

  • Pack flags into the high bits of the face indices -> 16 byte edge size
  • Store vertex indices+1 to avoid zero key in integer table
  • Make key function return first 8 bytes as uint64_t
See Also
DelaunayCore, DcFace

#include <dcedge.h>


struct  Hasher
 Computes hash value from vertex indices. More...
struct  PtrEqual
 Compares two edges for equality with respect to vertex indices. More...
struct  PtrLess
 Establish ordering between two edges with respect to vertex indices. More...

Public Types

enum  Flags {
  None = 0, Constrained = 1, Feature = 2, NeverSplit = 4,
  SurfaceIntersection = 11

Public Member Functions

 DcEdge ()
 create undefined edge
 DcEdge (uint32_t s, uint32_t t)
 create edge with source and target vertex only
bool checkFlag (int f) const
 test flag
void setFlag (int f)
 set flag
void unsetFlag (int f)
 unset flag
int getFlags () const
 access flags
int topoId () const
 return topo edge id embedded in high bits
void topoId (int id)
 embed topo edge id in high flag bits
bool canFlip () const
 check whether edge is allowed to flip
bool valid () const
 check whether edge is defined
void invalidate ()
 mark as invalid
uint32_t source () const
 access source vertex
uint32_t target () const
 access target vertex
bool connects (uint32_t s, uint32_t t) const
 check for equality
const uint32_t * faces () const
 access neighbor face indices
uint32_t nfaces () const
 number of defined face neighbors
uint32_t left () const
 access left neighbor face
uint32_t right () const
 access left neighbor face
uint32_t otherFace (uint32_t f) const
 face opposed to face f
void assign (uint32_t s, uint32_t t)
 set source and target vertices
uint32_t degree () const
 number of faces present
bool operator< (const DcEdge &e) const
 define sort order
bool operator== (const DcEdge &e) const
 define equality
uint32_t appendFace (uint32_t f)
 append face to neighbor set
void assignFaces (uint32_t f1, uint32_t f2)
 assign neighbor face indices
bool replaceFace (uint32_t k1, uint32_t k2)
 replace face index k1 with k2
bool replaceFace (uint32_t fr, uint32_t fl, uint32_t k2)
 replace face index fr or fl with k2

Private Attributes

uint32_t vix [2]
 source and target vertex indices, src < trg
uint32_t fix [2]
 left and right faces
int32_t flags
 bitmap for various edge properties

Member Enumeration Documentation


Normal, free edge.


Edge is part of a constraint.


Feature edge, should not be flipped.


Edge should never be split.


Edge is on a surface intersection.

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