| gvSIG desktop 1

/*

 * Copyright (c) 2005 by L. Paul Chew.

 * 

 * Permission is hereby granted, without written agreement and without

 * license or royalty fees, to use, copy, modify, and distribute this

 * software and its documentation for any purpose, subject to the following 

 * conditions:

 *

 * The above copyright notice and this permission notice shall be included 

 * in all copies or substantial portions of the Software.

 * 

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 

 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 

 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 

 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 

 * DEALINGS IN THE SOFTWARE.

 */

package com.iver.cit.gvsig.topology.triangulation;

import java.awt.geom.Point2D;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Set;

import com.vividsolutions.jts.geom.Coordinate;

/**

 * A 2D Delaunay Triangulation (DT) with incremental site insertion.

 * This is not the fastest way to build a DT, but it's a reasonable way

 * to build the DT incrementally and it makes a nice interactive display.

 * There are several O(n log n) methods, but they require that either (1) 

 * the sites are all known initially or (2) the sites are inserted in random

 * order.

 * 

 * @author Paul Chew

 * 

 * Created July 2005.  Derived from an earlier, messier version.

 */

public class DelaunayTriangulation extends Triangulation {

    private Simplex mostRecent = null;       // Most recently inserted triangle

    public boolean debug = false;            // Used for debugging

    private static double initialSize = Double.MAX_VALUE / 2.0;

//    private static Simplex initialTriangle = new Simplex(new Pnt[] {new Pnt(-10,10), new Pnt(10,10), new Pnt(0,-10)});

    private static Simplex initialTriangle = new Simplex(new Pnt[] {

            new Pnt(-initialSize, initialSize),

            new Pnt( initialSize, initialSize),

            new Pnt(           0,  -initialSize)});

    /**

     * Constructor.

     * All sites must fall within the initial triangle.

     * @param triangle the initial triangle

     */

    public DelaunayTriangulation (Simplex triangle) {

        super(triangle);

        mostRecent = triangle;

    }

    public DelaunayTriangulation()

    {

            super(initialTriangle);

            mostRecent = initialTriangle;

    }

    /**

     * Locate the triangle with point (a Pnt) inside (or on) it.

     * @param point the Pnt to locate

     * @return triangle (Simplex<Pnt>) that holds the point; null if no such triangle

     */

    public Simplex locate (Pnt point) {

        Simplex triangle = mostRecent;

        if (!this.contains(triangle)) triangle = null;

        // Try a directed walk (this works fine in 2D, but can fail in 3D)

        Set visited = new HashSet();

        while (triangle != null) {

            if (visited.contains(triangle)) { // This should never happen

                System.out.println("Warning: Caught in a locate loop");

                break;

            }

            visited.add(triangle);

            // Corner opposite point

            Pnt corner = point.isOutside((Pnt[]) triangle.toArray(new Pnt[0]));

            if (corner == null) return triangle;

            triangle = this.neighborOpposite(corner, triangle);

        }

        // No luck; try brute force

        System.out.println("Warning: Checking all triangles for " + point);

        for (Iterator it = this.iterator(); it.hasNext();) {

            Simplex tri = (Simplex) it.next();

            if (point.isOutside((Pnt[])tri.toArray(new Pnt[0])) == null) return tri;

        }

        // No such triangle

        System.out.println("Warning: No triangle holds " + point);

        return null;

    }

    /**

     * Place a new point site into the DT.

     * @param site the new Pnt

     * @return set of all new triangles created

     */

    public Set delaunayPlace (Pnt site) {

        Set newTriangles = new HashSet();

        Set oldTriangles = new HashSet();

        Set doneSet = new HashSet();

        LinkedList waitingQ = new LinkedList();

        // Locate containing triangle

        if (debug) System.out.println("Locate");

        Simplex triangle = locate(site);

        // Give up if no containing triangle or if site is already in DT

        if (triangle == null || triangle.contains(site)) return newTriangles;

        // Find Delaunay cavity (those triangles with site in their circumcircles)

        if (debug) System.out.println("Cavity");

        waitingQ.add(triangle);

        while (!waitingQ.isEmpty()) {

            triangle = (Simplex) waitingQ.removeFirst();      

            if (site.vsCircumcircle((Pnt[]) triangle.toArray(new Pnt[0])) == 1) continue;

            oldTriangles.add(triangle);

            Iterator it = this.neighbors(triangle).iterator();

            for (; it.hasNext();) {

                Simplex tri = (Simplex) it.next();

                if (doneSet.contains(tri)) continue;

                doneSet.add(tri);

                waitingQ.add(tri);

            }

        }

        // Create the new triangles

        if (debug) System.out.println("Create");

        for (Iterator it = Simplex.boundary(oldTriangles).iterator(); it.hasNext();) {

            Set facet = (Set) it.next();

            facet.add(site);

            newTriangles.add(new Simplex(facet));

        }

        // Replace old triangles with new triangles

        if (debug) System.out.println("Update");

        this.update(oldTriangles, newTriangles);

        // Update mostRecent triangle

        if (!newTriangles.isEmpty()) mostRecent = (Simplex) newTriangles.iterator().next();

        return newTriangles;

    }

    /**

     * Main program; used for testing.

     */

    public static void main (String[] args) {

//        Simplex tri = new Simplex(new Pnt[] {new Pnt(-10,10), new Pnt(10,10), new Pnt(0,-10)});

//        System.out.println("Triangle created: " + tri);

//        DelaunayTriangulation dt = new DelaunayTriangulation(tri);

            DelaunayTriangulation dt = new DelaunayTriangulation();

        System.out.println("DelaunayTriangulation created: " + dt);

        dt.delaunayPlace(new Pnt(0,0));

        dt.delaunayPlace(new Pnt(1,0));

        dt.delaunayPlace(new Pnt(0,1));

        System.out.println("After adding 3 points, the DelaunayTriangulation is a " + dt);

        dt.printStuff();

    }

    public void delaunayPlace(Point2D p)

    {

            Pnt aux = new Pnt(p.getX(), p.getY());

            delaunayPlace(aux);

    }

        public void delaunayPlace(Coordinate c) {

            Pnt aux = new Pnt(c.x, c.y);

            delaunayPlace(aux);                

        }

}