    001    //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.4_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    }