    001    //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.4_testing/src/org/deegree/graphics/optimizers/LabelOptimizer.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    package org.deegree.graphics.optimizers;
    037
    038    import java.awt.Graphics2D;
    039    import java.util.ArrayList;
    040    import java.util.List;
    041
    042    import org.deegree.framework.log.ILogger;
    043    import org.deegree.framework.log.LoggerFactory;
    044    import org.deegree.graphics.Theme;
    045    import org.deegree.graphics.displayelements.DisplayElement;
    046    import org.deegree.graphics.displayelements.Label;
    047    import org.deegree.graphics.displayelements.LabelDisplayElement;
    048    import org.deegree.graphics.displayelements.ScaledFeature;
    049    import org.deegree.graphics.sld.TextSymbolizer;
    050    import org.deegree.graphics.transformation.GeoTransform;
    051
    052    /**
    053     * Selects the optimal <code>Label</code>s (graphical representations generated from
    054     * <code>LabelDisplayElements</code>) with respect to the amount of overlapping.
    055     * <p>
    056     * The labeling and optimization approach uses ideas from papers by Ingo Petzold on automated label placement.
    057     * <p>
    058     * TODO: The handling of rotated labels is currently broken. Don't use rotated <code>LabelDisplayElement</code>s with
    059     * this optimizer at the moment!
    060     *
    061     * @author <a href="mailto:mschneider@lat-lon.de">Markus Schneider</a>
    062     * @author last edited by: $Author: mschneider $
    063     *
    064     * @version $Revision: 18195 $, $Date: 2009-06-18 17:55:39 +0200 (Do, 18. Jun 2009) $
    065     */
    066    public class LabelOptimizer extends AbstractOptimizer {
    067
    068        private static final ILogger LOG = LoggerFactory.getLogger( LabelOptimizer.class );
    069
    070        // contains the LabelDisplayElements that are to be optimized
    071        private ArrayList<DisplayElement> displayElements = new ArrayList<DisplayElement>( 1000 );
    072
    073        // contains the LabelChoices
    074        private ArrayList<LabelChoice> choices = new ArrayList<LabelChoice>( 1000 );
    075
    076        // collision matrix of LabelChoices that may collide
    077        private boolean[][] candidates;
    078
    079        /**
    080         * Creates a new instance of {@link LabelOptimizer} with no associated {@link Theme}s.
    081         */
    082        public LabelOptimizer() {
    083            // nothing to do
    084        }
    085
    086        /**
    087         * Creates a new instance of {@link LabelOptimizer} for the given {@link Theme}s.
    088         *
    089         * @param themes
    090         */
    091        public LabelOptimizer( Theme[] themes ) {
    092
    093            // collect all LabelDisplayElements from all Themes
    094            for ( int i = 0; i < themes.length; i++ ) {
    095                addTheme( themes[i] );
    096            }
    097        }
    098
    099        @Override
    100        public void addTheme( Theme theme ) {
    101            if ( !themes.contains( theme ) ) {
    102                List<DisplayElement> themeElements = theme.getDisplayElements();
    103                for ( int i = 0; i < themeElements.size(); i++ ) {
    104                    Object o = themeElements.get( i );
    105                    if ( o instanceof LabelDisplayElement ) {
    106                        LabelDisplayElement element = (LabelDisplayElement) o;
    107                        TextSymbolizer symbolizer = (TextSymbolizer) element.getSymbolizer();
    108                        // only add element if "auto" is set
    109                        if ( symbolizer.getLabelPlacement() != null ) {
    110                            if ( symbolizer.getLabelPlacement().getPointPlacement() != null
    111                                 && symbolizer.getLabelPlacement().getPointPlacement().isAuto() ) {
    112                                displayElements.add( (LabelDisplayElement) o );
    113                                // } else if (symbolizer.getLabelPlacement().getLinePlacement() != null)
    114                                // {
    115                                // displayElements.add (o);
    116                            }
    117                        }
    118                    }
    119                }
    120                themes.add( theme );
    121            }
    122        }
    123
    124        /**
    125         * Finds optimized {@link Label}s for the registered {@link LabelDisplayElement}s.
    126         *
    127         * @param g
    128         */
    129        public void optimize( Graphics2D g )
    130                                throws Exception {
    131
    132            choices.clear();
    133            double scale = mapView.getScale( g );
    134            GeoTransform projection = mapView.getProjection();
    135
    136            // used to signal the LabelDisplayElement that it should
    137            // not create Labels itself (in any case)
    138            Label[] dummyLabels = new Label[0];
    139
    140            // collect LabelChoices for all LabelDisplayElements
    141            for ( int i = 0; i < displayElements.size(); i++ ) {
    142                LabelDisplayElement element = (LabelDisplayElement) displayElements.get( i );
    143                if ( !element.doesScaleConstraintApply( scale ) )
    144                    continue;
    145
    146                element.setLabels( dummyLabels );
    147                ( (ScaledFeature) element.getFeature() ).setScale( scale / 0.00028 );
    148                choices.addAll( LabelChoiceFactory.createLabelChoices( element, g, projection ) );
    149            }
    150
    151            buildCollisionMatrix();
    152
    153            // do the magic
    154            try {
    155                anneal();
    156            } catch ( Exception e ) {
    157                e.printStackTrace();
    158            }
    159
    160            // sets the optimized labels to the LabelDisplayElements, so
    161            // they are considered when the DisplayElements are painted the next
    162            // time
    163
    164            for ( int i = 0; i < choices.size(); i++ ) {
    165                LabelChoice choice = choices.get( i );
    166                choice.getElement().addLabel( choice.getSelectedLabel() );
    167            }
    168        }
    169
    170        /**
    171         * Builds the collision matrix for all <code>LabelChoice</code>s.
    172         */
    173        private void buildCollisionMatrix() {
    174            long now = System.currentTimeMillis();
    175            candidates = new boolean[choices.size()][choices.size()];
    176            for ( int i = 0; i < choices.size(); i++ ) {
    177                LabelChoice choice1 = choices.get( i );
    178                for ( int j = i + 1; j < choices.size(); j++ ) {
    179                    LabelChoice choice2 = choices.get( j );
    180                    if ( choice1.intersects( choice2 ) ) {
    181                        candidates[i][j] = true;
    182                    }
    183                }
    184            }
    185            LOG.logDebug( "Building of collision matrix took: " + ( System.currentTimeMillis() - now ) + " millis." );
    186        }
    187
    188        /**
    189         * Performs "Simulated Annealing" on the {@link LabelChoice} combination.
    190         */
    191        private void anneal() {
    192            double currentValue = objectiveFunction();
    193
    194            double temperature = 1.0;
    195            int counter = 0;
    196            int successCounter = 0;
    197            int failCounter = 0;
    198
    199            int n = choices.size();
    200
    201            LOG.logDebug( "Starting Annealing with value: " + currentValue );
    202            long now = System.currentTimeMillis();
    203            while ( counter <= 2500 && currentValue > ( n + 0.8 * 40 ) ) {
    204
    205                counter++;
    206                if ( successCounter % 5 == 0 ) {
    207                    temperature *= 0.9;
    208                }
    209
    210                // choose one Label from one LabelChoice randomly
    211                int choiceIndex = (int) ( Math.random() * ( n - 1 ) + 0.5 );
    212                LabelChoice choice = choices.get( choiceIndex );
    213                int oldPos = choice.getSelected();
    214                choice.selectLabelRandomly();
    215
    216                double value = objectiveFunction();
    217
    218                // does the new placement imply an improvement?
    219                if ( value < currentValue ) {
    220                    // yes -> keep it
    221                    currentValue = value;
    222                    successCounter++;
    223                    failCounter = 0;
    224                } else {
    225                    // no -> only keep it with a certain probability
    226                    if ( Math.random() < temperature ) {
    227                        currentValue = value;
    228                        failCounter = 0;
    229                    } else {
    230                        // change it back to the old placement
    231                        choice.setSelected( oldPos );
    232                        failCounter++;
    233                    }
    234                }
    235            }
    236            LOG.logDebug( "Final value: " + currentValue );
    237            LOG.logDebug( "Annealing took: " + ( System.currentTimeMillis() - now ) + " millis." );
    238        }
    239
    240        /**
    241         * Calculates the quality value for the currently selected combination of {@link Label}s.
    242         *
    243         * @return quality of currently selected combination of {@link Label}s
    244         */
    245        private double objectiveFunction() {
    246            float value = 0.0f;
    247
    248            for ( int i = 0; i < choices.size(); i++ ) {
    249                LabelChoice choice1 = choices.get( i );
    250                Label label1 = choice1.getSelectedLabel();
    251                value += choice1.getQuality() + 1.0f;
    252
    253                for ( int j = i + 1; j < choices.size(); j++ ) {
    254                    if ( candidates[i][j] ) {
    255                        LabelChoice choice2 = choices.get( j );
    256                        Label label2 = choice2.getSelectedLabel();
    257                        if ( label1.intersects( label2 ) ) {
    258                            value += 40.0f;
    259                        }
    260                    }
    261                }
    262            }
    263            return value;
    264        }
    265    }