001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2006, GeoTools Project Managment Committee (PMC)
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation;
009: * version 2.1 of the License.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: */
016: package org.geotools.graph.util.delaunay;
017:
018: import com.vividsolutions.jts.geom.Coordinate;
019: import com.vividsolutions.jts.geom.Geometry;
020: import com.vividsolutions.jts.geom.Point;
021: import java.awt.geom.Ellipse2D;
022: import java.awt.geom.Line2D;
023: import java.awt.geom.Point2D;
024: import java.util.Arrays;
025: import java.util.Iterator;
026: import java.util.Vector;
027: import java.util.logging.Logger;
028: import org.geotools.feature.Feature;
029: import org.geotools.feature.FeatureCollection;
030: import org.geotools.feature.FeatureIterator;
031: import org.geotools.graph.structure.Edge;
032: import org.geotools.graph.structure.Graph;
033: import org.geotools.graph.structure.Node;
034: import org.geotools.graph.structure.basic.BasicEdge;
035: import org.geotools.graph.structure.basic.BasicGraph;
036: import org.geotools.graph.structure.line.BasicXYNode;
037: import org.geotools.graph.structure.line.XYNode;
038: import org.geotools.math.Line;
039:
040: /**
041: *
042: * @author jfc173
043: */
044: public class DelaunayTriangulator {
045:
046: public DelaunayNode temp1, temp2, temp3;
047: private DelaunayNode[] nodes;
048: private Vector triangleList;
049: private static final Logger LOGGER = org.geotools.util.logging.Logging
050: .getLogger("org.geotools.graph");
051:
052: /** Creates a new instance of delaunayTriangulator */
053: public DelaunayTriangulator() {
054: }
055:
056: public void setNodeArray(DelaunayNode[] nodeArray) {
057: nodes = nodeArray;
058: }
059:
060: public DelaunayNode[] getNodeArray() {
061: return nodes;
062: }
063:
064: public void setFeatureCollection(FeatureCollection data) {
065: nodes = featuresToNodes(data);
066: }
067:
068: public Vector getTriangles() {
069: return triangleList;
070: }
071:
072: public DelaunayNode[] featuresToNodes(FeatureCollection fc) {
073: FeatureIterator iter = fc.features();
074: int size = fc.size();
075: DelaunayNode[] nodes = new DelaunayNode[size];
076: int index = 0;
077: while (iter.hasNext()) {
078: Feature next = iter.next();
079: Geometry geom = next.getDefaultGeometry();
080: Point centroid;
081: if (geom instanceof Point) {
082: centroid = (Point) geom;
083: } else {
084: centroid = geom.getCentroid();
085: }
086: DelaunayNode node = new DelaunayNode();
087: node.setCoordinate(centroid.getCoordinate());
088: node.setFeature(next);
089: if (!(arrayContains(node, nodes, index))) {
090: nodes[index] = node;
091: index++;
092: }
093: }
094:
095: DelaunayNode[] trimmed = new DelaunayNode[index];
096: for (int i = 0; i < index; i++) {
097: trimmed[i] = nodes[i];
098: }
099:
100: return trimmed;
101: }
102:
103: private static boolean arrayContains(DelaunayNode node,
104: DelaunayNode[] nodes, int index) {
105: boolean ret = false;
106: boolean done = false;
107: int i = 0;
108: while (!(done)) {
109: if (i < index) {
110: done = ret = (nodes[i].equals(node));
111: i++;
112: } else {
113: done = true;
114: }
115: }
116: return ret;
117: }
118:
119: public Graph getTriangulation() {
120: //this algorithm is from "Computational Geometry: Algorithms and Applications" by M. de Berg et al.,
121: //written in 1997 and printed by Springer-Verlag (New York). Pseudocode from section 9.3 (pp. 190-194).
122: //A few additional checks for degenerate cases were needed. They're commented below.
123:
124: //find the initial bounding triangle and supplement the nodes with its corners
125: DelaunayNode[] tempNodes = new DelaunayNode[nodes.length + 3];
126: double max = 0;
127: for (int i = 0; i < nodes.length; i++) {
128: tempNodes[i] = nodes[i];
129: max = Math.max(max, Math.abs(nodes[i].getCoordinate().x));
130: max = Math.max(max, Math.abs(nodes[i].getCoordinate().y));
131: }
132: tempNodes[nodes.length] = new DelaunayNode();
133: tempNodes[nodes.length]
134: .setCoordinate(new Coordinate(0, 3 * max));
135: tempNodes[nodes.length + 1] = new DelaunayNode();
136: tempNodes[nodes.length + 1].setCoordinate(new Coordinate(
137: 3 * max, 0));
138: tempNodes[nodes.length + 2] = new DelaunayNode();
139: tempNodes[nodes.length + 2].setCoordinate(new Coordinate(-3
140: * max, -3 * max));
141:
142: temp1 = tempNodes[nodes.length];
143: temp2 = tempNodes[nodes.length + 1];
144: temp3 = tempNodes[nodes.length + 2];
145:
146: //initialize triangulation to the bounding triangle
147: triangleList = new Vector();
148: DelaunayEdge e1 = new DelaunayEdge(tempNodes[nodes.length],
149: tempNodes[nodes.length + 1]);
150: DelaunayEdge e2 = new DelaunayEdge(tempNodes[nodes.length],
151: tempNodes[nodes.length + 2]);
152: DelaunayEdge e3 = new DelaunayEdge(tempNodes[nodes.length + 1],
153: tempNodes[nodes.length + 2]);
154: Triangle first = new Triangle(e1, e2, e3);
155: e1.setFaceA(first);
156: e2.setFaceA(first);
157: e3.setFaceA(first);
158:
159: DelaunayNode U1 = new DelaunayNode();
160: U1.setCoordinate(new Coordinate(Double.POSITIVE_INFINITY, 0));
161: DelaunayNode U2 = new DelaunayNode();
162: U2.setCoordinate(new Coordinate(0, Double.POSITIVE_INFINITY));
163: DelaunayNode U3 = new DelaunayNode();
164: U3.setCoordinate(new Coordinate(Double.NEGATIVE_INFINITY,
165: Double.NEGATIVE_INFINITY));
166: Triangle UNBOUNDED = new Triangle(new DelaunayEdge(U1, U2),
167: new DelaunayEdge(U1, U3), new DelaunayEdge(U2, U3));
168:
169: e1.setFaceB(UNBOUNDED);
170: e2.setFaceB(UNBOUNDED);
171: e3.setFaceB(UNBOUNDED);
172:
173: triangleList.add(first);
174:
175: //add nodes one at a time.
176: for (int i = 0; i < nodes.length; i++) {
177: System.out.println("triangulating node " + i);
178: triangleList = insertNode(tempNodes[i], triangleList);
179: }
180:
181: Graph g = triangleListToGraph(triangleList);
182:
183: return g;
184: }
185:
186: public Graph triangleListToGraph(Vector tList) {
187: //turn what I've got into a proper GeoTools2 Graph!
188: //But don't include the three temporary nodes and all incident edges.
189: Vector edgeList = new Vector();
190: Vector nodeList = new Vector();
191: Iterator triangleIterator = tList.iterator();
192: while (triangleIterator.hasNext()) {
193: Triangle next = (Triangle) triangleIterator.next();
194: Edge[] edges = next.getEdges();
195: for (int i = 0; i < 3; i++) {
196: if (!(((DelaunayEdge) edges[i]).hasEndPoint(temp1) || //this test ensures that we don't
197: ((DelaunayEdge) edges[i]).hasEndPoint(temp2) || //add to the edge list any edges referring
198: ((DelaunayEdge) edges[i]).hasEndPoint(temp3))) { //to the temporary nodes
199: if (!(edgeList.contains(edges[i]))) {
200: edgeList.add(edges[i]);
201: edges[i].getNodeA().add(edges[i]);
202: edges[i].getNodeB().add(edges[i]);
203: if (!(nodeList.contains(edges[i].getNodeA()))) {
204: nodeList.add(edges[i].getNodeA());
205: }
206: if (!(nodeList.contains(edges[i].getNodeB()))) {
207: nodeList.add(edges[i].getNodeB());
208: }
209: }
210: }
211: }
212: }
213:
214: return new BasicGraph(nodeList, edgeList);
215: }
216:
217: public Vector insertNode(DelaunayNode newNode, Vector tList) {
218: //find triangle containing node or if node is on an edge, the two triangles bordering that edge.
219: //this finding-the-triangle section can be given better efficiency using the method on pp. 192-193 of book mentioned above.
220: Iterator triangleIterator = tList.iterator();
221: Triangle contains = null;
222: Triangle borderA = null;
223: Triangle borderB = null; //Note: assuming it's on the border of two triangles rather than at the intersection of 3 or more.
224: boolean notDone = true;
225: while ((triangleIterator.hasNext()) && (notDone)) {
226: Triangle next = (Triangle) triangleIterator.next();
227: int relation = next.relate(newNode);
228: switch (relation) {
229: case Triangle.INSIDE:
230: // System.out.println(newNode + " is inside " + next);
231: contains = next;
232: notDone = false;
233: break;
234:
235: case Triangle.ON_EDGE:
236: borderA = next;
237: borderB = ((DelaunayEdge) next.getBoundaryEdge(newNode))
238: .getOtherFace(next);
239: // System.out.println(newNode + " is on the border between " + borderA + " and " + borderB);
240: break;
241:
242: case Triangle.OUTSIDE:
243: notDone = true;
244: break;
245:
246: default:
247: throw new RuntimeException(
248: "So the point isn't inside, outside, or on the edge of this triangle?!");
249: } //end switch
250: }
251:
252: //Found the triangle(s). Now do something with them!
253: if (contains != null) {
254: //create three new triangles by adding edges from node to the vertices of contains
255: Node[] triangleNodes = contains.getNodes();
256: Edge[] triangleEdges = contains.getEdges();
257:
258: DelaunayEdge newEdgeP_0 = new DelaunayEdge(newNode,
259: (DelaunayNode) triangleNodes[0]);
260: DelaunayEdge newEdgeP_1 = new DelaunayEdge(newNode,
261: (DelaunayNode) triangleNodes[1]);
262: DelaunayEdge newEdgeP_2 = new DelaunayEdge(newNode,
263: (DelaunayNode) triangleNodes[2]);
264:
265: DelaunayEdge oldEdge0_1 = null;
266: DelaunayEdge oldEdge0_2 = null;
267: DelaunayEdge oldEdge1_2 = null;
268: for (int i = 0; i < 3; i++) {
269: if (((DelaunayEdge) triangleEdges[i])
270: .hasEndPoint((DelaunayNode) triangleNodes[0])) {
271: if (((DelaunayEdge) triangleEdges[i])
272: .hasEndPoint((DelaunayNode) triangleNodes[1])) {
273: oldEdge0_1 = (DelaunayEdge) triangleEdges[i];
274: } else {
275: oldEdge0_2 = (DelaunayEdge) triangleEdges[i];
276: }
277: } else {
278: oldEdge1_2 = (DelaunayEdge) triangleEdges[i];
279: }
280: }
281:
282: Triangle newTriangleP_0_1 = new Triangle(newEdgeP_0,
283: newEdgeP_1, oldEdge0_1);
284: Triangle newTriangleP_0_2 = new Triangle(newEdgeP_0,
285: newEdgeP_2, oldEdge0_2);
286: Triangle newTriangleP_1_2 = new Triangle(newEdgeP_1,
287: newEdgeP_2, oldEdge1_2);
288:
289: Triangle farSide0_1 = oldEdge0_1.getOtherFace(contains);
290: Triangle farSide0_2 = oldEdge0_2.getOtherFace(contains);
291: Triangle farSide1_2 = oldEdge1_2.getOtherFace(contains);
292:
293: oldEdge0_1.setOtherFace(newTriangleP_0_1, farSide0_1);
294: oldEdge0_2.setOtherFace(newTriangleP_0_2, farSide0_2);
295: oldEdge1_2.setOtherFace(newTriangleP_1_2, farSide1_2);
296:
297: newEdgeP_0.setFaceA(newTriangleP_0_1);
298: newEdgeP_0.setFaceB(newTriangleP_0_2);
299: newEdgeP_1.setFaceA(newTriangleP_0_1);
300: newEdgeP_1.setFaceB(newTriangleP_1_2);
301: newEdgeP_2.setFaceA(newTriangleP_0_2);
302: newEdgeP_2.setFaceB(newTriangleP_1_2);
303:
304: tList.remove(contains);
305: tList.add(newTriangleP_0_1);
306: tList.add(newTriangleP_0_2);
307: tList.add(newTriangleP_1_2);
308: LOGGER.finer("was inside " + contains);
309: LOGGER.finer("triangle List now is " + tList);
310: // System.out.println("triangle List now is " + tList);
311: //Make any necessary adjustments to other triangles.
312: legalizeEdge(newTriangleP_0_1, oldEdge0_1, newNode, tList);
313: legalizeEdge(newTriangleP_0_2, oldEdge0_2, newNode, tList);
314: legalizeEdge(newTriangleP_1_2, oldEdge1_2, newNode, tList);
315: LOGGER.finer("after legalization, triangle list now is: "
316: + triangleList);
317: // System.out.println("after legalization, triangle list now is: " + triangleList);
318:
319: } else if ((borderA != null) && (borderB != null)) {
320: //check to see that borderA and borderB share an edge. If not, whinge.
321: DelaunayEdge shared = (DelaunayEdge) borderA
322: .getSharedEdge(borderB);
323: if (shared == null) {
324: throw new RuntimeException(
325: "The two bordering triangles for a border case apparently don't share an edge(!)");
326: }
327:
328: //create four new triangles by adding edges from node to the vertices of borderA and borderB
329: DelaunayNode shared1 = (DelaunayNode) shared.getNodeA();
330: DelaunayNode shared2 = (DelaunayNode) shared.getNodeB();
331: DelaunayNode onlyInA = (DelaunayNode) borderA
332: .getThirdNode(shared);
333: DelaunayNode onlyInB = (DelaunayNode) borderB
334: .getThirdNode(shared);
335:
336: DelaunayEdge newEdgeP_1 = new DelaunayEdge(newNode, shared1);
337: DelaunayEdge newEdgeP_2 = new DelaunayEdge(newNode, shared2);
338: DelaunayEdge newEdgeP_A = new DelaunayEdge(newNode, onlyInA);
339: DelaunayEdge newEdgeP_B = new DelaunayEdge(newNode, onlyInB);
340:
341: DelaunayEdge oldEdgeA_1 = (DelaunayEdge) borderA
342: .getOppositeEdge(shared2);
343: DelaunayEdge oldEdgeA_2 = (DelaunayEdge) borderA
344: .getOppositeEdge(shared1);
345: DelaunayEdge oldEdgeB_1 = (DelaunayEdge) borderB
346: .getOppositeEdge(shared2);
347: DelaunayEdge oldEdgeB_2 = (DelaunayEdge) borderB
348: .getOppositeEdge(shared1);
349:
350: Triangle farSideA_1 = oldEdgeA_1.getOtherFace(borderA);
351: Triangle farSideA_2 = oldEdgeA_2.getOtherFace(borderA);
352: Triangle farSideB_1 = oldEdgeB_1.getOtherFace(borderB);
353: Triangle farSideB_2 = oldEdgeB_2.getOtherFace(borderB);
354:
355: Triangle newTriangleP_A_1 = new Triangle(newEdgeP_A,
356: newEdgeP_1, oldEdgeA_1);
357: Triangle newTriangleP_A_2 = new Triangle(newEdgeP_A,
358: newEdgeP_2, oldEdgeA_2);
359: Triangle newTriangleP_B_1 = new Triangle(newEdgeP_B,
360: newEdgeP_1, oldEdgeB_1);
361: Triangle newTriangleP_B_2 = new Triangle(newEdgeP_B,
362: newEdgeP_2, oldEdgeB_2);
363:
364: newEdgeP_A.setFaceA(newTriangleP_A_1);
365: newEdgeP_A.setFaceB(newTriangleP_A_2);
366: newEdgeP_B.setFaceA(newTriangleP_B_1);
367: newEdgeP_B.setFaceB(newTriangleP_B_2);
368: newEdgeP_1.setFaceA(newTriangleP_A_1);
369: newEdgeP_1.setFaceB(newTriangleP_B_1);
370: newEdgeP_2.setFaceA(newTriangleP_A_2);
371: newEdgeP_2.setFaceB(newTriangleP_B_2);
372:
373: oldEdgeA_1.setOtherFace(newTriangleP_A_1, farSideA_1);
374: oldEdgeA_2.setOtherFace(newTriangleP_A_2, farSideA_2);
375: oldEdgeB_1.setOtherFace(newTriangleP_B_1, farSideB_1);
376: oldEdgeB_2.setOtherFace(newTriangleP_B_2, farSideB_2);
377:
378: shared.disconnect();
379:
380: tList.remove(borderA);
381: tList.remove(borderB);
382: tList.add(newTriangleP_A_1);
383: tList.add(newTriangleP_A_2);
384: tList.add(newTriangleP_B_1);
385: tList.add(newTriangleP_B_2);
386: LOGGER.finer("bordered " + borderA + " and " + borderB);
387: LOGGER.finer("triangle list now is " + tList);
388:
389: legalizeEdge(newTriangleP_A_1, oldEdgeA_1, newNode, tList);
390: legalizeEdge(newTriangleP_A_2, oldEdgeA_2, newNode, tList);
391: legalizeEdge(newTriangleP_B_1, oldEdgeB_1, newNode, tList);
392: legalizeEdge(newTriangleP_B_2, oldEdgeB_2, newNode, tList);
393: LOGGER.finer("after legalization, triangle list now is: "
394: + triangleList);
395: } else {
396: throw new RuntimeException(
397: "What the? It isn't in any triangle or on any borders?");
398: }
399: return tList;
400: }
401:
402: private void legalizeEdge(Triangle t, DelaunayEdge e,
403: DelaunayNode p, Vector triangleList) {
404: LOGGER.fine("legalizing " + t + " and " + e.getOtherFace(t));
405: if (isIllegal(t, e, p)) {
406: Triangle otherFace = e.getOtherFace(t);
407: LOGGER.finer("switch internal edge");
408: // System.out.println("switch internal edge");
409: DelaunayNode fourthCorner = (DelaunayNode) otherFace
410: .getThirdNode(e);
411: DelaunayNode eNodeA = (DelaunayNode) e.getNodeA();
412: DelaunayNode eNodeB = (DelaunayNode) e.getNodeB();
413: //replace e with a new edge from p to fourthCorner
414: DelaunayEdge edgeP_4 = new DelaunayEdge(p, fourthCorner);
415: DelaunayEdge edgeP_A = (DelaunayEdge) t
416: .getOppositeEdge(eNodeB);
417: DelaunayEdge edgeP_B = (DelaunayEdge) t
418: .getOppositeEdge(eNodeA);
419: DelaunayEdge edgeA_4 = (DelaunayEdge) otherFace
420: .getOppositeEdge(eNodeB);
421: DelaunayEdge edgeB_4 = (DelaunayEdge) otherFace
422: .getOppositeEdge(eNodeA);
423:
424: Triangle farSideP_A = edgeP_A.getOtherFace(t);
425: Triangle farSideP_B = edgeP_B.getOtherFace(t);
426: Triangle farSideA_4 = edgeA_4.getOtherFace(otherFace);
427: Triangle farSideB_4 = edgeB_4.getOtherFace(otherFace);
428:
429: Triangle newTriangleP_A_4 = new Triangle(edgeP_A, edgeA_4,
430: edgeP_4);
431: Triangle newTriangleP_B_4 = new Triangle(edgeP_B, edgeB_4,
432: edgeP_4);
433:
434: if (rejectSwap(t, otherFace, newTriangleP_A_4,
435: newTriangleP_B_4)) { //Degenerate case. Explained in the method rejectSwap
436: LOGGER.finer("Rejected swap of " + t + " and "
437: + otherFace);
438: // System.out.println("Rejected swap of " + t + " and " + otherFace);
439: } else {
440: edgeP_A.setOtherFace(newTriangleP_A_4, farSideP_A);
441: edgeP_B.setOtherFace(newTriangleP_B_4, farSideP_B);
442: edgeA_4.setOtherFace(newTriangleP_A_4, farSideA_4);
443: edgeB_4.setOtherFace(newTriangleP_B_4, farSideB_4);
444:
445: edgeP_4.setFaceA(newTriangleP_A_4);
446: edgeP_4.setFaceB(newTriangleP_B_4);
447:
448: e.disconnect();
449:
450: triangleList.remove(t);
451: triangleList.remove(otherFace);
452: triangleList.add(newTriangleP_A_4);
453: triangleList.add(newTriangleP_B_4);
454: LOGGER.finer("swapped " + t + " and " + otherFace);
455: LOGGER.finer("new triangles are " + newTriangleP_A_4
456: + " and " + newTriangleP_B_4);
457: LOGGER.finer("Triangle list now is: " + triangleList);
458: // System.out.println("swapped " + t + " and " + otherFace);
459: // System.out.println("new triangles are " + newTriangleP_A_4 + " and " + newTriangleP_B_4);
460: // System.out.println("Triangle list now is: " + triangleList);
461: legalizeEdge(newTriangleP_A_4, edgeA_4, p, triangleList);
462: legalizeEdge(newTriangleP_B_4, edgeB_4, p, triangleList);
463: }
464: }
465: }
466:
467: private boolean isTemporary(DelaunayNode n) {
468: return ((n.equals(temp1)) || (n.equals(temp2)) || (n
469: .equals(temp3)));
470: }
471:
472: private boolean isIllegal(Triangle t, DelaunayEdge e, DelaunayNode p) {
473: DelaunayNode eNodeA = (DelaunayNode) e.getNodeA();
474: DelaunayNode eNodeB = (DelaunayNode) e.getNodeB();
475:
476: if (isTemporary(eNodeA) && isTemporary(eNodeB)) {
477: return false;
478: }
479:
480: DelaunayNode farNode = (DelaunayNode) e.getOtherFace(t)
481: .getThirdNode(e);
482:
483: DelaunayEdge p_a = ((DelaunayEdge) t.getOppositeEdge(e
484: .getNodeB()));
485: DelaunayEdge p_b = ((DelaunayEdge) t.getOppositeEdge(e
486: .getNodeA()));
487: DelaunayNode farNodeP_A = (DelaunayNode) p_a.getOtherFace(t)
488: .getThirdNode(p_a);
489: DelaunayNode farNodeP_B = (DelaunayNode) p_b.getOtherFace(t)
490: .getThirdNode(p_b);
491:
492: if ((farNode.equals(farNodeP_A))
493: || (farNode.equals(farNodeP_B))) {
494: //Degenerate case. There's already a line between p and farnode (p and k in the book) making either
495: //p_farnode_A or p_farNode_B a triangle already in the triangulation. This will eventually manifest
496: //itself as trying to create a triangle with two points.... Not a good situation.
497: return false;
498: }
499:
500: int numTemporary = 0;
501: if (isTemporary(eNodeA)) {
502: numTemporary++;
503: }
504: if (isTemporary(eNodeB)) {
505: numTemporary++;
506: }
507: if (isTemporary(p)) {
508: numTemporary++;
509: }
510: if (isTemporary(farNode)) {
511: numTemporary++;
512: }
513:
514: if (numTemporary == 0) {
515: Ellipse2D.Double circum = constructCircle(p, eNodeA, eNodeB);
516: Point2D.Double point = new Point2D.Double(farNode
517: .getCoordinate().x, farNode.getCoordinate().y);
518: if (circum.contains(point)) {
519: LOGGER.finer("Illegal by case 2");
520: // System.out.println("Illegal by case 2");
521: return true;
522: } else {
523: return false;
524: }
525: } else if (numTemporary == 1) {
526: if (isTemporary(eNodeA) || isTemporary(eNodeB)) {
527: LOGGER.finer("Illegal by case 3");
528: // System.out.println("Illegal by case 3");
529: return true;
530: } else {
531: return false;
532: }
533: } else if (numTemporary == 2) {
534: int i = whichSpecialNode(eNodeA, eNodeB);
535: int j = whichSpecialNode(p, farNode);
536: if (i < j) { //originally i<j. i<j for messedUp3.doc, i>j for messedUp1.doc
537: return false;
538: } else {
539: LOGGER.finer("Illegal by case 4");
540: // System.out.println("Illegal by case 4");
541: return true;
542: }
543: } else {
544: throw new RuntimeException(
545: "Problem in DelaunayTriangulator.isIllegal--This shouldn't've happened!");
546: }
547: }
548:
549: private int whichSpecialNode(DelaunayNode a, DelaunayNode b) {
550: if ((a.equals(temp1)) || (b.equals(temp1))) {
551: return 1;
552: } else if ((a.equals(temp2)) || (b.equals(temp2))) {
553: return 2;
554: } else if ((a.equals(temp3)) || (b.equals(temp3))) {
555: return 3;
556: } else {
557: throw new RuntimeException(
558: "I shouldn't be here. Either node a or node b should be temporary.");
559: }
560: }
561:
562: private static Ellipse2D.Double constructCircle(DelaunayNode a,
563: DelaunayNode b, DelaunayNode c) {
564: //center of this circle is the intersection of the perpendicular bisectors of the triangle
565:
566: Point2D.Double midPointA_B = new Point2D.Double((a
567: .getCoordinate().x + b.getCoordinate().x) / 2, (a
568: .getCoordinate().y + b.getCoordinate().y) / 2);
569: double deltaXA_B = a.getCoordinate().x - midPointA_B.getX();
570: double deltaYA_B = a.getCoordinate().y - midPointA_B.getY();
571:
572: Line bisectorA_B = new Line();
573: bisectorA_B.setLine(new Point2D.Double(
574: (midPointA_B.getX() + 100 * deltaYA_B), (midPointA_B
575: .getY() - 100 * deltaXA_B)),
576: new Point2D.Double(
577: (midPointA_B.getX() - 100 * deltaYA_B),
578: (midPointA_B.getY() + 100 * deltaXA_B)));
579:
580: Point2D.Double midPointA_C = new Point2D.Double((a
581: .getCoordinate().x + c.getCoordinate().x) / 2, (a
582: .getCoordinate().y + c.getCoordinate().y) / 2);
583: double deltaXA_C = a.getCoordinate().x - midPointA_C.getX();
584: double deltaYA_C = a.getCoordinate().y - midPointA_C.getY();
585:
586: Line bisectorA_C = new Line();
587:
588: Point2D intersection = null;
589: int i = 1;
590: do {
591: bisectorA_C.setLine(
592: new Point2D.Double((midPointA_C.getX() + Math.pow(
593: 100, i)
594: * deltaYA_C), (midPointA_C.getY() - Math
595: .pow(100, i)
596: * deltaXA_C)), new Point2D.Double(
597: (midPointA_C.getX() - Math.pow(100, i)
598: * deltaYA_C),
599: (midPointA_C.getY() + Math.pow(100, i)
600: * deltaXA_C)));
601: intersection = bisectorA_B.intersectionPoint(bisectorA_C);
602: i++;
603: } while (intersection == null);
604:
605: //radius is the distance to the three points (which is hopefully the same!)
606: double radius = intersection.distance(a.getCoordinate().x, a
607: .getCoordinate().y);
608:
609: //convert from center-radius to the java format
610: Ellipse2D.Double circle = new Ellipse2D.Double(intersection
611: .getX()
612: - radius, intersection.getY() - radius, 2 * radius,
613: 2 * radius);
614:
615: return circle;
616: }
617:
618: private boolean rejectSwap(Triangle oldFirst, Triangle oldSecond,
619: Triangle newFirst, Triangle newSecond) {
620: //I want to reject the swap if the new edge intersects any other edges in the graph, which can happen in
621: //the case where A or B (i or j in the book) is one of the bounding triangle points. This (I think)
622: //is equivalent to ensuring that the areas of the new triangles is the same as the areas of the old triangles.
623: double oldArea = oldFirst.getArea() + oldSecond.getArea();
624: double newArea = newFirst.getArea() + newSecond.getArea();
625: double diff = newArea - oldArea;
626: // System.out.println("area difference is " + diff);
627: double tolerance = 0.000001;
628: return (diff > tolerance);
629: }
630:
631: }
|