001: /*
002: * Copyright (c) 2005 by L. Paul Chew.
003: *
004: * Permission is hereby granted, without written agreement and without
005: * license or royalty fees, to use, copy, modify, and distribute this
006: * software and its documentation for any purpose, subject to the following
007: * conditions:
008: *
009: * The above copyright notice and this permission notice shall be included
010: * in all copies or substantial portions of the Software.
011: *
012: * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
013: * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
014: * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
015: * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
016: * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
017: * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
018: * DEALINGS IN THE SOFTWARE.
019: */
020:
021: package org.openjump.core.graph.delauneySimplexInsert;
022:
023: import java.util.Collection;
024: import java.util.HashSet;
025: import java.util.Iterator;
026: import java.util.LinkedList;
027: import java.util.NoSuchElementException;
028: import java.util.Set;
029:
030: /**
031: * A 2D Delaunay Triangulation (DT) with incremental site insertion.
032: * This is not the fastest way to build a DT, but it's a reasonable way
033: * to build the DT incrementally and it makes a nice interactive display.
034: * There are several O(n log n) methods, but they require that either (1)
035: * the sites are all known initially or (2) the sites are inserted in random
036: * order.
037: *
038: * @author Paul Chew
039: *
040: * Created July 2005. Derived from an earlier, messier version.
041: */
042: public class DelaunayTriangulation extends Triangulation {
043:
044: private Simplex mostRecent = null; // Most recently inserted triangle
045: public boolean debug = false; // Used for debugging
046:
047: /**
048: * Constructor.
049: * All sites must fall within the initial triangle.
050: * @param triangle the initial triangle
051: */
052: public DelaunayTriangulation(Simplex triangle) {
053: super (triangle);
054: mostRecent = triangle;
055: }
056:
057: /**
058: * Locate the triangle with point (a Pnt) inside (or on) it.
059: * @param point the Pnt to locate
060: * @return triangle (Simplex<Pnt>) that holds the point; null if no such triangle
061: */
062: public Simplex locate(Pnt point) {
063: Simplex triangle = mostRecent;
064: if (!this .contains(triangle))
065: triangle = null;
066:
067: // Try a directed walk (this works fine in 2D, but can fail in 3D)
068: Set visited = new HashSet();
069: while (triangle != null) {
070: if (visited.contains(triangle)) { // This should never happen
071: System.out.println("Warning: Caught in a locate loop");
072: break;
073: }
074: visited.add(triangle);
075: // Corner opposite point
076: Pnt corner = point.isOutside((Pnt[]) triangle
077: .toArray(new Pnt[0]));
078: if (corner == null)
079: return triangle;
080: triangle = this .neighborOpposite(corner, triangle);
081: }
082: // No luck; try brute force
083: System.out.println("Warning: Checking all triangles for "
084: + point);
085: for (Iterator it = this .iterator(); it.hasNext();) {
086: Simplex tri = (Simplex) it.next();
087: if (point.isOutside((Pnt[]) tri.toArray(new Pnt[0])) == null)
088: return tri;
089: }
090: // No such triangle
091: System.out.println("Warning: No triangle holds " + point);
092: return null;
093: }
094:
095: /**
096: * Place a new point site into the DT.
097: * @param site the new Pnt
098: * @return set of all new triangles created
099: */
100: public Set delaunayPlace(Pnt site) {
101: Set newTriangles = new HashSet();
102: Set oldTriangles = new HashSet();
103: Set doneSet = new HashSet();
104: LinkedList waitingQ = new LinkedList();
105:
106: // Locate containing triangle
107: if (debug)
108: System.out.println("Locate");
109: Simplex triangle = locate(site);
110:
111: // Give up if no containing triangle or if site is already in DT
112: if (triangle == null || triangle.contains(site))
113: return newTriangles;
114:
115: // Find Delaunay cavity (those triangles with site in their circumcircles)
116: if (debug)
117: System.out.println("Cavity");
118: waitingQ.add(triangle);
119: while (!waitingQ.isEmpty()) {
120: triangle = (Simplex) waitingQ.removeFirst();
121: if (site.vsCircumcircle((Pnt[]) triangle
122: .toArray(new Pnt[0])) == 1)
123: continue;
124: oldTriangles.add(triangle);
125: Iterator it = this .neighbors(triangle).iterator();
126: for (; it.hasNext();) {
127: Simplex tri = (Simplex) it.next();
128: if (doneSet.contains(tri))
129: continue;
130: doneSet.add(tri);
131: waitingQ.add(tri);
132: }
133: }
134: // Create the new triangles
135: if (debug)
136: System.out.println("Create");
137: for (Iterator it = Simplex.boundary(oldTriangles).iterator(); it
138: .hasNext();) {
139: Set facet = (Set) it.next();
140: facet.add(site);
141: newTriangles.add(new Simplex(facet));
142: }
143: // Replace old triangles with new triangles
144: if (debug)
145: System.out.println("Update");
146: this .update(oldTriangles, newTriangles);
147:
148: // Update mostRecent triangle
149: if (!newTriangles.isEmpty())
150: mostRecent = (Simplex) newTriangles.iterator().next();
151: return newTriangles;
152: }
153:
154: /**
155: * Main program; used for testing.
156: */
157: public static void main(String[] args) {
158: Simplex tri = new Simplex(new Pnt[] { new Pnt(-10, 10),
159: new Pnt(10, 10), new Pnt(0, -10) });
160: System.out.println("Triangle created: " + tri);
161: DelaunayTriangulation dt = new DelaunayTriangulation(tri);
162: System.out.println("DelaunayTriangulation created: " + dt);
163: dt.delaunayPlace(new Pnt(0, 0));
164: dt.delaunayPlace(new Pnt(1, 0));
165: dt.delaunayPlace(new Pnt(0, 1));
166: System.out
167: .println("After adding 3 points, the DelaunayTriangulation is a "
168: + dt);
169: dt.printStuff();
170: }
171: }
|