org.jzy3d.plot3d.builder.delaunay.jdt
Class Delaunay_Triangulation

java.lang.Object
  org.jzy3d.plot3d.builder.delaunay.jdt.Delaunay_Triangulation

All Implemented Interfaces:

Triangulation

public class Delaunay_Triangulation
extends java.lang.Object
implements Triangulation

This class represents a Delaunay Triangulation. The class was written for a large scale triangulation (1000 - 200,000 vertices). The application main use is 3D surface (terrain) presentation.
The class main properties are the following:
- fast point location. (O(n^0.5)), practical runtime is often very fast.
- 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 (done in early 2005): 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: benmo@ariel.ac.il

Author:

Boaz Ben Moshe 5/11/05
The project uses some ideas presented in the VoroGuide project, written by Klasse f?r Kreise (1996-1997), For the original applet see: http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/ .

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). if the file name is .smf - read it as an smf file as try to read it as .tsin
Note: duplicated points are ignored!

Method Summary

Point_dt[]	calcVoronoiCell(Triangle_dt triangle, Point_dt p) Calculates a Voronoi cell for a given neighborhood in this triangulation.
int	CH_size() compute the number of vertices in the convex hull.
java.util.Iterator<Point_dt>	CH_vertices_Iterator() returns an iterator to the set of all the points on the XY-convex hull
boolean	contains(double x, double y)
boolean	contains(Point_dt p)
void	deletePoint(Point_dt pointToDelete) Deletes the given point from this.
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). the search starts from the the start triangle
Point_dt	findClosePoint(Point_dt pointToDelete) return a point from the trangulation that is close to pointToDelete
java.util.Vector<Triangle_dt>	findTriangleNeighborhood(Triangle_dt firstTriangle, Point_dt point)
BoundingBox	getBoundingBox()
java.util.Iterator<Triangle_dt>	getLastUpdatedTriangles() returns an iterator object involved in the last update.
int	getModeCounter() returns the changes counter for this triangulation
void	IndexData(int xCellCount, int yCellCount) Index the triangulation using a grid index
void	insertPoint(Point_dt p) insert the point to this Delaunay Triangulation.
Point_dt	maxBoundingBox() return the max point of the bounding box of this triangulation {{x1,y1,z1}}
Point_dt	minBoundingBox() return the min point of the bounding box of this triangulation {{x0,y0,z0}}
void	RemoveIndex() Remove any existing spatial indexing
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() returns an iterator to the set of points compusing this triangulation.
void	write_CH(java.lang.String tsinFile)
void	write_smf(java.lang.String smfFile) this method write the triangulation as an SMF file (OFF like format)
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 - not 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()

Specified by:

trianglesSize in interface Triangulation

Returns:

the number of triangles in the triangulation.
Note: includes 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 or already exist in this triangulation p is ignored.

Specified by:

insertPoint in interface Triangulation

Parameters:

p - new vertex to be inserted the triangulation.

deletePoint

public void deletePoint(Point_dt pointToDelete)

Deletes the given point from this.

Parameters:

pointToDelete - The given point to delete. Implementation of the Mostafavia, Gold & Dakowicz algorithm (2002). By Eyal Roth & Doron Ganel (2009).

findClosePoint

public Point_dt findClosePoint(Point_dt pointToDelete)

return a point from the trangulation that is close to pointToDelete

Parameters:

pointToDelete - the point that the user wants to delete

Returns:

a point from the trangulation that is close to pointToDelete By Eyal Roth & Doron Ganel (2009).

calcVoronoiCell

public Point_dt[] calcVoronoiCell(Triangle_dt triangle,
                                  Point_dt p)

Calculates a Voronoi cell for a given neighborhood in this triangulation. A neighborhood is defined by a triangle and one of its corner points. By Udi Schneider

Parameters:

triangle - a triangle in the neighborhood

p - corner point whose surrounding neighbors will be checked

Returns:

set of Points representing the cell polygon

getLastUpdatedTriangles

public java.util.Iterator<Triangle_dt> getLastUpdatedTriangles()

returns an iterator object involved in the last update.

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 half 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

write_smf

public void write_smf(java.lang.String smfFile)
               throws java.lang.Exception

this method write the triangulation as an SMF file (OFF like format)

Parameters:

smfFile - - file name

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 of 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 that point p is 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 that point p is in..

findTriangleNeighborhood

public java.util.Vector<Triangle_dt> findTriangleNeighborhood(Triangle_dt firstTriangle,
                                                              Point_dt point)

contains

public boolean contains(Point_dt p)

Parameters:

p - query point

Returns:

true iff p is within this triangulation (in its 2D convex hull).

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).

getBoundingBox

public BoundingBox getBoundingBox()

Returns:

The bounding rectange between the minimum and maximum coordinates

minBoundingBox

public Point_dt minBoundingBox()

return the min point of the bounding box of this triangulation {{x0,y0,z0}}

maxBoundingBox

public Point_dt maxBoundingBox()

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.

Specified by:

trianglesIterator in interface Triangulation

Returns:

an iterator to the current set of all triangles.

CH_vertices_Iterator

public java.util.Iterator<Point_dt> CH_vertices_Iterator()

returns an iterator to the set of all the points on the XY-convex hull

Returns:

iterator to the set of all the points on the XY-convex hull.

verticesIterator

public java.util.Iterator<Point_dt> verticesIterator()

returns an iterator to the set of points compusing this triangulation.

Specified by:

verticesIterator in interface Triangulation

Returns:

iterator to the set of points compusing this triangulation.

IndexData

public void IndexData(int xCellCount,
                      int yCellCount)

Index the triangulation using a grid index

Parameters:

xCellCount - number of grid cells in a row

yCellCount - number of grid cells in a column

RemoveIndex

public void RemoveIndex()

Remove any existing spatial indexing