    001    //$HeadURL$
    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
    037    package org.deegree.framework.util;
    038
    039    import static org.deegree.framework.log.LoggerFactory.getLogger;
    040    import static org.deegree.framework.util.CollectionUtils.map;
    041    import static org.deegree.model.spatialschema.GeometryFactory.createCurve;
    042    import static org.deegree.model.spatialschema.GeometryFactory.createCurveSegment;
    043    import static org.deegree.model.spatialschema.GeometryFactory.createEnvelope;
    044    import static org.deegree.model.spatialschema.GeometryFactory.createPoint;
    045    import static org.deegree.model.spatialschema.GeometryFactory.createPosition;
    046    import static org.deegree.model.spatialschema.GeometryFactory.createSurface;
    047    import static org.deegree.model.spatialschema.GeometryFactory.createSurfacePatch;
    048
    049    import java.util.ArrayList;
    050    import java.util.List;
    051
    052    import org.deegree.framework.log.ILogger;
    053    import org.deegree.framework.util.CollectionUtils.Mapper;
    054    import org.deegree.model.spatialschema.Aggregate;
    055    import org.deegree.model.spatialschema.Curve;
    056    import org.deegree.model.spatialschema.CurveSegment;
    057    import org.deegree.model.spatialschema.Envelope;
    058    import org.deegree.model.spatialschema.Geometry;
    059    import org.deegree.model.spatialschema.GeometryException;
    060    import org.deegree.model.spatialschema.GeometryFactory;
    061    import org.deegree.model.spatialschema.JTSAdapter;
    062    import org.deegree.model.spatialschema.MultiSurface;
    063    import org.deegree.model.spatialschema.Point;
    064    import org.deegree.model.spatialschema.Position;
    065    import org.deegree.model.spatialschema.Ring;
    066    import org.deegree.model.spatialschema.Surface;
    067    import org.deegree.model.spatialschema.SurfaceInterpolationImpl;
    068    import org.deegree.model.spatialschema.SurfacePatch;
    069
    070    import com.vividsolutions.jts.algorithm.CGAlgorithms;
    071
    072    /**
    073     *
    074     *
    075     * @author <a href="mailto:poth@lat-lon.de">Andreas Poth</a>
    076     * @author last edited by: $Author: poth $
    077     *
    078     * @version $Revision: 6251 $, $Date: 2007-03-19 16:59:28 +0100 (Mo, 19 Mrz 2007) $
    079     */
    080    public class GeometryUtils {
    081
    082        private static final ILogger LOG = getLogger( GeometryUtils.class );
    083
    084        /**
    085         *
    086         * @param p1
    087         * @param p2
    088         * @return distance between two 2D positions
    089         */
    090        public static double distance( Position p1, Position p2 ) {
    091            return distance( p1.getX(), p1.getY(), p2.getX(), p2.getY() );
    092        }
    093
    094        /**
    095         *
    096         * @param xx
    097         * @param yy
    098         * @param xx_
    099         * @param yy_
    100         * @return distance between two points
    101         */
    102        public static double distance( double xx, double yy, double xx_, double yy_ ) {
    103            double dx = xx - xx_;
    104            double dy = yy - yy_;
    105            return Math.sqrt( dx * dx + dy * dy );
    106        }
    107
    108        /**
    109         * @param <T>
    110         * @param geom
    111         * @param x
    112         * @param y
    113         * @return moves 2D geometries only (will discard any z values
    114         */
    115        @SuppressWarnings("unchecked")
    116        public static <T> T move( T geom, double x, double y ) {
    117            final Mapper<Position, Position> mover = getMover( x, y );
    118            if ( geom instanceof Envelope ) {
    119                Envelope e = (Envelope) geom;
    120                // dammit, where's the proper typecase?
    121                return (T) createEnvelope( move( e.getMin(), x, y ), move( e.getMax(), x, y ), e.getCoordinateSystem() );
    122            }
    123            if ( geom instanceof Point ) {
    124                Point p = (Point) geom;
    125                return (T) createPoint( p.getX() + x, p.getY() + y, p.getCoordinateSystem() );
    126            }
    127            if ( geom instanceof Curve ) {
    128                Curve c = (Curve) geom;
    129                try {
    130                    return (T) createCurve( map( c.getCurveSegments(), GeometryUtils.<CurveSegment> getMover( x, y ) ),
    131                                            c.getCoordinateSystem() );
    132                } catch ( GeometryException e ) {
    133                    LOG.logError( "Unknown error", e );
    134                    return null;
    135                }
    136            }
    137            if ( geom instanceof CurveSegment ) {
    138                CurveSegment c = (CurveSegment) geom;
    139                try {
    140                    return (T) createCurveSegment( map( c.getPositions(), mover ), c.getCoordinateSystem() );
    141                } catch ( GeometryException e ) {
    142                    LOG.logError( "Unknown error", e );
    143                    return null;
    144                }
    145            }
    146            if ( geom instanceof Position ) {
    147                Position p = (Position) geom;
    148                return (T) createPosition( p.getX() + x, p.getY() + y );
    149            }
    150            if ( geom instanceof Surface ) {
    151                Surface s = (Surface) geom;
    152                SurfacePatch[] patches = new SurfacePatch[s.getNumberOfSurfacePatches()];
    153                for ( int i = 0; i < patches.length; ++i ) {
    154                    try {
    155                        patches[i] = move( s.getSurfacePatchAt( 0 ), x, y );
    156                    } catch ( GeometryException e ) {
    157                        LOG.logError( "Unknown error", e );
    158                        return null;
    159                    }
    160                }
    161                try {
    162                    return (T) createSurface( patches, s.getCoordinateSystem() );
    163                } catch ( GeometryException e ) {
    164                    LOG.logError( "Unknown error", e );
    165                    return null;
    166                }
    167            }
    168            if ( geom instanceof SurfacePatch ) {
    169                SurfacePatch p = (SurfacePatch) geom;
    170                Position[] ring = p.getExteriorRing();
    171                Position[] outer = map( ring, mover ).toArray( new Position[ring.length] );
    172                Position[][] inners = p.getInteriorRings();
    173                if ( inners != null ) {
    174                    for ( int i = 0; i < inners.length; ++i ) {
    175                        inners[i] = map( inners[i], mover ).toArray( new Position[inners[i].length] );
    176                    }
    177                }
    178                try {
    179                    return (T) createSurfacePatch( outer, inners, p.getInterpolation(), p.getCoordinateSystem() );
    180                } catch ( GeometryException e ) {
    181                    LOG.logError( "Unknown error", e );
    182                    return null;
    183                }
    184            }
    185            if ( geom instanceof Aggregate ) {
    186                Aggregate m = (Aggregate) geom;
    187                for ( int i = 0; i < m.getSize(); ++i ) {
    188                    try {
    189                        m.setObjectAt( move( m.getObjectAt( i ), x, y ), i );
    190                    } catch ( GeometryException e ) {
    191                        LOG.logError( "Unknown error", e );
    192                        return null;
    193                    }
    194                }
    195                return (T) m;
    196            }
    197
    198            throw new UnsupportedOperationException( "Moving geometries of class " + geom.getClass() + " is not supported." );
    199        }
    200
    201        /**
    202         * @param <T>
    203         * @param x
    204         * @param y
    205         * @return a move mapper wrapper
    206         */
    207        public static <T> Mapper<T, T> getMover( final double x, final double y ) {
    208            return new Mapper<T, T>() {
    209                public T apply( T u ) {
    210                    return move( u, x, y );
    211                }
    212            };
    213        }
    214
    215        /**
    216         *
    217         * @param surface
    218         * @return surface with inverted order of vertices
    219         * @throws GeometryException
    220         */
    221        public static Surface invertOrder( Surface surface )
    222                                throws GeometryException {
    223            Position[] exring = surface.getSurfaceBoundary().getExteriorRing().getPositions();
    224            // invert exterior ring vertices order
    225            for ( int i = 0; i < exring.length / 2; i++ ) {
    226                Position p = exring[i];
    227                exring[i] = exring[exring.length - 1 - i];
    228                exring[exring.length - 1 - i] = p;
    229            }
    230            Ring[] inner = surface.getSurfaceBoundary().getInteriorRings();
    231            Position[][] inPos = new Position[inner.length][];
    232            // invert interior ring vertices order
    233            for ( int i = 0; i < inner.length; i++ ) {
    234                Position[] tmp = inner[i].getPositions();
    235                for ( int j = 0; j < tmp.length; j++ ) {
    236                    Position p = tmp[j];
    237                    tmp[j] = tmp[tmp.length - 1 - j];
    238                    tmp[tmp.length - 1 - j] = p;
    239                }
    240                inPos[i] = tmp;
    241            }
    242            return GeometryFactory.createSurface( exring, inPos, new SurfaceInterpolationImpl(),
    243                                                  surface.getCoordinateSystem() );
    244        }
    245
    246        /**
    247         *
    248         * @param curve
    249         * @return curve with inverted order of vertices for each segment
    250         * @throws GeometryException
    251         */
    252        public static Curve invertOrder( Curve curve )
    253                                throws GeometryException {
    254            CurveSegment[] segments = curve.getCurveSegments();
    255            for ( int i = 0; i < segments.length; i++ ) {
    256                Position[] tmp = segments[i].getPositions();
    257                for ( int j = 0; j < tmp.length; j++ ) {
    258                    Position p = tmp[j];
    259                    tmp[j] = tmp[tmp.length - 1 - j];
    260                    tmp[tmp.length - 1 - j] = p;
    261                }
    262                segments[i] = GeometryFactory.createCurveSegment( tmp, curve.getCoordinateSystem() );
    263            }
    264            return GeometryFactory.createCurve( segments );
    265        }
    266
    267        /**
    268         *
    269         * @param surface
    270         * @return true if an array of passed {@link Position} forms a clockwise orientated ring
    271         */
    272        public static boolean isClockwise( Surface surface ) {
    273            Position[] ring = surface.getSurfaceBoundary().getExteriorRing().getPositions();
    274            return !CGAlgorithms.isCCW( JTSAdapter.export( ring ).getCoordinates() );
    275        }
    276
    277        /**
    278         *
    279         * @param geom
    280         * @return surface or multi surface with guaranteed clockwise vertices orientation
    281         * @throws GeometryException
    282         */
    283        public static Geometry ensureClockwise( Geometry geom )
    284                                throws GeometryException {
    285            if ( geom instanceof Surface ) {
    286                if ( !isClockwise( (Surface) geom ) ) {
    287                    geom = invertOrder( (Surface) geom );
    288                }
    289            } else if ( geom instanceof MultiSurface ) {
    290                Surface[] surfaces = ( (MultiSurface) geom ).getAllSurfaces();
    291                for ( int i = 0; i < surfaces.length; i++ ) {
    292                    surfaces[i] = invertOrder( surfaces[i] );
    293                }
    294                geom = GeometryFactory.createMultiSurface( surfaces );
    295            }
    296            return geom;
    297        }
    298
    299        /**
    300         *
    301         * @param distance
    302         *            if distance is < 0 left parallel will be created
    303         * @param curve
    304         * @return parallel curve with distance.
    305         * @throws GeometryException
    306         */
    307        // TODO
    308        // remove arte facts occuring if distance between at least two vertices is less passed distance
    309        public static Curve createCurveParallel( double distance, Curve curve )
    310                                throws GeometryException {
    311            Position[] pos = curve.getAsLineString().getPositions();
    312
    313            List<Position[]> posList = new ArrayList<Position[]>( pos.length );
    314            // create parallel for each segment
    315            for ( int j = 0; j < pos.length - 1; j++ ) {
    316                // calculate normal vector
    317                // swap x and y and change sign
    318                double nx = -( pos[j].getY() - pos[j + 1].getY() );
    319                double ny = pos[j].getX() - pos[j + 1].getX();
    320                double nl = Math.sqrt( nx * nx + ny * ny );
    321                nx = nx / nl * distance;
    322                ny = ny / nl * distance;
    323                Position[] p = new Position[2];
    324                p[0] = GeometryFactory.createPosition( pos[j].getX() + nx, pos[j].getY() + ny );
    325                p[1] = GeometryFactory.createPosition( pos[j + 1].getX() + nx, pos[j + 1].getY() + ny );
    326                posList.add( p );
    327            }
    328            List<Position> pList = new ArrayList<Position>( pos.length );
    329            // first point
    330            pList.add( posList.get( 0 )[0] );
    331            for ( int j = 0; j < posList.size() - 1; j++ ) {
    332                // find intersection point between j'th and j+1'th segment
    333                Position is = intersection( posList.get( j )[0], posList.get( j )[1], posList.get( j + 1 )[0],
    334                                            posList.get( j + 1 )[1] );
    335                if ( is != null ) {
    336                    // is == null if to segments are parallel or part of the same line
    337                    pList.add( is );
    338                }
    339            }
    340            // last point
    341            pList.add( posList.get( posList.size() - 1 )[1] );
    342            curve = GeometryFactory.createCurve( pList.toArray( new Position[pList.size()] ), curve.getCoordinateSystem() );
    343            return curve;
    344        }
    345
    346        /**
    347         *
    348         * @param startPoint1
    349         * @param endPoint1
    350         * @param startPoint2
    351         * @param endPoint2
    352         * @return intersection coordinates between to lines (not line segments!!!). This means the intersection point may
    353         *         not lies between passed start- and end-points
    354         */
    355        public static Position intersection( Position startPoint1, Position endPoint1, Position startPoint2,
    356                                             Position endPoint2 ) {
    357            double m1 = ( endPoint1.getY() - startPoint1.getY() ) / ( endPoint1.getX() - startPoint1.getX() );
    358            double m2 = ( endPoint2.getY() - startPoint2.getY() ) / ( endPoint2.getX() - startPoint2.getX() );
    359
    360            // lines are parallels
    361            if ( m1 == m2 ) {
    362                return null;
    363            }
    364
    365            double t1 = -( m1 * startPoint1.getX() - startPoint1.getY() );
    366            double t2 = -( m2 * startPoint2.getX() - startPoint2.getY() );
    367            double x = ( t2 - t1 ) / ( m1 - m2 );
    368            double y = m1 * x + t1;
    369            return GeometryFactory.createPosition( x, y );
    370        }
    371
    372        /**
    373         *
    374         * @param a1
    375         *            the first point
    376         * @param a2
    377         *            the second point
    378         * @param l
    379         *            the length of the segment starting from the second point
    380         * @param alpha
    381         *            the angle that the a1-a2 segment makes the following segment
    382         * @return the point found at length l from a2 and which (connected with a2) forms an angle of alfa to a1a2.
    383         */
    384        public static Point vectorByAngle( Point a1, Point a2, double l, double alpha ) {
    385            double beta = Math.atan2( a1.getY() - a2.getY(), a1.getX() - a2.getX() );
    386
    387            double absoluteAngle;
    388            if ( alpha >= 0 ) {
    389                absoluteAngle = beta + alpha;
    390            } else {
    391                absoluteAngle = beta - alpha;
    392            }
    393
    394            return GeometryFactory.createPoint( a2.getX() + l * Math.cos( absoluteAngle ), a2.getY() + l
    395                                                                                           * Math.sin( absoluteAngle ),
    396                                                a1.getCoordinateSystem() );
    397        }
    398
    399    }