001    //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_testing/src/org/deegree/model/spatialschema/LinearContains.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    import java.util.ArrayList;
039    
040    /**
041     *
042     *
043     *
044     * @version $Revision: 18195 $
045     * @author <a href="mailto:poth@lat-lon.de">Andreas Poth</a>
046     * @author last edited by: $Author: mschneider $
047     *
048     * @version 1.0. $Revision: 18195 $, $Date: 2009-06-18 17:55:39 +0200 (Do, 18 Jun 2009) $
049     *
050     * @since 2.0
051     */
052    public class LinearContains {
053    
054        /**
055         *
056         * @param geom1
057         * @param geom2
058         * @return maximum tolerance of geom1 and geom2
059         */
060        public static double getTolerance( Geometry geom1, Geometry geom2 ) {
061            double d = geom1.getTolerance();
062            if ( geom2.getTolerance() > d ) {
063                d = geom2.getTolerance();
064            }
065            return d;
066        }
067    
068        /**
069         * Currently not supported
070         *
071         * @param point1
072         * @param point2
073         * @return true if the the two submitted points are the same......maybe.
074         */
075        public static boolean contains( Position point1, Position point2 ) {
076            throw new UnsupportedOperationException( "contains(Position, Position)" + " not supported at the moment." );
077        }
078    
079        /**
080         * Currently not supported
081         *
082         * @param curve
083         * @param point
084         * @return true if the submitted point contains the submitted curve segment
085         */
086        public static boolean contains( CurveSegment curve, Position point ) {
087            throw new UnsupportedOperationException( "contains(CurveSegment, Position)" + " not supported at the moment." );
088        }
089    
090        /**
091         * the operation returns true if the submitted point contains the submitted surface patch
092         *
093         * @param surface
094         * @param point
095         * @param tolerance
096         * @return true if the passed point contains the submitted surface patch
097         */
098        public static boolean contains( SurfacePatch surface, Position point, double tolerance ) {
099            boolean con = false;
100            Position[] ex = surface.getExteriorRing();
101            con = contains( ex, point, tolerance );
102    
103            if ( con ) {
104                Position[][] inner = surface.getInteriorRings();
105    
106                if ( inner != null ) {
107                    for ( int i = 0; i < inner.length; i++ ) {
108                        if ( contains( inner[i], point, tolerance ) ) {
109                            con = false;
110                            break;
111                        }
112                    }
113                }
114            }
115    
116            return con;
117        }
118    
119        /**
120         * the operation is currently not supported
121         *
122         * @param curve1
123         * @param curve2
124         * @return true if the two submitted curves segments contain each other.
125         */
126        public static boolean contains( CurveSegment curve1, CurveSegment curve2 ) {
127            throw new UnsupportedOperationException( "contains(CurveSegment, CurveSegment)"
128                                                     + " not supported at the moment." );
129        }
130    
131        /**
132         * the operation returns true if the submitted curve segment contains the submitted surface patch
133         *
134         * @param surface
135         * @param curve
136         * @param tolerance
137         * @return true if the submitted curve segment contains the submitted surface patch
138         */
139        public static boolean contains( SurfacePatch surface, CurveSegment curve, double tolerance ) {
140            boolean con = true;
141            Position[] ex = surface.getExteriorRing();
142            Position[] cu = curve.getPositions();
143    
144            for ( int i = 0; i < cu.length; i++ ) {
145                if ( !contains( ex, cu[i], tolerance ) ) {
146                    con = false;
147                    break;
148                }
149            }
150    
151            if ( con ) {
152                Position[][] inner = surface.getInteriorRings();
153    
154                if ( inner != null ) {
155                    for ( int i = 0; i < inner.length; i++ ) {
156                        for ( int j = 0; j < cu.length; j++ ) {
157                            if ( contains( inner[i], cu[j], tolerance ) ) {
158                                con = false;
159                                break;
160                            }
161                        }
162    
163                        if ( !con ) {
164                            break;
165                        }
166                    }
167                }
168            }
169    
170            return con;
171        }
172    
173        /**
174         * the operation returns true if the first surface patches contains the second one
175         *
176         * @param surface1
177         * @param surface2
178         * @param tolerance
179         * @return true if the first surface patches contains
180         */
181        public static boolean contains( SurfacePatch surface1, SurfacePatch surface2, double tolerance ) {
182            boolean con = true;
183            Position[] ex = surface1.getExteriorRing();
184            Position[] ex_ = surface2.getExteriorRing();
185    
186            for ( int i = 0; i < ex_.length; i++ ) {
187                if ( !contains( ex, ex_[i], tolerance ) ) {
188                    con = false;
189                    break;
190                }
191            }
192    
193            if ( con ) {
194                Position[][] inner = surface1.getInteriorRings();
195                Position[][] inner_ = surface2.getInteriorRings();
196    
197                if ( inner != null ) {
198                    for ( int i = 0; i < inner.length; i++ ) {
199                        // a point of the second exterior is not allowed to be
200                        // within a inner ring of the first
201                        for ( int j = 0; j < ex_.length; j++ ) {
202                            if ( contains( inner[i], ex_[j], tolerance ) ) {
203                                con = false;
204                                break;
205                            }
206                        }
207    
208                        if ( !con ) {
209                            break;
210                        }
211    
212                        // a point of the inner rings of the second is not allowed
213                        // to be within a inner ring of the first
214                        if ( inner_ != null ) {
215                            for ( int k = 0; k < inner_.length; k++ ) {
216                                for ( int j = 0; j < inner_[k].length; j++ ) {
217                                    if ( contains( inner[i], inner_[k][j], tolerance ) ) {
218                                        con = false;
219                                        break;
220                                    }
221                                }
222    
223                                if ( !con ) {
224                                    break;
225                                }
226                            }
227                        }
228    
229                        // a point of the inner rings of the first is not allowed
230                        // to be within the second surface
231                        for ( int j = 0; j < inner[i].length; j++ ) {
232                            if ( contains( surface2, inner[i][j], tolerance ) ) {
233                                con = false;
234                                break;
235                            }
236                        }
237    
238                        if ( !con ) {
239                            break;
240                        }
241                    }
242                }
243            }
244    
245            // surface2 is not allowed to contain one point of surface1
246            if ( con ) {
247                for ( int i = 0; i < ex.length; i++ ) {
248                    if ( contains( surface2, ex[i], tolerance ) ) {
249                        con = false;
250                        break;
251                    }
252                }
253            }
254    
255            return con;
256        }
257    
258        /**
259         * the operations returns true if two the passed points contains
260         *
261         * @param point1
262         * @param point2
263         * @return true if two the passed points contains
264         */
265        public static boolean contains( Point point1, Point point2 ) {
266            return point1.equals( point2 );
267        }
268    
269        /**
270         * the operation is currently not supported.
271         *
272         * @param curve
273         * @param point
274         * @return true if the submitted point contains the submitted curve
275         */
276        public static boolean contains( Curve curve, Point point ) {
277            throw new UnsupportedOperationException( "contains(Curve, Point)" + " not supported at the moment." );
278        }
279    
280        /**
281         * the operation returns true if the submitted point contains the submitted surface
282         *
283         * @param surface
284         * @param point
285         * @return true if the submitted point contains the submitted surface
286         * @throws Exception
287         */
288        public static boolean contains( Surface surface, Point point )
289                                throws Exception {
290            boolean contain = false;
291            int cnt = surface.getNumberOfSurfacePatches();
292    
293            double tolerance = getTolerance( surface, point );
294            for ( int i = 0; i < cnt; i++ ) {
295                if ( contains( surface.getSurfacePatchAt( i ), point.getPosition(), tolerance ) ) {
296                    contain = true;
297                    break;
298                }
299            }
300    
301            return contain;
302        }
303    
304        /**
305         * the operation is currently not supported.
306         *
307         * @param curve1
308         * @param curve2
309         * @return true if the two submitted curves contains
310         */
311        public static boolean contains( Curve curve1, Curve curve2 ) {
312            throw new UnsupportedOperationException( "contains(Curve, Curve)" + " not supported at the moment." );
313        }
314    
315        /**
316         * Convenience method to extract all <tt>Position</tt>s from a <tt>Curve</tt>.
317         */
318        private static Position[] getPositions( Curve curve )
319                                throws GeometryException {
320            ArrayList<Position> positions = new ArrayList<Position>( 1000 );
321    
322            for ( int i = 0; i < curve.getNumberOfCurveSegments(); i++ ) {
323                CurveSegment segment = curve.getCurveSegmentAt( i );
324                Position[] segmentPos = segment.getPositions();
325    
326                for ( int j = 0; j < segmentPos.length; j++ )
327                    positions.add( segmentPos[j] );
328            }
329    
330            return positions.toArray( new Position[positions.size()] );
331        }
332    
333        /**
334         * the operation returns true if the submitted curve contains the submitted surface
335         *
336         * @param surface
337         * @param curve
338         * @return true if the submitted curve contains the submitted surface
339         * @throws GeometryException
340         */
341        public static boolean contains( Surface surface, Curve curve )
342                                throws GeometryException {
343            // gather the positions of the crings (exterior and interior) and
344            // the curve as arrays of Positions
345            SurfaceBoundary boundary = (SurfaceBoundary) surface.getBoundary();
346            Ring extRing = boundary.getExteriorRing();
347            Ring[] intRings = boundary.getInteriorRings();
348    
349            Position[] curvePos = getPositions( curve );
350            Position[] extRingPos = extRing.getPositions();
351            Position[][] intRingsPos = new Position[intRings.length][];
352    
353            for ( int i = 0; i < intRings.length; i++ )
354                intRingsPos[i] = intRings[i].getPositions();
355    
356            // necessary condition: all points of the curve have to be inside
357            // of the surface's exterior ring and none must be inside of one
358            // of the interior rings
359            for ( int i = 0; i < curvePos.length; i++ ) {
360                if ( !contains( extRingPos, curvePos[i], getTolerance( surface, curve ) ) ) {
361                    return false;
362                }
363    
364                for ( int j = 0; j < intRings.length; j++ ) {
365                    if ( contains( intRingsPos[j], curvePos[i], getTolerance( surface, curve ) ) ) {
366                        return false;
367                    }
368                }
369            }
370    
371            return true;
372        }
373    
374        /**
375         * the operation returns true if the two submitted surfaces contains
376         *
377         * @param surface2
378         * @param surface1
379         * @return true if the two submitted surfaces contains
380         * @throws Exception
381         */
382        public static boolean contains( Surface surface2, Surface surface1 )
383                                throws Exception {
384            double tolerance = getTolerance( surface1, surface2 );
385            return contains( surface2.getSurfacePatchAt( 0 ), surface1.getSurfacePatchAt( 0 ), tolerance );
386        }
387    
388        /**
389         * the operation returns true if polygon defined by an array of Position contains the submitted point.
390         *
391         * @param positions
392         * @param point
393         * @param tolerance
394         * @return true if polygon defined by an array of Position contains the submitted point.
395         */
396        protected static boolean contains( Position[] positions, Position point, double tolerance ) {
397    
398            // TODO
399            // consider tolerance value
400    
401            if ( positions.length <= 2 ) {
402                return false;
403            }
404    
405            int hits = 0;
406    
407            double lastx = positions[positions.length - 1].getX();
408            double lasty = positions[positions.length - 1].getY();
409            double curx;
410            double cury;
411    
412            // Walk the edges of the polygon
413            for ( int i = 0; i < positions.length; lastx = curx, lasty = cury, i++ ) {
414                curx = positions[i].getX();
415                cury = positions[i].getY();
416    
417                if ( cury == lasty ) {
418                    continue;
419                }
420    
421                double leftx;
422    
423                if ( curx < lastx ) {
424                    if ( point.getX() >= lastx ) {
425                        continue;
426                    }
427    
428                    leftx = curx;
429                } else {
430                    if ( point.getX() >= curx ) {
431                        continue;
432                    }
433    
434                    leftx = lastx;
435                }
436    
437                double test1;
438                double test2;
439    
440                if ( cury < lasty ) {
441                    if ( ( point.getY() < cury ) || ( point.getY() >= lasty ) ) {
442                        continue;
443                    }
444    
445                    if ( point.getX() < leftx ) {
446                        hits++;
447                        continue;
448                    }
449    
450                    test1 = point.getX() - curx;
451                    test2 = point.getY() - cury;
452                } else {
453                    if ( ( point.getY() < lasty ) || ( point.getY() >= cury ) ) {
454                        continue;
455                    }
456    
457                    if ( point.getX() < leftx ) {
458                        hits++;
459                        continue;
460                    }
461    
462                    test1 = point.getX() - lastx;
463                    test2 = point.getY() - lasty;
464                }
465    
466                if ( test1 < ( test2 / ( lasty - cury ) * ( lastx - curx ) ) ) {
467                    hits++;
468                }
469            }
470    
471            return ( ( hits & 1 ) != 0 );
472        }
473    }