001: /*
002: * The Unified Mapping Platform (JUMP) is an extensible, interactive GUI
003: * for visualizing and manipulating spatial features with geometry and attributes.
004: *
005: * Copyright (C) 2003 Vivid Solutions
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License
009: * as published by the Free Software Foundation; either version 2
010: * of the License, or (at your option) any later version.
011: *
012: * This program is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
015: * GNU General Public License for more details.
016: *
017: * You should have received a copy of the GNU General Public License
018: * along with this program; if not, write to the Free Software
019: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
020: *
021: * For more information, contact:
022: *
023: * Vivid Solutions
024: * Suite #1A
025: * 2328 Government Street
026: * Victoria BC V8T 5G5
027: * Canada
028: *
029: * (250)385-6040
030: * www.vividsolutions.com
031: */
032:
033: package com.vividsolutions.jump.warp;
034:
035: import java.util.ArrayList;
036: import java.util.Arrays;
037: import java.util.Collection;
038: import java.util.Collections;
039: import java.util.HashMap;
040: import java.util.Iterator;
041: import java.util.List;
042: import java.util.Map;
043: import java.util.TreeMap;
044: import java.util.TreeSet;
045:
046: import com.vividsolutions.jts.geom.Coordinate;
047: import com.vividsolutions.jts.geom.Envelope;
048: import com.vividsolutions.jts.geom.Geometry;
049: import com.vividsolutions.jts.geom.GeometryFactory;
050: import com.vividsolutions.jts.geom.LineString;
051: import com.vividsolutions.jts.util.Assert;
052: import com.vividsolutions.jump.task.TaskMonitor;
053: import com.vividsolutions.jump.util.CollectionMap;
054:
055: /**
056: * A better name for this class would have been TriangleMapFactory. Given the
057: * coordinates of an initial and final triangulation, it will return a map of source
058: * Triangle to destination Triangle.
059: *
060: * Creates a FeatureCollection of triangles covering a given area. Thin
061: * triangles are avoided. <p>
062: *
063: * Coordinates are not created, modified, or discarded. Thus, the triangles
064: * created will be composed of the Coordinates passed in to the Triangulator.
065: *
066: * See White, Marvin S., Jr. and Griffin, Patricia. 1985. Piecewise linear
067: * rubber-sheet map transformation. "The American Cartographer" 12:2,
068: * 123-31.
069: */
070: public class Triangulator {
071: private GeometryFactory factory = new GeometryFactory();
072: private Collection ignoredVectors = new ArrayList();
073:
074: public Triangulator() {
075: }
076:
077: /**
078: * Splits two regions into Triangles. The two regions are called the
079: * "source quadrilateral" and "destination quadrilateral", and are based on
080: * the given dataset envelope. The "source quadrilateral" is the dataset envelope
081: * expanded 5% along each margin. The "destination quadrilateral" is the
082: * source quadrilateral with each vertex shifted according to the vector with
083: * the nearest tail. The source quadrilateral is split using the vector tails;
084: * the destination quadrilateral is split using the vector tips. In this way,
085: * the vectors map the source Triangles to the destination Triangles.
086: * @param datasetEnvelope the region to triangulate
087: * @param vectorLineStrings vectors (2-point LineStrings) whose tails and tips split
088: * the "source quadrilateral" and "destination quadrilateral" into triangles
089: * @param monitor
090: * @return a map of source Triangles to destination Triangles
091: */
092: public Map triangleMap(Envelope datasetEnvelope,
093: Collection vectorLineStrings, TaskMonitor monitor) {
094: return triangleMap(datasetEnvelope, vectorLineStrings,
095: new ArrayList(), new ArrayList(), monitor);
096: }
097:
098: /**
099: * @param sourceHints "far-away" Coordinates (even outside the dataset envelope) for which
100: * we must ensure that source triangles include.
101: * @param destinationHints "far-away" Coordinates for which we must ensure that destination
102: * triangles include
103: */
104: public Map triangleMap(Envelope datasetEnvelope,
105: Collection vectorLineStrings, Collection sourceHints,
106: Collection destinationHints, TaskMonitor monitor) {
107: ArrayList vectorListCopy = new ArrayList(vectorLineStrings);
108: ignoredVectors = nonVectors(vectorListCopy);
109: vectorListCopy.removeAll(ignoredVectors);
110:
111: //Refinement on White & Griffin's algorithm: Bring outlying vectors back inside
112: //by gradually increasing the size of the source quad. This is a courtesy to
113: //the caller because really there shouldn't be any outlying vectors. [Jon Aquino]
114: Assert.isTrue(!datasetEnvelope.isNull());
115: Envelope sourceEnvelope = new Envelope(datasetEnvelope);
116: Quadrilateral sourceQuad;
117: Quadrilateral destQuad;
118: while (true) {
119: //#sourceQuad will grow the envelope by 5%. [Jon Aquino]
120: sourceQuad = sourceQuad(sourceEnvelope);
121: destQuad = destQuad(sourceQuad, vectorListCopy);
122: if (outlyingVectors(sourceQuad, destQuad, vectorListCopy)
123: .isEmpty()
124: && sourceQuad.verticesOutside(sourceHints)
125: .isEmpty()
126: && destQuad.verticesOutside(destinationHints)
127: .isEmpty()) {
128: break;
129: }
130: sourceEnvelope = sourceQuad.getEnvelope();
131: }
132:
133: Quadrilateral taggedSourceQuad = tag(sourceQuad, destQuad);
134: List taggedSourceTriangles = triangulate(taggedSourceQuad,
135: taggedVectorVertices(false, vectorListCopy), monitor);
136:
137: return triangleMap(taggedSourceTriangles);
138: }
139:
140: /**
141: * Permits the caller to identify which vectors were ignored because they
142: * were not 2-point LineStrings
143: */
144: public Collection getIgnoredVectors() {
145: return Collections.unmodifiableCollection(ignoredVectors);
146: }
147:
148: public static Collection nonVectors(Collection geometries) {
149: TreeSet nonVectors = new TreeSet();
150: for (Iterator i = geometries.iterator(); i.hasNext();) {
151: Geometry g = (Geometry) i.next();
152: if (vector(g)) {
153: continue;
154: }
155: nonVectors.add(g);
156: }
157: return nonVectors;
158: }
159:
160: public static boolean vector(Geometry g) {
161: return (g.getClass() == LineString.class)
162: && (((LineString) g).getNumPoints() == 2);
163: }
164:
165: /**
166: * @return vectors with the tail outside sourceQuad or the
167: * tip outside destQuad
168: */
169: private TreeSet outlyingVectors(Quadrilateral sourceQuad,
170: Quadrilateral destQuad, Collection vectors) {
171: TreeSet outliers = new TreeSet();
172: outliers.addAll(toVectors(sourceQuad
173: .verticesOutside(taggedVectorVertices(false, vectors)),
174: false));
175: outliers.addAll(toVectors(destQuad
176: .verticesOutside(taggedVectorVertices(true, vectors)),
177: true));
178: return outliers;
179: }
180:
181: /**
182: * The intent of this method is to avoid narrow triangles, which create near
183: * singularities.
184: *
185: *@param PQS a triangle sharing an edge with QRS; vertex order is irrelevant
186: *@return (PQS and QRS) or (PQR, PRS), whichever pair has the largest
187: * minimum height
188: */
189: protected List heightMaximizedTriangles(Triangle PQS, Triangle QRS) {
190: List originalTriangles = Arrays.asList(new Triangle[] { PQS,
191: QRS });
192: List alternativeTriangles = alternativeTriangles(PQS, QRS);
193:
194: if (alternativeTriangles == null) {
195: return originalTriangles;
196: }
197:
198: Triangle t1 = (Triangle) alternativeTriangles.get(0);
199: Triangle t2 = (Triangle) alternativeTriangles.get(1);
200:
201: if (Math.min(PQS.getMinHeight(), QRS.getMinHeight()) > Math
202: .min(t1.getMinHeight(), t2.getMinHeight())) {
203: return originalTriangles;
204: } else {
205: return alternativeTriangles;
206: }
207: }
208:
209: /**
210: *@return the triangle containing p, or null if no triangle contains p
211: */
212: protected Triangle triangleContaining(Coordinate p, List triangles) {
213: for (Iterator i = triangles.iterator(); i.hasNext();) {
214: Triangle triangle = (Triangle) i.next();
215:
216: if (triangle.contains(p)) {
217: return triangle;
218: }
219: }
220:
221: return null;
222: }
223:
224: /**
225: *@return a + the displacement represented by vector
226: */
227: protected Coordinate add(Coordinate a, LineString vector) {
228: return new Coordinate((a.x + vector.getCoordinateN(1).x)
229: - vector.getCoordinateN(0).x, (a.y + vector
230: .getCoordinateN(1).y)
231: - vector.getCoordinateN(0).y);
232: }
233:
234: protected LineString vectorWithNearestTail(Coordinate x,
235: List vectors) {
236: Assert.isTrue(vectors.size() > 0);
237:
238: LineString vectorWithNearestTail = (LineString) vectors.get(0);
239:
240: for (Iterator i = vectors.iterator(); i.hasNext();) {
241: LineString candidate = (LineString) i.next();
242:
243: if (candidate.getCoordinateN(0).distance(x) < vectorWithNearestTail
244: .getCoordinateN(0).distance(x)) {
245: vectorWithNearestTail = candidate;
246: }
247: }
248:
249: return vectorWithNearestTail;
250: }
251:
252: /**
253: *@return sourceQuad wrapped in TaggedCoordinates pointing to the
254: * corresponding Coordinates in destQuad.
255: */
256: protected Quadrilateral tag(Quadrilateral sourceQuad,
257: Quadrilateral destQuad) {
258: return new Quadrilateral(new TaggedCoordinate(sourceQuad
259: .getP1(), destQuad.getP1()), new TaggedCoordinate(
260: sourceQuad.getP2(), destQuad.getP2()),
261: new TaggedCoordinate(sourceQuad.getP3(), destQuad
262: .getP3()), new TaggedCoordinate(sourceQuad
263: .getP4(), destQuad.getP4()));
264: }
265:
266: /**
267: *@param PQS a triangle sharing an edge with QRS; vertex order is irrelevant
268: *@return triangles PQR and PRS, or null if PQRS is not convex
269: */
270: protected List alternativeTriangles(Triangle PQS, Triangle QRS) {
271: Quadrilateral quad = dissolve(PQS, QRS);
272:
273: if (!quad.isConvex()) {
274: return null;
275: }
276:
277: return quad.triangles();
278: }
279:
280: /**
281: *@return a rectangle 5% larger along each margin
282: *@see White and Griffin's paper
283: */
284: private Quadrilateral sourceQuad(Envelope datasetEnvelope) {
285: double dx = datasetEnvelope.getWidth() * 0.05;
286: double dy = datasetEnvelope.getHeight() * 0.05;
287:
288: return new Quadrilateral(new Coordinate(datasetEnvelope
289: .getMinX()
290: - dx, datasetEnvelope.getMinY() - dy), new Coordinate(
291: datasetEnvelope.getMaxX() + dx, datasetEnvelope
292: .getMinY()
293: - dy), new Coordinate(datasetEnvelope.getMaxX()
294: + dx, datasetEnvelope.getMaxY() + dy), new Coordinate(
295: datasetEnvelope.getMinX() - dx, datasetEnvelope
296: .getMaxY()
297: + dy));
298: }
299:
300: /**
301: * Modifies the triangle list to accomodate the new vertex.
302: */
303: private void triangulate(List triangles, Coordinate newVertex) {
304: Triangle triangleContainingNewVertex = triangleContaining(
305: newVertex, triangles);
306: Assert.isTrue(triangleContainingNewVertex != null);
307: triangles.remove(triangleContainingNewVertex);
308:
309: //Don't add triangles immediately, as we want #adjacentTriangle to return
310: //a triangle that isn't one of the split triangles. [Jon Aquino]
311: ArrayList trianglesToAdd = new ArrayList();
312:
313: for (Iterator i = triangleContainingNewVertex.subTriangles(
314: newVertex).iterator(); i.hasNext();) {
315: Triangle newTriangle = (Triangle) i.next();
316: Triangle adjacentTriangle = adjacentTriangle(newTriangle,
317: triangles);
318:
319: if (adjacentTriangle == null) {
320: //that is, a boundary triangle [Jon Aquino]
321: trianglesToAdd.add(newTriangle);
322: } else {
323: triangles.remove(adjacentTriangle);
324: trianglesToAdd.addAll(heightMaximizedTriangles(
325: newTriangle, adjacentTriangle));
326: }
327: }
328:
329: triangles.addAll(trianglesToAdd);
330: }
331:
332: /**
333: *@return the triangle adjacent to the given triangle, or null if there is
334: * none
335: */
336: private Triangle adjacentTriangle(Triangle triangle, List triangles) {
337: for (Iterator i = triangles.iterator(); i.hasNext();) {
338: Triangle candidate = (Triangle) i.next();
339: int vertexMatches = 0;
340:
341: if (candidate.hasVertex(triangle.getP1())) {
342: vertexMatches++;
343: }
344:
345: if (candidate.hasVertex(triangle.getP2())) {
346: vertexMatches++;
347: }
348:
349: if (candidate.hasVertex(triangle.getP3())) {
350: vertexMatches++;
351: }
352:
353: Assert.isTrue(vertexMatches != 3, candidate + "; "
354: + triangle);
355:
356: if (vertexMatches == 2) {
357: return candidate;
358: }
359: }
360:
361: return null;
362: }
363:
364: /**
365: *@return sourceQuad, with each vertex shifted according to the vector with
366: * the nearest tail
367: *@see White and Griffin's paper
368: */
369: private Quadrilateral destQuad(Quadrilateral sourceQuad,
370: List vectors) {
371: if (vectors.isEmpty()) {
372: return (Quadrilateral) sourceQuad.clone();
373: }
374: return new Quadrilateral(addVectorWithNearestTail(sourceQuad
375: .getP1(), vectors), addVectorWithNearestTail(sourceQuad
376: .getP2(), vectors), addVectorWithNearestTail(sourceQuad
377: .getP3(), vectors), addVectorWithNearestTail(sourceQuad
378: .getP4(), vectors));
379: }
380:
381: private Coordinate addVectorWithNearestTail(Coordinate x,
382: List vectors) {
383: return add(x, vectorWithNearestTail(x, vectors));
384: }
385:
386: /**
387: *@param quad quadrilateral region to triangulate
388: *@param vertices triangle vertices; Coordinate objects, all within the
389: * quadrilateral region (use #containsAll to check)
390: *@return the triangles; Triangle objects
391: *@throws JUMPException if one or more vertices are outside the quadrilateral
392: * region
393: */
394: private List triangulate(Quadrilateral quad, List vertices,
395: TaskMonitor monitor) {
396: monitor.allowCancellationRequests();
397: monitor.report("Triangulating...");
398:
399: List triangles = quad.triangles();
400: int count = 0;
401:
402: for (Iterator i = vertices.iterator(); i.hasNext()
403: && !monitor.isCancelRequested();) {
404: Coordinate vertex = (Coordinate) i.next();
405: triangulate(triangles, vertex);
406: count++;
407: monitor.report(count, vertices.size(), "vectors");
408: }
409:
410: return triangles;
411: }
412:
413: /**
414: * The returned Coordinates will be tagged with the tails if the tips are
415: * requested (or the tips, if the tails are requested).
416: *
417: *@param tips true to return the vector tips; otherwise, the tails
418: */
419: public static List taggedVectorVertices(boolean tips,
420: Collection vectors) {
421: ArrayList taggedVectorVertices = new ArrayList();
422:
423: for (Iterator i = vectors.iterator(); i.hasNext();) {
424: LineString vector = (LineString) i.next();
425: taggedVectorVertices.add(new TaggedCoordinate(tips ? vector
426: .getCoordinateN(1) : vector.getCoordinateN(0),
427: tips ? vector.getCoordinateN(0) : vector
428: .getCoordinateN(1)));
429: }
430:
431: return taggedVectorVertices;
432: }
433:
434: private Map triangleMap(List taggedSourceTriangles) {
435: HashMap triangleMap = new HashMap();
436:
437: for (Iterator i = taggedSourceTriangles.iterator(); i.hasNext();) {
438: Triangle sourceTriangle = (Triangle) i.next();
439: triangleMap.put(sourceTriangle, new Triangle(
440: ((TaggedCoordinate) sourceTriangle.getP1())
441: .getTag(),
442: ((TaggedCoordinate) sourceTriangle.getP2())
443: .getTag(),
444: ((TaggedCoordinate) sourceTriangle.getP3())
445: .getTag()));
446: }
447:
448: return triangleMap;
449: }
450:
451: /**
452: * @param tips true if c is the tip and c's tag is the tail; false if
453: * c is the tail and c's tag is the tip
454: */
455: private LineString toVector(TaggedCoordinate c, boolean tips) {
456: //Constructor requires the tail followed by the tip.
457: return factory.createLineString(new Coordinate[] {
458: tips ? c.getTag() : c, tips ? c : c.getTag() });
459: }
460:
461: /**
462: * The first coordinate of the returned quadrilateral will be an "unshared"
463: * vertex; that is, one that is present in only one of the triangles.
464: *
465: *@param PQS a triangle that shares an edge with QRS. The order of the
466: * Coordinates does not matter.
467: *@return a quadrilateral (four Coordinates) formed from the two
468: * triangles
469: */
470: private Quadrilateral dissolve(Triangle PQS, Triangle QRS) {
471: CollectionMap vertexListMap = new CollectionMap(TreeMap.class);
472: vertexListMap.addItem(PQS.getP1(), PQS.getP1());
473: vertexListMap.addItem(PQS.getP2(), PQS.getP2());
474: vertexListMap.addItem(PQS.getP3(), PQS.getP3());
475: vertexListMap.addItem(QRS.getP1(), QRS.getP1());
476: vertexListMap.addItem(QRS.getP2(), QRS.getP2());
477: vertexListMap.addItem(QRS.getP3(), QRS.getP3());
478:
479: ArrayList sharedVertices = new ArrayList();
480: ArrayList unsharedVertices = new ArrayList();
481:
482: for (Iterator i = vertexListMap.keySet().iterator(); i
483: .hasNext();) {
484: Coordinate vertex = (Coordinate) i.next();
485:
486: if (vertexListMap.getItems(vertex).size() == 1) {
487: unsharedVertices.add(vertex);
488: } else if (vertexListMap.getItems(vertex).size() == 2) {
489: sharedVertices.add(vertex);
490: } else {
491: Assert.shouldNeverReachHere();
492: }
493: }
494:
495: Assert.isTrue(2 == sharedVertices.size(), PQS + "; " + QRS);
496: Assert.isTrue(2 == unsharedVertices.size(), PQS + "; " + QRS);
497:
498: return new Quadrilateral((Coordinate) unsharedVertices.get(0),
499: (Coordinate) sharedVertices.get(0),
500: (Coordinate) unsharedVertices.get(1),
501: (Coordinate) sharedVertices.get(1));
502: }
503:
504: private TreeSet toVectors(Collection taggedVectorVertices,
505: boolean tips) {
506: TreeSet badVectors = new TreeSet();
507:
508: for (Iterator i = taggedVectorVertices.iterator(); i.hasNext();) {
509: TaggedCoordinate c = (TaggedCoordinate) i.next();
510: badVectors.add(toVector(c, tips));
511: }
512:
513: return badVectors;
514: }
515: }
|