001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2003-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2003, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library 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 GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph.util.geom;
018:
019: import java.util.Collection;
020: import java.util.Iterator;
021:
022: import com.vividsolutions.jts.geom.Coordinate;
023: import com.vividsolutions.jts.geom.Geometry;
024: import com.vividsolutions.jts.geom.GeometryFactory;
025: import com.vividsolutions.jts.geom.LineSegment;
026: import com.vividsolutions.jts.geom.LineString;
027: import com.vividsolutions.jts.geom.Point;
028: import com.vividsolutions.jts.geom.PrecisionModel;
029:
030: public class GeometryUtil {
031:
032: private static GeometryFactory geomFactory;
033: private static PrecisionModel precModel;
034:
035: public static boolean isEqual(Coordinate[] c1, Coordinate c2[]) {
036: return (isEqual(c1, c2, false));
037: }
038:
039: public static boolean isEqual(Coordinate[] c1, Coordinate c2[],
040: boolean reverse) {
041: if (c1.length != c2.length)
042: return (false);
043:
044: if (!reverse) {
045: for (int i = 0; i < c1.length; i++) {
046: if (!c1[i].equals(c2[i]))
047: return (false);
048: }
049: return (true);
050: }
051:
052: for (int i = 0; i < c1.length; i++) {
053: if (!c1[i].equals(c2[c1.length - i - 1]))
054: return (false);
055: }
056: return (true);
057: }
058:
059: public static LineString joinLinestrings(LineString l1,
060: LineString l2) {
061: Coordinate[] merged = new Coordinate[l1.getNumPoints()
062: + l2.getNumPoints() - 1];
063:
064: //linestrings could join in one of 4 ways:
065: // tip to tail
066: // tail to tip
067: // tip to tip
068: // tail to tail
069: if (l1.getCoordinateN(l1.getNumPoints() - 1).equals(
070: l2.getCoordinateN(0))) {
071: //tip to tail
072: for (int i = 0; i < l1.getNumPoints(); i++) {
073: merged[i] = l1.getCoordinateN(i);
074: }
075: for (int i = 0; i < l2.getNumPoints() - 1; i++) {
076: merged[i + l1.getNumPoints()] = l2
077: .getCoordinateN(i + 1);
078: }
079: } else if (l2.getCoordinateN(l2.getNumPoints() - 1).equals(
080: l1.getCoordinateN(0))) {
081: //tail to tip
082: for (int i = 0; i < l2.getNumPoints(); i++) {
083: merged[i] = l2.getCoordinateN(i);
084: }
085: for (int i = 0; i < l1.getNumPoints() - 1; i++) {
086: merged[i + l2.getNumPoints()] = l1
087: .getCoordinateN(i + 1);
088: }
089: } else if (l1.getCoordinateN(l1.getNumPoints() - 1).equals(
090: l2.getCoordinateN(l2.getNumPoints() - 1))) {
091: //tip to tip
092: for (int i = 0; i < l1.getNumPoints(); i++) {
093: merged[i] = l1.getCoordinateN(i);
094: }
095: for (int i = 0; i < l2.getNumPoints() - 1; i++) {
096: merged[i + l1.getNumPoints()] = l2.getCoordinateN(l2
097: .getNumPoints()
098: - 2 - i);
099: }
100: } else if (l1.getCoordinateN(0).equals(l2.getCoordinateN(0))) {
101: //tail to tail
102: for (int i = 0; i < l2.getNumPoints(); i++) {
103: merged[i] = l2
104: .getCoordinateN(l2.getNumPoints() - 1 - i);
105: }
106:
107: for (int i = 0; i < l1.getNumPoints() - 1; i++) {
108: merged[i + l2.getNumPoints()] = l1
109: .getCoordinateN(i + 1);
110: }
111: } else
112: return (null);
113:
114: return (gf().createLineString(merged));
115: }
116:
117: public static double angleBetween(LineSegment l1, LineSegment l2,
118: double tol) {
119: //analyze slopes
120: //TODO straight vertical lines
121: double s1 = (l1.p1.y - l1.p0.y) / (l1.p1.x - l1.p0.x);
122: double s2 = (l2.p1.y - l2.p0.y) / (l2.p1.x - l2.p0.x);
123:
124: if (Math.abs(s1 - s2) < tol)
125: return (0);
126: if (Math.abs(s1 + s2) < tol)
127: return (Math.PI);
128:
129: //not of equal slope, transform lines so that they are tail to tip and
130: // use the cosine law to calculate angle between
131:
132: //transform line segments tail to tail, originating at (0,0)
133: LineSegment tls1 = new LineSegment(new Coordinate(0, 0),
134: new Coordinate(l1.p1.x - l1.p0.x, l1.p1.y - l1.p0.y));
135: LineSegment tls2 = new LineSegment(new Coordinate(0, 0),
136: new Coordinate(l2.p1.x - l2.p0.x, l2.p1.y - l2.p0.y));
137:
138: //line segment for third side of triangle
139: LineSegment ls3 = new LineSegment(tls1.p1, tls2.p1);
140:
141: double c = ls3.getLength();
142: double a = tls1.getLength();
143: double b = tls2.getLength();
144:
145: return (Math.acos((a * a + b * b - c * c) / (2 * a * b)));
146: }
147:
148: public static double angleBetween(LineString l1, LineString l2,
149: double tol) {
150: LineSegment ls1 = new LineSegment(l1.getCoordinateN(l1
151: .getNumPoints() - 2), l1.getCoordinateN(l1
152: .getNumPoints() - 1));
153: LineSegment ls2 = new LineSegment(l2.getCoordinateN(0), l2
154: .getCoordinateN(1));
155:
156: return (angleBetween(ls1, ls2, tol));
157: }
158:
159: public static double dx(LineString ls) {
160: return (ls.getPointN(ls.getNumPoints() - 1).getX() - ls
161: .getPointN(0).getX());
162: }
163:
164: public static double dy(LineString ls) {
165: return (ls.getPointN(ls.getNumPoints() - 1).getY() - ls
166: .getPointN(0).getY());
167: }
168:
169: // public static Geometry reverseGeometry(Geometry geometry) {
170: // if (geometry instanceof Point) return(geometry);
171: // if (geometry instanceof LineString) {
172: // return(
173: // gf().createLineString(reverseCoordinates(geometry.getCoordinates()))
174: // );
175: // }
176: // //TODO: implement polygon and multi geometries
177: // return(null);
178: // }
179:
180: // public static Coordinate[] reverseCoordinates(Coordinate[] c) {
181: // int n = c.length;
182: // Coordinate[] reversed = new Coordinate[n];
183: // for (int i = 0; i < n; i++) reversed[i] = c[n-i-1];
184: // return(reversed);
185: // }
186:
187: public static Geometry reverseGeometry(Geometry geom, boolean modify) {
188: if (geom instanceof Point)
189: return (geom);
190: if (geom instanceof LineString) {
191: Coordinate[] reversed = reverseCoordinates(geom
192: .getCoordinates(), modify);
193: if (modify)
194: return (geom);
195: else
196: return (gf().createLineString(reversed));
197: }
198: return (null);
199: }
200:
201: public static Coordinate[] reverseCoordinates(Coordinate[] c,
202: boolean modify) {
203: if (modify) {
204: int n = c.length / 2; //truncate if odd number
205:
206: for (int i = 0; i < n; i++) {
207: Coordinate tmp = c[i];
208: c[i] = c[c.length - 1 - i];
209: c[c.length - 1 - i] = tmp;
210: }
211:
212: return (c);
213: } else {
214: Coordinate[] cnew = new Coordinate[c.length];
215: for (int i = 0; i < c.length; i++) {
216: cnew[i] = c[c.length - 1 - i];
217: }
218: return (cnew);
219: }
220:
221: }
222:
223: public static double averageDistance(LineString to, Collection from) {
224: double avg = 0;
225: int n = 0;
226: for (Iterator itr = from.iterator(); itr.hasNext();) {
227: LineString ls = (LineString) itr.next();
228: n += ls.getNumPoints();
229: for (int i = 0; i < ls.getNumPoints(); i++) {
230: avg += ls.getPointN(i).distance(to);
231: }
232: }
233: return (avg / ((double) n));
234: }
235:
236: public static LineString simplifyLineString(LineString line) {
237: double x = 0d;
238: double y = 0d;
239: int n = line.getNumPoints();
240:
241: for (int i = 0; i < n; i++) {
242: Coordinate c = line.getCoordinateN(i);
243: x += c.x;
244: y += c.y;
245: }
246:
247: x /= (double) n;
248: y /= (double) n;
249:
250: LineString simple = gf().createLineString(
251: new Coordinate[] { line.getCoordinateN(0),
252: new Coordinate(x, y),
253: line.getCoordinateN(n - 1) });
254:
255: return (simple);
256: }
257:
258: public static PrecisionModel basicPrecisionModel() {
259: return (pm());
260: }
261:
262: public static GeometryFactory gf() {
263: if (geomFactory == null) {
264: geomFactory = new GeometryFactory();
265: }
266: return (geomFactory);
267: }
268:
269: public static PrecisionModel pm() {
270: if (precModel == null) {
271: precModel = new PrecisionModel();
272: }
273: return (precModel);
274: }
275:
276: // public static LineString normalize(LineString line, double sample) {
277: // Coordinate[] orig = line.getCoordinates();
278: // ArrayList normal = new ArrayList();
279: //
280: //
281: // return(null);
282: // }
283:
284: public static LineString normalizeLinestring(LineString line,
285: double sample) {
286: Coordinate[] c = line.getCoordinates();
287: boolean[] remove = new boolean[c.length];
288: int nremove = 0;
289:
290: double[] add = new double[c.length];
291: int nadd = 0;
292:
293: //special case if linestirng 2 coordinates
294: if (c.length == 2) {
295: if (distance(c, 0, 1) > sample) {
296: //do the point interepolation
297: int n = (int) (distance(c, 0, 1) / sample);
298: if (n > 1) {
299: nadd += n - 1;
300: add[0] = distance(c, 0, 1) / ((double) n);
301: }
302: } else
303: return (line);
304: } else {
305: int i = 0;
306: while (i < c.length - 2) {
307: //Coordinate c1 = c[i];
308: int j = i + 1;
309:
310: while (j < c.length - 1) {
311: //Coordinate c2 = c[j];
312: if (distance(c, i, j) < sample) {
313: remove[j] = true;
314: nremove++;
315: j++;
316: } else
317: break;
318: }
319:
320: int n = (int) (distance(c, i, j) / (sample));
321: if (n > 1) {
322: add[i] = distance(c, i, j) / ((double) n);
323: nadd += n - 1;
324: }
325:
326: i = j;
327: }
328:
329: //the last two points that will not be removed may need to be adjusted
330: for (int k = c.length - 2; k >= 1; k--) {
331: if (!remove[k]) {
332: //if distance between this point and last point is less then sample
333: // remove this point, and find the point before it, and asjust the
334: // interval in which to add points
335:
336: if (distance(c, c.length - 1, k) < sample) {
337: remove[k] = true;
338: nremove++;
339:
340: //move backward to find the last coordinate that wasn't removed
341: // and readjust any points that were added
342: int l = k - 1;
343: for (; l >= 0; l--) {
344: if (!remove[l])
345: break;
346: }
347:
348: if (l > -1) {
349: int n = (int) (distance(c, l, k) / sample);
350: if (n > 1) {
351: add[l] = 0d;
352: nadd -= (n - 1);
353: }
354:
355: //recalculate
356: n = (int) (distance(c, l, c.length - 1) / sample);
357: if (n > 1) {
358: add[l] = distance(c, l, c.length - 1)
359: / ((double) n);
360: nadd += n - 1;
361: }
362: }
363: } else {
364: //if the last point is the second to last in the coordinate
365: // array, we may have to add points inbetween
366: if (k == c.length - 2) {
367: //determine if we need to add any points between last two points
368: int n = (int) (distance(c, k, c.length - 1) / sample);
369: if (n > 1) {
370: nadd += n - 1;
371: add[k] = distance(c, k, c.length - 1)
372: / ((double) n);
373: }
374: }
375: }
376:
377: break;
378: }
379: }
380:
381: // if (!remove[c.length-2]) {
382: // if (c[c.length-1].distance(c[c.length-2]) < sample) {
383: // remove[c.length-2] = true;
384: // nremove++;
385: //
386: // //move backward to find the last coordinate that wasn't removed
387: // // and readjust any points that were added
388: // int k = c.length-3;
389: // for (; k >= 0; k--) {
390: // if (!remove[k]) break;
391: // }
392: //
393: // if (k > -1) {
394: // int n = (int) (c[k].distance(c[c.length-2]) / sample);
395: // if (n > 1) {
396: // add[k] = 0d;
397: // nadd -= (n-1);
398: // }
399: //
400: // //recalculate
401: // n = (int)(c[k].distance(c[c.length-1]) / sample);
402: // if (n > 1) {
403: // add[k] = c[k].distance(c[c.length-1]) / ((double)n);
404: // nadd += n-1;
405: // }
406: //
407: // }
408: // }
409: // else {
410: // //determine if we need to add any points between last two points
411: // int n = (int) (c[c.length-2].distance(c[c.length-1]) / sample);
412: // if (n > 1) {
413: // nadd += n-1;
414: // add[c.length-2] = c[c.length-2].distance(c[c.length-1]) / ((double)n);
415: // }
416: //
417: // }
418: // }
419: }
420:
421: Coordinate[] newc = new Coordinate[c.length - nremove + nadd];
422: //Coordinate[] newc = new Coordinate[c.length-nremove];
423: int j = 0;
424: for (int i = 0; i < c.length; i++) {
425: if (!remove[i]) {
426: newc[j++] = c[i];
427: if (add[i] > 0d) {
428: int next = -1;
429: for (int k = i + 1; k < c.length && next == -1; k++) {
430: if (!remove[k])
431: next = k;
432: }
433: if (next == -1)
434: continue;
435:
436: double dx = (c[next].x - c[i].x) * (add[i])
437: / distance(c, i, next);
438: double dy = (c[next].y - c[i].y) * (add[i])
439: / distance(c, i, next);
440:
441: int n = (int) (distance(c, i, next) / add[i] + +0.000001);
442: for (int k = 1; k < n; k++) {
443: newc[j++] = new Coordinate(c[i].x + k * dx,
444: c[i].y + k * dy);
445: }
446: }
447: }
448: }
449:
450: // for (int i = 0; i < newc.length; i++) {
451: // Coordinate coord = newc[i];
452: // if (coord != null)
453: // System.out.println("POINT(" + coord.x + " " + coord.y + ")");
454: // else System.out.println("null");
455: // }
456:
457: return (gf().createLineString(newc));
458: }
459:
460: public static double distance(Coordinate[] c, int i, int j) {
461: if (i > j) {
462: int tmp = i;
463: i = j;
464: j = tmp;
465: }
466:
467: double dist = 0d;
468: for (int k = i; k < j; k++) {
469: dist += c[k].distance(c[k + 1]);
470: }
471:
472: return (dist);
473: }
474: }
|