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 }