delaunay_triangulation
Class Delaunay_Triangulation

java.lang.Object
  extended by delaunay_triangulation.Delaunay_Triangulation

public class Delaunay_Triangulation
extends java.lang.Object

This class represents a Delaunay Triangulation. The class was written for a large scale triangulation (1000 - 200,000 vertices). The code is based on Klasse für Kreise code from 1996-1997 , which is written in a C like flavor see: http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/ .
the changes and additions suggested here are aimed towards usability in 3D terrain & performance!.
Main Methods:
- adaptive inserting of points.
- fast point location. (O(n^0.5)).
- handles degenerate cases and none general position input (ignores duplicate points).
- save & load from\to text file in TSIN format.
- 3D support: including z value approximation.
- standard java (1.5 generic) iterators for the vertices and triangles.
- smart iterator to only the updated triangles - for terrain simplification

Testing: Platform java 1.5.02 windows XP (SP2), AMD laptop 1.6G sempron CPU 512MB RAM. Constructing a triangulation of 100,000 vertices takes ~ 10 seconds. point location of 100,000 points on a triangulation of 100,000 vertices takes ~ 5 seconds. Note: constructing a triangulation with 200,000 vertices and more requires extending java heap size (otherwise an exception will be thrown).
Bugs: if U find a bug or U have an idea as for how to improve the code, please send me an email to: boaz.benmoshe@idc.ac.il

Author:
Boaz Ben Moshe 5/11/05

Field Summary
 Triangle_dt startTriangleHull
           
 
Constructor Summary
Delaunay_Triangulation()
          creates an empty Delaunay Triangulation.
Delaunay_Triangulation(Point_dt[] ps)
          creates a Delaunay Triangulation from all the points.
Delaunay_Triangulation(java.lang.String file)
          creates a Delaunay Triangulation from all the points in the suggested tsin file or from a smf file (off like).
 
Method Summary
 Point_dt bb_max()
          return the max point of the bounding box of this triangulation {{x1,y1,z1}}
 Point_dt bb_min()
          return the min point of the bounding box of this triangulation {{x0,y0,z0}}
 int CH_size()
          compute the number of vertices in the convex hull.
 java.util.Iterator<Point_dt> CH_vertices_Iterator()
           
 boolean contains(double x, double y)
           
 boolean contains(Point_dt p)
           
 Triangle_dt find(Point_dt p)
          finds the triangle the query point falls in, note if out-side of this triangulation a half plane triangle will be returned (see contains), the search has expected time of O(n^0.5), and it starts form a fixed triangle (this.startTriangle),
 Triangle_dt find(Point_dt p, Triangle_dt start)
          finds the triangle the query point falls in, note if out-side of this triangulation a half plane triangle will be returned (see contains).
 java.util.Iterator<Triangle_dt> getLastUpdatedTriangles()
           
 int getModeCounter()
          returns the changes counter for this triangulation
 void insertPoint(Point_dt p)
          insert the point to this Delaunay Triangulation.
 int size()
          the number of (different) vertices in this triangulation.
 java.util.Iterator<Triangle_dt> trianglesIterator()
          computes the current set (vector) of all triangles and return an iterator to them.
 int trianglesSize()
           
 java.util.Iterator<Point_dt> verticesIterator()
           
 void write_CH(java.lang.String tsinFile)
           
 void write_tsin(java.lang.String tsinFile)
          write all the vertices of this triangulation to a text file of the following format
#vertices (n)
x1 y1 z1
...
 double z(double x, double y)
           
 Point_dt z(Point_dt q)
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

startTriangleHull

public Triangle_dt startTriangleHull
Constructor Detail

Delaunay_Triangulation

public Delaunay_Triangulation()
creates an empty Delaunay Triangulation.


Delaunay_Triangulation

public Delaunay_Triangulation(Point_dt[] ps)
creates a Delaunay Triangulation from all the points. Note: duplicated points are ignored.


Delaunay_Triangulation

public Delaunay_Triangulation(java.lang.String file)
                       throws java.lang.Exception
creates a Delaunay Triangulation from all the points in the suggested tsin file or from a smf file (off like). if the file name is .smf - read it as an smf file as try to read it as .tsin
Note: duplicated points are ignored!
SMF file has an OFF like format (a face (f) is presented by the indexes of its points - starting from 1 - NOTS from 0):
begin
v x1 y1 z1
...
v xn yn zn
f i11 i12 i13
...
f im1 im2 im3
end

The tsin text file has the following (very simple) format
vertices# (n)
x1 y1 z1
...
xn yn zn

Throws:
java.lang.Exception
Method Detail

size

public int size()
the number of (different) vertices in this triangulation.

Returns:
the number of vertices in the triangulation (duplicates are ignore - set size).

trianglesSize

public int trianglesSize()
Returns:
the number of triangles in the triangulation. Note: incluse infinife faces!!.

getModeCounter

public int getModeCounter()
returns the changes counter for this triangulation


insertPoint

public void insertPoint(Point_dt p)
insert the point to this Delaunay Triangulation. Note: if p is null of already exist in this triangulation p is ignored.

Parameters:
p - new vertex to be inserted the triangulation.

getLastUpdatedTriangles

public java.util.Iterator<Triangle_dt> getLastUpdatedTriangles()
Returns:
iterator to all triangles involved in the last update of the triangulation NOTE: works ONLY if the are triangles (it there is only a halh plane - returns an empty iterator

write_tsin

public void write_tsin(java.lang.String tsinFile)
                throws java.lang.Exception
write all the vertices of this triangulation to a text file of the following format
#vertices (n)
x1 y1 z1
...
xn yn zn

Throws:
java.lang.Exception

CH_size

public int CH_size()
compute the number of vertices in the convex hull. NOTE: has a 'bug-like' behavor: in cases of colinear - not on a asix parallel rectangle, colinear points are reported

Returns:
the number ov vertices in the convex hull.

write_CH

public void write_CH(java.lang.String tsinFile)
              throws java.lang.Exception
Throws:
java.lang.Exception

find

public Triangle_dt find(Point_dt p)
finds the triangle the query point falls in, note if out-side of this triangulation a half plane triangle will be returned (see contains), the search has expected time of O(n^0.5), and it starts form a fixed triangle (this.startTriangle),

Parameters:
p - query point
Returns:
the triangle p falls in.

find

public Triangle_dt find(Point_dt p,
                        Triangle_dt start)
finds the triangle the query point falls in, note if out-side of this triangulation a half plane triangle will be returned (see contains). the search starts from the the start triangle

Parameters:
p - query point
start - the triangle the search starts at.
Returns:
the triangle p falls in.

contains

public boolean contains(Point_dt p)
Parameters:
p - query point
Returns:
true iff p is within this triangulation.

contains

public boolean contains(double x,
                        double y)
Parameters:
x - - X cordination of the query point
y - - Y cordination of the query point
Returns:
true iff (x,y) falls inside this triangulation (in its 2D convex hull).

z

public Point_dt z(Point_dt q)
Parameters:
q - Query point
Returns:
the q point with updated Z value (z value is as given the triangulation).

z

public double z(double x,
                double y)
Parameters:
x - - X cordination of the query point
y - - Y cordination of the query point
Returns:
the q point with updated Z value (z value is as given the triangulation).

bb_min

public Point_dt bb_min()
return the min point of the bounding box of this triangulation {{x0,y0,z0}}


bb_max

public Point_dt bb_max()
return the max point of the bounding box of this triangulation {{x1,y1,z1}}


trianglesIterator

public java.util.Iterator<Triangle_dt> trianglesIterator()
computes the current set (vector) of all triangles and return an iterator to them.


CH_vertices_Iterator

public java.util.Iterator<Point_dt> CH_vertices_Iterator()
Returns:
iterator to the set of all the points on the XY-convex hull.

verticesIterator

public java.util.Iterator<Point_dt> verticesIterator()
Returns:
iterator to the set of points compusing this triangulation.