001 //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_testing/src/org/deegree/ogcwebservices/wpvs/utils/QuadTreeSplitter.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
037 package org.deegree.ogcwebservices.wpvs.utils;
038
039 import java.awt.Color;
040 import java.awt.Composite;
041 import java.awt.Graphics2D;
042 import java.util.ArrayList;
043 import java.util.Collections;
044 import java.util.Iterator;
045 import java.util.LinkedHashMap;
046 import java.util.List;
047 import java.util.Set;
048 import java.util.TreeSet;
049
050 import javax.vecmath.Vector3d;
051
052 import org.deegree.framework.log.ILogger;
053 import org.deegree.framework.log.LoggerFactory;
054 import org.deegree.model.crs.CoordinateSystem;
055 import org.deegree.model.spatialschema.Envelope;
056 import org.deegree.model.spatialschema.GeometryException;
057 import org.deegree.model.spatialschema.GeometryFactory;
058 import org.deegree.model.spatialschema.Position;
059 import org.deegree.model.spatialschema.Surface;
060 import org.deegree.model.spatialschema.WKTAdapter;
061 import org.deegree.ogcwebservices.wpvs.configuration.WPVSConfiguration;
062 import org.deegree.ogcwebservices.wpvs.configuration.WPVSDeegreeParams;
063
064 /**
065 * <p>
066 * The <code>QuadTreeSplitter</code> class can be used to create x-y axis alligned request quads from a qiven List of
067 * {@link ResolutionStripe} s. These Stripes depend on the ViewFrustrum and it's projection on the x-y plane (the so
068 * called footprint). To create an approximation of this footprint a Quadtree (a geometric spatial structure, which
069 * recursively divides a boundingbox into four containing boundingboxes) is built. The leafs of this tree are merged
070 * according to their resolution and size to create the requeststripes.
071 * </p>
072 *
073 * @author <a href="mailto:bezema@lat-lon.de">Rutger Bezema</a>
074 *
075 * @author last edited by: $Author: aschmitz $
076 *
077 * @version $Revision: 23585 $, $Date: 2010-04-13 14:07:18 +0200 (Di, 13 Apr 2010) $
078 *
079 */
080
081 public class QuadTreeSplitter {
082
083 private static final ILogger LOG = LoggerFactory.getLogger( QuadTreeSplitter.class );
084
085 private QuadNode rootNode;
086
087 private TreeSet<ResolutionStripe> resolutionStripes;
088
089 private double minimalTerrainHeight;
090
091 private double minimalResolution;
092
093 private CoordinateSystem crs;
094
095 private boolean highQuality;
096
097 private double scale;
098
099 // private double imageWidth;
100
101 /**
102 * Creates a new Quadtree, from the given resolutionstripes. The resulting tree can be used to generate
103 * requeststripes which are (x-y) axis aligned.
104 * <p>
105 * The Quality argument is used for the recursive termination criteria, if it is set to true the requeststripes will
106 * accurately approximate the footprint (=projection of the viewfrustrum onto the ground) and the resolutions given
107 * in the resolutionstripes this results in a lot of requests which can slow down the wpvs. If set to false the
108 * footprint and the given resolutions will be approximated poorly but only a few requeststripes are created,
109 * resulting in a faster wpvs.
110 * </p>
111 *
112 * @param resolutionStripes
113 * the different resolutionstripes.
114 * @param imageWidth
115 * the width of the target image, necessary for calculating the width resolution of the requeststripe.
116 * @param highQuality
117 * true if accurate (but many) requeststripes should be generated, false if none accurate (but only a
118 * few) requests should be generated.
119 */
120 public QuadTreeSplitter( ArrayList<ResolutionStripe> resolutionStripes, double imageWidth, boolean highQuality ) {
121 if ( resolutionStripes == null || resolutionStripes.size() <= 0 ) {
122 return;
123 }
124 this.resolutionStripes = new TreeSet<ResolutionStripe>( resolutionStripes );
125 // this.imageWidth = imageWidth;
126 this.crs = resolutionStripes.get( 0 ).getCRSName();
127 this.scale = resolutionStripes.get( 0 ).getScale();
128 this.minimalTerrainHeight = resolutionStripes.get( 0 ).getMinimalTerrainHeight();
129 this.highQuality = highQuality;
130 // For the merge, the check is newmin < existing_min therefore -> min large and max small
131 // Position minPos = GeometryFactory.createPosition( 0, 0, 0 );
132 // Position maxPos = GeometryFactory.createPosition( 0, 0, 0 );
133 Envelope bbox = resolutionStripes.get( 0 ).getSurface().getEnvelope();
134 minimalResolution = Double.MAX_VALUE;
135 double maxResolution = Double.MIN_VALUE;
136
137 // find the highest and loweset maxResolution (which are needed for termination decissions and
138 // find create the axis-alligned bbox of the resolutionstripes which will be the rootnode.
139 for ( int i = 0; i < resolutionStripes.size(); ++i ) {
140 try {
141 bbox = bbox.merge( resolutionStripes.get( i ).getSurface().getEnvelope() );
142 // minimalResolution is the smallest number
143 minimalResolution = Math.min( minimalResolution, resolutionStripes.get( i ).getMinResolution() );
144 maxResolution = Math.max( maxResolution, resolutionStripes.get( i ).getMaxResolution() );
145 } catch ( GeometryException e ) {
146 e.printStackTrace();
147 System.out.println( e.getLocalizedMessage() );
148 }
149 }
150 LOG.logDebug( "Found minimalResolution: " + minimalResolution );
151 LOG.logDebug( "Found maximumResolution: " + maxResolution );
152 try {
153 if ( Math.abs( minimalResolution ) < 0.00001 ) { // almost null
154 minimalResolution = Math.pow( maxResolution, 1.0 / resolutionStripes.size() );
155 LOG.logDebug( "Recalculated minimalResolution (< 0.00001) ) to: " + minimalResolution );
156 }
157 Position min = bbox.getMin();
158
159 double zValue = min.getZ();
160 if ( Double.isNaN( min.getZ() ) ) {
161 zValue = minimalTerrainHeight;
162 }
163
164 Vector3d leftPoint = new Vector3d( min.getX(), min.getY(), zValue );
165 Vector3d rightPoint = new Vector3d( min.getX() + ( bbox.getWidth() ), min.getY() + ( bbox.getHeight() ),
166 zValue );
167 Vector3d ul = new Vector3d( leftPoint.x, rightPoint.y, zValue );
168 double quadResolution = StripeFactory.calcScaleOfVector( leftPoint, rightPoint, imageWidth );
169 double quadResolution2 = StripeFactory.calcScaleOfVector( leftPoint, ul, imageWidth );
170 if ( quadResolution < quadResolution2 ) {
171 quadResolution = quadResolution2;
172 }
173
174 LOG.logDebug( "The root node of the quadtree has a max resolution of: " + maxResolution
175 + " and a min Resolution of: " + minimalResolution );
176
177 rootNode = new QuadNode( GeometryFactory.createSurface( bbox, crs ), maxResolution, minimalResolution );
178
179 createTree( rootNode, quadResolution );
180
181 } catch ( GeometryException e ) {
182 LOG.logError( e.getLocalizedMessage(), e );
183 }
184 }
185
186 /**
187 * After instantiating a Quadtree, this method can be called to build the (x-y) axis-alligned request stripes.
188 *
189 * @param extraRequestPercentage
190 * a percentage to be added to the resulting stripes ( a value between [0,1] ), which might correct gapes
191 * between stripes.{@link WPVSDeegreeParams#getExtendRequestPercentage()}
192 * @param quadMergeCount
193 * the number of leaves this splitter can have, before it starts merging leaves together
194 * {@link WPVSDeegreeParams#getQuadMergeCount() }
195 * @return the (x-y) axis-alligned request squares best fitted the given resolutionstripes.
196 */
197 public ArrayList<ResolutionStripe> getRequestQuads( double extraRequestPercentage, int quadMergeCount ) {
198
199 ArrayList<ResolutionStripe> resultList = new ArrayList<ResolutionStripe>();
200 if ( rootNode != null ) {
201 LinkedHashMap<Double, ArrayList<QuadNode>> lhm = new LinkedHashMap<Double, ArrayList<QuadNode>>( 100 );
202 outputNodes( rootNode, lhm );
203 Set<Double> keys = lhm.keySet();
204 int nrOfStripes = 0;
205 for ( Double resolution : keys ) {
206 if ( lhm.containsKey( resolution ) ) {
207 List<QuadNode> originalNodes = lhm.get( resolution );
208 nrOfStripes += originalNodes.size();
209 }
210 }
211
212 if ( LOG.getLevel() == ILogger.LOG_DEBUG ) {
213 if ( nrOfStripes < quadMergeCount ) {
214 LOG.logDebug( "Not merging leaves because there are less leaves: " + nrOfStripes
215 + " then configured quadMergeCount:" + quadMergeCount );
216 }
217 try {
218 StringBuilder sb = new StringBuilder();
219 outputNodes( rootNode, sb );
220 LOG.logDebug( "tree-leaves:\n" + sb.toString() );
221 } catch ( GeometryException e ) {
222 // TODO Auto-generated catch block
223 e.printStackTrace();
224 }
225 }
226 retrieveStripes( resultList, lhm, extraRequestPercentage, ( nrOfStripes > quadMergeCount ) );
227 }
228 return resultList;
229 }
230
231 private void retrieveStripes( List<ResolutionStripe> resultList, LinkedHashMap<Double, ArrayList<QuadNode>> lhm,
232 double extraRequestPercentage, boolean mergeAndSort ) {
233 Set<Double> keys = lhm.keySet();
234 for ( Double resolution : keys ) {
235 if ( lhm.containsKey( resolution ) ) {
236 List<QuadNode> originalNodes = lhm.get( resolution );
237 List<QuadNode> result = new ArrayList<QuadNode>( originalNodes.size() );
238 if ( mergeAndSort ) {
239 // sorted to x values first.
240 LOG.logDebug( "Sorting x order" );
241 List<QuadNode> resultX = mergeAndSort( originalNodes );
242
243 // Check if sorting to y results in better values;
244 for ( QuadNode node : originalNodes ) {
245 node.compareY();
246 }
247 LOG.logDebug( "Sorting y order" );
248 List<QuadNode> resultY = mergeAndSort( originalNodes );
249
250 // Find the optimal sorting order (lesser quads) and check if the perpendicular
251 // order results in lesser requeststripes (it usually does)
252 if ( resultX.size() < resultY.size() ) {
253 for ( QuadNode node : resultX ) {
254 node.compareY();
255 }
256 LOG.logDebug( "res-Sorting x order" );
257 result = mergeAndSort( resultX );
258 } else {
259 for ( QuadNode node : resultY ) {
260 node.compareX();
261 }
262 LOG.logDebug( "res-Sorting y order" );
263 result = mergeAndSort( resultY );
264 }
265 } else {
266 result.addAll( originalNodes );
267 }
268 for ( QuadNode quad : result ) {
269 Envelope env = quad.getBBox().getEnvelope();
270 Position envMin = env.getMin();
271 Position envMax = env.getMax();
272
273 double width = env.getWidth();
274 double height = env.getHeight();
275
276 // enlarge the envelope to extraRequestPercentage to correct gapes between stripes.
277 double extraWidth = width * extraRequestPercentage;
278 double extraHeight = height * extraRequestPercentage;
279
280 Position newMin = GeometryFactory.createPosition( envMin.getX() - extraWidth, envMin.getY()
281 - extraHeight,
282 envMin.getZ() );
283
284 Position newMax = GeometryFactory.createPosition( envMax.getX() + extraWidth, envMax.getY()
285 + extraHeight,
286 envMax.getZ() );
287
288 double minResolution = quad.getMinResolution();
289 double maxResolution = quad.getMaxResolution();
290
291 if ( minResolution > maxResolution ) {
292 double tmp = minResolution;
293 minResolution = maxResolution;
294 maxResolution = tmp;
295 }
296
297 try {
298 Surface resultSurface = GeometryFactory.createSurface(
299 GeometryFactory.createEnvelope( newMin,
300 newMax,
301 this.crs ),
302 this.crs );
303 ResolutionStripe rs = new ResolutionStripe( resultSurface, maxResolution, minResolution,
304 minimalTerrainHeight, scale );
305 resultList.add( rs );
306
307 } catch ( GeometryException e ) {
308 LOG.logError( e.getLocalizedMessage(), e );
309 }
310 }
311 }
312 }
313 }
314
315 /**
316 * A little helper function which first sorts the given list of quadnodes according to their sorting order and
317 * afterwards merges all stripes which are adjacent and have the same resolution.
318 *
319 * @param toBeMerged
320 * the list of Quadnodes which must be sorted and merged.
321 * @return a list containing the merged quadnodes of the given list.
322 */
323 private List<QuadNode> mergeAndSort( List<QuadNode> toBeMerged ) {
324 Collections.sort( toBeMerged );
325 List<QuadNode> resultList = new ArrayList<QuadNode>( toBeMerged );
326 boolean needsResort = true;
327 while ( needsResort ) {
328 needsResort = false;
329 List<QuadNode> tmpResults = new ArrayList<QuadNode>( resultList );
330 Iterator<QuadNode> it = tmpResults.iterator();
331 QuadNode first = null;
332 QuadNode second = null;
333 resultList.clear();
334 // Iterate over the quadnodes.
335 while ( second != null || it.hasNext() ) {
336 // this is neccessary if the first could not be merged with the next, we don't want to lose the
337 // iterators reference, therefore the first quad references the second which was actually the it.next()
338 if ( second == null ) {
339 first = it.next();
340 } else {
341 first = second;
342 second = null;
343 }
344 Envelope requestEnvelope = first.getBBox().getEnvelope();
345 int nrOfMerges = 0;
346 double curMinResolution = first.getMinResolution();
347 double curMaxResolution = first.getMaxResolution();
348 while ( it.hasNext() && second == null ) {
349 second = it.next();
350 // if the first and the second quad cannot be merged, the second will become the first, if they can
351 // merge, they will be merged together and the iterator moves on, this means, we have to go over all
352 // quads again after this round, for else we might not find all possible merges.
353 if ( first.canMerge( second ) ) {
354 try {
355 Envelope tmpEnvelope = requestEnvelope;
356 requestEnvelope = requestEnvelope.merge( second.getBBox().getEnvelope() );
357 // curMinResolution = first.getMinResolution() / ( nrOfMerges + 2 );
358 // curMaxResolution = first.getMaxResolution() / ( nrOfMerges + 2 );
359 int rH = (int) Math.round( requestEnvelope.getHeight() / Math.abs( curMinResolution ) );
360 int rW = (int) Math.round( requestEnvelope.getWidth() / Math.abs( curMinResolution ) );
361 if ( rH < WPVSConfiguration.MAX_REQUEST_SIZE && rW < WPVSConfiguration.MAX_REQUEST_SIZE ) {
362 LOG.logDebug( "Merging quads:\n"
363 + WKTAdapter.export( GeometryFactory.createSurface( tmpEnvelope, crs ) ).toString()
364 + "\n" + WKTAdapter.export( second.getBBox() ).toString() );
365 // double tmpScale = WPVSConfiguration.MAX_REQUEST_SIZE / (double)((rH > rW )?rW:rH);
366 // curMaxResolution *=tmpScale;
367 // curMinResolution *=tmpScale;
368
369 second = null;
370 needsResort = true;
371 nrOfMerges++;
372 } else {
373 requestEnvelope = tmpEnvelope;
374 LOG.logDebug( "Cannot merge two quads, because their merged sizes( rw: "
375 + rW
376 + ", rH: "
377 + rH
378 + " would be bigger as the maximum retrievable size:\n"
379 + WKTAdapter.export( GeometryFactory.createSurface( requestEnvelope, crs ) ).toString()
380 + "\n" + WKTAdapter.export( second.getBBox() ).toString() );
381
382 }
383 } catch ( GeometryException ge ) {
384 // An error occured, it might be best to not merge these envelopes.
385 LOG.logError( ge.getLocalizedMessage(), ge );
386 }
387 }
388
389 }
390 if ( nrOfMerges > 0 ) {
391 try {
392 Surface resultSurface = GeometryFactory.createSurface( requestEnvelope, crs );
393 resultList.add( new QuadNode( resultSurface,
394 // first.getMaxResolution(),
395 // first.getMinResolution(),
396 curMaxResolution, curMinResolution, first.isComparingX() ) );
397 } catch ( GeometryException ge ) {
398 // An error occured, it might be best not to merge these envelopes.
399 LOG.logError( ge.getLocalizedMessage(), ge );
400 }
401 } else {
402 resultList.add( first );
403 }
404 }
405 }
406 return resultList;
407 }
408
409 /**
410 * This Method actually builds the tree. The decission of a split is made by evaluating the minimal maxResolution of
411 * the intersecting ResultionStripe.
412 *
413 * @param father
414 * the Father node which will be splittet into four axis aligned sons
415 * @param quadResolution
416 * the maxResolution of a width axis of the axis-aligned bbox
417 * @throws GeometryException
418 * if the Envelope cannot be created
419 */
420 private void createTree( QuadNode father, double quadResolution )
421 throws GeometryException {
422 LOG.logDebug( WKTAdapter.export( father.getBBox() ).toString() );
423 LOG.logDebug( father.toString() );
424 LOG.logDebug( "Fatherresolution: " + quadResolution );
425 Position min = father.getBBox().getEnvelope().getMin();
426 double widthHalf = 0.5 * father.getBBox().getEnvelope().getWidth();
427 double heightHalf = 0.5 * father.getBBox().getEnvelope().getHeight();
428 double lowerLeftX = min.getX();
429 double lowerLeftY = min.getY();
430 double sonsResolution = 0.5 * quadResolution;
431 // recursion is not necessary if the resolution is smaller then the minimalResolution.
432 if ( sonsResolution < minimalResolution ) {
433 LOG.logDebug( "The currentresolution (" + sonsResolution + ") is smaller then the minimalResolution("
434 + minimalResolution + ")" );
435 return;
436 }
437
438 checkSon( father, sonsResolution, QuadNode.LOWER_LEFT_SON, lowerLeftX, lowerLeftY, lowerLeftX + widthHalf,
439 lowerLeftY + heightHalf );
440
441 // lowerright
442 checkSon( father, sonsResolution, QuadNode.LOWER_RIGHT_SON, lowerLeftX + widthHalf, lowerLeftY,
443 lowerLeftX + ( 2 * widthHalf ), lowerLeftY + heightHalf );
444
445 // upperleft
446 checkSon( father, sonsResolution, QuadNode.UPPER_LEFT_SON, lowerLeftX, lowerLeftY + heightHalf, lowerLeftX
447 + widthHalf,
448 lowerLeftY + ( 2 * heightHalf ) );
449
450 // upperright
451 checkSon( father, sonsResolution, QuadNode.UPPER_RIGHT_SON, lowerLeftX + widthHalf, lowerLeftY + heightHalf,
452 lowerLeftX + 2 * widthHalf, lowerLeftY + 2 * heightHalf );
453 }
454
455 /**
456 * Decides if the father quad has to be subdivided into it's sons.
457 *
458 * @param father
459 * the Father quad to divide
460 * @param quadResolution
461 * the maxResolution of the fathers son (half the maxResolution of the father)
462 * @param SON_ID
463 * the son to check
464 * @param lowerLeftX
465 * minx of the bbox of the fathers son
466 * @param lowerLeftY
467 * miny of the bbox of the fathers son
468 * @param upperRightX
469 * maxx of the bbox of the fathers son
470 * @param upperRightY
471 * maxY of the bbox of the fathers son
472 * @throws GeometryException
473 * if no surface can be created
474 */
475 private void checkSon( QuadNode father, double quadResolution, final int SON_ID, double lowerLeftX,
476 double lowerLeftY, double upperRightX, double upperRightY )
477 throws GeometryException {
478 Position min = GeometryFactory.createPosition( lowerLeftX, lowerLeftY, minimalTerrainHeight );
479 /*
480 * father.getBBox() .getEnvelope() .getMin() .getZ() );
481 */
482 Position max = GeometryFactory.createPosition( upperRightX, upperRightY, minimalTerrainHeight );
483 /*
484 * father.getBBox() .getEnvelope() .getMax() .getZ());
485 */
486 Surface bbox = GeometryFactory.createSurface( GeometryFactory.createEnvelope( min, max, crs ), crs );
487
488 ResolutionStripe intersectedStripe = ( highQuality ) ? getIntersectionForQualityConfiguration( bbox )
489 : getIntersectionForFastConfiguration( bbox );
490
491 if ( intersectedStripe != null ) { // found an intersecting resolutionStripe
492 LOG.logDebug( "Following quad( 1 ) Found intersecting stripe(2):\n" + WKTAdapter.export( bbox ) + "\n"
493 + WKTAdapter.export( intersectedStripe.getSurface() ) );
494 QuadNode son = new QuadNode( bbox, intersectedStripe.getMaxResolution(),
495 intersectedStripe.getMinResolution() );
496 double intersectResolution = ( highQuality ) ? intersectedStripe.getMinResolution()
497 : intersectedStripe.getMaxResolution();
498 LOG.logDebug( "sonsResolution: " + intersectResolution + " currentResolution of quad: " + quadResolution );
499 father.addSon( SON_ID, son );
500 int rH = (int) Math.round( bbox.getEnvelope().getHeight() / Math.abs( intersectedStripe.getMinResolution() ) );
501 int rW = (int) Math.round( bbox.getEnvelope().getWidth() / Math.abs( intersectedStripe.getMinResolution() ) );
502 /* ( rH < WPVSConfiguration.MAX_REQUEST_SIZE && rW < WPVSConfiguration.MAX_REQUEST_SIZE ) || */
503 if ( ( rH > WPVSConfiguration.MAX_REQUEST_SIZE || rW > WPVSConfiguration.MAX_REQUEST_SIZE )
504 || quadResolution >= ( intersectResolution * 0.95 ) ) {
505 createTree( son, quadResolution );
506 }
507 } else {
508 LOG.logDebug( "Following quad found no intersections :\n" + WKTAdapter.export( bbox ) );
509 }
510 }
511
512 /**
513 * Finds the resolutionstripe with the lowest minResolution which intersects with the given bbox. Resulting in a lot
514 * of different requests.
515 *
516 * @param bbox
517 * the BoundingBox of the Envelope to check.
518 * @return the resolutionStripe which intersects the bbox.
519 */
520 private ResolutionStripe getIntersectionForQualityConfiguration( Surface bbox ) {
521 LOG.logDebug( "Trying to find intersection with Quality, e.g. min( of all intersecting minResolutions )" );
522 ResolutionStripe resultStripe = null;
523 for ( ResolutionStripe stripe : resolutionStripes ) {
524 if ( bbox.intersects( stripe.getSurface() ) ) {
525 if ( resultStripe != null ) {
526 if ( ( stripe.getMinResolution() < resultStripe.getMinResolution() ) ) {
527 resultStripe = stripe;
528 }
529 } else {
530 resultStripe = stripe;
531 }
532 }
533 }
534 return resultStripe;
535 }
536
537 /**
538 * Finds the resolutionstripe with the highest maxResolution which intersects with the given bbox. Resulting in only
539 * a few different requests.
540 *
541 * @param bbox
542 * the BoundingBox of the Envelope to check.
543 * @return the resolutionStripe which intersects the bbox.
544 */
545 private ResolutionStripe getIntersectionForFastConfiguration( Surface bbox ) {
546 LOG.logDebug( "Trying to find intersection with Speed, e.g. max( of all intersecting maxResolutions )" );
547 ResolutionStripe resultStripe = null;
548 for ( ResolutionStripe stripe : resolutionStripes ) {
549 if ( bbox.intersects( stripe.getSurface() ) ) {
550 if ( resultStripe != null ) {
551 if ( ( stripe.getMaxResolution() < resultStripe.getMaxResolution() ) ) {
552 resultStripe = stripe;
553 }
554 } else {
555 resultStripe = stripe;
556 }
557 }
558 }
559 return resultStripe;
560 }
561
562 /**
563 * Outputs the tree
564 *
565 * @param g2d
566 * if the quadtree should be drawn.
567 */
568 public void outputTree( Graphics2D g2d ) {
569 if ( rootNode != null ) {
570 if ( g2d != null ) {
571 System.out.println( "number Of leaves-> " + outputNodes( rootNode, g2d ) );
572 } else {
573 outputNodes( rootNode, "" );
574 }
575 }
576 }
577
578 private int outputNodes( QuadNode father, Graphics2D g2d ) {
579 if ( father.isLeaf() ) {
580 drawSquare( father, g2d, Color.BLACK );
581 return 1;
582 }
583 QuadNode[] nodes = father.getSons();
584 int result = 0;
585 for ( QuadNode node : nodes ) {
586 if ( node != null ) {
587 result += outputNodes( node, g2d );
588 }
589
590 }
591 return result;
592 }
593
594 private void outputNodes( QuadNode father, String indent ) {
595 if ( father.isLeaf() ) {
596 System.out.println( indent + "(father)" + father.getBBox() );
597 } else {
598 QuadNode[] nodes = father.getSons();
599 for ( QuadNode node : nodes ) {
600 if ( node != null ) {
601 indent += "-";
602 outputNodes( node, indent );
603 }
604 }
605 }
606 }
607
608 private void outputNodes( QuadNode father, StringBuilder sb )
609 throws GeometryException {
610 if ( father.isLeaf() ) {
611 sb.append( WKTAdapter.export( father.getBBox() ).toString() ).append( "\n" );
612 } else {
613 QuadNode[] nodes = father.getSons();
614 for ( QuadNode node : nodes ) {
615 if ( node != null ) {
616 outputNodes( node, sb );
617 }
618 }
619 }
620 }
621
622 /**
623 * Find the leaf nodes and add them according to their maxResolution in a LinkedHashMap.
624 *
625 * @param father
626 * the node to check
627 * @param outputMap
628 * the map to output to.
629 */
630 private void outputNodes( QuadNode father, LinkedHashMap<Double, ArrayList<QuadNode>> outputMap ) {
631 if ( father.isLeaf() ) {
632 Double key = new Double( father.getMinResolution() );
633 ArrayList<QuadNode> ts = outputMap.get( key );
634 if ( ts == null ) { // I know, but I don't put null values so it's ok
635 ts = new ArrayList<QuadNode>();
636 outputMap.put( key, ts );
637 }
638 if ( ts.add( father ) == false ) {
639 System.out.println( "quadnode allready in set" );
640 }
641 } else {
642 QuadNode[] nodes = father.getSons();
643 for ( QuadNode node : nodes ) {
644 if ( node != null ) {
645 outputNodes( node, outputMap );
646 }
647 }
648 }
649 }
650
651 private void drawSquare( QuadNode node, Graphics2D g2d, Color c ) {
652 if ( g2d != null ) {
653 g2d.setColor( c );
654 Envelope env = node.getBBox().getEnvelope();
655 Position min = env.getMin();
656 int height = (int) env.getHeight();
657 int width = (int) env.getWidth();
658 g2d.drawRect( (int) min.getX(), (int) min.getY(), width, height );
659 Composite co = g2d.getComposite();
660 g2d.setColor( new Color( c.getRed(), c.getGreen(), c.getBlue(), 64 ) );
661 g2d.fillRect( (int) min.getX(), (int) min.getY(), width, height );
662 g2d.setComposite( co );
663 }
664 }
665
666 /**
667 *
668 * The <code>QuadNode</code> class is the bean for every node of the quadtree. It contains a axis-aligned BBox and
669 * the maxResolution of its associated resolutionStripe. It can have upto four sons.
670 *
671 * @author <a href="mailto:bezema@lat-lon.de">Rutger Bezema</a>
672 *
673 * @author last edited by: $Author: aschmitz $
674 *
675 * @version $Revision: 23585 $, $Date: 2010-04-13 14:07:18 +0200 (Di, 13 Apr 2010) $
676 *
677 */
678 private class QuadNode implements Comparable<QuadNode> {
679
680 private QuadNode[] sons;
681
682 private Surface bbox;
683
684 private double maxResolution;
685
686 private double minResolution;
687
688 private double comparePosition;
689
690 private double compareLength;
691
692 private boolean comparingX;
693
694 /**
695 * The Denoting lower left son
696 */
697 static final int LOWER_LEFT_SON = 0;
698
699 /**
700 * The Denoting lower right son
701 */
702 static final int LOWER_RIGHT_SON = 1;
703
704 /**
705 * The Denoting upper left son
706 */
707 static final int UPPER_LEFT_SON = 2;
708
709 /**
710 * The Denoting upper right son
711 */
712 static final int UPPER_RIGHT_SON = 3;
713
714 /**
715 *
716 * @param bbox
717 * @param maxResolution
718 * @param minResolution
719 */
720 QuadNode( Surface bbox, double maxResolution, double minResolution ) {
721 this.bbox = bbox;
722 sons = new QuadNode[4];
723 this.maxResolution = maxResolution;
724 this.minResolution = minResolution;
725 comparePosition = bbox.getEnvelope().getMin().getX();
726 compareLength = bbox.getEnvelope().getWidth();
727 comparingX = true;
728 }
729
730 /**
731 *
732 * @param bbox
733 * @param maxResolution
734 * @param minResolution
735 * @param compareDirection
736 */
737 QuadNode( Surface bbox, double maxResolution, double minResolution, boolean compareDirection ) {
738 this( bbox, maxResolution, minResolution );
739 if ( compareDirection )
740 compareX();
741 else
742 compareY();
743 }
744
745 /**
746 * Add a son to this node.
747 *
748 * @param sonID
749 * which son
750 * @param son
751 * the reference
752 */
753 void addSon( final int sonID, QuadNode son ) {
754 if ( sonID == LOWER_LEFT_SON || sonID == LOWER_RIGHT_SON || sonID == UPPER_LEFT_SON
755 || sonID == UPPER_RIGHT_SON ) {
756 this.sons[sonID] = son;
757 }
758 }
759
760 /**
761 * @return bbox of node
762 */
763 Surface getBBox() {
764 return bbox;
765 }
766
767 /**
768 * set the node to compare along the x axis
769 */
770 void compareX() {
771 comparePosition = bbox.getEnvelope().getMin().getX();
772 compareLength = bbox.getEnvelope().getWidth();
773 comparingX = true;
774 }
775
776 /**
777 * set the node to compare along the y axis
778 */
779 void compareY() {
780 comparePosition = bbox.getEnvelope().getMin().getY();
781 compareLength = bbox.getEnvelope().getHeight();
782 comparingX = false;
783 }
784
785 /**
786 * If this Quadnode has no sons it is called a leaf.
787 *
788 * @return true if no sons, false otherwhise.
789 */
790 boolean isLeaf() {
791 return ( sons[0] == null && sons[1] == null && sons[2] == null && sons[3] == null );
792 }
793
794 /**
795 * @return the sons or null if no sons are set.
796 */
797 QuadNode[] getSons() {
798 return sons;
799 }
800
801 /**
802 * @param sonID
803 * @return the son or null if no son could be mapped to the sonid.
804 */
805 QuadNode getSon( final int sonID ) {
806 if ( sonID != LOWER_LEFT_SON || sonID != LOWER_RIGHT_SON || sonID != UPPER_LEFT_SON
807 || sonID != UPPER_RIGHT_SON )
808 return null;
809 return sons[sonID];
810 }
811
812 /**
813 * @return The max maxResolution of the Stripe.
814 */
815 double getMaxResolution() {
816 return maxResolution;
817 }
818
819 /**
820 * @return the minResolution value.
821 */
822 double getMinResolution() {
823 return minResolution;
824 }
825
826 /**
827 * @return true if the comparing will be along the x axis.
828 */
829 boolean isComparingX() {
830 return comparingX;
831 }
832
833 /**
834 * @return true if the comparing will be along the y axis.
835 */
836 double getComparePosition() {
837 return comparePosition;
838 }
839
840 /**
841 * @return true if the length will be compared
842 */
843 double getCompareLength() {
844 return compareLength;
845 }
846
847 /*
848 * Attention, the equal result "0" is not really a check for the equality of two Quadnodes, it just reflex, that
849 * two QuadNodes have the same sorting properties -> the position - (y or x) and the length in this direction
850 * are equal. It is very plausible that they have totally different positions and length in the other (not
851 * checked) direction.
852 *
853 * @see java.lang.Comparable#compareTo(T)
854 */
855 public int compareTo( QuadNode other ) {
856 double otherPosition = other.getComparePosition();
857 if ( Math.abs( comparePosition - otherPosition ) < 0.00001 ) {
858 double otherLength = other.getCompareLength();
859 if ( Math.abs( compareLength - otherLength ) < 0.00001 ) {
860 if ( comparingX ) {
861 double thisMinY = this.bbox.getEnvelope().getMin().getY();
862 double otherMinY = other.getBBox().getEnvelope().getMin().getY();
863 if ( ( Math.abs( thisMinY - otherMinY ) < 0.00001 ) )
864 return 0;
865 if ( thisMinY < otherMinY )
866 return 1;
867 return -1;
868 }
869 double thisMinX = this.bbox.getEnvelope().getMin().getX();
870 double otherMinX = other.getBBox().getEnvelope().getMin().getX();
871 if ( ( Math.abs( thisMinX - otherMinX ) < 0.00001 ) )
872 return 0;
873 if ( thisMinX < otherMinX )
874 return 1;
875 return -1;
876 }
877 if ( compareLength < otherLength ) {
878 return -1;
879 }
880 return 1;
881 }
882 if ( comparePosition < otherPosition )
883 return -1;
884 return 1;
885 }
886
887 /**
888 * simple check if two quadnodes can be merged, according to their positions, length and if they are adjacent.
889 *
890 * @param other
891 * @return true if this QuadNode can be merged with the Other.
892 */
893 boolean canMerge( QuadNode other ) {
894 double otherPosition = other.getComparePosition();
895 if ( Math.abs( comparePosition - otherPosition ) < 0.01 ) {
896 double otherLength = other.compareLength;
897 if ( Math.abs( compareLength - otherLength ) < 0.01 ) {
898 // the origins and the length are mergable, now check if the Quadnodes are
899 // adjacent
900 if ( comparingX ) {
901 double thisMaxY = this.bbox.getEnvelope().getMax().getY();
902 double thisMinY = this.bbox.getEnvelope().getMin().getY();
903 double otherMinY = other.getBBox().getEnvelope().getMin().getY();
904 double otherMaxY = other.getBBox().getEnvelope().getMax().getY();
905 return ( ( Math.abs( thisMaxY - otherMinY ) < 0.00001 ) || ( Math.abs( thisMinY - otherMaxY ) < 0.00001 ) );
906 }
907 // comparing Y
908 double thisMaxX = this.bbox.getEnvelope().getMax().getX();
909 double thisMinX = this.bbox.getEnvelope().getMin().getX();
910 double otherMinX = other.getBBox().getEnvelope().getMin().getX();
911 double otherMaxX = other.getBBox().getEnvelope().getMax().getX();
912 return ( Math.abs( thisMaxX - otherMinX ) < 0.00001 )
913 || ( Math.abs( thisMinX - otherMaxX ) < 0.00001 );
914
915 }
916 }
917 return false;
918 }
919
920 @Override
921 public String toString() {
922 return "QuadNode sorted in Direction: " + ( ( comparingX ) ? "x" : "y" ) + " comparePosition: "
923 + comparePosition + " compareLength: " + compareLength;
924 }
925
926 }
927 }