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