intersection.java

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

                ((float) geo.getLongitude()), ((float) anti.getLatitude()),
                ((float) anti.getLongitude()) };
    }

    /**
     * Returns a Geo representing the interection of two great circles
     * defined by the arcs (lat1, lon1) to (lat2, lon2) and (lat2,
     * lon2) to (lat4, lon4). All lat-lon values are in degrees.
     * 
     * @return Geo containing intersection, might have to check
     *         antipode of Geo for actual intersection.
     */
    public static Geo getIntersectionGeo(float lat1, float lon1, float lat2,
                                         float lon2, float lat3, float lon3,
                                         float lat4, float lon4) {

        Geo geoCross1 = (new Geo(lat1, lon1)).crossNormalize(new Geo(lat2, lon2));
        Geo geoCross2 = (new Geo(lat3, lon3)).crossNormalize(new Geo(lat4, lon4));

        return geoCross1.crossNormalize(geoCross2);
    }

    /**
     * Returns true if the two segs intersect in at least one point.
     * All lat-lon values are in degrees. lat1,lon1-lat2,lon2 make up
     * one segment, lat3,lon3-lat4,lon4 make up the other segment.
     */
    public static boolean intersects(float lat1, float lon1, float lat2,
                                     float lon2, float lat3, float lon3,
                                     float lat4, float lon4) {

        float[] llp = getSegIntersection(lat1,
                lon1,
                lat2,
                lon2,
                lat3,
                lon3,
                lat4,
                lon4);

        return (llp[0] != Float.MAX_VALUE && llp[1] != Float.MAX_VALUE)
                || (llp[2] != Float.MAX_VALUE && llp[3] != Float.MAX_VALUE);
    }

    /**
     * Checks if the two polygonal areas intersect. The two polygonal
     * regions are represented by two lat-lon arrays in the lat1,
     * lon1, lat2, lon2,... format. For closed polygons the last pair
     * of points in the array should be the same as the first pair.
     * All lat-lon values are in degrees.
     */
    public static boolean polyIntersect(float[] polyPoints1, float[] polyPoints2) {

        // go through each side of poly1 and test to see if it
        // intersects with any side of poly2

        for (int i = 0; i < polyPoints1.length / 2 - 1; i++) {

            for (int j = 0; j < polyPoints2.length / 2 - 1; j++) {

                if (intersects(polyPoints1[2 * i],
                        polyPoints1[2 * i + 1],
                        polyPoints1[2 * i + 2],
                        polyPoints1[2 * i + 3],
                        polyPoints2[2 * j],
                        polyPoints2[2 * j + 1],
                        polyPoints2[2 * j + 2],
                        polyPoints2[2 * j + 3]))
                    return true;
            }
        }

        return false;
    }

    /**
     * checks if the polygon or polyline represented by the polypoints
     * contains any lines that intersect each other. All lat-lon
     * values are in degrees.
     */
    public static boolean isSelfIntersectingPoly(float[] polyPoints) {

        for (int i = 0; i < polyPoints.length / 2 - 1; i++) {

            for (int j = i + 1; j < polyPoints.length / 2 - 1; j++) {

                float lat1 = polyPoints[2 * i];
                float lon1 = polyPoints[2 * i + 1];
                float lat2 = polyPoints[2 * i + 2];
                float lon2 = polyPoints[2 * i + 3];

                float lat3 = polyPoints[2 * j];
                float lon3 = polyPoints[2 * j + 1];
                float lat4 = polyPoints[2 * j + 2];
                float lon4 = polyPoints[2 * j + 3];

                // ignore adjacent segments
                if ((lat1 == lat4 && lon1 == lon4)
                        || (lat2 == lat3 && lon2 == lon3))
                    continue;

                if (intersects(lat1, lon1, lat2, lon2, lat3, lon3, lat4, lon4))
                    return true;

            }
        }

        return false;

    }

    /**
     * Calculates the great circle distance from the point (lat, lon)
     * to the great circle containing the points (lat1, lon1) and
     * (lat2, lon2).
     * 
     * @return nautical miles
     */
    public static float pointCircleDistanceNM(Geo p1, Geo p2, Geo center) {
        return (float) Geo.nm(pointCircleDistance(p1, p2, center));
    }

    /**
     * Calculates the great circle distance from the point (lat, lon)
     * to the great circle containing the points (lat1, lon1) and
     * (lat2, lon2).
     * 
     * @return radians
     */
    public static double pointCircleDistance(Geo p1, Geo p2, Geo center) {

        Geo n = Geo.crossNormalize(p1, p2);
        Geo c = center;
        c = c.normalize();
        double cosTheta = Geo.dot(n, c);
        double theta = Math.acos(cosTheta);

        return Math.abs(Math.PI / 2 - theta);
    }

    /**
     * Point i is on the great circle defined by the points a and b.
     * Returns true if i is between a and b, false otherwise.
     */
    public static boolean isOnSegment(Geo a, Geo b, Geo i) {

        // assert (< (Math.abs (.dot (.crossNormalize a b) i))
        // 1.e-15))

        return ((a.distance(i) < a.distance(b)) && (b.distance(i) < b.distance(a)));
    }

    /**
     * @return the Geo point i, which is on the great circle segment
     *         between Geo points a and b and which is closest to Geo
     *         point c. Returns null if there is no such point.
     */
    public static Geo segIntersection(Geo a, Geo b, Geo c) {
        // Normal to great circle between a and b
        Geo g = a.crossNormalize(b);
        // Normal to the great circle between c and g
        Geo f = c.crossNormalize(g);
        // The intersection is normal to both
        Geo i = f.crossNormalize(g);
        if (isOnSegment(a, b, i)) {
            return i;
        } else {
            Geo ai = i.antipode();
            if (isOnSegment(a, b, ai)) {
                return i.antipode();
            } else {
                return null;
            }
        }
    }

    /**
     * returns the distance in NM between the point (lat, lon) and the
     * point of intersection of the great circle passing through (lat,
     * lon) and perpendicular to great circle segment (lat1, lon1,
     * lat2, lon2). returns -1 if point of intersection of the two
     * great circle segs is not on the great circle segment (lat1,
     * lon1, lat2, lon2).
     */
    public static float pointSegDistanceNM(float lat1, float lon1, float lat2,
                                           float lon2, float lat, float lon) {
        double ret = pointSegDistance(new Geo(lat1, lon1),
                new Geo(lat2, lon2),
                new Geo(lat, lon));

        return (float) (ret == -1 ? ret : Geo.nm(ret));
    }

    /**
     * Returns the distance in radians between the point c and the
     * point of intersection of the great circle passing through c and
     * perpendicular to great circle segment between a and b. Returns
     * -1 if point of intersection of the two great circle segs is not
     * on the great circle segment a-b.
     */
    public static double pointSegDistance(Geo a, Geo b, Geo c) {
        Geo i = segIntersection(a, b, c);
        return (i == null) ? -1 : c.distance(i);
    }

    /**
     * Returns true or false depending on whether the great circle seg
     * from point p1 to point p2 intersects the circle of radius
     * (radians) around center.
     */
    public static boolean intersectsCircle(Geo p1, Geo p2, Geo center,
                                           double radius) {

        // check if either of the end points of the seg are inside the
        // circle
        double d1 = Geo.distance(p1, center);
        if (d1 < radius)
            return true;

        double d2 = Geo.distance(p2, center);
        if (d2 < radius)
            return true;

        double dist = pointCircleDistance(p1, p2, center);

        if (dist > radius)
            return false;

        // calculate point of intersection of great circle containing
        // (lat, lon) and perpendicular to great circle containing
        // (lat1, lon1) and (lat2, lon2)
        Geo a = p1;
        Geo b = p2;
        Geo c = center;

        Geo g = a.cross(b);
        Geo f = c.cross(g);
        Geo i = f.crossNormalize(g);
        Geo i2 = i.antipode();

        // check if point of intersection lies on the segment
        // length of seg
        double d = Geo.distance(p1, p2);

        // Make sure the intersection point is inside the exclusion
        // zone
        if (c.distance(i) < radius) {
            // between seg endpoints and first point of intersection
            double d11 = Geo.distance(p1, i);
            double d12 = Geo.distance(p2, i);
            // Check the distance of the intersection point and either
            // endpoint to see if it falls between them. Add a second
            // test to make sure that we are on the shorter of the two
            // segments between the endpoints.
            return (d11 <= d && d12 <= d && Math.abs(d11 + d12 - d) < 0.01f);
        }
        // Make sure the intersection point is inside the exclusion
        // zone
        else if (c.distance(i2) < radius) {
            // between seg1 endpoints and second point of intersection
            double d21 = Geo.distance(p1, i2);
            double d22 = Geo.distance(p2, i2);
            // Check the distance of the intersection point and either
            // endpoint to see if it falls between them. Add a second
            // test to make sure that we are on the shorter of the two
            // segments between the endpoints.
            return (d21 <= d && d22 <= d && Math.abs(d21 + d22 - d) < 0.01f);
        } else {
            return false;
        }
    }

    /**
     * returns true if the specified poly path intersects the circle
     * centered at (lat, lon). All lat-lon values are in degrees.
     * radius is in radians.
     */
    public static boolean intersectsCircle(float[] polyPoints, float lat,
                                           float lon, double radius) {

        Geo a = null;
        Geo b = null;
        Geo c = new Geo(lat, lon);

        for (int i = 0; i < polyPoints.length / 2 - 1; i++) {

            float lat1 = polyPoints[2 * i];
            float lon1 = polyPoints[2 * i + 1];
            float lat2 = polyPoints[2 * i + 2];
            float lon2 = polyPoints[2 * i + 3];

            if (a == null || b == null) {
                a = new Geo(lat1, lon1);
                b = new Geo(lat2, lon2);
            } else {
                a.initialize(lat1, lon1);
                b.initialize(lat2, lon2);
            }

            if (intersectsCircle(a, b, c, radius))
                return true;
        }

        return false;
    }

    /**
     * Returns the center of the polygon poly.
     */
    public static Geo center(Geo[] poly) {
        Geo c = new Geo(poly[0]);
        Geo p = new Geo(poly[0]);
        for (int i = 1; i < poly.length; i++) {
            p.initialize(poly[i]);
            c = c.add(p);
        }
        Geo res = c.normalize();
        return res;
    }

    /**
     * Determines whether <code>x</code> is inside <code>poly</code>.
     * 
     * <p>
     * <em>N.B.</em><br>
     * <ul>
     * <li><code>poly</code> must be a closed polygon. In other
     * words, the first and last point must be the same.
     * <li>It is recommended that a bounds check is run before this
     * method. This method will return true if either <code>x</code>
     * or the antipode (the point on the opposite side of the planet)
     * of <code>x</code> are inside <code>poly</code>.
     * </ul>
     * 
     * <p>