Jcg.triangulations2D

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

Constructor Summary

Constructors

Constructor and 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 and Description
java.util.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, toString

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

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 Detail

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 java.util.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.