    001    //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.4_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    }