Delaunay

java.lang.Object
- Jcg.triangulations3D.Delaunay_3

```
public class Delaunay_3
extends java.lang.Object
```
Incremental 3D Delaunay Triangulation. Data points can be inserted in any arbitrary order. Each point insertion is performed in three steps: - locate the point in the triangulation, i.e. find a cell containing it; - perform a breadth-first search from this cell to discover the conflicts zone of the point. - delete the conflicts zone and re-triangulate it by starring it with respect to the new vertex.

Author:

Steve Oudot Notes: - the implementation assumes that the points lie in general position (no 3 points must be aligned, nor 4 points coplanar, nor 5 points cospherical. - there is still an issue in the handling of infinite cells in the detection of conflicts (see the bounding box factor in method updateBB()).

Constructor Summary

Constructors
Constructor and Description
`Delaunay_3()` creates an empty 3D Delaunay triangulation, ready to be used for insertions and localizations.
`Delaunay_3(Delaunay_3 del)` cloning constructor that only copies internal pointers and does not actually duplicate the content.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`java.util.Collection<TriangulationDSCell_3<Point_3>>`	`cells()` returns the collection of all cells of the triangulation.
`java.util.Collection<FacetHandle<Point_3>>`	`convexHullFacets()` Outputs the collection of all facets of the boundary of the convex hull.
`Point_3`	`dual(TriangulationDSCell_3<Point_3> c)` Outputs the Voronoi vertex dual to cell c.
`java.util.Collection<Triangle_3>`	`dual(TriangulationDSVertex_3<Point_3> v)` Outputs the (triangulated) boundary of the Voronoi region dual to vertex v.
`java.util.Set<TriangulationDSCell_3<Point_3>>`	`findConflicts(Point_3 p, TriangulationDSCell_3<Point_3> cstart)` Computes the set of cells that are in conflict with p, that is, the cells whose circumspheres have p in their interior.
`java.util.Collection<TriangulationDSCell_3<Point_3>>`	`finiteCells()` returns the collection of all finite cells of the triangulation.
`java.util.Collection<FacetHandle<Point_3>>`	`finiteFacets()` Outputs the collection of all finite facets of the triangulation (the ones not linked to bounding box vertices).
`java.util.Collection<TriangulationDSVertex_3<Point_3>>`	`finiteVertices()` returns the collection of all finite vertices of the triangulation.
`java.util.Collection<TriangulationDSCell_3<Point_3>>`	`incidentCells(TriangulationDSCell_3<Point_3> c, int i, int j)` Returns the collection of all cells incident to edge (c,i,j).
`java.util.Collection<TriangulationDSCell_3<Point_3>>`	`incidentCells(TriangulationDSVertex_3<Point_3> v)` Outputs the collection of all cells incident to vertex v.
`java.util.Collection<TriangulationDSCell_3<Point_3>>`	`incidentCells(TriangulationDSVertex_3<Point_3> u, TriangulationDSVertex_3<Point_3> v)` Returns the collection of all cells incident to edge (u,v).
`java.util.Collection<TriangulationDSCell_3<Point_3>>`	`incidentFiniteCells(TriangulationDSCell_3<Point_3> c, int i, int j)` Returns the collection of all finite cells incident to edge (c,i,j).
`java.util.Collection<TriangulationDSCell_3<Point_3>>`	`incidentFiniteCells(TriangulationDSVertex_3<Point_3> v)` Outputs the collection of all finite cells incident to vertex v.
`java.util.Collection<TriangulationDSCell_3<Point_3>>`	`incidentFiniteCells(TriangulationDSVertex_3<Point_3> u, TriangulationDSVertex_3<Point_3> v)` Returns the collection of all finite cells incident to edge (u,v).
`TriangulationDSCell_3<Point_3>`	`infiniteCell()` returns an infinite cell of the triangulation.
`TriangulationDSVertex_3<Point_3>`	`infiniteVertex()` returns an infinite vertex of the triangulation.
`TriangulationDSVertex_3<Point_3>`	`insert(Point_3 p)` Inserts point p in the triangulation, using a random cell to locate p then the output of the locate to compute the conflicts zone of p.
`TriangulationDSVertex_3<Point_3>`	`insert(Point_3 p, TriangulationDSCell_3<Point_3> cstart)` Inserts point p in the triangulation, using cell cstart to initiate the conflicts zone computation.
`boolean`	`isInfinite(FacetHandle f)` returns the status of a triangulation facet: infinite if it is incident to at least one infinite vertex, and finite otherwise.
`boolean`	`isInfinite(Point_3 p)` returns the status of a 3D point: infinite if it is a bounding box vertex, finite otherwise.
`boolean`	`isInfinite(TriangulationDSCell_3 c)` returns the status of a triangulation cell: infinite if it is incident to at least one infinite vertex, and finite otherwise.
`boolean`	`isInfinite(TriangulationDSVertex_3 v)` returns the status of a triangulation vertex: infinite if it is a vertex of the bounding box, finite otherwise.
`boolean`	`isValid()` checks the combinatorial validity of the Delaunay triangulation.
`TriangulationDSCell_3<Point_3>`	`locate(Point_3 p)` locates point p using a straight-line walk from a random cell.
`static void`	`main(java.lang.String[] args)` Testing function.
`TriangulationDSCell_3<Point_3>`	`randomCell()` returns a random (possibly infinite) cell of the triangulation, chosen according to uniform distribution over the set of all triangulation cells.
`TriangulationDSCell_3<Point_3>`	`randomFiniteCell()` returns a random finite cell of the triangulation, chosen according to a uniform distribution over the set of finite triangulation cells.
`TriangulationDSVertex_3<Point_3>`	`randomFiniteVertex()` returns a random finite vertex of the triangulation, chosen according to a uniform distribution over the set of finite triangulation vertices.
`TriangulationDSVertex_3<Point_3>`	`randomVertex()` returns a random (possibly infinite) vertex of the triangulation, chosen according to uniform distribution over the set of all triangulation vertices.
`void`	`starZone(TriangulationDSVertex_3<Point_3> v, java.util.TreeSet<TriangulationDSCell_3<Point_3>> zone)` Triangulates a zone (= facet-connected set of cells) by creating a star of simplices joining vertex v to the triangles on the zone's boundary.
`java.util.Collection<TriangulationDSVertex_3<Point_3>>`	`vertices()` returns the collection of all vertices of the triangulation.
`void`	`writeToFile(java.lang.String filename)` outputs the triangulation in an OFF file.

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - Delaunay_3
```
public Delaunay_3()
```
    creates an empty 3D Delaunay triangulation, ready to be used for insertions and localizations. In effect the triangulation contains only infinite vertices (the vertices of the bounding box) after its construction.
  - Delaunay_3
```
public Delaunay_3(Delaunay_3 del)
```
    cloning constructor that only copies internal pointers and does not actually duplicate the content.
- Method Detail
  - isInfinite
```
public boolean isInfinite(Point_3 p)
```
    returns the status of a 3D point: infinite if it is a bounding box vertex, finite otherwise. This method runs in constant time and does not check whether p is a vertex of the triangulation.
  - isInfinite
```
public boolean isInfinite(TriangulationDSVertex_3 v)
```
    returns the status of a triangulation vertex: infinite if it is a vertex of the bounding box, finite otherwise.
  - isInfinite
```
public boolean isInfinite(TriangulationDSCell_3 c)
```
    returns the status of a triangulation cell: infinite if it is incident to at least one infinite vertex, and finite otherwise.
  - isInfinite
```
public boolean isInfinite(FacetHandle f)
```
    returns the status of a triangulation facet: infinite if it is incident to at least one infinite vertex, and finite otherwise.
  - isValid
```
public boolean isValid()
```
    checks the combinatorial validity of the Delaunay triangulation.
  - randomCell
```
public TriangulationDSCell_3<Point_3> randomCell()
```
    returns a random (possibly infinite) cell of the triangulation, chosen according to uniform distribution over the set of all triangulation cells.
  - randomFiniteCell
```
public TriangulationDSCell_3<Point_3> randomFiniteCell()
```
    returns a random finite cell of the triangulation, chosen according to a uniform distribution over the set of finite triangulation cells.
  - infiniteCell
```
public TriangulationDSCell_3<Point_3> infiniteCell()
```
    returns an infinite cell of the triangulation.
  - randomVertex
```
public TriangulationDSVertex_3<Point_3> randomVertex()
```
    returns a random (possibly infinite) vertex of the triangulation, chosen according to uniform distribution over the set of all triangulation vertices.
  - randomFiniteVertex
```
public TriangulationDSVertex_3<Point_3> randomFiniteVertex()
```
    returns a random finite vertex of the triangulation, chosen according to a uniform distribution over the set of finite triangulation vertices.
  - infiniteVertex
```
public TriangulationDSVertex_3<Point_3> infiniteVertex()
```
    returns an infinite vertex of the triangulation.
  - vertices
```
public java.util.Collection<TriangulationDSVertex_3<Point_3>> vertices()
```
    returns the collection of all vertices of the triangulation.
  - finiteVertices
```
public java.util.Collection<TriangulationDSVertex_3<Point_3>> finiteVertices()
```
    returns the collection of all finite vertices of the triangulation.
  - cells
```
public java.util.Collection<TriangulationDSCell_3<Point_3>> cells()
```
    returns the collection of all cells of the triangulation.
  - finiteCells
```
public java.util.Collection<TriangulationDSCell_3<Point_3>> finiteCells()
```
    returns the collection of all finite cells of the triangulation.
  - locate
```
public TriangulationDSCell_3<Point_3> locate(Point_3 p)
```
    locates point p using a straight-line walk from a random cell.
  - findConflicts
```
public java.util.Set<TriangulationDSCell_3<Point_3>> findConflicts(Point_3 p,
                                                                   TriangulationDSCell_3<Point_3> cstart)
```
    Computes the set of cells that are in conflict with p, that is, the cells whose circumspheres have p in their interior.
    
    Parameters:
    
    cstart - any cell that is in conflict with p (for instance a cell containing p)
  - starZone
```
public void starZone(TriangulationDSVertex_3<Point_3> v,
                     java.util.TreeSet<TriangulationDSCell_3<Point_3>> zone)
```
    Triangulates a zone (= facet-connected set of cells) by creating a star of simplices joining vertex v to the triangles on the zone's boundary. This method is used typically in the Delaunay insertion, to re-triangulate the conflicts zone.
    
    Parameters:
    
    v - the new vertex to become the center of the star
    
    zone - the facet-connected set of cells forming the zone
  - insert
```
public TriangulationDSVertex_3<Point_3> insert(Point_3 p,
                                               TriangulationDSCell_3<Point_3> cstart)
```
    Inserts point p in the triangulation, using cell cstart to initiate the conflicts zone computation.
    
    Parameters:
    
    cstart - a cell that is in conflict with p (for instance a cell containing p). This method casts an Error if cstart turns out not to be in conflict with p.
  - insert
```
public TriangulationDSVertex_3<Point_3> insert(Point_3 p)
```
    Inserts point p in the triangulation, using a random cell to locate p then the output of the locate to compute the conflicts zone of p.
  - finiteFacets
```
public java.util.Collection<FacetHandle<Point_3>> finiteFacets()
```
    Outputs the collection of all finite facets of the triangulation (the ones not linked to bounding box vertices). This method takes linear time in the triangulation size.
  - convexHullFacets
```
public java.util.Collection<FacetHandle<Point_3>> convexHullFacets()
```
    Outputs the collection of all facets of the boundary of the convex hull. This method takes linear time in the triangulation size.
  - incidentCells
```
public java.util.Collection<TriangulationDSCell_3<Point_3>> incidentCells(TriangulationDSVertex_3<Point_3> v)
```
    Outputs the collection of all cells incident to vertex v.
  - incidentFiniteCells
```
public java.util.Collection<TriangulationDSCell_3<Point_3>> incidentFiniteCells(TriangulationDSVertex_3<Point_3> v)
```
    Outputs the collection of all finite cells incident to vertex v.
  - incidentCells
```
public java.util.Collection<TriangulationDSCell_3<Point_3>> incidentCells(TriangulationDSCell_3<Point_3> c,
                                                                          int i,
                                                                          int j)
```
    Returns the collection of all cells incident to edge (c,i,j).
  - incidentFiniteCells
```
public java.util.Collection<TriangulationDSCell_3<Point_3>> incidentFiniteCells(TriangulationDSCell_3<Point_3> c,
                                                                                int i,
                                                                                int j)
```
    Returns the collection of all finite cells incident to edge (c,i,j).
  - incidentCells
```
public java.util.Collection<TriangulationDSCell_3<Point_3>> incidentCells(TriangulationDSVertex_3<Point_3> u,
                                                                          TriangulationDSVertex_3<Point_3> v)
```
    Returns the collection of all cells incident to edge (u,v).
  - incidentFiniteCells
```
public java.util.Collection<TriangulationDSCell_3<Point_3>> incidentFiniteCells(TriangulationDSVertex_3<Point_3> u,
                                                                                TriangulationDSVertex_3<Point_3> v)
```
    Returns the collection of all finite cells incident to edge (u,v).
  - dual
```
public Point_3 dual(TriangulationDSCell_3<Point_3> c)
```
    Outputs the Voronoi vertex dual to cell c. By definition, this vertex coincides with the circumcenter of c. Throws a RuntimeException if c is infinite.
  - dual
```
public java.util.Collection<Triangle_3> dual(TriangulationDSVertex_3<Point_3> v)
```
    Outputs the (triangulated) boundary of the Voronoi region dual to vertex v. Each Voronoi face forming the Voronoi region boundary is triangulated. When vertex v lies on the boundary of the convex hull, only the finite faces of the boundary of its region are output. Throws a RuntimeException if v is infinite.
  - writeToFile
```
public void writeToFile(java.lang.String filename)
```
    outputs the triangulation in an OFF file.
  - main
```
public static void main(java.lang.String[] args)
```
    Testing function.

Class Delaunay_3

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

Delaunay_3

Delaunay_3

Method Detail

isInfinite

isInfinite

isInfinite

isInfinite

isValid

randomCell

randomFiniteCell

infiniteCell

randomVertex

randomFiniteVertex

infiniteVertex

vertices

finiteVertices

cells

finiteCells

locate

findConflicts

starZone

insert

insert

finiteFacets

convexHullFacets

incidentCells

incidentFiniteCells

incidentCells

incidentFiniteCells

incidentCells

incidentFiniteCells

dual

dual

writeToFile

main