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 }