Package il.ac.idc.jdt

Class DelaunayTriangulation

java.lang.Object
il.ac.idc.jdt.DelaunayTriangulation
public class DelaunayTriangulation extends Object
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 invalid input: '&' 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/ .

  • Constructor Details

    • DelaunayTriangulation

      public DelaunayTriangulation()
      creates an empty Delaunay Triangulation.

    • DelaunayTriangulation

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

    • DelaunayTriangulation

      public DelaunayTriangulation(Collection<Point> points)

  • Method Details

    • 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: includes infinife faces!!.

    • getModeCounter

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

    • insertPoints

      public void insertPoints(Collection<Point> points)

    • insertPoint

      public void insertPoint(Point p)
      insert the point to this Delaunay Triangulation. Note: if p is null or already exist in this triangulation p is ignored.
      Parameters:
      p - new vertex to be inserted the triangulation.

    • deletePoint

      public void deletePoint(Point pointToDelete)
      Deletes the given point from this.
      Parameters:
      pointToDelete - The given point to delete. Implementation of the Mostafavia, Gold invalid input: '&' Dakowicz algorithm (2002). By Eyal Roth invalid input: '&' Doron Ganel (2009).

    • findClosePoint

      public Point findClosePoint(Point 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 invalid input: '&' Doron Ganel (2009).

    • calcVoronoiCell

      public Point[] calcVoronoiCell(Triangle triangle, Point 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 Iterator<Triangle> 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

    • getConvexHullSize

      public int getConvexHullSize()
      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.

    • find

      public Triangle find(Point 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 find(Point p, Triangle 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 Vector<Triangle> findTriangleNeighborhood(Triangle firstTriangle, Point point)

    • contains

      public boolean contains(Point 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 z(Point 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 minBoundingBox()
      return the min point of the bounding box of this triangulation {{x0,y0,z0}}

    • maxBoundingBox

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

    • trianglesIterator

      public Iterator<Triangle> trianglesIterator()
      computes the current set (vector) of all triangles and return an iterator to them.
      Returns:
      an iterator to the current set of all triangles.

    • getConvexHullVerticesIterator

      public Iterator<Point> getConvexHullVerticesIterator()
      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 Iterator<Point> verticesIterator()
      returns an iterator to the set of points compusing this 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

    • getTriangulation

      public List<Triangle> getTriangulation()