ProGAL.geomNd.complex.delaunayComplex
Class BowyerWatson

java.lang.Object
  ProGAL.geomNd.complex.delaunayComplex.BowyerWatson

public class BowyerWatson
extends java.lang.Object

A Delaunay complex for a set of d-dimensional points is a tesselation of the points such that no point is inside the circumscribing hypersphere of the d-simplices (for the 3D case: Tetrahedra). This class builds a d-dimensional Delaunay complex in the constructor and enables access to it using the public methods getTessels and getAllTessels.

The original point-set is left unaltered and non-referenced by this class. A new set of vertices is allocated using the CVertex class. The position of these are randomly perturbed to avoid degeneracies. If one wishes to associate the original points with a vertex in the complex it would be sufficient to test if the distance between the point and the vertex is less than 0.0001.

The complex is bounded by a big tetrahedron whose corner-points are located sufficiently far from any of the vertices of the complex. The simplices that have one of these 'big points' as corners can not be accessed directly via the tessels field, but they will be neighbors of other normal simplices.

Author:

Desiree M. S. J¿rgensen, Annie J. Pinder

Constructor Summary

BowyerWatson(java.util.List<Point> points)
Builds the Delaunay complex of the specified point-set using Bowyer-Watson algorithm

Method Summary

boolean	checkTessels() Checks that all tetrahedra comply with the Delaunay-criteria.
static java.util.List<Tessel>	createAndDrawDelaunay(java.util.List<Point> points) Convenient static method for creating delaunay tessellation of a point-set and if its 2D or 3D also displaying it.
static java.util.List<Tessel>	createDelaunay(java.util.List<Point> points) Convenient static method for creating delaunay tessellation of a point-set
void	findNTes(Tessel tess, Vertex p, int apexID) Find star shaped polytope and retriangulate
java.util.List<Tessel>	getAllTessels() Returns all tessels (including tessels with 'big points')
int	getDim() The dimension of the tessellation
java.util.List<Tessel>	getTessels() Get the tesselts in the complex.
Vertex	getVertex(int i) Get the i'th vertex
java.util.List<Vertex>	getVertices() Get the vertices in the complex.
static boolean	inSphere(Tessel t, Point p) Return true if and only if the point p is inside or on the boundary of the circumsphere of t
static void	main(java.lang.String[] args)

Methods inherited from class java.lang.Object

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

Constructor Detail

BowyerWatson

public BowyerWatson(java.util.List<Point> points)

Builds the Delaunay complex of the specified point-set using Bowyer-Watson algorithm

Method Detail

getTessels

public java.util.List<Tessel> getTessels()

Get the tesselts in the complex. The tessels that has 'big points' as corners are not returned

getAllTessels

public java.util.List<Tessel> getAllTessels()

Returns all tessels (including tessels with 'big points')

getDim

public int getDim()

The dimension of the tessellation

getVertices

public java.util.List<Vertex> getVertices()

Get the vertices in the complex. The 'big points' are not returned

getVertex

public Vertex getVertex(int i)

Get the i'th vertex

findNTes

public void findNTes(Tessel tess,
                     Vertex p,
                     int apexID)

Find star shaped polytope and retriangulate

inSphere

public static boolean inSphere(Tessel t,
                               Point p)

Return true if and only if the point p is inside or on the boundary of the circumsphere of t

checkTessels

public boolean checkTessels()

Checks that all tetrahedra comply with the Delaunay-criteria.

createDelaunay

public static java.util.List<Tessel> createDelaunay(java.util.List<Point> points)

Convenient static method for creating delaunay tessellation of a point-set

createAndDrawDelaunay

public static java.util.List<Tessel> createAndDrawDelaunay(java.util.List<Point> points)

Convenient static method for creating delaunay tessellation of a point-set and if its 2D or 3D also displaying it.

main

public static void main(java.lang.String[] args)