HE_Mesh2014  2.0.11
Public Member Functions | Static Public Member Functions | Static Public Attributes | Protected Member Functions | Protected Attributes | Static Protected Attributes | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
wblut.geom.WB_ConstrainedTriangulation Class Reference

Public Member Functions

 WB_ConstrainedTriangulation ()
 
int size ()
 
int boundarySize ()
 
void clear ()
 
void clearFlags (final int flag)
 
boolean contains (final Tri_Point p)
 
int indexOf (final Tri_Point p)
 
Tri_Point getPoint (final int i)
 
WB_Coordinate[] getFaceCoordinates ()
 
WB_Triangle[] getExplicitTriangles ()
 
List< WB_TrianglegetExplicitTrianglesAsList ()
 
WB_Coordinate[] getPoints ()
 
void translate (final double x, final double y)
 
void startWithBoundary (final WB_Coordinate[] pts)
 
void startWithBoundary (final WB_Coordinate[] pts, final boolean reverse)
 
Tri_Point addBoundaryPoint (final Tri_Point p, final Tri_HalfEdge he0)
 
Tri_Point addInteriorPoint (final WB_Coordinate point)
 
boolean addConstraint (final int start, final int end)
 
boolean addConstraint (Tri_Point pStart, final Tri_Point pEnd)
 
void removeBoundaryPoint (final Tri_BPoint bp)
 
void removeInteriorPoint (final Tri_Point p)
 
void updateDelaunay ()
 
void updateDelaunayAll ()
 
void updateInteriorPoint (Tri_Point p)
 
void updateBoundaryPointOutside (final Tri_Point p)
 
boolean updateBoundaryPointInside (final Tri_Point p, final Tri_Point pPrev, Tri_Point pTemp)
 
void constrainAllEdges ()
 
void initRemoveConstraints (final Tri_Point p)
 
void restoreConstraints (final Tri_Point p)
 
Tri_FaceWalk findFaceBruteForce (final Tri_HalfEdge heStart, final Tri_Point p)
 
Tri_FaceWalk findFace (final Tri_HalfEdge heStart, final Tri_Point p)
 
final boolean coincident (final WB_Coordinate a, final WB_Coordinate b)
 
final boolean intersect (final WB_Coordinate a, final WB_Coordinate b, final WB_Coordinate c, final WB_Coordinate d)
 
final boolean intersectProper (final WB_Coordinate a, final WB_Coordinate b, final WB_Coordinate c, final WB_Coordinate d)
 
final boolean between (final WB_Coordinate a, final WB_Coordinate b, final WB_Coordinate c)
 
final boolean betweenProper (final WB_Coordinate a, final WB_Coordinate b, final WB_Coordinate c)
 
void listPoints ()
 
final void listHalfEdges ()
 
final void message (final String s)
 
final void message (final String s, final Object...args)
 

Static Public Member Functions

static void linkBoundary (final Tri_BPoint[] pts)
 
static final double projection (final WB_Coordinate p1, final WB_Coordinate p2, final WB_Coordinate p)
 
static final WB_Coordinate intersection (final WB_Coordinate a, final WB_Coordinate b, final WB_Coordinate c, final WB_Coordinate d)
 
static final double edgeDistanceSq (final WB_Coordinate p1, final WB_Coordinate p2, final WB_Coordinate p)
 

Static Public Attributes

static final boolean MESSAGES = false
 

Protected Member Functions

void fillQuadrilateral (final Tri_HalfEdge he1)
 
FastTable< Tri_HalfEdgeconstructPolygon (final Tri_HalfEdge he)
 
void fillGeneralPolygon (final Tri_HalfEdge he)
 
void fillGeneralPolygon (final FastTable< Tri_HalfEdge > polygon)
 
void fillEdgeVisiblePolygon (final Tri_HalfEdge he)
 
final void updateHalfEdge (final Tri_HalfEdge he)
 
final Tri_HalfEdge findPrevious (final Tri_HalfEdge he)
 
final String error (final String s)
 
final String error (final String s, final Object...args)
 

Protected Attributes

final List< Tri_Pointpoints
 
final List< Tri_HalfEdgehalfEdges
 
int nBoundary
 
LinkedList< Tri_HalfEdgedelaunayQueue = new LinkedList<Tri_HalfEdge>()
 
LinkedList< Tri_PointremovedConstraints = new LinkedList<Tri_Point>()
 
LinkedList< Tri_PointdeleteQueue = new LinkedList<Tri_Point>()
 

Static Protected Attributes

static final String E_EXHAUSTED = "Exhausted halfedges or points!"
 
static final String E_MISSING = "Missing halfedge or point!"
 
static final String E_IDENTICAL = "Identical halfedges or points!"
 
static final String E_COINCIDENT = "Coincident points!"
 
static final String E_TYPE = "Incorrect type!"
 
static final String E_POLYGON = "Illegal polygonal region!"
 
static final String E_HALFEDGE = "Mismatched halfedge!"
 
static final int NULL_VALUE = -100000
 

Private Member Functions

Tri_HalfEdge addHalfEdge (final Tri_Point origin, final Tri_Point destination)
 
Tri_HalfEdge addEdge (final Tri_HalfEdge he1, final Tri_HalfEdge he2, final Tri_HalfEdge he1prev, final Tri_HalfEdge he2prev)
 
void addConstraintEdge (final Tri_HalfEdge he1, final Tri_HalfEdge he2, final Tri_HalfEdge he1prev, final Tri_HalfEdge he2prev)
 
void fillGeneralPolygonRecurse (final FastTable< Tri_HalfEdge > polygon)
 
void fillEdgeVisiblePolygonRecurse (final FastTable< Tri_HalfEdge > polygon)
 
void splitEdge (final Tri_Point p, final Tri_HalfEdge he)
 
void splitFace (final Tri_Point p, final Tri_HalfEdge he1)
 
void splitConstraint (final Tri_HalfEdge he, final WB_Coordinate p)
 
void removeBoundaryPoint (final Tri_Point p, final Tri_Point pPrev)
 
void removePoint (final Tri_Point p)
 
void removeEdge (final Tri_HalfEdge he)
 
void floodDelete (final Tri_Point[] bounds)
 
void clearNewBoundaryEdge (final Tri_Point pStart, final Tri_Point pEnd)
 
boolean constrainEdge (final Tri_HalfEdge he)
 
boolean flipEdge (final Tri_HalfEdge he)
 

Static Private Member Functions

static final double projNorm (final WB_Coordinate a, final WB_Coordinate b, final WB_Coordinate c)
 
static final double perpDistSq (final WB_Coordinate a, final WB_Coordinate b, final WB_Coordinate c)
 

Private Attributes

Tri_Point removeConstraintPeg = null
 

Detailed Description

Represents a 2D triangulation using points (vertices) and halfedges. Triangulation is performed by an interactive constrained Delaunay algorithm. Point insertion uses Lawson's algorithm. Constraint insertion and removal, as well as vertex removal and relocation are supported.

For full details, see the "Interactive Constrained Delaunay Triangulation" section of:

Howison, M. CAD Tools for Creating Space-filling 3D Escher Tiles. Master�s thesis, U.C. Berkeley, Berkeley, CA, May 2009. (also Tech Report EECS-2009-56, http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-56.html)

Or contact the author: mark..nosp@m.howi.nosp@m.son@g.nosp@m.mail.nosp@m..com

Author
Mark Howison

Constructor & Destructor Documentation

wblut.geom.WB_ConstrainedTriangulation.WB_ConstrainedTriangulation ( )

Member Function Documentation

Tri_Point wblut.geom.WB_ConstrainedTriangulation.addBoundaryPoint ( final Tri_Point  p,
final Tri_HalfEdge  he0 
)
Parameters
p
he0
Returns
boolean wblut.geom.WB_ConstrainedTriangulation.addConstraint ( final int  start,
final int  end 
)
Parameters
start
end
Returns
boolean wblut.geom.WB_ConstrainedTriangulation.addConstraint ( Tri_Point  pStart,
final Tri_Point  pEnd 
)
Parameters
pStart
pEnd
Returns
void wblut.geom.WB_ConstrainedTriangulation.addConstraintEdge ( final Tri_HalfEdge  he1,
final Tri_HalfEdge  he2,
final Tri_HalfEdge  he1prev,
final Tri_HalfEdge  he2prev 
)
private
Parameters
he1
he2
he1prev
he2prev
Tri_HalfEdge wblut.geom.WB_ConstrainedTriangulation.addEdge ( final Tri_HalfEdge  he1,
final Tri_HalfEdge  he2,
final Tri_HalfEdge  he1prev,
final Tri_HalfEdge  he2prev 
)
private
Parameters
he1
he2
he1prev
he2prev
Returns
Tri_HalfEdge wblut.geom.WB_ConstrainedTriangulation.addHalfEdge ( final Tri_Point  origin,
final Tri_Point  destination 
)
private
Parameters
origin
destination
Returns
Tri_Point wblut.geom.WB_ConstrainedTriangulation.addInteriorPoint ( final WB_Coordinate  point)
Parameters
point
Returns
final boolean wblut.geom.WB_ConstrainedTriangulation.between ( final WB_Coordinate  a,
final WB_Coordinate  b,
final WB_Coordinate  c 
)
Parameters
a
b
c
Returns
final boolean wblut.geom.WB_ConstrainedTriangulation.betweenProper ( final WB_Coordinate  a,
final WB_Coordinate  b,
final WB_Coordinate  c 
)
Parameters
a
b
c
Returns
int wblut.geom.WB_ConstrainedTriangulation.boundarySize ( )
Returns
void wblut.geom.WB_ConstrainedTriangulation.clear ( )
void wblut.geom.WB_ConstrainedTriangulation.clearFlags ( final int  flag)
Parameters
flag
void wblut.geom.WB_ConstrainedTriangulation.clearNewBoundaryEdge ( final Tri_Point  pStart,
final Tri_Point  pEnd 
)
private
Parameters
pStart
pEnd
final boolean wblut.geom.WB_ConstrainedTriangulation.coincident ( final WB_Coordinate  a,
final WB_Coordinate  b 
)
Parameters
a
b
Returns
void wblut.geom.WB_ConstrainedTriangulation.constrainAllEdges ( )
boolean wblut.geom.WB_ConstrainedTriangulation.constrainEdge ( final Tri_HalfEdge  he)
private
Parameters
he
Returns
FastTable<Tri_HalfEdge> wblut.geom.WB_ConstrainedTriangulation.constructPolygon ( final Tri_HalfEdge  he)
protected
Parameters
he
Returns
boolean wblut.geom.WB_ConstrainedTriangulation.contains ( final Tri_Point  p)
Parameters
p
Returns
static final double wblut.geom.WB_ConstrainedTriangulation.edgeDistanceSq ( final WB_Coordinate  p1,
final WB_Coordinate  p2,
final WB_Coordinate  p 
)
static
Parameters
p1
p2
p
Returns
final String wblut.geom.WB_ConstrainedTriangulation.error ( final String  s)
protected
Parameters
s
Returns
final String wblut.geom.WB_ConstrainedTriangulation.error ( final String  s,
final Object...  args 
)
protected
Parameters
s
args
Returns
void wblut.geom.WB_ConstrainedTriangulation.fillEdgeVisiblePolygon ( final Tri_HalfEdge  he)
protected
Parameters
he
void wblut.geom.WB_ConstrainedTriangulation.fillEdgeVisiblePolygonRecurse ( final FastTable< Tri_HalfEdge polygon)
private
Parameters
polygon
void wblut.geom.WB_ConstrainedTriangulation.fillGeneralPolygon ( final Tri_HalfEdge  he)
protected
Parameters
he
void wblut.geom.WB_ConstrainedTriangulation.fillGeneralPolygon ( final FastTable< Tri_HalfEdge polygon)
protected
Parameters
polygon
void wblut.geom.WB_ConstrainedTriangulation.fillGeneralPolygonRecurse ( final FastTable< Tri_HalfEdge polygon)
private
Parameters
polygon
void wblut.geom.WB_ConstrainedTriangulation.fillQuadrilateral ( final Tri_HalfEdge  he1)
protected
Parameters
he1
Tri_FaceWalk wblut.geom.WB_ConstrainedTriangulation.findFace ( final Tri_HalfEdge  heStart,
final Tri_Point  p 
)

A slightly smarter face walk routine that resorts to brute force only when it gets confused by an concave boundary.

Parameters
heStart
p
Returns
Tri_FaceWalk wblut.geom.WB_ConstrainedTriangulation.findFaceBruteForce ( final Tri_HalfEdge  heStart,
final Tri_Point  p 
)
Parameters
heStart
p
Returns
    This brute force approach works for *any* non-intersecting
    boundary, concave or convex. If the boundary is guaranteed to be
    a convex, a smarter face-walking algorithm could be used.
final Tri_HalfEdge wblut.geom.WB_ConstrainedTriangulation.findPrevious ( final Tri_HalfEdge  he)
protected
Parameters
he
Returns
boolean wblut.geom.WB_ConstrainedTriangulation.flipEdge ( final Tri_HalfEdge  he)
private
Parameters
he
Returns
void wblut.geom.WB_ConstrainedTriangulation.floodDelete ( final Tri_Point[]  bounds)
private
Parameters
bounds
WB_Triangle [] wblut.geom.WB_ConstrainedTriangulation.getExplicitTriangles ( )
Returns
List<WB_Triangle> wblut.geom.WB_ConstrainedTriangulation.getExplicitTrianglesAsList ( )
Returns
WB_Coordinate [] wblut.geom.WB_ConstrainedTriangulation.getFaceCoordinates ( )
Returns
Tri_Point wblut.geom.WB_ConstrainedTriangulation.getPoint ( final int  i)
Parameters
i
Returns
WB_Coordinate [] wblut.geom.WB_ConstrainedTriangulation.getPoints ( )
Returns
int wblut.geom.WB_ConstrainedTriangulation.indexOf ( final Tri_Point  p)
Parameters
p
Returns
void wblut.geom.WB_ConstrainedTriangulation.initRemoveConstraints ( final Tri_Point  p)
Parameters
p
final boolean wblut.geom.WB_ConstrainedTriangulation.intersect ( final WB_Coordinate  a,
final WB_Coordinate  b,
final WB_Coordinate  c,
final WB_Coordinate  d 
)
Parameters
a
b
c
d
Returns
static final WB_Coordinate wblut.geom.WB_ConstrainedTriangulation.intersection ( final WB_Coordinate  a,
final WB_Coordinate  b,
final WB_Coordinate  c,
final WB_Coordinate  d 
)
static
Parameters
a
b
c
d
Returns
final boolean wblut.geom.WB_ConstrainedTriangulation.intersectProper ( final WB_Coordinate  a,
final WB_Coordinate  b,
final WB_Coordinate  c,
final WB_Coordinate  d 
)
Parameters
a
b
c
d
Returns
static void wblut.geom.WB_ConstrainedTriangulation.linkBoundary ( final Tri_BPoint[]  pts)
static
Parameters
pts
final void wblut.geom.WB_ConstrainedTriangulation.listHalfEdges ( )
void wblut.geom.WB_ConstrainedTriangulation.listPoints ( )
final void wblut.geom.WB_ConstrainedTriangulation.message ( final String  s)
Parameters
s
final void wblut.geom.WB_ConstrainedTriangulation.message ( final String  s,
final Object...  args 
)
Parameters
s
args
static final double wblut.geom.WB_ConstrainedTriangulation.perpDistSq ( final WB_Coordinate  a,
final WB_Coordinate  b,
final WB_Coordinate  c 
)
staticprivate
Parameters
a
b
c
Returns
static final double wblut.geom.WB_ConstrainedTriangulation.projection ( final WB_Coordinate  p1,
final WB_Coordinate  p2,
final WB_Coordinate  p 
)
static
Parameters
p1
p2
p
Returns
static final double wblut.geom.WB_ConstrainedTriangulation.projNorm ( final WB_Coordinate  a,
final WB_Coordinate  b,
final WB_Coordinate  c 
)
staticprivate
Parameters
a
b
c
Returns
void wblut.geom.WB_ConstrainedTriangulation.removeBoundaryPoint ( final Tri_BPoint  bp)
Parameters
bp
void wblut.geom.WB_ConstrainedTriangulation.removeBoundaryPoint ( final Tri_Point  p,
final Tri_Point  pPrev 
)
private
Parameters
p
pPrev
void wblut.geom.WB_ConstrainedTriangulation.removeEdge ( final Tri_HalfEdge  he)
private
Parameters
he
void wblut.geom.WB_ConstrainedTriangulation.removeInteriorPoint ( final Tri_Point  p)
Parameters
p
void wblut.geom.WB_ConstrainedTriangulation.removePoint ( final Tri_Point  p)
private
Parameters
p
void wblut.geom.WB_ConstrainedTriangulation.restoreConstraints ( final Tri_Point  p)
Parameters
p
int wblut.geom.WB_ConstrainedTriangulation.size ( )
Returns
void wblut.geom.WB_ConstrainedTriangulation.splitConstraint ( final Tri_HalfEdge  he,
final WB_Coordinate  p 
)
private
Parameters
he
p
void wblut.geom.WB_ConstrainedTriangulation.splitEdge ( final Tri_Point  p,
final Tri_HalfEdge  he 
)
private
Parameters
p
he
void wblut.geom.WB_ConstrainedTriangulation.splitFace ( final Tri_Point  p,
final Tri_HalfEdge  he1 
)
private
Parameters
p
he1
void wblut.geom.WB_ConstrainedTriangulation.startWithBoundary ( final WB_Coordinate[]  pts)
Parameters
pts
void wblut.geom.WB_ConstrainedTriangulation.startWithBoundary ( final WB_Coordinate[]  pts,
final boolean  reverse 
)
Parameters
pts
reverse
void wblut.geom.WB_ConstrainedTriangulation.translate ( final double  x,
final double  y 
)
Parameters
x
y
boolean wblut.geom.WB_ConstrainedTriangulation.updateBoundaryPointInside ( final Tri_Point  p,
final Tri_Point  pPrev,
Tri_Point  pTemp 
)
Parameters
p
pPrev
pTemp
Returns
void wblut.geom.WB_ConstrainedTriangulation.updateBoundaryPointOutside ( final Tri_Point  p)
Parameters
p
void wblut.geom.WB_ConstrainedTriangulation.updateDelaunay ( )
void wblut.geom.WB_ConstrainedTriangulation.updateDelaunayAll ( )
final void wblut.geom.WB_ConstrainedTriangulation.updateHalfEdge ( final Tri_HalfEdge  he)
protected
void wblut.geom.WB_ConstrainedTriangulation.updateInteriorPoint ( Tri_Point  p)
Parameters
p

Member Data Documentation

LinkedList<Tri_HalfEdge> wblut.geom.WB_ConstrainedTriangulation.delaunayQueue = new LinkedList<Tri_HalfEdge>()
protected
LinkedList<Tri_Point> wblut.geom.WB_ConstrainedTriangulation.deleteQueue = new LinkedList<Tri_Point>()
protected
final String wblut.geom.WB_ConstrainedTriangulation.E_COINCIDENT = "Coincident points!"
staticprotected
final String wblut.geom.WB_ConstrainedTriangulation.E_EXHAUSTED = "Exhausted halfedges or points!"
staticprotected
final String wblut.geom.WB_ConstrainedTriangulation.E_HALFEDGE = "Mismatched halfedge!"
staticprotected
final String wblut.geom.WB_ConstrainedTriangulation.E_IDENTICAL = "Identical halfedges or points!"
staticprotected
final String wblut.geom.WB_ConstrainedTriangulation.E_MISSING = "Missing halfedge or point!"
staticprotected
final String wblut.geom.WB_ConstrainedTriangulation.E_POLYGON = "Illegal polygonal region!"
staticprotected
final String wblut.geom.WB_ConstrainedTriangulation.E_TYPE = "Incorrect type!"
staticprotected
final List<Tri_HalfEdge> wblut.geom.WB_ConstrainedTriangulation.halfEdges
protected
Initial value:
= Collections
.synchronizedList(new LinkedList<Tri_HalfEdge>())
final boolean wblut.geom.WB_ConstrainedTriangulation.MESSAGES = false
static
int wblut.geom.WB_ConstrainedTriangulation.nBoundary
protected
final int wblut.geom.WB_ConstrainedTriangulation.NULL_VALUE = -100000
staticprotected
final List<Tri_Point> wblut.geom.WB_ConstrainedTriangulation.points
protected
Initial value:
= Collections
.synchronizedList(new LinkedList<Tri_Point>())
Tri_Point wblut.geom.WB_ConstrainedTriangulation.removeConstraintPeg = null
private
LinkedList<Tri_Point> wblut.geom.WB_ConstrainedTriangulation.removedConstraints = new LinkedList<Tri_Point>()
protected

The documentation for this class was generated from the following file: