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