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.GeometryFactory;
020: import com.vividsolutions.jts.geom.LinearRing;
021: import com.vividsolutions.jts.geom.Point;
022: import com.vividsolutions.jts.geom.Polygon;
023: import java.awt.geom.Line2D;
024: import java.awt.geom.Point2D;
025: import org.geotools.graph.structure.Edge;
026: import org.geotools.graph.structure.Node;
027: import org.geotools.graph.structure.line.XYNode;
028:
029: /**
030: *
031: * @author jfc173
032: */
033: public class Triangle {
034:
035: Edge edge1, edge2, edge3;
036: Node node1, node2, node3;
037: GeometryFactory fact = new GeometryFactory();
038:
039: public final static int OUTSIDE = 0;
040: public final static int INSIDE = 1;
041: public final static int ON_EDGE = 2;
042: private final static double TOLERANCE = 0.0001;
043:
044: /** Creates a new instance of Triangle */
045: public Triangle(Edge e1, Edge e2, Edge e3) {
046: Node n1a = e1.getNodeA();
047: Node n1b = e1.getNodeB();
048: Node n2a = e2.getNodeA();
049: Node n2b = e2.getNodeB();
050: Node n3a = e3.getNodeA();
051: Node n3b = e3.getNodeB();
052:
053: Node temp1, temp2, temp3;
054: if (n1a.equals(n2a)) {
055: temp1 = n1a; //==n2a
056: temp2 = n1b;
057: temp3 = n2b;
058: if (n3a.equals(temp2)) {
059: if (n3b.equals(temp3)) {
060: assign(e1, e2, e3, temp1, temp2, temp3);
061: } else {
062: whinge(e1, e2, e3);
063: }
064: } else if (n3a.equals(temp3)) {
065: if (n3b.equals(temp2)) {
066: assign(e1, e2, e3, temp1, temp2, temp3);
067: } else {
068: whinge(e1, e2, e3);
069: }
070: } else {
071: whinge(e1, e2, e3);
072: }
073: } else if (n1a.equals(n2b)) {
074: temp1 = n1a; //==n2b
075: temp2 = n1b;
076: temp3 = n2a;
077: if (n3a.equals(temp2)) {
078: if (n3b.equals(temp3)) {
079: assign(e1, e2, e3, temp1, temp2, temp3);
080: } else {
081: whinge(e1, e2, e3);
082: }
083: } else if (n3a.equals(temp3)) {
084: if (n3b.equals(temp2)) {
085: assign(e1, e2, e3, temp1, temp2, temp3);
086: } else {
087: whinge(e1, e2, e3);
088: }
089: } else {
090: whinge(e1, e2, e3);
091: }
092: } else if (n1b.equals(n2a)) {
093: temp1 = n1a;
094: temp2 = n1b; //==n2a
095: temp3 = n2b;
096: if (n3a.equals(temp1)) {
097: if (n3b.equals(temp3)) {
098: assign(e1, e2, e3, temp1, temp2, temp3);
099: } else {
100: whinge(e1, e2, e3);
101: }
102: } else if (n3a.equals(temp3)) {
103: if (n3b.equals(temp1)) {
104: assign(e1, e2, e3, temp1, temp2, temp3);
105: } else {
106: whinge(e1, e2, e3);
107: }
108: } else {
109: whinge(e1, e2, e3);
110: }
111: } else if (n1b.equals(n2b)) {
112: temp1 = n1a;
113: temp2 = n1b; //==n2b
114: temp3 = n2a;
115: if (n3a.equals(temp1)) {
116: if (n3b.equals(temp3)) {
117: assign(e1, e2, e3, temp1, temp2, temp3);
118: } else {
119: whinge(e1, e2, e3);
120: }
121: } else if (n3a.equals(temp3)) {
122: if (n3b.equals(temp1)) {
123: assign(e1, e2, e3, temp1, temp2, temp3);
124: } else {
125: whinge(e1, e2, e3);
126: }
127: } else {
128: whinge(e1, e2, e3);
129: }
130: } else {
131: whinge(e1, e2, e3);
132: }
133:
134: }
135:
136: private void assign(Edge e1, Edge e2, Edge e3, Node n1, Node n2,
137: Node n3) {
138: edge1 = e1;
139: edge2 = e2;
140: edge3 = e3;
141: node1 = n1;
142: node2 = n2;
143: node3 = n3;
144: }
145:
146: private void whinge(Edge e1, Edge e2, Edge e3) {
147: throw new RuntimeException(
148: "You didn't give me a proper triangle. " + e1 + ", "
149: + e2 + ", " + e3);
150: }
151:
152: public int relate(XYNode n) {
153: int ret;
154: if ((!(node1 instanceof XYNode))
155: || (!(node2 instanceof XYNode))
156: || (!(node3 instanceof XYNode))) {
157: throw new RuntimeException(
158: "I can't perform a relate function on a non-spatial triangle");
159: }
160: LinearRing lr = fact.createLinearRing(new Coordinate[] {
161: ((XYNode) node1).getCoordinate(),
162: ((XYNode) node2).getCoordinate(),
163: ((XYNode) node3).getCoordinate(),
164: ((XYNode) node1).getCoordinate() });
165: Polygon poly = fact.createPolygon(lr, null);
166: Point nPoint = fact.createPoint(n.getCoordinate());
167:
168: Line2D.Double line12 = new Line2D.Double(((XYNode) node1)
169: .getCoordinate().x, ((XYNode) node1).getCoordinate().y,
170: ((XYNode) node2).getCoordinate().x, ((XYNode) node2)
171: .getCoordinate().y);
172: Line2D.Double line13 = new Line2D.Double(((XYNode) node1)
173: .getCoordinate().x, ((XYNode) node1).getCoordinate().y,
174: ((XYNode) node3).getCoordinate().x, ((XYNode) node3)
175: .getCoordinate().y);
176: Line2D.Double line23 = new Line2D.Double(((XYNode) node2)
177: .getCoordinate().x, ((XYNode) node2).getCoordinate().y,
178: ((XYNode) node3).getCoordinate().x, ((XYNode) node3)
179: .getCoordinate().y);
180: Point2D.Double point2D = new Point2D.Double(
181: n.getCoordinate().x, n.getCoordinate().y);
182: if ((line12.ptSegDist(point2D) <= TOLERANCE)
183: || (line13.ptSegDist(point2D) <= TOLERANCE)
184: || (line23.ptSegDist(point2D) <= TOLERANCE)) {
185: ret = ON_EDGE;
186: } else if (poly.contains(nPoint)) {
187: ret = INSIDE;
188: } else {
189: ret = OUTSIDE;
190: }
191: return ret;
192: }
193:
194: public Edge getBoundaryEdge(XYNode n) {
195: if (!(relate(n) == ON_EDGE)) {
196: throw new RuntimeException(
197: "Can't get the boundary edge for a point that isn't on an edge.");
198: }
199: Point2D.Double point = new Point2D.Double(n.getCoordinate().x,
200: n.getCoordinate().y);
201: Line2D.Double line1 = new Line2D.Double(((XYNode) edge1
202: .getNodeA()).getCoordinate().x, ((XYNode) edge1
203: .getNodeA()).getCoordinate().y, ((XYNode) edge1
204: .getNodeB()).getCoordinate().x, ((XYNode) edge1
205: .getNodeB()).getCoordinate().y);
206: Line2D.Double line2 = new Line2D.Double(((XYNode) edge2
207: .getNodeA()).getCoordinate().x, ((XYNode) edge2
208: .getNodeA()).getCoordinate().y, ((XYNode) edge2
209: .getNodeB()).getCoordinate().x, ((XYNode) edge2
210: .getNodeB()).getCoordinate().y);
211: Line2D.Double line3 = new Line2D.Double(((XYNode) edge3
212: .getNodeA()).getCoordinate().x, ((XYNode) edge3
213: .getNodeA()).getCoordinate().y, ((XYNode) edge3
214: .getNodeB()).getCoordinate().x, ((XYNode) edge3
215: .getNodeB()).getCoordinate().y);
216: Edge ret = null;
217: if (line1.ptSegDist(point) <= TOLERANCE) {
218: ret = edge1;
219: } else if (line2.ptSegDist(point) <= TOLERANCE) {
220: ret = edge2;
221: } else if (line3.ptSegDist(point) <= TOLERANCE) {
222: ret = edge3;
223: } else {
224: throw new RuntimeException("So... node " + n
225: + " is on an edge of " + this .toString()
226: + " but isn't on any of its edges: " + edge1 + ", "
227: + edge2 + ", or " + edge3);
228: }
229: return ret;
230: }
231:
232: public Node getThirdNode(Edge e) {
233: if (e.getNodeA().equals(node1)) {
234: if (e.getNodeB().equals(node2)) {
235: return node3;
236: } else if (e.getNodeB().equals(node3)) {
237: return node2;
238: } else {
239: throw new RuntimeException(
240: "Edge e must be in this triangle for Triangle.getThirdNode to work!");
241: }
242: } else if (e.getNodeA().equals(node2)) {
243: if (e.getNodeB().equals(node1)) {
244: return node3;
245: } else if (e.getNodeB().equals(node3)) {
246: return node1;
247: } else {
248: throw new RuntimeException(
249: "Edge e must be in this triangle for Triangle.getThirdNode to work!");
250: }
251: } else if (e.getNodeA().equals(node3)) {
252: if (e.getNodeB().equals(node2)) {
253: return node1;
254: } else if (e.getNodeB().equals(node1)) {
255: return node2;
256: } else {
257: throw new RuntimeException(
258: "Edge e must be in this triangle for Triangle.getThirdNode to work!");
259: }
260: } else {
261: throw new RuntimeException("Edge " + e
262: + " must be in this triangle " + this .toString()
263: + " for Triangle.getThirdNode to work!");
264: }
265: }
266:
267: public Edge getOppositeEdge(Node n) {
268: if ((edge1.getNodeA().equals(n) || (edge1.getNodeB().equals(n)))) {
269: if ((edge2.getNodeA().equals(n) || (edge2.getNodeB()
270: .equals(n)))) {
271: return edge3;
272: } else if ((edge3.getNodeA().equals(n) || (edge3.getNodeB()
273: .equals(n)))) {
274: return edge2;
275: } else {
276: throw new RuntimeException(
277: "Node n must be in this triangle for Triangle.getOppositeEdge to work!");
278: }
279: } else if ((edge2.getNodeA().equals(n) || (edge2.getNodeB()
280: .equals(n)))) {
281: if ((edge3.getNodeA().equals(n) || (edge3.getNodeB()
282: .equals(n)))) {
283: return edge1;
284: } else {
285: throw new RuntimeException(
286: "Node n must be in this triangle for Triangle.getOppositeEdge to work!");
287: }
288: } else {
289: throw new RuntimeException(
290: "Node n must be in this triangle for Triangle.getOppositeEdge to work!");
291: }
292: }
293:
294: public Edge getSharedEdge(Triangle t) {
295: Edge[] tEdges = t.getEdges();
296: Edge shared = null;
297: for (int i = 0; i < 3; i++) {
298: if (tEdges[i].equals(edge1)) {
299: shared = edge1;
300: } else if (tEdges[i].equals(edge2)) {
301: shared = edge2;
302: } else if (tEdges[i].equals(edge3)) {
303: shared = edge3;
304: }
305: }
306: return shared;
307: }
308:
309: public Edge[] getEdges() {
310: return new Edge[] { edge1, edge2, edge3 };
311: }
312:
313: public Node[] getNodes() {
314: return new Node[] { node1, node2, node3 };
315: }
316:
317: public double getArea() {
318: if ((node1 instanceof XYNode) || (node2 instanceof XYNode)
319: || (node3 instanceof XYNode)) {
320: double x1 = ((XYNode) node1).getCoordinate().x;
321: double y1 = ((XYNode) node1).getCoordinate().y;
322: double x2 = ((XYNode) node2).getCoordinate().x;
323: double y2 = ((XYNode) node2).getCoordinate().y;
324: double x3 = ((XYNode) node3).getCoordinate().x;
325: double y3 = ((XYNode) node3).getCoordinate().y;
326:
327: double length1_2 = Math.sqrt((x1 - x2) * (x1 - x2)
328: + (y1 - y2) * (y1 - y2));
329: double length1_3 = Math.sqrt((x1 - x3) * (x1 - x3)
330: + (y1 - y3) * (y1 - y3));
331: double length2_3 = Math.sqrt((x2 - x3) * (x2 - x3)
332: + (y2 - y3) * (y2 - y3));
333: double s = (length1_2 + length1_3 + length2_3) / 2;
334:
335: return Math.sqrt((s) * (s - length1_2) * (s - length1_3)
336: * (s - length2_3));
337: } else {
338: throw new RuntimeException(
339: "I can't calculate the area if the triangle doesn't have XY coordinates.");
340: }
341: }
342:
343: public boolean containsEdge(Edge e) {
344: return ((edge1.equals(e)) || (edge2.equals(e)) || (edge3
345: .equals(e)));
346: }
347:
348: public boolean equals(Object o) {
349: boolean ret;
350: if (o instanceof Triangle) {
351: ret = ((this .containsEdge(((Triangle) o).getEdges()[0]))
352: && (this .containsEdge(((Triangle) o).getEdges()[1])) && (this
353: .containsEdge(((Triangle) o).getEdges()[2])));
354: } else {
355: ret = false;
356: }
357: return ret;
358: }
359:
360: public String toString() {
361: return ("{" + node1.toString() + ", " + node2.toString() + ", "
362: + node3.toString() + "}");
363: }
364:
365: }
|