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