Class Delaunay_2

java.lang.Object

Jcg.triangulations2D.Triangulation_2

Jcg.triangulations2D.Delaunay_2

public class Delaunay_2
extends Triangulation_2

Incremental 2D Delaunay Triangulation using Face/Vertex data structure (TriangulationDS_2).

Author:

Java-code by Luca Castelli-Aleardi and Steve Oudot

Nested Class Summary

Nested classes/interfaces inherited from class Jcg.triangulations2D.Triangulation_2

Triangulation_2.BoundingBox

Field Summary

Fields inherited from class Jcg.triangulations2D.Triangulation_2

bbox, startingFace, tri

Constructor Summary

Constructors

Constructor	Description
Delaunay_2()	Constuctor: builds an empty Delaunay triangulation.
Delaunay_2(Point_2 a, Point_2 b, Point_2 c)

Method Summary

Modifier and Type	Method	Description
Collection<HalfedgeHandle<Point_2>>	constraintEdges()	Computes and returns the list of constraint edges.
Point_2	dual(TriangulationDSFace_2<Point_2> f)	Outputs the Voronoi vertex dual to face f.
TriangulationDSVertex_2<Point_2>	insert(Point_2 p)	Inserts point p in the Delaunay triangulation and returns the newly created vertex
HalfedgeHandle<Point_2>	insert(Point_2 p, Point_2 q)	Inserts a constraint edge in the Delaunay triangulation.

Methods inherited from class Jcg.triangulations2D.Triangulation_2

convexHullEdges, finiteEdges, finiteFaces, finiteVertices, isInfinite, isInfinite, isInfinite, isInfinite, isValid, locate, setBoundingBox, toString, updateBoundingBox

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Details

Delaunay_2

public Delaunay_2()

Constuctor: builds an empty Delaunay triangulation.

Delaunay_2

public Delaunay_2(Point_2 a,
 Point_2 b,
 Point_2 c)

Method Details

insert

public TriangulationDSVertex_2<Point_2> insert(Point_2 p)

Inserts point p in the Delaunay triangulation and returns the newly created vertex

Overrides:

insert in class Triangulation_2

Parameters:

p - the point to insert

insert

public HalfedgeHandle<Point_2> insert(Point_2 p,
 Point_2 q)

Inserts a constraint edge in the Delaunay triangulation. Warning: in the current implementation, constraint edges cannot intersect one another except at a common vertex, otherwise there is a risk of falling into an infinite loop...

Parameters:

p - ,q the vertices of the edge

Returns:

the halfedge of origin p that points in the direction of q along the input constraint edge

constraintEdges

public Collection<HalfedgeHandle<Point_2>> constraintEdges()

Computes and returns the list of constraint edges. Each edge is represented as an array of two points.

dual

public Point_2 dual(TriangulationDSFace_2<Point_2> f)

Outputs the Voronoi vertex dual to face f. By definition, this vertex coincides with the circumcenter of f. Throws a RuntimeException if f is infinite.