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 }