intersection.java

来自「OpenMap是一个基于JavaBeansTM的开发工具包。利用OpenMap你」· Java 代码 · 共 1,455 行 · 第 1/4 页

     * @return true if p is in region.
     */
    public boolean considerPointXRegion(GeoPoint p, GeoRegion region) {
        return isPointInPolygon(p.getPoint(), region.getPoints());
    }

    //
    // Static versions of intersection methods
    //

    /**
     * Simplified version of #intersect(Path, Collection, Algorithm) for old
     * code, using the default match algorithm, and returning the identifiers of
     * the regions that intersect with the path.
     * 
     * @param path
     * @param regions
     * @return a list of the identifiers of the intersecting regions.
     */
    public static Iterator intersect(Object path, Object regions) {
        MatchCollector.SetMatchCollector c = new MatchCollector.SetMatchCollector();
        Intersection ix = new Intersection(new MatchFilter.MatchParametersMF(MatchParameters.STRICT), c);
        ix.consider(path, regions);
        return c.iterator();
    }

    //
    // Utility methods (The Mathematics)
    //

    /**
     * Returns the two antipodal points of 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 an array of two lat-lon points arranged as lat, lon, lat, lon
     */
    public static float[] getIntersection(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));

        Geo geo = geoCross1.crossNormalize(geoCross2);
        Geo anti = geo.antipode();

        return new float[] { ((float) geo.getLatitude()),
                ((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));

        // geoCross memory is reused for answer.
        return geoCross1.crossNormalize(geoCross2, geoCross1);
    }

    /**
     * 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, new Geo());
        Geo c = center.normalize(new Geo());
        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. NOTE: i is assumed to be
     * on the great circle line.
     */
    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)));
    }

    /**
     * Returns true if i is on the great circle between a and b and between
     * them, false otherwise. In other words, this method does the great circle
     * test for you, too.
     */
    public static boolean isOnSegment(Geo a, Geo b, Geo i, double withinRad) {

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

        return ((Math.abs(a.crossNormalize(b).dot(i)) <= withinRad)
                && (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, reusing g object for it's memory.
        Geo i = f.crossNormalize(g, g);
        if (isOnSegment(a, b, i)) {
            return i;
        } else {
            // reuse i object memory
            Geo ai = i.antipode(i);
            if (isOnSegment(a, b, ai)) {
                return ai;
            } else {
                return null;
            }
        }
    }

    /**
     * Test if [p1-p2] and [p3-p4] intersect
     */
    public static final boolean segIntersects(Geo p1, Geo p2, Geo p3, Geo p4) {
        Geo[] r = getSegIntersection(p1, p2, p3, p4);
        return (r[0] != null || r[1] != 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 g = p1.cross(p2);
        Geo f = center.cross(g);
        // Reusing g object for i
        Geo i = f.crossNormalize(g, g);

        // 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 (center.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, reusing i object for i2
        Geo i2 = i.antipode(i);
        if (center.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);
        }

        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 = new Geo(polyPoints[0], polyPoints[1]);
        Geo b = new Geo();
        Geo c = new Geo(lat, lon);

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

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

            b.initialize(lat2, lon2);

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

            a.initialize(b);
        }

        return false;
    }