Programmer's Documentation

Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
DcGeometry Class Reference

Detailed Description

Geometric criteria used in Delaunay triangulation.

DcGeometry contains geometry (as opposed to topology) information needed for generalized constrained Delaunay triangulation. It stores (at least) the 2-dimensional coordinates of each mesh vertex (s,t) in the, possibly metric, plane where the Delaunay condition is fulfilled and implements a lookup function locateTriangle which finds the triangle closest to some (e.g. newly inserted) vertex.

Child classes can overload the criteria functions (encroaches((), etc); the default implementation works in the (s,t) plane.

See Also

#include <dcgeometry.h>

Inheritance diagram for DcGeometry:
Collaboration diagram for DcGeometry:

Public Types

enum  Orient { Clockwise, Colinear, CounterClockwise }
enum  PointLoc {
  Inside, Outside, OnEdge1, OnEdge2,
  OnEdge3, OnVertex1, OnVertex2, OnVertex3,
  BeyondEdge1, BeyondEdge2, BeyondEdge3
enum  EdgeIntersection { NoEdgeIntersection = 0, EdgesIntersect, EdgesTouch, EdgesColinear }

Public Member Functions

 DcGeometry (Real stmin=-0.1, Real stmax=1.1)
 construct with default quantization range
virtual ~DcGeometry ()
 virtual destructor
virtual void reserve (uint n)
 pre-allocate space for n vertices
void quantRange (Real stmin, Real stmax)
 change quantization range
Real pointTolerance () const
 access squared min distance between points
void pointTolerance (Real sqd)
 set squared min distance between points
uint stInsertVertex (const Vct2 &pst)
 append vertex (s-t space)
const PointList< 2 > & stVertices () const
 access s-t vertices
const Vct2 & stVertex (uint k) const
 access s-t vertex
Vct2 & stVertex (uint k)
 access s-t vertex
void assign (const PointList< 2 > &pts)
 assign/copy vertex set
virtual int orientation (uint a, uint b, uint c) const
 evaluate whether a, b, c occur in counterclockwise order
int orientChanged (const uint vi[], uint a, const Vct2 &pa) const
 determine how the orientation changes when a is moved to pa
virtual int edgesIntersect (uint as, uint at, uint bs, uint bt) const
 check whether edge (as,at) intersects (bs,bt)
virtual void insertFace (const DelaunayCore &core, uint f)
 add a face to triangle search data structure (empty)
size_t insertFace (uint f, const uint vix[])
 add a face to triangle search data structure
virtual void eraseFace (const DelaunayCore &core, uint f)
 remove face from search data structure (empty)
bool eraseFace (uint, const uint vix[])
 remove face from search data structure
bool eraseFaceKey (size_t key)
 given its key, erase face from map
virtual bool encroaches (const DelaunayCore &core, const uint vf[], uint v) const
 encroachment criterion
virtual bool encroachesEdge (uint src, uint trg, uint v) const
 true if vertex encroaches ball around protected edge
virtual int locateTriangle (const DelaunayCore &core, uint v, uint &nearest) const
 locate triangle in which to find v (empty)
void remapFaces (const DelaunayCore &core)
 recompute z-ordering of all faces following vertex smoothing pass
virtual void clear ()
 clear out everything
uint calls () const
uint iterations () const

Static Public Member Functions

static int orientationPlanar (const Vct2 &pa, const Vct2 &pb, const Vct2 &pc)
 planar orientation test
static bool encroachCircle (const Vct2 &p0, const Vct2 &p1, const Vct2 &p2, const Vct2 &ptest)
 planar encroachment test
template<uint ND>
static bool encroachesBall (const SVector< ND > &ps, const SVector< ND > &pt, const SVector< ND > &v)
 point inside smallest ball touching ps and pt?

Protected Member Functions

size_t mortonKey (const uint vix[]) const
 compute Morton key for center of triangle with vertices vix[]
int walkEdge (const DelaunayCore &core, const Vct2 &pt, uint &iface) const

Protected Attributes

PointList< 2 > m_st
 vertices in the definition plane
DcIndexMap m_fmap
 keep sorted ordering of faces
Real m_qoffset
 quantization parameters
Real m_qscale
Real m_sqptsize
 squared distance at which two points are considered identical
uint ncall
 call statistics
uint niter

Member Enumeration Documentation


point is inside the triangle returned


point is outside of the domain


point is on first edge (0-1)


point is on second edge (1-2)


point is on third edge (2-0)


point matches first vertex within tolerance


point matches second vertex within tolerance


point matches third vertex within tolerance


on the outboard side of first edge


on the outboard side of second edge


on the outboard side of third edge

The documentation for this class was generated from the following files:
Generated on Mon Aug 15 2022 03:03:15 for libsurf by   doxygen 1.8.5