toxi.geom.mesh2d
Class DelaunayTriangulation

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<toxi.geom.mesh2d.DelaunayTriangle>
          toxi.geom.mesh2d.DelaunayTriangulation

All Implemented Interfaces:

java.lang.Iterable<toxi.geom.mesh2d.DelaunayTriangle>, java.util.Collection<toxi.geom.mesh2d.DelaunayTriangle>, java.util.Set<toxi.geom.mesh2d.DelaunayTriangle>

public class DelaunayTriangulation
extends java.util.AbstractSet<toxi.geom.mesh2d.DelaunayTriangle>

A 2D Delaunay DelaunayTriangulation (DT) with incremental site insertion. This is not the fastest way to build a DT, but it's a reasonable way to build a DT incrementally and it makes a nice interactive display. There are several O(n log n) methods, but they require that the sites are all known initially. A DelaunayTriangulation is a Set of Triangles. A DelaunayTriangulation is unmodifiable as a Set; the only way to change it is to add sites (via delaunayPlace).

Constructor Summary

DelaunayTriangulation(toxi.geom.mesh2d.DelaunayTriangle triangle)
All sites must fall within the initial triangle.

Method Summary

boolean	contains(java.lang.Object triangle) True iff triangle is a member of this triangulation.
void	delaunayPlace(DelaunayVertex site) Place a new site into the DT.
java.util.Iterator<toxi.geom.mesh2d.DelaunayTriangle>	iterator()
toxi.geom.mesh2d.DelaunayTriangle	locate(DelaunayVertex point) Locate the triangle with point inside it or on its boundary.
toxi.geom.mesh2d.DelaunayTriangle	neighborOpposite(DelaunayVertex site, toxi.geom.mesh2d.DelaunayTriangle triangle) Report neighbor opposite the given vertex of triangle.
java.util.Set<toxi.geom.mesh2d.DelaunayTriangle>	neighbors(toxi.geom.mesh2d.DelaunayTriangle triangle) Return the set of triangles adjacent to triangle.
int	size()
java.util.List<toxi.geom.mesh2d.DelaunayTriangle>	surroundingTriangles(DelaunayVertex site, toxi.geom.mesh2d.DelaunayTriangle triangle) Report triangles surrounding site in order (cw or ccw).
java.lang.String	toString()

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

add, addAll, clear, containsAll, isEmpty, remove, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

add, addAll, clear, containsAll, isEmpty, remove, retainAll, toArray, toArray

Constructor Detail

DelaunayTriangulation

public DelaunayTriangulation(toxi.geom.mesh2d.DelaunayTriangle triangle)

All sites must fall within the initial triangle.

Parameters:

triangle - the initial triangle

Method Detail

contains

public boolean contains(java.lang.Object triangle)

True iff triangle is a member of this triangulation. This method isn't required by AbstractSet, but it improves efficiency.

Specified by:

contains in interface java.util.Collection<toxi.geom.mesh2d.DelaunayTriangle>

Specified by:

contains in interface java.util.Set<toxi.geom.mesh2d.DelaunayTriangle>

Overrides:

contains in class java.util.AbstractCollection<toxi.geom.mesh2d.DelaunayTriangle>

Parameters:

triangle - the object to check for membership

delaunayPlace

public void delaunayPlace(DelaunayVertex site)

Place a new site into the DT. Nothing happens if the site matches an existing DT vertex.

Parameters:

site - the new DelaunayVertex

Throws:

java.lang.IllegalArgumentException - if site does not lie in any triangle

iterator

public java.util.Iterator<toxi.geom.mesh2d.DelaunayTriangle> iterator()

Specified by:

iterator in interface java.lang.Iterable<toxi.geom.mesh2d.DelaunayTriangle>

Specified by:

iterator in interface java.util.Collection<toxi.geom.mesh2d.DelaunayTriangle>

Specified by:

iterator in interface java.util.Set<toxi.geom.mesh2d.DelaunayTriangle>

Specified by:

iterator in class java.util.AbstractCollection<toxi.geom.mesh2d.DelaunayTriangle>

locate

public toxi.geom.mesh2d.DelaunayTriangle locate(DelaunayVertex point)

Locate the triangle with point inside it or on its boundary.

Parameters:

point - the point to locate

Returns:

the triangle that holds point; null if no such triangle

neighborOpposite

public toxi.geom.mesh2d.DelaunayTriangle neighborOpposite(DelaunayVertex site,
                                                          toxi.geom.mesh2d.DelaunayTriangle triangle)

Report neighbor opposite the given vertex of triangle.

Parameters:

site - a vertex of triangle

triangle - we want the neighbor of this triangle

Returns:

the neighbor opposite site in triangle; null if none

Throws:

java.lang.IllegalArgumentException - if site is not in this triangle

neighbors

public java.util.Set<toxi.geom.mesh2d.DelaunayTriangle> neighbors(toxi.geom.mesh2d.DelaunayTriangle triangle)

Return the set of triangles adjacent to triangle.

Parameters:

triangle - the triangle to check

Returns:

the neighbors of triangle

size

public int size()

Specified by:

size in interface java.util.Collection<toxi.geom.mesh2d.DelaunayTriangle>

Specified by:

size in interface java.util.Set<toxi.geom.mesh2d.DelaunayTriangle>

Specified by:

size in class java.util.AbstractCollection<toxi.geom.mesh2d.DelaunayTriangle>

surroundingTriangles

public java.util.List<toxi.geom.mesh2d.DelaunayTriangle> surroundingTriangles(DelaunayVertex site,
                                                                              toxi.geom.mesh2d.DelaunayTriangle triangle)

Report triangles surrounding site in order (cw or ccw).

Parameters:

site - we want the surrounding triangles for this site

triangle - a "starting" triangle that has site as a vertex

Returns:

all triangles surrounding site in order (cw or ccw)

Throws:

java.lang.IllegalArgumentException - if site is not in triangle

toString

public java.lang.String toString()

Overrides:

toString in class java.util.AbstractCollection<toxi.geom.mesh2d.DelaunayTriangle>