Package il.ac.idc.jdt

Class 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 & 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 Detail

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

      • getModeCounter

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

      • 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 & Dakowicz algorithm (2002). By Eyal Roth & 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 & 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..

      • 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()