001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/branches/2.2_testing/src/org/deegree/model/spatialschema/LinearContains.java $
002 /*---------------- FILE HEADER ------------------------------------------
003
004 This file is part of deegree.
005 Copyright (C) 2001-2008 by:
006 EXSE, Department of Geography, University of Bonn
007 http://www.giub.uni-bonn.de/deegree/
008 lat/lon GmbH
009 http://www.lat-lon.de
010
011 This library is free software; you can redistribute it and/or
012 modify it under the terms of the GNU Lesser General Public
013 License as published by the Free Software Foundation; either
014 version 2.1 of the License, or (at your option) any later version.
015
016 This library is distributed in the hope that it will be useful,
017 but WITHOUT ANY WARRANTY; without even the implied warranty of
018 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
019 Lesser General Public License for more details.
020
021 You should have received a copy of the GNU Lesser General Public
022 License along with this library; if not, write to the Free Software
023 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
024
025 Contact:
026
027 Andreas Poth
028 lat/lon GmbH
029 Aennchenstr. 19
030 53177 Bonn
031 Germany
032 E-Mail: poth@lat-lon.de
033
034 Prof. Dr. Klaus Greve
035 Department of Geography
036 University of Bonn
037 Meckenheimer Allee 166
038 53115 Bonn
039 Germany
040 E-Mail: greve@giub.uni-bonn.de
041
042
043 ---------------------------------------------------------------------------*/
044 package org.deegree.model.spatialschema;
045
046 import java.util.ArrayList;
047
048 /**
049 *
050 *
051 *
052 * @version $Revision: 9343 $
053 * @author <a href="mailto:poth@lat-lon.de">Andreas Poth</a>
054 * @author last edited by: $Author: apoth $
055 *
056 * @version 1.0. $Revision: 9343 $, $Date: 2007-12-27 14:30:32 +0100 (Do, 27 Dez 2007) $
057 *
058 * @since 2.0
059 */
060 class LinearContains {
061
062 /**
063 *
064 * @param geom1
065 * @param geom2
066 * @return maximum tolerance of geom1 and geom2
067 */
068 public static double getTolerance( Geometry geom1, Geometry geom2 ) {
069 double d = geom1.getTolerance();
070 if ( geom2.getTolerance() > d ) {
071 d = geom2.getTolerance();
072 }
073 return d;
074 }
075
076 /**
077 * the operations returns true if two the submitted points contains
078 */
079 public static boolean contains( Position point1, Position point2 ) {
080 throw new UnsupportedOperationException( "contains(Position, Position)" + " not supported at the moment." );
081 }
082
083 /**
084 * the operations returns 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 returns true if the two submitted curves segments contains
121 */
122 public static boolean contains( CurveSegment curve1, CurveSegment curve2 ) {
123 throw new UnsupportedOperationException( "contains(CurveSegment, CurveSegment)"
124 + " not supported at the moment." );
125 }
126
127 /**
128 * the operation returns true if the submitted curve segment contains the submitted surface
129 * patch
130 *
131 * @param surface
132 * @param curve
133 * @param tolerance
134 */
135 public static boolean contains( SurfacePatch surface, CurveSegment curve, double tolerance ) {
136 boolean con = true;
137 Position[] ex = surface.getExteriorRing();
138 Position[] cu = curve.getPositions();
139
140 for ( int i = 0; i < cu.length; i++ ) {
141 if ( !contains( ex, cu[i], tolerance ) ) {
142 con = false;
143 break;
144 }
145 }
146
147 if ( con ) {
148 Position[][] inner = surface.getInteriorRings();
149
150 if ( inner != null ) {
151 for ( int i = 0; i < inner.length; i++ ) {
152 for ( int j = 0; j < cu.length; j++ ) {
153 if ( contains( inner[i], cu[j], tolerance ) ) {
154 con = false;
155 break;
156 }
157 }
158
159 if ( !con ) {
160 break;
161 }
162 }
163 }
164 }
165
166 return con;
167 }
168
169 /**
170 * the operation returns true if the first surface patches contains the second one
171 *
172 * @param surface1
173 * @param surface2
174 * @param tolerance
175 * @return true if the first surface patches contains
176 */
177 public static boolean contains( SurfacePatch surface1, SurfacePatch surface2, double tolerance ) {
178 boolean con = true;
179 Position[] ex = surface1.getExteriorRing();
180 Position[] ex_ = surface2.getExteriorRing();
181
182 for ( int i = 0; i < ex_.length; i++ ) {
183 if ( !contains( ex, ex_[i], tolerance ) ) {
184 con = false;
185 break;
186 }
187 }
188
189 if ( con ) {
190 Position[][] inner = surface1.getInteriorRings();
191 Position[][] inner_ = surface2.getInteriorRings();
192
193 if ( inner != null ) {
194 for ( int i = 0; i < inner.length; i++ ) {
195 // a point of the second exterior is not allowed to be
196 // within a inner ring of the first
197 for ( int j = 0; j < ex_.length; j++ ) {
198 if ( contains( inner[i], ex_[j], tolerance ) ) {
199 con = false;
200 break;
201 }
202 }
203
204 if ( !con ) {
205 break;
206 }
207
208 // a point of the inner rings of the second is not allowed
209 // to be within a inner ring of the first
210 if ( inner_ != null ) {
211 for ( int k = 0; k < inner_.length; k++ ) {
212 for ( int j = 0; j < inner_[k].length; j++ ) {
213 if ( contains( inner[i], inner_[k][j], tolerance ) ) {
214 con = false;
215 break;
216 }
217 }
218
219 if ( !con ) {
220 break;
221 }
222 }
223 }
224
225 // a point of the inner rings of the first is not allowed
226 // to be within the second surface
227 for ( int j = 0; j < inner[i].length; j++ ) {
228 if ( contains( surface2, inner[i][j], tolerance ) ) {
229 con = false;
230 break;
231 }
232 }
233
234 if ( !con ) {
235 break;
236 }
237 }
238 }
239 }
240
241 // surface2 is not allowed to contain one point of surface1
242 if ( con ) {
243 for ( int i = 0; i < ex.length; i++ ) {
244 if ( contains( surface2, ex[i], tolerance ) ) {
245 con = false;
246 break;
247 }
248 }
249 }
250
251 return con;
252 }
253
254 /**
255 * the operations returns true if two the passed points contains
256 *
257 * @param point1
258 * @param point2
259 * @return true if two the passed points contains
260 */
261 public static boolean contains( Point point1, Point point2 ) {
262 return point1.equals( point2 );
263 }
264
265 /**
266 * the operations returns true if the submitted point contains the submitted curve
267 */
268 public static boolean contains( Curve curve, Point point ) {
269 throw new UnsupportedOperationException( "contains(Curve, Point)" + " not supported at the moment." );
270 }
271
272 /**
273 * the operation returns true if the submitted point contains the submitted surface
274 */
275 public static boolean contains( Surface surface, Point point )
276 throws Exception {
277 boolean contain = false;
278 int cnt = surface.getNumberOfSurfacePatches();
279
280 double tolerance = getTolerance( surface, point );
281 for ( int i = 0; i < cnt; i++ ) {
282 if ( contains( surface.getSurfacePatchAt( i ), point.getPosition(), tolerance ) ) {
283 contain = true;
284 break;
285 }
286 }
287
288 return contain;
289 }
290
291 /**
292 * the operation returns true if the two submitted curves contains
293 */
294 public static boolean contains( Curve curve1, Curve curve2 ) {
295 throw new UnsupportedOperationException( "contains(Curve, Curve)" + " not supported at the moment." );
296 }
297
298 /**
299 * Convenience method to extract all <tt>Position</tt>s from a <tt>Curve</tt>.
300 */
301 private static Position[] getPositions( Curve curve )
302 throws GeometryException {
303 ArrayList<Position> positions = new ArrayList<Position>( 1000 );
304
305 for ( int i = 0; i < curve.getNumberOfCurveSegments(); i++ ) {
306 CurveSegment segment = curve.getCurveSegmentAt( i );
307 Position[] segmentPos = segment.getPositions();
308
309 for ( int j = 0; j < segmentPos.length; j++ )
310 positions.add( segmentPos[j] );
311 }
312
313 return positions.toArray( new Position[positions.size()] );
314 }
315
316 /**
317 * the operation returns true if the submitted curve contains the submitted surface
318 */
319 public static boolean contains( Surface surface, Curve curve )
320 throws GeometryException {
321 // gather the positions of the crings (exterior and interior) and
322 // the curve as arrays of Positions
323 SurfaceBoundary boundary = (SurfaceBoundary) surface.getBoundary();
324 Ring extRing = boundary.getExteriorRing();
325 Ring[] intRings = boundary.getInteriorRings();
326
327 Position[] curvePos = getPositions( curve );
328 Position[] extRingPos = extRing.getPositions();
329 Position[][] intRingsPos = new Position[intRings.length][];
330
331 for ( int i = 0; i < intRings.length; i++ )
332 intRingsPos[i] = intRings[i].getPositions();
333
334 // necessary condition: all points of the curve have to be inside
335 // of the surface's exterior ring and none must be inside of one
336 // of the interior rings
337 for ( int i = 0; i < curvePos.length; i++ ) {
338 if ( !contains( extRingPos, curvePos[i], getTolerance( surface, curve ) ) ) {
339 return false;
340 }
341
342 for ( int j = 0; j < intRings.length; j++ ) {
343 if ( contains( intRingsPos[j], curvePos[i], getTolerance( surface, curve ) ) ) {
344 return false;
345 }
346 }
347 }
348
349 return true;
350 }
351
352 /**
353 * the operation returns true if the two submitted surfaces contains
354 */
355 public static boolean contains( Surface surface2, Surface surface1 )
356 throws Exception {
357 double tolerance = getTolerance( surface1, surface2 );
358 return contains( surface2.getSurfacePatchAt( 0 ), surface1.getSurfacePatchAt( 0 ), tolerance );
359 }
360
361 /**
362 * the operation returns true if polygon defined by an array of Position contains the submitted
363 * point.
364 *
365 * @param positions
366 * @param point
367 * @param tolerance
368 */
369 protected static boolean contains( Position[] positions, Position point, double tolerance ) {
370
371 // TODO
372 // consider tolerance value
373
374 if ( positions.length <= 2 ) {
375 return false;
376 }
377
378 int hits = 0;
379
380 double lastx = positions[positions.length - 1].getX();
381 double lasty = positions[positions.length - 1].getY();
382 double curx;
383 double cury;
384
385 // Walk the edges of the polygon
386 for ( int i = 0; i < positions.length; lastx = curx, lasty = cury, i++ ) {
387 curx = positions[i].getX();
388 cury = positions[i].getY();
389
390 if ( cury == lasty ) {
391 continue;
392 }
393
394 double leftx;
395
396 if ( curx < lastx ) {
397 if ( point.getX() >= lastx ) {
398 continue;
399 }
400
401 leftx = curx;
402 } else {
403 if ( point.getX() >= curx ) {
404 continue;
405 }
406
407 leftx = lastx;
408 }
409
410 double test1;
411 double test2;
412
413 if ( cury < lasty ) {
414 if ( ( point.getY() < cury ) || ( point.getY() >= lasty ) ) {
415 continue;
416 }
417
418 if ( point.getX() < leftx ) {
419 hits++;
420 continue;
421 }
422
423 test1 = point.getX() - curx;
424 test2 = point.getY() - cury;
425 } else {
426 if ( ( point.getY() < lasty ) || ( point.getY() >= cury ) ) {
427 continue;
428 }
429
430 if ( point.getX() < leftx ) {
431 hits++;
432 continue;
433 }
434
435 test1 = point.getX() - lastx;
436 test2 = point.getY() - lasty;
437 }
438
439 if ( test1 < ( test2 / ( lasty - cury ) * ( lastx - curx ) ) ) {
440 hits++;
441 }
442 }
443
444 return ( ( hits & 1 ) != 0 );
445 }
446 }