drawutil.java

openmap java写的开源数字地图程序. 用applet实现,可以像google map 那样放大缩小地图.

// **********************************************************************
// 
// <copyright>
// 
//  BBN Technologies
//  10 Moulton Street
//  Cambridge, MA 02138
//  [phone]
// 
//  Copyright (C) BBNT Solutions LLC. All rights reserved.
// 
// </copyright>
// **********************************************************************
// 
// $Source: /cvs/distapps/openmap/src/openmap/com/bbn/openmap/proj/DrawUtil.java,v $
// $RCSfile: DrawUtil.java,v $
// $Revision: 1.3.2.1 $
// $Date: 2004/10/14 18:27:35 $
// $Author: dietrick $
// 
// **********************************************************************

package com.bbn.openmap.proj;

import java.awt.Point;
import java.util.ArrayList;
import com.bbn.openmap.MoreMath;

/**
 * Drawing utility functions.
 */
public class DrawUtil {

    // cannot construct
    private DrawUtil() {}

    /**
     * Generate additional vertices between two points.
     * <p>
     * 
     * @param x1 x coord
     * @param y1 y coord
     * @param x2 x coord
     * @param y2 y coord
     * @param n num segments
     * @param include_last include the last one?
     * @param ret_val the array to put them in
     * @return int[] ret_val
     */
    public final static int[] lineSegments(int x1, int y1, int x2, int y2,
                                           int n, boolean include_last,
                                           int[] ret_val) {
        if (n <= 0) {
            ret_val = new int[2];
            ret_val[0] = x1;
            ret_val[1] = y1;
            return ret_val;
        }
        float dx = x2 - x1;
        float dy = y2 - y1;
        int end = include_last ? n + 1 : n;
        end <<= 1;
        float inc = 1f / (float) n;
        float t = inc;

        // add all the vertices in x,y order
        ret_val[0] = x1;
        ret_val[1] = y1;
        for (int i = 2; i < end; i += 2, t += inc) {
            ret_val[i] = x1 + (int) (dx * t);
            ret_val[i + 1] = y1 + (int) (dy * t);
        }
        return ret_val;
    }

    /**
     * Returns n or n+1 points along a line.
     * <p>
     * 
     * @param pt1 point
     * @param pt2 point
     * @param n count
     * @param include_last boolean
     * @return Point[]
     */
    public final static Point[] lineSegments(Point pt1, Point pt2, int n,
                                             boolean include_last) {

        Point v = new Point(pt2.x - pt1.x, pt2.y - pt1.y);
        int end = include_last ? n + 1 : n;
        Point[] ret_val = new Point[end];
        float inc = 1f / (float) n;
        float t = inc;

        ret_val[0] = pt1;
        for (int i = 1; i < end; i++, t += inc) {
            ret_val[i] = new Point(pt1.x + (int) ((float) v.x * t), pt1.y
                    + (int) ((float) v.y * t));
        }
        return ret_val;
    }

    /**
     * Bresenham's line algorithm.
     * <p>
     * Returns an array of points to draw.
     * <p>
     * 
     * @param pt1 point
     * @param pt2 point
     * @return Point[]
     *  
     */
    public final static Point[] bresenham_line(Point pt1, Point pt2) {
        return bresenham_line(pt1.x, pt1.y, pt2.x, pt2.y);
    }

    /**
     * Bresenham's line algorithm.
     * <p>
     * 
     * @param x1 horizontal pixel window location of first point.
     * @param y1 vertical pixel window location of first point.
     * @param x2 horizontal pixel window location of second point.
     * @param y2 vertical pixel window location of second point.
     * @return Point[]
     *  
     */
    public final static Point[] bresenham_line(int x1, int y1, int x2, int y2) {
        // This is actually NOT bresenhams algorithm. It is faster!
        // -rmf

        //      Debug.output("DrawUtil.bresenham_line(" +
        //                         x1 + "," + y1 + ")->(" + x2 + "," + y2 + ")");
        int i;
        int d, x, y, ax, ay, sx, sy, dx, dy, t;

        dx = x2 - x1;
        ax = Math.abs(dx) << 1;
        sx = MoreMath.sign(dx);
        dy = y2 - y1;
        ay = Math.abs(dy) << 1;
        sy = MoreMath.sign(dy);

        t = Math.max(Math.abs(dx), Math.abs(dy)) + 1;
        Point[] ret_val = new Point[t];

        x = x1;
        y = y1;
        if (ax > ay) { /* x dominant */
            d = ay - (ax >> 1);
            for (i = 0;;) {
                ret_val[i++] = new Point(x, y);
                //ret_val[i].x = x; ret_val[i++].y = y;
                if (x == x2)
                    return ret_val;
                if (d >= 0) {
                    y += sy;
                    d -= ax;
                }
                x += sx;
                d += ay;
            }
        } else { /* y dominant */
            d = ax - (ay >> 1);
            for (i = 0;;) {
                ret_val[i++] = new Point(x, y);
                //ret_val[i].x = x; ret_val[i++].y = y;
                if (y == y2)
                    return ret_val;
                if (d >= 0) {
                    x += sx;
                    d -= ay;
                }
                y += sy;
                d += ax;
            }
        }
    }

    /**
     * Tests if a point is inside a polygon.
     * <p>
     * 
     * @param xpts horizontal pixel window points of polygon.
     * @param ypts vertical pixel window points of polygon.
     * @param ptx horizontal pixel window points of location
     * @param pty vertical pixel window points of location.
     * @return boolean
     */
    public final static boolean inside_polygon(int[] xpts, int[] ypts, int ptx,
                                               int pty) {

        int j, inside_flag = 0;
        int numverts = xpts.length;
        if (numverts <= 2)
            return false;
        Point vtx0 = new Point(0, 0), vtx1 = new Point(0, 0);
        double dv0; // prevents OVERFLOW!!
        int crossings = 0;
        boolean xflag0 = false, yflag0 = false, yflag1 = false;

        vtx0.x = xpts[numverts - 1];
        vtx0.y = ypts[numverts - 1];
        // get test bit for above/below Y axis
        yflag0 = ((dv0 = vtx0.y - pty) >= 0);

        for (j = 0; j < numverts; j++) {
            if ((j & 0x1) != 0) { //HACK - slightly changed
                vtx0.x = xpts[j];
                vtx0.y = ypts[j];
                yflag0 = ((dv0 = vtx0.y - pty) >= 0);
            } else {
                vtx1.x = xpts[j];
                vtx1.y = ypts[j];
                yflag1 = (vtx1.y >= pty);
            }

            /*
             * check if points not both above/below X axis - can't hit
             * ray
             */
            if (yflag0 != yflag1) {
                /* check if points on same side of Y axis */
                if ((xflag0 = (vtx0.x >= ptx)) == (vtx1.x >= ptx)) {
                    if (xflag0)
                        crossings++;
                } else {
                    crossings += ((vtx0.x - dv0 * (vtx1.x - vtx0.x)
                            / (vtx1.y - vtx0.y)) >= ptx) ? 1 : 0;
                }
            }
            inside_flag = crossings & 0x01;
        }
        return (inside_flag != 0);
    }

    /**
     * Returns the distance from Point (x,y) to the closest line
     * segment in the Poly (int[] xpts, int[] ypts).
     * <p>
     * This procedure assumes that xpts.length == ypts.length.
     * <p>
     * 
     * @param xpts X points of the polygon
     * @param ypts Y points of the polygon
     * @param ptx x location of the point
     * @param pty y location of the point
     * @param connected polyline or polygon
     */
    public final static float closestPolyDistance(int[] xpts, int[] ypts,
                                                  int ptx, int pty,
                                                  boolean connected) {
        if (xpts.length == 0)
            return Float.POSITIVE_INFINITY;
        if (xpts.length == 1)
            return distance(xpts[0], ypts[0], ptx, pty);

        float temp, distance = Float.POSITIVE_INFINITY;
        int i, j;

        for (i = 0, j = 1; j < xpts.length; i++, j++) {
            temp = distance_to_line(xpts[i],
                    ypts[i],
                    xpts[j],
                    ypts[j],
                    ptx,
                    pty);
            //          Debug.output(
            //              "\tdistance from line (" + from.x + "," + from.y +
            // "<->" +
            //              to.x + "," + to.y + ") to point (" + ptx + "," + pty +
            // ")=" +
            //              temp);
            if (temp < distance)
                distance = temp;
        }

        // connect
        if (connected) {
            temp = distance_to_line(xpts[i],
                    ypts[i],
                    xpts[0],
                    ypts[0],
                    ptx,
                    pty);
            if (temp < distance)
                distance = temp;
        }
        return distance;
    }

    /**
     * 2D distance formula.
     * <p>
     * 
     * @param x1 x coord
     * @param y1 y coord
     * @param x2 x coord
     * @param y2 y coord
     * @return float distance
     */
    public final static float distance(float x1, float y1, float x2, float y2) {
        float xdiff = x2 - x1;
        float ydiff = y2 - y1;
        return (float) Math.sqrt((xdiff * xdiff + ydiff * ydiff));
    }

    /**
     * 2D distance formula.
     * <p>
     * 
     * @param x1 x coord
     * @param y1 y coord
     * @param x2 x coord
     * @param y2 y coord
     * @return float distance
     */
    public final static float distance(int x1, int y1, int x2, int y2) {
        int xdiff = x2 - x1;
        int ydiff = y2 - y1;
        return (float) Math.sqrt((float) (xdiff * xdiff + ydiff * ydiff));
    }

    /**
     * Calculate the "pixel distance" between two points (squaring not
     * envolved).
     * <p>
     * 
     * @param x1 x coord
     * @param y1 y coord
     * @param x2 x coord
     * @param y2 y coord
     * @return int pixel distance
     */
    public final static int pixel_distance(int x1, int y1, int x2, int y2) {

        int dx = Math.abs(x1 - x2);
        int dy = Math.abs(y1 - y2);
        return (dx > dy) ? dx : dy;
    }

    /**
     * Distance to closest endpoint.
     * <p>
     * 
     * @param x1 x coord
     * @param y1 y coord
     * @param x2 x coord
     * @param y2 y coord
     * @param x x coord of point
     * @param y y coord of point
     * @return float distance to endpoint
     */
    public final static float distance_to_endpoint(int x1, int y1, int x2,
                                                   int y2, int x, int y) {

        return (float) Math.min(distance(x1, y1, x, y), distance(x2, y2, x, y));
    }

    /**
     * Compute distance from point to line segment.
     * <p>
     * Compute the distance from point (x,y) to a line by computing
     * the perpendicular line from (x,y) to the line and finding the
     * intersection of this perpendicular and the line. If the
     * intersection is on the line segment, then the distance is the
     * distance from the mouse to the intersection, otherwise it is
     * the distance from (x,y) to the nearest endpoint.
     * <p>
     * Equations used to compute distance: <br>
     * <ul>
     * <li>m = (y2-y1)/(x2-x1) slope of the line
     * <li>y = mx + b equation of the line
     * <li>c = -1/m slope of line perpendicular to it
     * <li>y = cx + d equation of perpendicular line
     * <li>xi = (d-b)/(m-c) x-intersection, from equating the 2 line
     * equations
     * <li>y1 = c* xi + d y-intersection
     * <li>distance = sqrt(sqr(x-xi) + sqr(y-yi)) distance between
     * two points
     * </ul>
     * 
     * @param x1 line x coord1
     * @param y1 line y coord1
     * @param x2 line x coord2
     * @param y2 line y coord2
     * @param x point x coord
     * @param y point y coord
     * @return float distance to line segment
     * @deprecated USE THE NEW FUNCTION
     *  
     */