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