001 //$HeadURL: svn+ssh://rbezema@svn.wald.intevation.org/deegree/base/branches/2.2_testing/src/org/deegree/graphics/displayelements/CurveWalker.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.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: apoth $
055 *
056 * @version $Revision: 9340 $, $Date: 2007-12-27 13:32:12 +0100 (Do, 27 Dez 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, boolean polygon ) {
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 && polygon ) || i < count ) {
107 double x = i == count ? pos[0][0] : pos[0][i];
108 double y = i == count ? pos[1][0] : 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 ) || isInROI( boxEndX, boxEndY )
135 || 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 * ( y1 - y0 ) - d * d )
194 / ( u * u + 1 );
195 double minX = p1[0];
196 double maxX = p2[0];
197 double minY = p1[1];
198 double maxY = p2[1];
199 if ( minX > maxX ) {
200 minX = p2[0];
201 maxX = p1[0];
202 }
203 if ( minY > maxY ) {
204 minY = p2[1];
205 maxY = p1[1];
206 }
207
208 if ( x1 < x2 ) {
209 // to the right
210 x = -p / 2 + Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
211 } else {
212 // to the left
213 x = -p / 2 - Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
214 }
215
216 // if ((int) (x + 0.5) <= minX || (int) (x + 0.5) >= maxX) {
217 // x = -p / 2 + Math.sqrt ((p / 2) * (p / 2) - q);
218 // }
219 y = ( x - x1 ) * u + y1;
220 } else {
221 // vertical line segment
222 x = x1;
223 double minY = p1[1];
224 double maxY = p2[1];
225
226 if ( minY > maxY ) {
227 minY = p2[1];
228 maxY = p1[1];
229 }
230
231 double p = -2 * y0;
232 double q = y0 * y0 + ( x1 - x0 ) * ( x1 - x0 ) - d * d;
233
234 if ( y1 > y2 ) {
235 // down
236 y = -p / 2 - Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
237 } else {
238 // up
239 y = -p / 2 + Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
240 }
241
242 // y = -p / 2 - Math.sqrt ((p / 2) * (p / 2) - q);
243 // if ((int) (y + 0.5) <= minY || (int) (y + 0.5) >= maxY) {
244 // y = -p / 2 + Math.sqrt ((p / 2) * (p / 2) - q);
245 // }
246 }
247 return new double[] { x, y };
248 }
249
250 /**
251 * Returns the slope of the line that is constructed by two given points.
252 *
253 * @param x1
254 * x coordinate of point 1
255 * @param y1
256 * y coordinate of point 1
257 * @param x2
258 * x coordinate of point 2
259 * @param y2
260 * y coordinate of point 2
261 * @return the slope of the line (in degrees)
262 */
263 private double getSlope( double x1, double y1, double x2, double y2 ) {
264 double dx = x2 - x1;
265 double dy = -( y2 - y1 );
266 double rotation = 0.0;
267
268 if ( dx <= 0 ) {
269 // dx = 0. division not possible.
270 if ( dx == 0 ) {
271 dx = 1;
272 }
273 if ( dy <= 0 ) {
274 // left down
275 rotation = -Math.atan( dy / dx );
276 } else {
277 // left up
278 rotation = -Math.atan( dy / dx );
279 }
280 } else {
281 if ( dy <= 0 ) {
282 // right down
283 rotation = -Math.PI - Math.atan( dy / dx );
284 } else {
285 // right up
286 rotation = -Math.PI - Math.atan( dy / dx );
287 }
288 }
289 return Math.toDegrees( rotation );
290 }
291
292 /**
293 * Returns the Euclidean distance between two given points.
294 *
295 * @param x1
296 * x coordinate of point 1
297 * @param y1
298 * y coordinate of point 1
299 * @param x2
300 * x coordinate of point 2
301 * @param y2
302 * y coordinate of point 2
303 * @return the Euclidean distance between (x1,y1) and (x2,y2)
304 */
305 private double getDistance( double x1, double y1, double x2, double y2 ) {
306 double dx = x2 - x1;
307 double dy = y2 - y1;
308 return Math.sqrt( dx * dx + dy * dy );
309 }
310
311 // /**
312 // * Returns the Euclidean distance between two given points.
313 // *
314 // * @param p1
315 // * point 1
316 // * @param p2
317 // * point 2
318 // * @return the Euclidean distance between p1 and p2
319 // */
320 // private double getDistance( double[] p1, double[] p2 ) {
321 // double dx = p1[0] - p2[0];
322 // double dy = p1[1] - p2[1];
323 // return Math.sqrt( dx * dx + dy * dy );
324 // }
325
326 // /**
327 // * Calculates the maximum deviation that points on a linestring have to the ideal line between
328 // * the starting point and the end point.
329 // * <p>
330 // * The ideal line is thought to be running from left to right, the left deviation value
331 // * generally is above the line, the right value is below.
332 // *
333 // * @param start
334 // * starting point of the linestring
335 // * @param end
336 // * end point of the linestring
337 // * @param points
338 // * points in between
339 // * @return the maximum deviation
340 // */
341 // private double[] calcDeviation( double[] start, double[] end, List points ) {
342 //
343 // // extreme deviation to the left
344 // double d1 = 0.0;
345 // // extreme deviation to the right
346 // double d2 = 0.0;
347 // Iterator it = points.iterator();
348 //
349 // // eventually swap start and end point
350 // if ( start[0] > end[0] ) {
351 // double[] tmp = start;
352 // start = end;
353 // end = tmp;
354 // }
355 //
356 // if ( start[0] != end[0] ) {
357 // // label orientation is not completly vertical
358 // if ( start[1] != end[1] ) {
359 // // label orientation is not completly horizontal
360 // while ( it.hasNext() ) {
361 // double[] point = (double[]) it.next();
362 // double u = ( end[1] - start[1] ) / ( end[0] - start[0] );
363 // double x = ( u * u * start[0] - u * ( start[1] - point[1] ) + point[0] )
364 // / ( 1.0 + u * u );
365 // double y = ( x - start[0] ) * u + start[1];
366 // double d = getDistance( point, new double[] { x, y } );
367 // if ( y >= point[1] ) {
368 // // candidate for left extreme value
369 // if ( d > d1 ) {
370 // d1 = d;
371 // }
372 // } else if ( d > d2 ) {
373 // // candidate for right extreme value
374 // d2 = d;
375 // }
376 // }
377 // } else {
378 // // label orientation is completly horizontal
379 // while ( it.hasNext() ) {
380 // double[] point = (double[]) it.next();
381 // double d = point[1] - start[1];
382 // if ( d < 0 ) {
383 // // candidate for left extreme value
384 // if ( -d > d1 ) {
385 // d1 = -d;
386 // }
387 // } else if ( d > d2 ) {
388 // // candidate for left extreme value
389 // d2 = d;
390 // }
391 // }
392 // }
393 // } else {
394 // // label orientation is completely vertical
395 // while ( it.hasNext() ) {
396 // double[] point = (double[]) it.next();
397 // double d = point[0] - start[0];
398 // if ( d < 0 ) {
399 // // candidate for left extreme value
400 // if ( -d > d1 ) {
401 // d1 = -d;
402 // }
403 // } else if ( d > d2 ) {
404 // // candidate for right extreme value
405 // d2 = d;
406 // }
407 // }
408 // }
409 // return new double[] { d1, d2 };
410 // }
411 }