001: //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/trunk/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 04:32:12 -0800 (Thu, 27 Dec 2007) $
072: */
073: public class LabelOptimizer extends AbstractOptimizer {
074:
075: private static final ILogger LOG = LoggerFactory
076: .getLogger(LabelOptimizer.class);
077:
078: // contains the LabelDisplayElements that are to be optimized
079: private ArrayList<DisplayElement> displayElements = new ArrayList<DisplayElement>(
080: 1000);
081:
082: // contains the LabelChoices
083: private ArrayList<LabelChoice> choices = new ArrayList<LabelChoice>(
084: 1000);
085:
086: // collision matrix of LabelChoices that may collide
087: private boolean[][] candidates;
088:
089: /**
090: * Creates a new instance of LabelOptimizer.
091: */
092: public LabelOptimizer() {
093: }
094:
095: /**
096: * Creates a new instance of LabelOptimizer for the given <tt>Themes</tt>.
097: *
098: * @param themes
099: */
100: public LabelOptimizer(Theme[] themes) {
101:
102: // collect all LabelDisplayElements from all Themes
103: for (int i = 0; i < themes.length; i++) {
104: addTheme(themes[i]);
105: }
106: }
107:
108: /**
109: * Adds a <tt>Theme</tt> that the <tt>Optimizer</tt> should consider.
110: *
111: * @param theme
112: */
113: public void addTheme(Theme theme) {
114: if (!themes.contains(theme)) {
115: List<DisplayElement> themeElements = theme
116: .getDisplayElements();
117: for (int i = 0; i < themeElements.size(); i++) {
118: Object o = themeElements.get(i);
119: if (o instanceof LabelDisplayElement) {
120: LabelDisplayElement element = (LabelDisplayElement) o;
121: TextSymbolizer symbolizer = (TextSymbolizer) element
122: .getSymbolizer();
123: // only add element if "auto" is set
124: if (symbolizer.getLabelPlacement() != null) {
125: if (symbolizer.getLabelPlacement()
126: .getPointPlacement() != null
127: && symbolizer.getLabelPlacement()
128: .getPointPlacement().isAuto()) {
129: displayElements
130: .add((LabelDisplayElement) o);
131: // } else if (symbolizer.getLabelPlacement().getLinePlacement() != null)
132: // {
133: // displayElements.add (o);
134: }
135: }
136: }
137: }
138: themes.add(theme);
139: }
140: }
141:
142: /**
143: * Finds optimized <tt>Label</tt> representations for the registered
144: * <tt>LabelDisplayElement</tt>s.
145: * <p>
146: *
147: * @param g
148: */
149: public void optimize(Graphics2D g) throws Exception {
150:
151: choices.clear();
152: double scale = mapView.getScale(g);
153: GeoTransform projection = mapView.getProjection();
154:
155: // used to signal the LabelDisplayElement that it should
156: // not create Labels itself (in any case)
157: Label[] dummyLabels = new Label[0];
158:
159: // collect LabelChoices for all LabelDisplayElements
160: for (int i = 0; i < displayElements.size(); i++) {
161: LabelDisplayElement element = (LabelDisplayElement) displayElements
162: .get(i);
163: if (!element.doesScaleConstraintApply(scale))
164: continue;
165:
166: element.setLabels(dummyLabels);
167: ((ScaledFeature) element.getFeature())
168: .setScale(scale / 0.00028);
169: choices.addAll(LabelChoiceFactory.createLabelChoices(
170: element, g, projection));
171: }
172:
173: buildCollisionMatrix();
174:
175: // do the magic
176: try {
177: anneal();
178: } catch (Exception e) {
179: e.printStackTrace();
180: }
181:
182: // sets the optimized labels to the LabelDisplayElements, so
183: // they are considered when the DisplayElements are painted the next
184: // time
185:
186: for (int i = 0; i < choices.size(); i++) {
187: LabelChoice choice = choices.get(i);
188: choice.getElement().addLabel(choice.getSelectedLabel());
189: }
190: }
191:
192: /**
193: * Builds the collision matrix for all <tt>LabelChoice</tt>s.
194: */
195: private void buildCollisionMatrix() {
196: long now = System.currentTimeMillis();
197: candidates = new boolean[choices.size()][choices.size()];
198: for (int i = 0; i < choices.size(); i++) {
199: LabelChoice choice1 = choices.get(i);
200: for (int j = i + 1; j < choices.size(); j++) {
201: LabelChoice choice2 = choices.get(j);
202: if (choice1.intersects(choice2)) {
203: candidates[i][j] = true;
204: }
205: }
206: }
207: LOG.logDebug("Building of collision matrix took: "
208: + (System.currentTimeMillis() - now) + " millis.");
209: }
210:
211: /**
212: * Performs the "Simulated Annealing" for the <tt>LabelChoices</tt>.
213: */
214: private void anneal() {
215: double currentValue = objectiveFunction();
216:
217: double temperature = 1.0;
218: int counter = 0;
219: int successCounter = 0;
220: int failCounter = 0;
221:
222: int n = choices.size();
223:
224: LOG.logDebug("Starting Annealing with value: " + currentValue);
225: long now = System.currentTimeMillis();
226: while (counter <= 2500 && currentValue > (n + 0.8 * 40)) {
227:
228: counter++;
229: if (successCounter % 5 == 0) {
230: temperature *= 0.9;
231: }
232:
233: // choose one Label from one LabelChoice randomly
234: int choiceIndex = (int) (Math.random() * (n - 1) + 0.5);
235: LabelChoice choice = choices.get(choiceIndex);
236: int oldPos = choice.getSelected();
237: choice.selectLabelRandomly();
238:
239: double value = objectiveFunction();
240:
241: // does the new placement imply an improvement?
242: if (value < currentValue) {
243: // yes -> keep it
244: currentValue = value;
245: successCounter++;
246: failCounter = 0;
247: } else {
248: // no -> only keep it with a certain probability
249: if (Math.random() < temperature) {
250: currentValue = value;
251: failCounter = 0;
252: } else {
253: // change it back to the old placement
254: choice.setSelected(oldPos);
255: failCounter++;
256: }
257: }
258: }
259: LOG.logDebug("Final value: " + currentValue);
260: LOG.logDebug("Annealing took: "
261: + (System.currentTimeMillis() - now) + " millis.");
262: }
263:
264: /**
265: * Calculates a quality value for the currently selected combination of <tt>Label</tt>s.
266: * <p>
267: *
268: * @return
269: */
270: private double objectiveFunction() {
271: float value = 0.0f;
272:
273: for (int i = 0; i < choices.size(); i++) {
274: LabelChoice choice1 = choices.get(i);
275: Label label1 = choice1.getSelectedLabel();
276: value += choice1.getQuality() + 1.0f;
277:
278: for (int j = i + 1; j < choices.size(); j++) {
279: if (candidates[i][j]) {
280: LabelChoice choice2 = choices.get(j);
281: Label label2 = choice2.getSelectedLabel();
282: if (label1.intersects(label2)) {
283: value += 40.0f;
284: }
285: }
286: }
287: }
288: return value;
289: }
290: }
|