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