uchicago.src.sim.space
Class Delaunay

java.lang.Object
  |
  +--uchicago.src.sim.space.Delaunay

public class Delaunay

extends Object

This is an implementation of the guibas and stolfi incremental algorithm for finding the delaunay triangulation of a set of points. After playing around with several algorithms, including the divide and conquer included in that artical, I decided that this was the fastest. It also allows us to add additional points to the triangulation, although this is tricky if the point is outside the original triangulation. It employs the QuadEdge data structure. For more info see: Guibas, L. and Stolfi, J., "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams", ACT TOG, 4(2), April, 1985.

Field Summary

QuadEdge[]	edges
SpatialNode[]	nodes

Constructor Summary

Delaunay()
construct a triangulation object

Method Summary

static boolean	ccw(SpatialNode a, SpatialNode b, SpatialNode c) determine if the points are oriented in counter-clock wise fasion
void	findInfiniteTriangle(SpatialNode[] nodes) calculate the infinite triangle.
static boolean	inCircle(SpatialNode a, SpatialNode b, SpatialNode c, SpatialNode d) primitive to determine if a point is in the circle created by three other points.
void	insertPoints(SpatialNode[] nodes) Insert an array of points into the triangulation.
boolean	isOn(SpatialNode x, QuadEdge e) is point on edge
boolean	leftOf(SpatialNode x, QuadEdge e) is point left of edge
void	removeEdge(QuadEdge e) remove an individual edge from the structure.
void	removeInfiniteTriangle() delete the edges from the infinite triangle.
void	resetEdges(int len) clear all of the edges
boolean	rightOf(SpatialNode x, QuadEdge e) is point right of edge

Methods inherited from class java.lang.Object

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

Field Detail

edges

public QuadEdge[] edges

nodes

public SpatialNode[] nodes

Constructor Detail

Delaunay

public Delaunay()

construct a triangulation object

Method Detail

findInfiniteTriangle

public void findInfiniteTriangle(SpatialNode[] nodes)

calculate the infinite triangle.

Parameters:

nodes -

removeInfiniteTriangle

public void removeInfiniteTriangle()

delete the edges from the infinite triangle.

insertPoints

public void insertPoints(SpatialNode[] nodes)

Insert an array of points into the triangulation. This calculates the infinite triangle (see article), then adds the points incrementally. It is not randomized, because the benefits were negligable.

Parameters:

nodes -

ccw

public static boolean ccw(SpatialNode a,
                          SpatialNode b,
                          SpatialNode c)

determine if the points are oriented in counter-clock wise fasion

Parameters:

a -

b -

c -

Returns:

inCircle

public static boolean inCircle(SpatialNode a,
                               SpatialNode b,
                               SpatialNode c,
                               SpatialNode d)

primitive to determine if a point is in the circle created by three other points. see stolfi and guibas for algorithm

Parameters:

a -

b -

c -

d -

Returns:

resetEdges

public void resetEdges(int len)

clear all of the edges

Parameters:

len -

removeEdge

public void removeEdge(QuadEdge e)

remove an individual edge from the structure. see stolfi and guibas for algorithm

Parameters:

e -

rightOf

public boolean rightOf(SpatialNode x,
                       QuadEdge e)

is point right of edge

Parameters:

x -

e -

Returns:

leftOf

public boolean leftOf(SpatialNode x,
                      QuadEdge e)

is point left of edge

Parameters:

x -

e -

Returns:

isOn

public boolean isOn(SpatialNode x,
                    QuadEdge e)

is point on edge

Parameters:

x -

e -

Returns: