001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/tags/2.1/src/org/deegree/model/spatialschema/LinearIntersects.java $
002 /*---------------- FILE HEADER ------------------------------------------
003
004 This file is part of deegree.
005 Copyright (C) 2001-2006 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 *
052 * @version $Revision: 6259 $
053 * @author <a href="mailto:poth@lat-lon.de">Andreas Poth</a>
054 */
055 class LinearIntersects {
056
057 /**
058 *
059 * @param geom1
060 * @param geom2
061 * @return maximum tolerance of geom1 and geom2
062 */
063 public static double getTolerance(Geometry geom1, Geometry geom2) {
064 double d = geom1.getTolerance();
065 if ( geom2.getTolerance() > d ) {
066 d = geom2.getTolerance();
067 }
068 return d;
069 }
070
071 /**
072 * the operations returns true if two the submitted points intersects
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
092 * the passed curve segment
093 * @param point
094 * @param curve
095 * @param tolerance
096 */
097 public static boolean intersects( Position point, CurveSegment curve, double tolerance ) throws Exception {
098 boolean inter = false;
099
100 Position[] points = curve.getPositions();
101
102 for ( int i = 0; i < ( points.length - 1 ); i++ ) {
103 if ( linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(),
104 points[i + 1].getY(), point.getX() - tolerance, point.getY() - tolerance,
105 point.getX() + tolerance, point.getY() - tolerance ) ||
106 linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(),
107 points[i + 1].getY(), point.getX() + tolerance, point.getY() - tolerance,
108 point.getX() + tolerance, point.getY() + tolerance ) ||
109 linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(),
110 points[i + 1].getY(), point.getX() + tolerance, point.getY() + tolerance,
111 point.getX() - tolerance, point.getY() + tolerance ) ||
112 linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(),
113 points[i + 1].getY(), point.getX() - tolerance, point.getY() + tolerance,
114 point.getX() - tolerance, point.getY() - tolerance ) ) {
115 inter = true;
116 break;
117 }
118 }
119
120 return inter;
121 }
122
123 /**
124 * the operation returns true if the submitted point intersects
125 * the submitted surface patch
126 * @param point
127 * @param surface
128 * @param tolerance
129 */
130 public static boolean intersects( Position point, SurfacePatch surface, double tolerance ) {
131 return LinearContains.contains( surface, point, tolerance );
132 }
133
134 /**
135 * the operation returns true if the two submitted curves segments intersects
136 */
137 public static boolean intersects( CurveSegment curve1, CurveSegment curve2 ) {
138 Position[] points = curve1.getPositions();
139 Position[] other = curve2.getPositions();
140 boolean inter = false;
141
142 for ( int i = 0; i < ( points.length - 1 ); i++ ) {
143 for ( int j = 0; j < ( other.length - 1 ); j++ ) {
144 if ( linesIntersect( points[i].getX(), points[i].getY(), points[i + 1].getX(),
145 points[i + 1].getY(), other[j].getX(), other[j].getY(),
146 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
158 * the submitted surface patch
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],
189 surface.getCoordinateSystem() );
190
191 if ( intersects( curve, cs ) ) {
192 inter = true;
193 break;
194 }
195 }
196 }
197 }
198
199 return inter;
200 }
201
202 /**
203 * the operation returns true if the two passed surface patches intersects
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,
209 double tolerance)
210 throws Exception {
211 boolean inter = false;
212 CoordinateSystem crs1 = surface1.getCoordinateSystem();
213 CoordinateSystem crs2 = surface2.getCoordinateSystem();
214
215 if ( LinearContains.contains( surface1, surface2, tolerance ) ||
216 LinearContains.contains( surface2, surface1, tolerance ) ) {
217 inter = true;
218 }
219
220 if ( !inter ) {
221 Position[] ex1 = surface1.getExteriorRing();
222 CurveSegment cs1 = new LineStringImpl( ex1, crs1 );
223 Position[] ex2 = surface2.getExteriorRing();
224 CurveSegment cs2 = new LineStringImpl( ex2, crs2 );
225
226 // intersects exterior rings ?
227 inter = intersects( cs1, cs2 );
228
229 // intersects first exterior ring one of the interior rings of the
230 // second szrface patch
231 if ( !inter ) {
232 Position[][] interior = surface2.getInteriorRings();
233
234 if ( interior != null ) {
235 for ( int i = 0; i < interior.length; i++ ) {
236 cs2 = new LineStringImpl( interior[i], crs2 );
237
238 if ( intersects( cs1, cs2 ) ) {
239 inter = true;
240 break;
241 }
242 }
243 }
244 }
245
246 // intersects the interior rings of the first surface patch with one
247 //of the interior rings of the second surface patch
248 if ( !inter ) {
249 Position[][] interior1 = surface1.getInteriorRings();
250 Position[][] interior2 = surface2.getInteriorRings();
251
252 if ( interior1 != null && interior2 != null ) {
253 for ( int i = 0; i < interior1.length; i++ ) {
254 cs1 = new LineStringImpl( interior1[i], crs1 );
255
256 for ( int j = 0; j < interior2.length; j++ ) {
257 cs2 = new LineStringImpl( interior2[j], crs2 );
258
259 if ( intersects( cs1, cs2 ) ) {
260 inter = true;
261 break;
262 }
263 }
264
265 if ( inter ) {
266 break;
267 }
268 }
269 }
270 }
271 }
272
273 return inter;
274 }
275
276 /**
277 * the operations returns true if two the submitted points intersects
278 */
279 public static boolean intersects( Point point1, Point point2 ) {
280 double tolerance = getTolerance( point1, point2 );
281 return intersects( point1.getPosition(), point2.getPosition(), tolerance );
282 }
283
284 /**
285 * the operations returns true if the submitted point intersects
286 * the submitted curve
287 */
288 public static boolean intersects( Point point, Curve curve ) throws Exception {
289 boolean inter = false;
290
291 int cnt = curve.getNumberOfCurveSegments();
292
293 double tolerance = getTolerance( point, curve );
294 for ( int i = 0; i < cnt; i++ ) {
295 if ( intersects( point.getPosition(), curve.getCurveSegmentAt( i ), tolerance ) ) {
296 inter = true;
297 break;
298 }
299 }
300
301 return inter;
302 }
303
304 /**
305 * the operation returns true if the submitted point intersects
306 * the submitted surface
307 */
308 public static boolean intersects( Point point, Surface surface ) throws Exception {
309 boolean inter = false;
310
311 int cnt = surface.getNumberOfSurfacePatches();
312
313 double tolerance = getTolerance( point, surface );
314 for ( int i = 0; i < cnt; i++ ) {
315 if ( intersects( point.getPosition(), surface.getSurfacePatchAt( i ), tolerance ) ) {
316 inter = true;
317 break;
318 }
319 }
320
321 return inter;
322 }
323
324 /**
325 * the operation returns true if the two submitted curves intersects
326 */
327 public static boolean intersects( Curve curve1, Curve curve2 ) 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
346 * the submitted surface
347 */
348 public static boolean intersects( Curve curve, Surface surface ) 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 ),
357 tolerance ) ) {
358 inter = true;
359 break;
360 }
361 }
362
363 if ( inter ) {
364 break;
365 }
366 }
367
368 return inter;
369 }
370
371 /**
372 * the operation returns true if the two passed surfaces intersects
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 ) throws Exception {
378 boolean inter = false;
379
380 int cnt1 = surface1.getNumberOfSurfacePatches();
381 int cnt2 = surface2.getNumberOfSurfacePatches();
382
383 double tolerance = getTolerance( surface1, surface2 );
384 for ( int i = 0; i < cnt1; i++ ) {
385 for ( int j = 0; j < cnt2; j++ ) {
386 if ( intersects( surface1.getSurfacePatchAt( i ),
387 surface2.getSurfacePatchAt( j ),
388 tolerance) ) {
389 inter = true;
390 break;
391 }
392 }
393
394 if ( inter ) {
395 break;
396 }
397 }
398
399 return inter;
400 }
401
402 /**
403 *
404 *
405 * @param X1
406 * @param Y1
407 * @param X2
408 * @param Y2
409 * @param PX
410 * @param PY
411 *
412 * @return
413 */
414 protected static int relativeCCW( double X1, double Y1, double X2, double Y2, double PX, double PY ) {
415 X2 -= X1;
416 Y2 -= Y1;
417 PX -= X1;
418 PY -= Y1;
419
420 double ccw = ( PX * Y2 ) - ( PY * X2 );
421
422 if ( ccw == 0.0 ) {
423 ccw = ( PX * X2 ) + ( PY * Y2 );
424
425 if ( ccw > 0.0 ) {
426 PX -= X2;
427 PY -= Y2;
428 ccw = ( PX * X2 ) + ( PY * Y2 );
429
430 if ( ccw < 0.0 ) {
431 ccw = 0.0;
432 }
433 }
434 }
435
436 return ( ccw < 0.0 ) ? ( -1 ) : ( ( ccw > 0.0 ) ? 1 : 0 );
437 }
438
439 /**
440 * Tests if the line segment from (x1, y1) to
441 * (x2, y2) intersects the line segment from (x3, y3)
442 * to (x4, y4).
443 * @return <code>true</code> if the first specified line segment
444 * and the second specified line segment intersect
445 * each other; <code>false</code> otherwise.
446 */
447 protected static boolean linesIntersect( double x1, double y1, double x2, double y2, double x3,
448 double y3, double x4, double y4 ) {
449 return ( ( relativeCCW( x1, y1, x2, y2, x3, y3 ) * relativeCCW( x1, y1, x2, y2, x4, y4 ) <= 0 ) &&
450 ( relativeCCW( x3, y3, x4, y4, x1, y1 ) * relativeCCW( x3, y3, x4, y4, x2, y2 ) <= 0 ) );
451 }
452 }/* ********************************************************************
453 Changes to this class. What the people have been up to:
454 $Log$
455 Revision 1.9 2007/02/22 19:48:53 poth
456 support for tolerance added form some topological operations
457
458 Revision 1.8 2007/02/22 11:24:19 poth
459 support for tolerance added form some topological operations
460
461 Revision 1.7 2006/07/12 14:46:15 poth
462 comment footer added
463
464 ********************************************************************** */