001    //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_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    }