fr.inria.zvtm.layout.delaunay

Class DelaunayTriangulation

java.lang.Object

fr.inria.zvtm.layout.delaunay.Triangulation<Pnt>

fr.inria.zvtm.layout.delaunay.DelaunayTriangulation

All Implemented Interfaces:

Iterable<Simplex<Pnt>>

public class DelaunayTriangulation
extends Triangulation<Pnt>

A 2D Delaunay Triangulation (DT) with incremental site insertion. This is not the fastest way to build a DT, but it's a reasonable way to build the DT incrementally and it makes a nice interactive display. There are several O(n log n) methods, but they require that either (1) the sites are all known initially or (2) the sites are inserted in random order.

Author:

Paul Chew Created July 2005. Derived from an earlier, messier version.

Field Summary

Fields

Modifier and Type	Field and Description
boolean	debug

Constructor Summary

Constructors

Constructor and Description
DelaunayTriangulation(Simplex<Pnt> triangle) Constructor.

Method Summary

Modifier and Type	Method and Description
Set<Simplex<Pnt>>	delaunayPlace(Pnt site) Place a new point site into the DT.
Simplex<Pnt>	locate(Pnt point) Locate the triangle with point (a Pnt) inside (or on) it.
static void	main(String[] args) Main program; used for testing.

Methods inherited from class fr.inria.zvtm.layout.delaunay.Triangulation

contains, iterator, neighborOpposite, neighbors, printStuff, size, toString, update

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

debug

public boolean debug

Constructor Detail

DelaunayTriangulation

public DelaunayTriangulation(Simplex<Pnt> triangle)

Constructor. All sites must fall within the initial triangle.

Parameters:

triangle - the initial triangle

Method Detail

locate

public Simplex<Pnt> locate(Pnt point)

Locate the triangle with point (a Pnt) inside (or on) it.

Parameters:

point - the Pnt to locate

Returns:

triangle (Simplex) that holds the point; null if no such triangle

delaunayPlace

public Set<Simplex<Pnt>> delaunayPlace(Pnt site)

Place a new point site into the DT.

Parameters:

site - the new Pnt

Returns:

set of all new triangles created

main

public static void main(String[] args)

Main program; used for testing.