001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/tags/2.1/src/org/deegree/graphics/displayelements/CurveWalker.java $
002 /*---------------- FILE HEADER ------------------------------------------
003
004 This file is part of deegree.
005 Copyright (C) 2001-2006 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.displayelements;
044
045 import java.awt.Rectangle;
046 import java.util.ArrayList;
047 import java.util.List;
048
049 /**
050 * Walks along a given curve and generates positions on the line string in regular intervals (i.e. a
051 * series of points on the line string with steps of the same distance).
052 *
053 * @author <a href="mailto:mschneider@lat-lon.de>Markus Schneider </a>
054 * @author last edited by: $Author: bezema $
055 *
056 * @version $Revision: 6259 $, $Date: 2007-03-20 10:15:15 +0100 (Di, 20 Mär 2007) $
057 */
058 class CurveWalker {
059
060 private double minX;
061
062 private double minY;
063
064 private double maxX;
065
066 private double maxY;
067
068 /**
069 * Creates a new instance of <code>CurveWalker</code>. The region of interest (where
070 * positions are actually needed, because they are visible) is specified by the given
071 * {@link Rectangle}.
072 *
073 * @param roi
074 * region of interest (visibile area)
075 */
076 CurveWalker( Rectangle roi ) {
077 minX = roi.getMinX();
078 minY = roi.getMinY();
079 maxX = roi.getMaxX();
080 maxY = roi.getMaxY();
081 }
082
083 /**
084 * Determines positions on the given curve where a caption could be drawn. For each of these
085 * positions, three candidates are produced; one on the line, one above of it and one below.
086 *
087 * @param pos
088 * @param width
089 * distance between single positions
090 * @return ArrayList containing positions
091 */
092 ArrayList<double[]> createPositions( int[][] pos, double width ) {
093
094 // walk along the linestring and "collect" possible placement positions
095 int w = (int) width;
096 double lastX = pos[0][0];
097 double lastY = pos[1][0];
098 double count = pos[2][0];
099 double boxStartX = lastX;
100 double boxStartY = lastY;
101
102 ArrayList<double[]> labels = new ArrayList<double[]>( 300 );
103 List<double[]> eCandidates = new ArrayList<double[]>( 300 );
104 int i = 0;
105
106 while ( i < count ) {
107 double x = pos[0][i];
108 double y = pos[1][i];
109
110 // segment found where endpoint of box should be located?
111 if ( getDistance( boxStartX, boxStartY, x, y ) >= w ) {
112
113 double[] p0 = new double[] { boxStartX, boxStartY };
114 double[] p1 = new double[] { lastX, lastY };
115 double[] p2 = new double[] { x, y };
116
117 double[] p = findPointWithDistance( p0, p1, p2, w );
118 x = p[0];
119 y = p[1];
120
121 lastX = x;
122 lastY = y;
123 double boxEndX = x;
124 double boxEndY = y;
125
126 double rotation = getSlope( boxStartX, boxStartY, boxEndX, boxEndY );
127
128 /*
129 * double[] deviation = calcDeviation(new double[] { boxStartX, boxStartY }, new
130 * double[] { boxEndX, boxEndY }, eCandidates);
131 */
132
133 // only add position if it is (at least partly) visible
134 if ( isInROI( boxStartX, boxStartY ) || isInROI( boxStartX, boxEndY )
135 || isInROI( boxEndX, boxEndY ) || isInROI( boxEndX, boxStartY ) ) {
136 labels.add( new double[] { boxStartX, boxStartY, rotation } );
137 }
138
139 boxStartX = lastX;
140 boxStartY = lastY;
141 eCandidates.clear();
142 } else {
143 eCandidates.add( new double[] { x, y } );
144 lastX = x;
145 lastY = y;
146 i++;
147 }
148 }
149 return labels;
150 }
151
152 /**
153 * Returns whether the given point is inside the region of interest.
154 *
155 * @param x
156 * x coordinate of the point
157 * @param y
158 * y coordinate of the point
159 * @return true, if the point is inside the region of interest, false otherwise
160 */
161 private boolean isInROI( double x, double y ) {
162 return x >= minX && x <= maxX && y >= minY && y <= maxY;
163 }
164
165 /**
166 * Finds a point on the line between p1 and p2 that has a certain distance from point p0
167 * (provided that there is such a point).
168 *
169 * @param p0
170 * point that is used as reference point for the distance
171 * @param p1
172 * starting point of the line
173 * @param p2
174 * end point of the line
175 * @param d
176 * distance
177 * @return a point on the line between p1 and p2 with distance d from p0
178 */
179 private static double[] findPointWithDistance( double[] p0, double[] p1, double[] p2, double d ) {
180
181 double x, y;
182 double x0 = p0[0];
183 double y0 = p0[1];
184 double x1 = p1[0];
185 double y1 = p1[1];
186 double x2 = p2[0];
187 double y2 = p2[1];
188
189 if ( x1 != x2 ) {
190 // line segment does not run vertical
191 double u = ( y2 - y1 ) / ( x2 - x1 );
192 double p = -2 * ( x0 + u * u * x1 - u * ( y1 - y0 ) ) / ( u * u + 1 );
193 double q = ( ( y1 - y0 ) * ( y1 - y0 ) + u * u * x1 * x1 + x0 * x0 - 2 * u * x1
194 * ( y1 - y0 ) - d * d )
195 / ( u * u + 1 );
196 double minX = p1[0];
197 double maxX = p2[0];
198 double minY = p1[1];
199 double maxY = p2[1];
200 if ( minX > maxX ) {
201 minX = p2[0];
202 maxX = p1[0];
203 }
204 if ( minY > maxY ) {
205 minY = p2[1];
206 maxY = p1[1];
207 }
208
209 if ( x1 < x2 ) {
210 // to the right
211 x = -p / 2 + Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
212 } else {
213 // to the left
214 x = -p / 2 - Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
215 }
216
217 // if ((int) (x + 0.5) <= minX || (int) (x + 0.5) >= maxX) {
218 // x = -p / 2 + Math.sqrt ((p / 2) * (p / 2) - q);
219 // }
220 y = ( x - x1 ) * u + y1;
221 } else {
222 // vertical line segment
223 x = x1;
224 double minY = p1[1];
225 double maxY = p2[1];
226
227 if ( minY > maxY ) {
228 minY = p2[1];
229 maxY = p1[1];
230 }
231
232 double p = -2 * y0;
233 double q = y0 * y0 + ( x1 - x0 ) * ( x1 - x0 ) - d * d;
234
235 if ( y1 > y2 ) {
236 // down
237 y = -p / 2 - Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
238 } else {
239 // up
240 y = -p / 2 + Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
241 }
242
243 // y = -p / 2 - Math.sqrt ((p / 2) * (p / 2) - q);
244 // if ((int) (y + 0.5) <= minY || (int) (y + 0.5) >= maxY) {
245 // y = -p / 2 + Math.sqrt ((p / 2) * (p / 2) - q);
246 // }
247 }
248 return new double[] { x, y };
249 }
250
251 /**
252 * Returns the slope of the line that is constructed by two given points.
253 *
254 * @param x1
255 * x coordinate of point 1
256 * @param y1
257 * y coordinate of point 1
258 * @param x2
259 * x coordinate of point 2
260 * @param y2
261 * y coordinate of point 2
262 * @return the slope of the line (in degrees)
263 */
264 private double getSlope( double x1, double y1, double x2, double y2 ) {
265 double dx = x2 - x1;
266 double dy = -( y2 - y1 );
267 double rotation = 0.0;
268
269 if ( dx <= 0 ) {
270 // dx = 0. division not possible.
271 if ( dx == 0 ) {
272 dx = 1;
273 }
274 if ( dy <= 0 ) {
275 // left down
276 rotation = -Math.atan( dy / dx );
277 } else {
278 // left up
279 rotation = -Math.atan( dy / dx );
280 }
281 } else {
282 if ( dy <= 0 ) {
283 // right down
284 rotation = -Math.PI - Math.atan( dy / dx );
285 } else {
286 // right up
287 rotation = -Math.PI - Math.atan( dy / dx );
288 }
289 }
290 return Math.toDegrees( rotation );
291 }
292
293 /**
294 * Returns the Euclidean distance between two given points.
295 *
296 * @param x1
297 * x coordinate of point 1
298 * @param y1
299 * y coordinate of point 1
300 * @param x2
301 * x coordinate of point 2
302 * @param y2
303 * y coordinate of point 2
304 * @return the Euclidean distance between (x1,y1) and (x2,y2)
305 */
306 private double getDistance( double x1, double y1, double x2, double y2 ) {
307 double dx = x2 - x1;
308 double dy = y2 - y1;
309 return Math.sqrt( dx * dx + dy * dy );
310 }
311
312 // /**
313 // * Returns the Euclidean distance between two given points.
314 // *
315 // * @param p1
316 // * point 1
317 // * @param p2
318 // * point 2
319 // * @return the Euclidean distance between p1 and p2
320 // */
321 // private double getDistance( double[] p1, double[] p2 ) {
322 // double dx = p1[0] - p2[0];
323 // double dy = p1[1] - p2[1];
324 // return Math.sqrt( dx * dx + dy * dy );
325 // }
326
327 // /**
328 // * Calculates the maximum deviation that points on a linestring have to the ideal line between
329 // * the starting point and the end point.
330 // * <p>
331 // * The ideal line is thought to be running from left to right, the left deviation value
332 // * generally is above the line, the right value is below.
333 // *
334 // * @param start
335 // * starting point of the linestring
336 // * @param end
337 // * end point of the linestring
338 // * @param points
339 // * points in between
340 // * @return the maximum deviation
341 // */
342 // private double[] calcDeviation( double[] start, double[] end, List points ) {
343 //
344 // // extreme deviation to the left
345 // double d1 = 0.0;
346 // // extreme deviation to the right
347 // double d2 = 0.0;
348 // Iterator it = points.iterator();
349 //
350 // // eventually swap start and end point
351 // if ( start[0] > end[0] ) {
352 // double[] tmp = start;
353 // start = end;
354 // end = tmp;
355 // }
356 //
357 // if ( start[0] != end[0] ) {
358 // // label orientation is not completly vertical
359 // if ( start[1] != end[1] ) {
360 // // label orientation is not completly horizontal
361 // while ( it.hasNext() ) {
362 // double[] point = (double[]) it.next();
363 // double u = ( end[1] - start[1] ) / ( end[0] - start[0] );
364 // double x = ( u * u * start[0] - u * ( start[1] - point[1] ) + point[0] )
365 // / ( 1.0 + u * u );
366 // double y = ( x - start[0] ) * u + start[1];
367 // double d = getDistance( point, new double[] { x, y } );
368 // if ( y >= point[1] ) {
369 // // candidate for left extreme value
370 // if ( d > d1 ) {
371 // d1 = d;
372 // }
373 // } else if ( d > d2 ) {
374 // // candidate for right extreme value
375 // d2 = d;
376 // }
377 // }
378 // } else {
379 // // label orientation is completly horizontal
380 // while ( it.hasNext() ) {
381 // double[] point = (double[]) it.next();
382 // double d = point[1] - start[1];
383 // if ( d < 0 ) {
384 // // candidate for left extreme value
385 // if ( -d > d1 ) {
386 // d1 = -d;
387 // }
388 // } else if ( d > d2 ) {
389 // // candidate for left extreme value
390 // d2 = d;
391 // }
392 // }
393 // }
394 // } else {
395 // // label orientation is completely vertical
396 // while ( it.hasNext() ) {
397 // double[] point = (double[]) it.next();
398 // double d = point[0] - start[0];
399 // if ( d < 0 ) {
400 // // candidate for left extreme value
401 // if ( -d > d1 ) {
402 // d1 = -d;
403 // }
404 // } else if ( d > d2 ) {
405 // // candidate for right extreme value
406 // d2 = d;
407 // }
408 // }
409 // }
410 // return new double[] { d1, d2 };
411 // }
412 }
413
414 /***************************************************************************************************
415 * <code>
416 Changes to this class. What the people have been up to:
417
418 $Log$
419 Revision 1.9 2007/02/13 17:01:15 mschneider
420 Fixed problem that positions for partly overlapping boxes were not generated.
421
422 Revision 1.8 2006/07/12 14:46:16 poth
423 comment footer added
424
425 * </code>
426 **************************************************************************************************/