ProGAL.geom3d.complex.tessellation
Class DelaunayTessellation

java.lang.Object
  ProGAL.geom3d.complex.tessellation.DelaunayTessellation

public class DelaunayTessellation
extends java.lang.Object

A Delaunay tessellation 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 three-dimensional Delaunay tessellation in the constructor and accesses it using the getTetrahedra method. The following example displays the Delaunay complex of ten random points.

  //Generate the complex
  List<Point> pl = PointList.generatePointsInCube(10);
  DelaunayTessellation dc = new DelaunayTessellation(pl);
    
  //Display the complex
  J3DScene scene = J3DScene.createJ3DSceneInFrame();
  for(CTetrahedron t: dc.getTetrahedra()){
    scene.addShape(t, new Color(200,100,100,100));
  }
  
  

The original point-set is left unaltered and non-referenced by this class. A new set of vertices are allocated using the CVertex class. These are randomly permuted 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. These points are part of the tessellation. The simplices that have one of these 'big points' as corners can not be accessed directly via the getter-methods, but they will be neighbors of other normal simplices. For instance:

  DelaunayComplex dc = new DelaunayComplex( PointList.generatePointsInCube(4) );
  for(CTetrahedron t: dc.getTetrahedra()){
        System.out.println( t.containsBigPoint() );
        System.out.println( t.getNeighbor(0).containsBigPoint() );
        System.out.println( t.getNeighbor(1).containsBigPoint() );
        System.out.println( t.getNeighbor(2).containsBigPoint() );
        System.out.println( t.getNeighbor(3).containsBigPoint() );
  }
  

Will print false, true, true, true and true. A tetrahedron will contain a big-point if and only if it is outside the convex hull.

Author:

P.Sterner, H.Sterner, R.Fonseca

Constructor Summary

DelaunayTessellation(java.util.List<Point> points)
Builds the Delaunay complex of the specified point-set

Method Summary

boolean	checkTetrahedra() Checks that all tetrahedra comply with the Delaunay-criteria.
java.util.List<CTetrahedron>	getTetrahedra() Get the tetrahedra in the complex.
java.util.List<CVertex>	getVertices() Get the vertices in the complex.
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

DelaunayTessellation

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

Builds the Delaunay complex of the specified point-set

Method Detail

main

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

getTetrahedra

public java.util.List<CTetrahedron> getTetrahedra()

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

getVertices

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

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

checkTetrahedra

public boolean checkTetrahedra()

Checks that all tetrahedra comply with the Delaunay-criteria.