001 //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_testing/src/org/deegree/graphics/displayelements/CurveWalker.java $
002 /*----------------------------------------------------------------------------
003 This file is part of deegree, http://deegree.org/
004 Copyright (C) 2001-2009 by:
005 Department of Geography, University of Bonn
006 and
007 lat/lon GmbH
008
009 This library is free software; you can redistribute it and/or modify it under
010 the terms of the GNU Lesser General Public License as published by the Free
011 Software Foundation; either version 2.1 of the License, or (at your option)
012 any later version.
013 This library is distributed in the hope that it will be useful, but WITHOUT
014 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
015 FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
016 details.
017 You should have received a copy of the GNU Lesser General Public License
018 along with this library; if not, write to the Free Software Foundation, Inc.,
019 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
020
021 Contact information:
022
023 lat/lon GmbH
024 Aennchenstr. 19, 53177 Bonn
025 Germany
026 http://lat-lon.de/
027
028 Department of Geography, University of Bonn
029 Prof. Dr. Klaus Greve
030 Postfach 1147, 53001 Bonn
031 Germany
032 http://www.geographie.uni-bonn.de/deegree/
033
034 e-mail: info@deegree.org
035 ----------------------------------------------------------------------------*/
036 package org.deegree.graphics.displayelements;
037
038 import java.awt.Rectangle;
039 import java.util.ArrayList;
040 import java.util.List;
041
042 /**
043 * Walks along a given curve and generates positions on the line string in regular intervals (i.e. a
044 * series of points on the line string with steps of the same distance).
045 *
046 * @author <a href="mailto:mschneider@lat-lon.de>Markus Schneider </a>
047 * @author last edited by: $Author: mschneider $
048 *
049 * @version $Revision: 18195 $, $Date: 2009-06-18 17:55:39 +0200 (Do, 18 Jun 2009) $
050 */
051 class CurveWalker {
052
053 private double minX;
054
055 private double minY;
056
057 private double maxX;
058
059 private double maxY;
060
061 /**
062 * Creates a new instance of <code>CurveWalker</code>. The region of interest (where
063 * positions are actually needed, because they are visible) is specified by the given
064 * {@link Rectangle}.
065 *
066 * @param roi
067 * region of interest (visibile area)
068 */
069 CurveWalker( Rectangle roi ) {
070 minX = roi.getMinX();
071 minY = roi.getMinY();
072 maxX = roi.getMaxX();
073 maxY = roi.getMaxY();
074 }
075
076 /**
077 * Determines positions on the given curve where a caption could be drawn. For each of these
078 * positions, three candidates are produced; one on the line, one above of it and one below.
079 *
080 * @param pos
081 * @param width
082 * distance between single positions
083 * @param polygon true if the positions denote a polygon
084 * @return ArrayList containing positions
085 */
086 ArrayList<double[]> createPositions( int[][] pos, double width, boolean polygon ) {
087
088 // walk along the linestring and "collect" possible placement positions
089 int w = (int) width;
090 double lastX = pos[0][0];
091 double lastY = pos[1][0];
092 double count = pos[2][0];
093 double boxStartX = lastX;
094 double boxStartY = lastY;
095
096 ArrayList<double[]> labels = new ArrayList<double[]>( 300 );
097 List<double[]> eCandidates = new ArrayList<double[]>( 300 );
098 int i = 0;
099
100 while ( ( i <= count && polygon ) || i < count ) {
101 double x = i == count ? pos[0][0] : pos[0][i];
102 double y = i == count ? pos[1][0] : pos[1][i];
103
104 // segment found where endpoint of box should be located?
105 if ( getDistance( boxStartX, boxStartY, x, y ) >= w ) {
106
107 double[] p0 = new double[] { boxStartX, boxStartY };
108 double[] p1 = new double[] { lastX, lastY };
109 double[] p2 = new double[] { x, y };
110
111 double[] p = findPointWithDistance( p0, p1, p2, w );
112 x = p[0];
113 y = p[1];
114
115 lastX = x;
116 lastY = y;
117 double boxEndX = x;
118 double boxEndY = y;
119
120 double rotation = getSlope( boxStartX, boxStartY, boxEndX, boxEndY );
121
122 /*
123 * double[] deviation = calcDeviation(new double[] { boxStartX, boxStartY }, new
124 * double[] { boxEndX, boxEndY }, eCandidates);
125 */
126
127 // only add position if it is (at least partly) visible
128 if ( isInROI( boxStartX, boxStartY ) || isInROI( boxStartX, boxEndY ) || isInROI( boxEndX, boxEndY )
129 || isInROI( boxEndX, boxStartY ) ) {
130 labels.add( new double[] { boxStartX, boxStartY, rotation } );
131 }
132
133 boxStartX = lastX;
134 boxStartY = lastY;
135 eCandidates.clear();
136 } else {
137 eCandidates.add( new double[] { x, y } );
138 lastX = x;
139 lastY = y;
140 i++;
141 }
142 }
143 return labels;
144 }
145
146 /**
147 * Returns whether the given point is inside the region of interest.
148 *
149 * @param x
150 * x coordinate of the point
151 * @param y
152 * y coordinate of the point
153 * @return true, if the point is inside the region of interest, false otherwise
154 */
155 private boolean isInROI( double x, double y ) {
156 return x >= minX && x <= maxX && y >= minY && y <= maxY;
157 }
158
159 /**
160 * Finds a point on the line between p1 and p2 that has a certain distance from point p0
161 * (provided that there is such a point).
162 *
163 * @param p0
164 * point that is used as reference point for the distance
165 * @param p1
166 * starting point of the line
167 * @param p2
168 * end point of the line
169 * @param d
170 * distance
171 * @return a point on the line between p1 and p2 with distance d from p0
172 */
173 private static double[] findPointWithDistance( double[] p0, double[] p1, double[] p2, double d ) {
174
175 double x, y;
176 double x0 = p0[0];
177 double y0 = p0[1];
178 double x1 = p1[0];
179 double y1 = p1[1];
180 double x2 = p2[0];
181 double y2 = p2[1];
182
183 if ( x1 != x2 ) {
184 // line segment does not run vertical
185 double u = ( y2 - y1 ) / ( x2 - x1 );
186 double p = -2 * ( x0 + u * u * x1 - u * ( y1 - y0 ) ) / ( u * u + 1 );
187 double q = ( ( y1 - y0 ) * ( y1 - y0 ) + u * u * x1 * x1 + x0 * x0 - 2 * u * x1 * ( y1 - y0 ) - d * d )
188 / ( u * u + 1 );
189 double minX = p1[0];
190 double maxX = p2[0];
191 double minY = p1[1];
192 double maxY = p2[1];
193 if ( minX > maxX ) {
194 minX = p2[0];
195 maxX = p1[0];
196 }
197 if ( minY > maxY ) {
198 minY = p2[1];
199 maxY = p1[1];
200 }
201
202 if ( x1 < x2 ) {
203 // to the right
204 x = -p / 2 + Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
205 } else {
206 // to the left
207 x = -p / 2 - Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
208 }
209
210 // if ((int) (x + 0.5) <= minX || (int) (x + 0.5) >= maxX) {
211 // x = -p / 2 + Math.sqrt ((p / 2) * (p / 2) - q);
212 // }
213 y = ( x - x1 ) * u + y1;
214 } else {
215 // vertical line segment
216 x = x1;
217 double minY = p1[1];
218 double maxY = p2[1];
219
220 if ( minY > maxY ) {
221 minY = p2[1];
222 maxY = p1[1];
223 }
224
225 double p = -2 * y0;
226 double q = y0 * y0 + ( x1 - x0 ) * ( x1 - x0 ) - d * d;
227
228 if ( y1 > y2 ) {
229 // down
230 y = -p / 2 - Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
231 } else {
232 // up
233 y = -p / 2 + Math.sqrt( ( p / 2 ) * ( p / 2 ) - q );
234 }
235
236 // y = -p / 2 - Math.sqrt ((p / 2) * (p / 2) - q);
237 // if ((int) (y + 0.5) <= minY || (int) (y + 0.5) >= maxY) {
238 // y = -p / 2 + Math.sqrt ((p / 2) * (p / 2) - q);
239 // }
240 }
241 return new double[] { x, y };
242 }
243
244 /**
245 * Returns the slope of the line that is constructed by two given points.
246 *
247 * @param x1
248 * x coordinate of point 1
249 * @param y1
250 * y coordinate of point 1
251 * @param x2
252 * x coordinate of point 2
253 * @param y2
254 * y coordinate of point 2
255 * @return the slope of the line (in degrees)
256 */
257 private double getSlope( double x1, double y1, double x2, double y2 ) {
258 double dx = x2 - x1;
259 double dy = -( y2 - y1 );
260 double rotation = 0.0;
261
262 if ( dx <= 0 ) {
263 // dx = 0. division not possible.
264 if ( dx == 0 ) {
265 dx = 1;
266 }
267 if ( dy <= 0 ) {
268 // left down
269 rotation = -Math.atan( dy / dx );
270 } else {
271 // left up
272 rotation = -Math.atan( dy / dx );
273 }
274 } else {
275 if ( dy <= 0 ) {
276 // right down
277 rotation = -Math.PI - Math.atan( dy / dx );
278 } else {
279 // right up
280 rotation = -Math.PI - Math.atan( dy / dx );
281 }
282 }
283 return Math.toDegrees( rotation );
284 }
285
286 /**
287 * Returns the Euclidean distance between two given points.
288 *
289 * @param x1
290 * x coordinate of point 1
291 * @param y1
292 * y coordinate of point 1
293 * @param x2
294 * x coordinate of point 2
295 * @param y2
296 * y coordinate of point 2
297 * @return the Euclidean distance between (x1,y1) and (x2,y2)
298 */
299 private double getDistance( double x1, double y1, double x2, double y2 ) {
300 double dx = x2 - x1;
301 double dy = y2 - y1;
302 return Math.sqrt( dx * dx + dy * dy );
303 }
304
305 // /**
306 // * Returns the Euclidean distance between two given points.
307 // *
308 // * @param p1
309 // * point 1
310 // * @param p2
311 // * point 2
312 // * @return the Euclidean distance between p1 and p2
313 // */
314 // private double getDistance( double[] p1, double[] p2 ) {
315 // double dx = p1[0] - p2[0];
316 // double dy = p1[1] - p2[1];
317 // return Math.sqrt( dx * dx + dy * dy );
318 // }
319
320 // /**
321 // * Calculates the maximum deviation that points on a linestring have to the ideal line between
322 // * the starting point and the end point.
323 // * <p>
324 // * The ideal line is thought to be running from left to right, the left deviation value
325 // * generally is above the line, the right value is below.
326 // *
327 // * @param start
328 // * starting point of the linestring
329 // * @param end
330 // * end point of the linestring
331 // * @param points
332 // * points in between
333 // * @return the maximum deviation
334 // */
335 // private double[] calcDeviation( double[] start, double[] end, List points ) {
336 //
337 // // extreme deviation to the left
338 // double d1 = 0.0;
339 // // extreme deviation to the right
340 // double d2 = 0.0;
341 // Iterator it = points.iterator();
342 //
343 // // eventually swap start and end point
344 // if ( start[0] > end[0] ) {
345 // double[] tmp = start;
346 // start = end;
347 // end = tmp;
348 // }
349 //
350 // if ( start[0] != end[0] ) {
351 // // label orientation is not completly vertical
352 // if ( start[1] != end[1] ) {
353 // // label orientation is not completly horizontal
354 // while ( it.hasNext() ) {
355 // double[] point = (double[]) it.next();
356 // double u = ( end[1] - start[1] ) / ( end[0] - start[0] );
357 // double x = ( u * u * start[0] - u * ( start[1] - point[1] ) + point[0] )
358 // / ( 1.0 + u * u );
359 // double y = ( x - start[0] ) * u + start[1];
360 // double d = getDistance( point, new double[] { x, y } );
361 // if ( y >= point[1] ) {
362 // // candidate for left extreme value
363 // if ( d > d1 ) {
364 // d1 = d;
365 // }
366 // } else if ( d > d2 ) {
367 // // candidate for right extreme value
368 // d2 = d;
369 // }
370 // }
371 // } else {
372 // // label orientation is completly horizontal
373 // while ( it.hasNext() ) {
374 // double[] point = (double[]) it.next();
375 // double d = point[1] - start[1];
376 // if ( d < 0 ) {
377 // // candidate for left extreme value
378 // if ( -d > d1 ) {
379 // d1 = -d;
380 // }
381 // } else if ( d > d2 ) {
382 // // candidate for left extreme value
383 // d2 = d;
384 // }
385 // }
386 // }
387 // } else {
388 // // label orientation is completely vertical
389 // while ( it.hasNext() ) {
390 // double[] point = (double[]) it.next();
391 // double d = point[0] - start[0];
392 // if ( d < 0 ) {
393 // // candidate for left extreme value
394 // if ( -d > d1 ) {
395 // d1 = -d;
396 // }
397 // } else if ( d > d2 ) {
398 // // candidate for right extreme value
399 // d2 = d;
400 // }
401 // }
402 // }
403 // return new double[] { d1, d2 };
404 // }
405 }