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