001: //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/trunk/src/org/deegree/model/spatialschema/LinearIntersects.java $
002: /*---------------- FILE HEADER ------------------------------------------
003:
004: This file is part of deegree.
005: Copyright (C) 2001-2008 by:
006: EXSE, Department of Geography, University of Bonn
007: http://www.giub.uni-bonn.de/deegree/
008: lat/lon GmbH
009: http://www.lat-lon.de
010:
011: This library is free software; you can redistribute it and/or
012: modify it under the terms of the GNU Lesser General Public
013: License as published by the Free Software Foundation; either
014: version 2.1 of the License, or (at your option) any later version.
015:
016: This library is distributed in the hope that it will be useful,
017: but WITHOUT ANY WARRANTY; without even the implied warranty of
018: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
019: Lesser General Public License for more details.
020:
021: You should have received a copy of the GNU Lesser General Public
022: License along with this library; if not, write to the Free Software
023: Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
024:
025: Contact:
026:
027: Andreas Poth
028: lat/lon GmbH
029: Aennchenstr. 19
030: 53115 Bonn
031: Germany
032: E-Mail: poth@lat-lon.de
033:
034: Prof. Dr. Klaus Greve
035: Department of Geography
036: University of Bonn
037: Meckenheimer Allee 166
038: 53115 Bonn
039: Germany
040: E-Mail: greve@giub.uni-bonn.de
041:
042:
043: ---------------------------------------------------------------------------*/
044: package org.deegree.model.spatialschema;
045:
046: import org.deegree.model.crs.CoordinateSystem;
047:
048: /**
049: *
050: *
051: * @version $Revision: 9343 $
052: * @author <a href="mailto:poth@lat-lon.de">Andreas Poth</a>
053: */
054: class LinearIntersects {
055:
056: /**
057: *
058: * @param geom1
059: * @param geom2
060: * @return maximum tolerance of geom1 and geom2
061: */
062: public static double getTolerance(Geometry geom1, Geometry geom2) {
063: double d = geom1.getTolerance();
064: if (geom2.getTolerance() > d) {
065: d = geom2.getTolerance();
066: }
067: return d;
068: }
069:
070: /**
071: * the operations returns true if two the submitted points intersects
072: *
073: * @param point1
074: * @param point2
075: * @param tolerance
076: */
077: public static boolean intersects(Position point1, Position point2,
078: double tolerance) {
079:
080: double d = 0;
081: double[] p1 = point1.getAsArray();
082: double[] p2 = point2.getAsArray();
083:
084: for (int i = 0; i < p1.length; i++) {
085: d += ((p1[i] - p2[i]) * (p1[i] - p2[i]));
086: }
087:
088: return Math.sqrt(d) < tolerance;
089: }
090:
091: /**
092: * the operations returns true if the submitted point intersects the passed curve segment
093: *
094: * @param point
095: * @param curve
096: * @param tolerance
097: */
098: public static boolean intersects(Position point,
099: CurveSegment curve, double tolerance) throws Exception {
100: boolean inter = false;
101:
102: Position[] points = curve.getPositions();
103:
104: for (int i = 0; i < (points.length - 1); i++) {
105: if (linesIntersect(points[i].getX(), points[i].getY(),
106: points[i + 1].getX(), points[i + 1].getY(), point
107: .getX()
108: - tolerance, point.getY() - tolerance,
109: point.getX() + tolerance, point.getY() - tolerance)
110: || linesIntersect(points[i].getX(), points[i]
111: .getY(), points[i + 1].getX(),
112: points[i + 1].getY(), point.getX()
113: + tolerance, point.getY()
114: - tolerance, point.getX()
115: + tolerance, point.getY()
116: + tolerance)
117: || linesIntersect(points[i].getX(), points[i]
118: .getY(), points[i + 1].getX(),
119: points[i + 1].getY(), point.getX()
120: + tolerance, point.getY()
121: + tolerance, point.getX()
122: - tolerance, point.getY()
123: + tolerance)
124: || linesIntersect(points[i].getX(), points[i]
125: .getY(), points[i + 1].getX(),
126: points[i + 1].getY(), point.getX()
127: - tolerance, point.getY()
128: + tolerance, point.getX()
129: - tolerance, point.getY()
130: - tolerance)) {
131: inter = true;
132: break;
133: }
134: }
135:
136: return inter;
137: }
138:
139: /**
140: * the operation returns true if the submitted point intersects the submitted surface patch
141: *
142: * @param point
143: * @param surface
144: * @param tolerance
145: */
146: public static boolean intersects(Position point,
147: SurfacePatch surface, double tolerance) {
148: return LinearContains.contains(surface, point, tolerance);
149: }
150:
151: /**
152: * the operation returns true if the two submitted curves segments intersects
153: */
154: public static boolean intersects(CurveSegment curve1,
155: CurveSegment curve2) {
156: Position[] points = curve1.getPositions();
157: Position[] other = curve2.getPositions();
158: boolean inter = false;
159:
160: for (int i = 0; i < (points.length - 1); i++) {
161: for (int j = 0; j < (other.length - 1); j++) {
162: if (linesIntersect(points[i].getX(), points[i].getY(),
163: points[i + 1].getX(), points[i + 1].getY(),
164: other[j].getX(), other[j].getY(), other[j + 1]
165: .getX(), other[j + 1].getY())) {
166: inter = true;
167: break;
168: }
169: }
170: }
171:
172: return inter;
173: }
174:
175: /**
176: * the operation returns true if the passed curve segment intersects the submitted surface patch
177: *
178: * @param curve
179: * @param surface
180: * @return true if the submitted curve segment intersects the passed surface patch
181: */
182: public static boolean intersects(CurveSegment curve,
183: SurfacePatch surface, double tolerance) throws Exception {
184: boolean inter = false;
185: // is the curve completly embedded within the surface patch
186:
187: if (LinearContains.contains(surface, curve, tolerance)) {
188: inter = true;
189: }
190:
191: // intersects the curve the exterior ring of the surface patch
192: if (!inter) {
193: Position[] ex = surface.getExteriorRing();
194: CurveSegment cs = new LineStringImpl(ex, surface
195: .getCoordinateSystem());
196:
197: if (intersects(curve, cs)) {
198: inter = true;
199: }
200: }
201:
202: // intersects the curve one of the interior rings of the surface patch
203: if (!inter) {
204: Position[][] interior = surface.getInteriorRings();
205:
206: if (interior != null) {
207: for (int i = 0; i < interior.length; i++) {
208: CurveSegment cs = new LineStringImpl(interior[i],
209: surface.getCoordinateSystem());
210:
211: if (intersects(curve, cs)) {
212: inter = true;
213: break;
214: }
215: }
216: }
217: }
218:
219: return inter;
220: }
221:
222: /**
223: * the operation returns true if the two passed surface patches intersects
224: *
225: * @param surface1
226: * @param surface2
227: * @return true if the two passed surface patches intersects
228: */
229: public static boolean intersects(SurfacePatch surface1,
230: SurfacePatch surface2, double tolerance) throws Exception {
231: boolean inter = false;
232: CoordinateSystem crs1 = surface1.getCoordinateSystem();
233: CoordinateSystem crs2 = surface2.getCoordinateSystem();
234:
235: if (LinearContains.contains(surface1, surface2, tolerance)
236: || LinearContains.contains(surface2, surface1,
237: tolerance)) {
238: inter = true;
239: }
240:
241: if (!inter) {
242: Position[] ex1 = surface1.getExteriorRing();
243: CurveSegment cs1 = new LineStringImpl(ex1, crs1);
244: Position[] ex2 = surface2.getExteriorRing();
245: CurveSegment cs2 = new LineStringImpl(ex2, crs2);
246:
247: // intersects exterior rings ?
248: inter = intersects(cs1, cs2);
249:
250: // intersects first exterior ring one of the interior rings of the
251: // second szrface patch
252: if (!inter) {
253: Position[][] interior = surface2.getInteriorRings();
254:
255: if (interior != null) {
256: for (int i = 0; i < interior.length; i++) {
257: cs2 = new LineStringImpl(interior[i], crs2);
258:
259: if (intersects(cs1, cs2)) {
260: inter = true;
261: break;
262: }
263: }
264: }
265: }
266:
267: // intersects the interior rings of the first surface patch with one
268: // of the interior rings of the second surface patch
269: if (!inter) {
270: Position[][] interior1 = surface1.getInteriorRings();
271: Position[][] interior2 = surface2.getInteriorRings();
272:
273: if (interior1 != null && interior2 != null) {
274: for (int i = 0; i < interior1.length; i++) {
275: cs1 = new LineStringImpl(interior1[i], crs1);
276:
277: for (int j = 0; j < interior2.length; j++) {
278: cs2 = new LineStringImpl(interior2[j], crs2);
279:
280: if (intersects(cs1, cs2)) {
281: inter = true;
282: break;
283: }
284: }
285:
286: if (inter) {
287: break;
288: }
289: }
290: }
291: }
292: }
293:
294: return inter;
295: }
296:
297: /**
298: * the operations returns true if two the submitted points intersects
299: */
300: public static boolean intersects(Point point1, Point point2) {
301: double tolerance = getTolerance(point1, point2);
302: return intersects(point1.getPosition(), point2.getPosition(),
303: tolerance);
304: }
305:
306: /**
307: * the operations returns true if the submitted point intersects the submitted curve
308: */
309: public static boolean intersects(Point point, Curve curve)
310: throws Exception {
311: boolean inter = false;
312:
313: int cnt = curve.getNumberOfCurveSegments();
314:
315: double tolerance = getTolerance(point, curve);
316: for (int i = 0; i < cnt; i++) {
317: if (intersects(point.getPosition(), curve
318: .getCurveSegmentAt(i), tolerance)) {
319: inter = true;
320: break;
321: }
322: }
323:
324: return inter;
325: }
326:
327: /**
328: * the operation returns true if the submitted point intersects the submitted surface
329: */
330: public static boolean intersects(Point point, Surface surface)
331: throws Exception {
332: boolean inter = false;
333:
334: int cnt = surface.getNumberOfSurfacePatches();
335:
336: double tolerance = getTolerance(point, surface);
337: for (int i = 0; i < cnt; i++) {
338: if (intersects(point.getPosition(), surface
339: .getSurfacePatchAt(i), tolerance)) {
340: inter = true;
341: break;
342: }
343: }
344:
345: return inter;
346: }
347:
348: /**
349: * the operation returns true if the two submitted curves intersects
350: */
351: public static boolean intersects(Curve curve1, Curve curve2)
352: throws Exception {
353: boolean inter = false;
354: int cnt1 = curve1.getNumberOfCurveSegments();
355: int cnt2 = curve2.getNumberOfCurveSegments();
356:
357: for (int i = 0; (i < cnt1) && !inter; i++) {
358: for (int j = 0; j < cnt2; j++) {
359: if (intersects(curve1.getCurveSegmentAt(i), curve2
360: .getCurveSegmentAt(j))) {
361: inter = true;
362: break;
363: }
364: }
365: }
366:
367: return inter;
368: }
369:
370: /**
371: * the operation returns true if the submitted curve intersects the submitted surface
372: */
373: public static boolean intersects(Curve curve, Surface surface)
374: throws Exception {
375: boolean inter = false;
376: int cnt1 = curve.getNumberOfCurveSegments();
377: int cnt2 = surface.getNumberOfSurfacePatches();
378:
379: double tolerance = getTolerance(curve, surface);
380: for (int i = 0; i < cnt1; i++) {
381: for (int j = 0; j < cnt2; j++) {
382: if (intersects(curve.getCurveSegmentAt(i), surface
383: .getSurfacePatchAt(j), tolerance)) {
384: inter = true;
385: break;
386: }
387: }
388:
389: if (inter) {
390: break;
391: }
392: }
393:
394: return inter;
395: }
396:
397: /**
398: * the operation returns true if the two passed surfaces intersects
399: *
400: * @param surface1
401: * @param surface2
402: * @return true if the two passed surfaces intersects
403: */
404: public static boolean intersects(Surface surface1, Surface surface2)
405: throws Exception {
406: boolean inter = false;
407:
408: int cnt1 = surface1.getNumberOfSurfacePatches();
409: int cnt2 = surface2.getNumberOfSurfacePatches();
410:
411: double tolerance = getTolerance(surface1, surface2);
412: for (int i = 0; i < cnt1; i++) {
413: for (int j = 0; j < cnt2; j++) {
414: if (intersects(surface1.getSurfacePatchAt(i), surface2
415: .getSurfacePatchAt(j), tolerance)) {
416: inter = true;
417: break;
418: }
419: }
420:
421: if (inter) {
422: break;
423: }
424: }
425:
426: return inter;
427: }
428:
429: /**
430: *
431: *
432: * @param X1
433: * @param Y1
434: * @param X2
435: * @param Y2
436: * @param PX
437: * @param PY
438: *
439: * @return
440: */
441: protected static int relativeCCW(double X1, double Y1, double X2,
442: double Y2, double PX, double PY) {
443: X2 -= X1;
444: Y2 -= Y1;
445: PX -= X1;
446: PY -= Y1;
447:
448: double ccw = (PX * Y2) - (PY * X2);
449:
450: if (ccw == 0.0) {
451: ccw = (PX * X2) + (PY * Y2);
452:
453: if (ccw > 0.0) {
454: PX -= X2;
455: PY -= Y2;
456: ccw = (PX * X2) + (PY * Y2);
457:
458: if (ccw < 0.0) {
459: ccw = 0.0;
460: }
461: }
462: }
463:
464: return (ccw < 0.0) ? (-1) : ((ccw > 0.0) ? 1 : 0);
465: }
466:
467: /**
468: * Tests if the line segment from (x1, y1) to (x2, y2) intersects the line segment
469: * from (x3, y3) to (x4, y4).
470: *
471: * @return <code>true</code> if the first specified line segment and the second specified line
472: * segment intersect each other; <code>false</code> otherwise.
473: */
474: protected static boolean linesIntersect(double x1, double y1,
475: double x2, double y2, double x3, double y3, double x4,
476: double y4) {
477: return ((relativeCCW(x1, y1, x2, y2, x3, y3)
478: * relativeCCW(x1, y1, x2, y2, x4, y4) <= 0) && (relativeCCW(
479: x3, y3, x4, y4, x1, y1)
480: * relativeCCW(x3, y3, x4, y4, x2, y2) <= 0));
481: }
482: }
|