001: /*
002: * Geotools2 - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2005, 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.referencing.operation.builder;
017:
018: import org.opengis.geometry.DirectPosition;
019: import java.util.ArrayList;
020: import java.util.Iterator;
021: import java.util.List;
022:
023: /**
024: * Generates TIN with respect to delaunay criterion. It
025: * means that there are no alien vertices in the circumcircle of each
026: * triangle. The algorithm that is used is also known as incremental insertion.
027: *
028: * @since 2.4
029: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/library/referencing/src/main/java/org/geotools/referencing/operation/builder/TriangulationFactory.java $
030: * @version $Id: TriangulationFactory.java 28966 2008-01-27 17:36:43Z acuster $
031: * @author Jan Jezek
032: */
033: class TriangulationFactory {
034: /** The list of TINTrianlgles of TIN. */
035: private List triangles;
036:
037: /**
038: * Constructs the TriangulationFactory.
039: *
040: * @param quad of location to be triangulated.
041: * @param pt Array of points for triangulation.
042: * @throws TriangulationException when the vertices are outside of the specified quad.
043: */
044: protected TriangulationFactory(Quadrilateral quad,
045: DirectPosition[] pt) throws TriangulationException {
046: List vertices = new ArrayList();
047:
048: for (int i = 0; i < pt.length; i++) {
049: vertices.add(pt[i]);
050: }
051:
052: if (quad.containsAll(vertices) == false) {
053: throw new TriangulationException(
054: "Point is outside triangles");
055: }
056:
057: this .triangles = quad.getTriangles();
058:
059: for (Iterator i = vertices.iterator(); i.hasNext();) {
060: DirectPosition vertex = (DirectPosition) i.next();
061: insertPoint(vertex);
062: }
063: }
064:
065: /**
066: * Set a List of points for triangulation
067: *
068: * @return TIN as list of triangles.
069: */
070: public List getTriangulation() {
071: return triangles;
072: }
073:
074: /**
075: * This is the test loop, that starts to tests of triangles until
076: * the result of insertation of triangle evokes changes in TIN.
077: *
078: * @param ChangedTriangles List of changed triangles
079: *
080: * @throws TriangulationException TriangulationException
081: */
082: protected void recursiveDelaunayTest(List ChangedTriangles)
083: throws TriangulationException {
084: int i = ChangedTriangles.size();
085:
086: while (i != 0) {
087: triangles.removeAll(ChangedTriangles);
088: ChangedTriangles = insertTriangles(ChangedTriangles);
089: i = ChangedTriangles.size();
090: }
091: }
092:
093: /**
094: * Decides whether to insert triangle directly or go throught
095: * delaunay test.
096: *
097: * @param trian if triangles to be inserted
098: *
099: * @return List of changed triangles
100: *
101: * @throws TriangulationException TriangulationException
102: */
103: protected List insertTriangles(List trian)
104: throws TriangulationException {
105: List ChangedTriangles = new ArrayList();
106:
107: for (Iterator i = trian.iterator(); i.hasNext();) {
108: TINTriangle trig = (TINTriangle) i.next();
109:
110: if (trig.getAdjacentTriangles().size() <= 2) {
111: // this triangles were generate by splitting one of a boundary triangle
112: triangles.add(trig);
113: } else {
114: ChangedTriangles.addAll(delaunayCircleTest(trig));
115: }
116: }
117:
118: return ChangedTriangles;
119: }
120:
121: /**
122: * Tests whether there is a alien vertex in the circumcircle of
123: * triangle. When there is, the diagonal of quad made by these triangles
124: * changes.
125: *
126: * @param triangle to be tested
127: *
128: * @return List of changed triangles
129: *
130: * @throws TriangulationException DOCUMENT ME!
131: */
132: private List delaunayCircleTest(TINTriangle triangle)
133: throws TriangulationException {
134: List changedTriangles = new ArrayList();
135:
136: Iterator j = triangle.getAdjacentTriangles().iterator();
137: int ct = changedTriangles.size();
138:
139: while (j.hasNext() && (changedTriangles.size() == ct)) {
140: TINTriangle adjacent = (TINTriangle) j.next();
141:
142: List NewTriangles = new ArrayList();
143:
144: // The delaunay test
145: if (triangle.getCircumCicle().contains(adjacent.p1)
146: || triangle.getCircumCicle().contains(adjacent.p0)
147: || triangle.getCircumCicle().contains(adjacent.p2)) {
148: triangles.remove(triangle);
149: triangles.remove(adjacent);
150:
151: NewTriangles.addAll(alternativeTriangles(triangle,
152: adjacent));
153:
154: triangles.addAll(NewTriangles);
155: changedTriangles = NewTriangles;
156: } else if (!triangles.contains(triangle)) {
157: triangles.add(triangle);
158: }
159: }
160:
161: return changedTriangles;
162: }
163:
164: /**
165: * Accommodate new vertex into the existing triangles.
166: *
167: * @param newVertex new vertex
168: *
169: * @throws TriangulationException when {@code newVertex} is outside triangles
170: */
171: public void insertPoint(DirectPosition newVertex)
172: throws TriangulationException {
173: TINTriangle triangleContainingNewVertex = triangleContains(newVertex);
174:
175: if (triangleContainingNewVertex == null) {
176: throw new TriangulationException(
177: "Point is outside triangles");
178: }
179:
180: triangles.remove(triangleContainingNewVertex);
181: recursiveDelaunayTest(triangleContainingNewVertex
182: .subTriangles(newVertex));
183: }
184:
185: /**
186: * Changes the diagonal of the quad generated from two
187: * adjacent triangles.
188: *
189: * @param ABC triangle sharing an edge with BCD
190: * @param BCD triangle sharing an edge with ABC
191: *
192: * @return triangles ABD and ADC, or null if ABCD is not convex
193: *
194: * @throws TriangulationException if {@code ABC} and {@code BCD} are not adjacent
195: */
196: private List alternativeTriangles(TINTriangle ABC, TINTriangle BCD)
197: throws TriangulationException {
198: ArrayList ABCvertices = new ArrayList();
199: ArrayList BCDvertices = new ArrayList();
200:
201: ABCvertices.add(ABC.p0);
202: ABCvertices.add(ABC.p1);
203: ABCvertices.add(ABC.p2);
204: BCDvertices.add(BCD.p0);
205: BCDvertices.add(BCD.p1);
206: BCDvertices.add(BCD.p2);
207:
208: ArrayList sharedVertices = new ArrayList();
209: ArrayList unsharedVertices = new ArrayList();
210:
211: // Finds shared and unshared vertices
212: for (Iterator i = ABCvertices.iterator(); i.hasNext();) {
213: DirectPosition vertex = (DirectPosition) i.next();
214:
215: if (!BCDvertices.contains(vertex)) {
216: unsharedVertices.add(vertex);
217: } else if (BCDvertices.contains(vertex)) {
218: sharedVertices.add(vertex);
219: BCDvertices.remove(vertex);
220: } else {
221: throw new TriangulationException(
222: "should never reach here");
223: }
224: }
225:
226: unsharedVertices.addAll(BCDvertices);
227:
228: if (sharedVertices.size() < 2) {
229: throw new TriangulationException(
230: "Unable to make alternative triangles");
231: }
232:
233: // remove Adjacent from original triangles
234: ABC.removeAdjacent(BCD);
235: BCD.removeAdjacent(ABC);
236:
237: // new triangles are generated
238: TINTriangle trigA = new TINTriangle(
239: (DirectPosition) sharedVertices.get(0),
240: (DirectPosition) unsharedVertices.get(0),
241: (DirectPosition) unsharedVertices.get(1));
242: TINTriangle trigB = new TINTriangle(
243: (DirectPosition) unsharedVertices.get(0),
244: (DirectPosition) unsharedVertices.get(1),
245: (DirectPosition) sharedVertices.get(1));
246:
247: // Adjacent triangles are added
248: trigA.addAdjacentTriangle(trigB);
249: trigB.addAdjacentTriangle(trigA);
250: trigA.tryToAddAdjacent(BCD.getAdjacentTriangles());
251: trigA.tryToAddAdjacent(ABC.getAdjacentTriangles());
252: trigB.tryToAddAdjacent(BCD.getAdjacentTriangles());
253: trigB.tryToAddAdjacent(ABC.getAdjacentTriangles());
254:
255: List list = new ArrayList();
256: list.add(trigA);
257: list.add(trigB);
258:
259: // Adjacent triangles of adjacent triangles are modified.
260: for (Iterator i = ABC.getAdjacentTriangles().iterator(); i
261: .hasNext();) {
262: TINTriangle trig = (TINTriangle) i.next();
263: trig.removeAdjacent(ABC);
264: trig.tryToAddAdjacent(list);
265: }
266:
267: for (Iterator i = BCD.getAdjacentTriangles().iterator(); i
268: .hasNext();) {
269: TINTriangle trig = (TINTriangle) i.next();
270: trig.removeAdjacent(BCD);
271: trig.tryToAddAdjacent(list);
272: }
273:
274: return list;
275: }
276:
277: /**
278: * Returns the TINTriangle that contains the p Coordinate.
279: *
280: * @param p The Coordinate to be tested
281: *
282: * @return the triangle containing p, or null if there is no triangle that
283: * contains p
284: */
285: private TINTriangle triangleContains(DirectPosition p) {
286: for (Iterator i = triangles.iterator(); i.hasNext();) {
287: TINTriangle triangle = (TINTriangle) i.next();
288:
289: if (triangle.containsOrIsVertex(p)) {
290: return triangle;
291: }
292: }
293:
294: return null;
295: }
296: }
|