visad
Class Delaunay

java.lang.Object
  visad.Delaunay

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

DelaunayClarkson, DelaunayFast, DelaunayOverlap, DelaunayWatson

public abstract class Delaunay
extends java.lang.Object
implements java.io.Serializable

Delaunay represents an abstract class for calculating an N-dimensional Delaunay triangulation, that can be extended to allow for various triangulation algorithms.

See Also:

Serialized Form

Field Summary

int[][]	Edges tri/tetra edges --> global edge number.
int	NumEdges number of unique global edge numbers
int[][]	Tri triangles/tetrahedra --> vertices.
int[][]	Vertices vertices --> triangles/tetrahedra.
int[][]	Walk triangles/tetrahedra --> triangles/tetrahedra.

Constructor Summary

Delaunay()
The abstract constructor initializes the class's data arrays.

Method Summary

static Delaunay	factory(float[][] samples, boolean exact) The factory class method heuristically decides which extension to the Delaunay abstract class to use in order to construct the fastest triangulation, and calls that extension, returning the finished triangulation.
void	finish_triang(float[][] samples) calculate a triangulation's helper arrays, Walk and Edges, if the triangulation algorithm hasn't calculated them already.
boolean	getNonConvex()
void	improve(float[][] samples, int pass) use edge-flipping to bring the current triangulation closer to the true Delaunay triangulation.
static float[][]	perturb(float[][] samples, float epsilon, boolean copy) increments samples coordinates by random numbers between -epsilon and epsilon, in order to eliminate triangulation problems such as co-linear and co-located points
java.lang.String	sampleString(float[][] samples)
static float[][]	scale(float[][] samples, float mult, boolean copy) alters the values of the samples by multiplying them by the mult factor
void	setNonConvex() set flag indicating this Delaunay topology is non-convex
boolean	test(float[][] samples) check this triangulation in various ways to make sure it is constructed correctly.
boolean	test(float[][] samples, boolean printErrors)
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

Tri

public int[][] Tri

triangles/tetrahedra --> vertices.

Tri = new int[ntris][dim + 1]

This is the key output, a list of triangles (in two dimensions, tetrahedra in three dimensions, etc). ntris is the number of triangles.

In 2-D, Tri[i] is an array of 3 integers, which are three indices into the samples[0] and samples[1] arrays to get the x and y values of the three vertices of the triangle.

In 3-D, Tri[i] is an array of 4 integers, which are four indices into the samples[0], samples[1] and samples[2] arrays to get the x, y and z values of the four vertices of the tetrahedron.

This pattern continues for higher dimensionalities.

Vertices

public int[][] Vertices

vertices --> triangles/tetrahedra.

Vertices = new int[nrs][nverts[i]]

nrs is the number of samples (the length of the samples[0] and samples[1] arrays. For sample i, Vertices[i] is a (variable length) list of indices into the Tri array above, giving the indices of the triangles that include vertex i.

nverts is an array as the second index of the Vertices array since different vertices may be part of different numbers of triangles.

You can use Tri and Vertices together to traverse the triangulation. If you don't need to traverse, then you can probably ignore all arrays except Tri.

Walk

public int[][] Walk

triangles/tetrahedra --> triangles/tetrahedra.

Walk = new int[ntris][dim + 1]

Also useful for traversing the triangulation, in this case giving the indices of triangles that share edges with the current triangle.

Edges

public int[][] Edges

tri/tetra edges --> global edge number.

Edges = new int[ntris][3 * (dim - 1)];

'global edge number' is the number of an edge that is unique among the whole triangulation. This number is not an index into any array, but will match for a shared edge between two triangles.

NumEdges

public int NumEdges

number of unique global edge numbers

Constructor Detail

Delaunay

public Delaunay()
         throws VisADException

The abstract constructor initializes the class's data arrays.

Throws:

VisADException - a VisAD error occurred

Method Detail

setNonConvex

public void setNonConvex()

set flag indicating this Delaunay topology is non-convex

getNonConvex

public boolean getNonConvex()

Returns:

flag indicating whether this Delaunay topology is non-convex

factory

public static Delaunay factory(float[][] samples,
                               boolean exact)
                        throws VisADException

The factory class method heuristically decides which extension to the Delaunay abstract class to use in order to construct the fastest triangulation, and calls that extension, returning the finished triangulation. The method chooses from among the Fast, Clarkson, and Watson methods.

Parameters:

samples - locations of points for topology - dimensioned float[dimension][number_of_points]

exact - flag indicating need for exact Delaunay triangulation

Returns:

a topology using an appropriate sub-class of Delaunay

Throws:

VisADException - a VisAD error occurred

scale

public static float[][] scale(float[][] samples,
                              float mult,
                              boolean copy)

alters the values of the samples by multiplying them by the mult factor

Parameters:

samples - locations of points for topology - dimensioned float[dimension][number_of_points]

mult - multiplication factor

copy - specifies whether scale should modify and return the argument samples array or a copy

Returns:

array of scaled values

perturb

public static float[][] perturb(float[][] samples,
                                float epsilon,
                                boolean copy)

increments samples coordinates by random numbers between -epsilon and epsilon, in order to eliminate triangulation problems such as co-linear and co-located points

Parameters:

samples - locations of points for topology - dimensioned float[dimension][number_of_points]

epsilon - size limit on random perturbations

copy - specifies whether perturb should modify and return the argument samples array or a copy

Returns:

array of perturbed values

test

public boolean test(float[][] samples)

check this triangulation in various ways to make sure it is constructed correctly. This method is expensive, provided mainly for debugging purposes.

Parameters:

samples - locations of points for topology - dimensioned float[dimension][number_of_points]

Returns:

flag that is false to indicate there are problems with the triangulation

test

public boolean test(float[][] samples,
                    boolean printErrors)

improve

public void improve(float[][] samples,
                    int pass)
             throws VisADException

use edge-flipping to bring the current triangulation closer to the true Delaunay triangulation.

Parameters:

samples - locations of points for topology - dimensioned float[dimension][number_of_points]

pass - the number of passes the algorithm should take over all edges (however, the algorithm terminates if no edges are flipped for an entire pass).

Throws:

VisADException - a VisAD error occurred

finish_triang

public void finish_triang(float[][] samples)
                   throws VisADException

calculate a triangulation's helper arrays, Walk and Edges, if the triangulation algorithm hasn't calculated them already. Any extension to the Delaunay class should call finish_triang() at the end of its triangulation constructor.

Parameters:

samples - locations of points for topology - dimensioned float[dimension][number_of_points]

Throws:

VisADException - a VisAD error occurred

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

Returns:

a String representation of this

sampleString

public java.lang.String sampleString(float[][] samples)

Parameters:

samples - locations of points for topology - dimensioned float[dimension][number_of_points] - may be null

Returns:

a String representation of this, including samples if it is non-null