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,&nbsp;y1) to (x2,&nbsp;y2) intersects the line segment from (x3,&nbsp;y3) to
407         * (x4,&nbsp;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    }