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 }