001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/branches/2.2_testing/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, double tolerance ) {
078
079 double d = 0;
080 double[] p1 = point1.getAsArray();
081 double[] p2 = point2.getAsArray();
082
083 for ( int i = 0; i < p1.length; i++ ) {
084 d += ( ( p1[i] - p2[i] ) * ( p1[i] - p2[i] ) );
085 }
086
087 return Math.sqrt( d ) < tolerance;
088 }
089
090 /**
091 * the operations returns true if the submitted point intersects the passed curve segment
092 *
093 * @param point
094 * @param curve
095 * @param tolerance
096 */
097 public static boolean intersects( Position point, CurveSegment curve, double tolerance )
098 throws Exception {
099 boolean inter = false;
100
101 Position[] points = curve.getPositions();
102
103 for ( int i = 0; i < ( points.length - 1 ); i++ ) {
104 if ( linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(), points[i + 1].getY(),
105 point.getX() - tolerance, point.getY() - tolerance, point.getX() + tolerance,
106 point.getY() - tolerance )
107 || linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(), points[i + 1].getY(),
108 point.getX() + tolerance, point.getY() - tolerance, point.getX() + tolerance,
109 point.getY() + tolerance )
110 || linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(), points[i + 1].getY(),
111 point.getX() + tolerance, point.getY() + tolerance, point.getX() - tolerance,
112 point.getY() + tolerance )
113 || linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(), points[i + 1].getY(),
114 point.getX() - tolerance, point.getY() + tolerance, point.getX() - tolerance,
115 point.getY() - tolerance ) ) {
116 inter = true;
117 break;
118 }
119 }
120
121 return inter;
122 }
123
124 /**
125 * the operation returns true if the submitted point intersects the submitted surface patch
126 *
127 * @param point
128 * @param surface
129 * @param tolerance
130 */
131 public static boolean intersects( Position point, SurfacePatch surface, double tolerance ) {
132 return LinearContains.contains( surface, point, tolerance );
133 }
134
135 /**
136 * the operation returns true if the two submitted curves segments intersects
137 */
138 public static boolean intersects( CurveSegment curve1, CurveSegment curve2 ) {
139 Position[] points = curve1.getPositions();
140 Position[] other = curve2.getPositions();
141 boolean inter = false;
142
143 for ( int i = 0; i < ( points.length - 1 ); i++ ) {
144 for ( int j = 0; j < ( other.length - 1 ); j++ ) {
145 if ( linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(), points[i + 1].getY(),
146 other[j].getX(), other[j].getY(), other[j + 1].getX(), other[j + 1].getY() ) ) {
147 inter = true;
148 break;
149 }
150 }
151 }
152
153 return inter;
154 }
155
156 /**
157 * the operation returns true if the passed curve segment intersects the submitted surface patch
158 *
159 * @param curve
160 * @param surface
161 * @return true if the submitted curve segment intersects the passed surface patch
162 */
163 public static boolean intersects( CurveSegment curve, SurfacePatch surface, double tolerance )
164 throws Exception {
165 boolean inter = false;
166 // is the curve completly embedded within the surface patch
167
168 if ( LinearContains.contains( surface, curve, tolerance ) ) {
169 inter = true;
170 }
171
172 // intersects the curve the exterior ring of the surface patch
173 if ( !inter ) {
174 Position[] ex = surface.getExteriorRing();
175 CurveSegment cs = new LineStringImpl( ex, surface.getCoordinateSystem() );
176
177 if ( intersects( curve, cs ) ) {
178 inter = true;
179 }
180 }
181
182 // intersects the curve one of the interior rings of the surface patch
183 if ( !inter ) {
184 Position[][] interior = surface.getInteriorRings();
185
186 if ( interior != null ) {
187 for ( int i = 0; i < interior.length; i++ ) {
188 CurveSegment cs = new LineStringImpl( interior[i], surface.getCoordinateSystem() );
189
190 if ( intersects( curve, cs ) ) {
191 inter = true;
192 break;
193 }
194 }
195 }
196 }
197
198 return inter;
199 }
200
201 /**
202 * the operation returns true if the two passed surface patches intersects
203 *
204 * @param surface1
205 * @param surface2
206 * @return true if the two passed surface patches intersects
207 */
208 public static boolean intersects( SurfacePatch surface1, SurfacePatch surface2, double tolerance )
209 throws Exception {
210 boolean inter = false;
211 CoordinateSystem crs1 = surface1.getCoordinateSystem();
212 CoordinateSystem crs2 = surface2.getCoordinateSystem();
213
214 if ( LinearContains.contains( surface1, surface2, tolerance )
215 || LinearContains.contains( surface2, surface1, tolerance ) ) {
216 inter = true;
217 }
218
219 if ( !inter ) {
220 Position[] ex1 = surface1.getExteriorRing();
221 CurveSegment cs1 = new LineStringImpl( ex1, crs1 );
222 Position[] ex2 = surface2.getExteriorRing();
223 CurveSegment cs2 = new LineStringImpl( ex2, crs2 );
224
225 // intersects exterior rings ?
226 inter = intersects( cs1, cs2 );
227
228 // intersects first exterior ring one of the interior rings of the
229 // second szrface patch
230 if ( !inter ) {
231 Position[][] interior = surface2.getInteriorRings();
232
233 if ( interior != null ) {
234 for ( int i = 0; i < interior.length; i++ ) {
235 cs2 = new LineStringImpl( interior[i], crs2 );
236
237 if ( intersects( cs1, cs2 ) ) {
238 inter = true;
239 break;
240 }
241 }
242 }
243 }
244
245 // intersects the interior rings of the first surface patch with one
246 // of the interior rings of the second surface patch
247 if ( !inter ) {
248 Position[][] interior1 = surface1.getInteriorRings();
249 Position[][] interior2 = surface2.getInteriorRings();
250
251 if ( interior1 != null && interior2 != null ) {
252 for ( int i = 0; i < interior1.length; i++ ) {
253 cs1 = new LineStringImpl( interior1[i], crs1 );
254
255 for ( int j = 0; j < interior2.length; j++ ) {
256 cs2 = new LineStringImpl( interior2[j], crs2 );
257
258 if ( intersects( cs1, cs2 ) ) {
259 inter = true;
260 break;
261 }
262 }
263
264 if ( inter ) {
265 break;
266 }
267 }
268 }
269 }
270 }
271
272 return inter;
273 }
274
275 /**
276 * the operations returns true if two the submitted points intersects
277 */
278 public static boolean intersects( Point point1, Point point2 ) {
279 double tolerance = getTolerance( point1, point2 );
280 return intersects( point1.getPosition(), point2.getPosition(), tolerance );
281 }
282
283 /**
284 * the operations returns true if the submitted point intersects the submitted curve
285 */
286 public static boolean intersects( Point point, Curve curve )
287 throws Exception {
288 boolean inter = false;
289
290 int cnt = curve.getNumberOfCurveSegments();
291
292 double tolerance = getTolerance( point, curve );
293 for ( int i = 0; i < cnt; i++ ) {
294 if ( intersects( point.getPosition(), curve.getCurveSegmentAt( i ), tolerance ) ) {
295 inter = true;
296 break;
297 }
298 }
299
300 return inter;
301 }
302
303 /**
304 * the operation returns true if the submitted point intersects the submitted surface
305 */
306 public static boolean intersects( Point point, Surface surface )
307 throws Exception {
308 boolean inter = false;
309
310 int cnt = surface.getNumberOfSurfacePatches();
311
312 double tolerance = getTolerance( point, surface );
313 for ( int i = 0; i < cnt; i++ ) {
314 if ( intersects( point.getPosition(), surface.getSurfacePatchAt( i ), tolerance ) ) {
315 inter = true;
316 break;
317 }
318 }
319
320 return inter;
321 }
322
323 /**
324 * the operation returns true if the two submitted curves intersects
325 */
326 public static boolean intersects( Curve curve1, Curve curve2 )
327 throws Exception {
328 boolean inter = false;
329 int cnt1 = curve1.getNumberOfCurveSegments();
330 int cnt2 = curve2.getNumberOfCurveSegments();
331
332 for ( int i = 0; ( i < cnt1 ) && !inter; i++ ) {
333 for ( int j = 0; j < cnt2; j++ ) {
334 if ( intersects( curve1.getCurveSegmentAt( i ), curve2.getCurveSegmentAt( j ) ) ) {
335 inter = true;
336 break;
337 }
338 }
339 }
340
341 return inter;
342 }
343
344 /**
345 * the operation returns true if the submitted curve intersects the submitted surface
346 */
347 public static boolean intersects( Curve curve, Surface surface )
348 throws Exception {
349 boolean inter = false;
350 int cnt1 = curve.getNumberOfCurveSegments();
351 int cnt2 = surface.getNumberOfSurfacePatches();
352
353 double tolerance = getTolerance( curve, surface );
354 for ( int i = 0; i < cnt1; i++ ) {
355 for ( int j = 0; j < cnt2; j++ ) {
356 if ( intersects( curve.getCurveSegmentAt( i ), surface.getSurfacePatchAt( j ), tolerance ) ) {
357 inter = true;
358 break;
359 }
360 }
361
362 if ( inter ) {
363 break;
364 }
365 }
366
367 return inter;
368 }
369
370 /**
371 * the operation returns true if the two passed surfaces intersects
372 *
373 * @param surface1
374 * @param surface2
375 * @return true if the two passed surfaces intersects
376 */
377 public static boolean intersects( Surface surface1, Surface surface2 )
378 throws Exception {
379 boolean inter = false;
380
381 int cnt1 = surface1.getNumberOfSurfacePatches();
382 int cnt2 = surface2.getNumberOfSurfacePatches();
383
384 double tolerance = getTolerance( surface1, surface2 );
385 for ( int i = 0; i < cnt1; i++ ) {
386 for ( int j = 0; j < cnt2; j++ ) {
387 if ( intersects( surface1.getSurfacePatchAt( i ), surface2.getSurfacePatchAt( j ), tolerance ) ) {
388 inter = true;
389 break;
390 }
391 }
392
393 if ( inter ) {
394 break;
395 }
396 }
397
398 return inter;
399 }
400
401 /**
402 *
403 *
404 * @param X1
405 * @param Y1
406 * @param X2
407 * @param Y2
408 * @param PX
409 * @param PY
410 *
411 * @return
412 */
413 protected static int relativeCCW( double X1, double Y1, double X2, double Y2, double PX, double PY ) {
414 X2 -= X1;
415 Y2 -= Y1;
416 PX -= X1;
417 PY -= Y1;
418
419 double ccw = ( PX * Y2 ) - ( PY * X2 );
420
421 if ( ccw == 0.0 ) {
422 ccw = ( PX * X2 ) + ( PY * Y2 );
423
424 if ( ccw > 0.0 ) {
425 PX -= X2;
426 PY -= Y2;
427 ccw = ( PX * X2 ) + ( PY * Y2 );
428
429 if ( ccw < 0.0 ) {
430 ccw = 0.0;
431 }
432 }
433 }
434
435 return ( ccw < 0.0 ) ? ( -1 ) : ( ( ccw > 0.0 ) ? 1 : 0 );
436 }
437
438 /**
439 * Tests if the line segment from (x1, y1) to (x2, y2) intersects the line segment
440 * from (x3, y3) to (x4, y4).
441 *
442 * @return <code>true</code> if the first specified line segment and the second specified line
443 * segment intersect each other; <code>false</code> otherwise.
444 */
445 protected static boolean linesIntersect( double x1, double y1, double x2, double y2, double x3, double y3,
446 double x4, double y4 ) {
447 return ( ( relativeCCW( x1, y1, x2, y2, x3, y3 ) * relativeCCW( x1, y1, x2, y2, x4, y4 ) <= 0 ) && ( relativeCCW(
448 x3,
449 y3,
450 x4,
451 y4,
452 x1,
453 y1 )
454 * relativeCCW(
455 x3,
456 y3,
457 x4,
458 y4,
459 x2,
460 y2 ) <= 0 ) );
461 }
462 }