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