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 }