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    }