intersection.java

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

     * region and returns after first hit, which is why it returns
     * boolean.
     */
    public static final boolean isSegmentNearPolyRegion(Geo s1, Geo s2,
                                                        Geo[] r, double near) {

        return isSegmentNearPoly(s1, s2, r, near) != null
                || isPointInPolygon(s1, r);
    }

    /**
     * Where does the segment come within near radians of the region
     * defined by the polygon in r[*]?
     * 
     * @return a List of Geos where the intersections occur. If the
     *         segment is contained within the region, an empty list
     *         is returned. If there are no intersections and the
     *         segment is not contained in the region, the method
     *         returns null.
     */
    public static final List segmentNearPolyRegion(GeoSegment segment, Geo[] r,
                                                   double near) {
        Geo[] s = segment.getSeg();
        List list = null;
        if (s != null && s.length == 2) {
            list = segmentNearPolyRegion(s[0], s[1], r, near);
        }
        return list;
    }

    /**
     * Where does the segment s1-s2 come within near radians of the
     * region defined by the polygon in r[*]?
     * 
     * @return a List of Geos where the intersections occur. If the
     *         segment is contained within the region, an empty list
     *         is returned. If there are no intersections and the
     *         segment is not contained in the region, the method
     *         returns null.
     */
    public static final List segmentNearPolyRegion(Geo s1, Geo s2, Geo[] r,
                                                   double near) {
        List list = segmentNearPoly(s1, s2, r, near);
        // second arg is geo[]!
        if (list == null && Intersection.isPointInPolygon(s1, r)) {
            list = new LinkedList();
        }

        return list;
    }

    /**
     * Where is a segment within range of a region?
     */
    public static final Geo isSegmentNearPoly(GeoSegment segment, Geo[] r,
                                              double near) {
        Geo[] s = segment.getSeg();
        if (s != null && s.length == 2) {
            return isSegmentNearPoly(s[0], s[1], r, near);
        }
        return null;
    }

    /**
     * Is a segment, represented by endpoints 's1' and 's2', withing a
     * range 'near' of region 'r'?
     * 
     * @param s1 Endpoint of segment
     * @param s2 Endpoint of segment
     * @param r Region of interest
     * @param near acceptable range between the segment and region, in
     *        radians.
     * @return Geo location where the condition was initially met
     *         (yes), null if conditions weren't met (no).
     */
    public static final Geo isSegmentNearPoly(Geo s1, Geo s2, Geo[] r,
                                              double near) {

        int rlen = r.length;
        Geo pl0 = r[rlen - 1];
        Geo pl1;
        for (int j = 0; j < rlen; j++) {
            pl1 = r[j];
            Geo ret = segmentsIntersectOrNear(s1, s2, pl0, pl1, near);

            if (ret != null) {
                return ret;
            }

            pl0 = pl1;
        }
        return null;
    }

    /**
     * Where is a segment within range of a region?
     */
    public static final List segmentNearPoly(GeoSegment segment, Geo[] r,
                                             double near) {
        Geo[] s = segment.getSeg();
        List list = null;
        if (s != null && s.length == 2) {
            list = segmentNearPoly(s[0], s[1], r, near);
        }
        return list;
    }

    /**
     * Where is a segment, represented by endpoints 's1' and 's2',
     * withing a range 'near' of region 'r'?
     * 
     * @param s1 Endpoint of segment
     * @param s2 Endpoint of segment
     * @param r Region of interest
     * @param near acceptable range between the segment and region, in
     *        radians.
     * @return Geo location where the condition was met (yes), null if
     *         conditions weren't met (no).
     */
    public static final List segmentNearPoly(Geo s1, Geo s2, Geo[] r,
                                             double near) {
        int rlen = r.length;
        Geo pl0 = r[rlen - 1];
        Geo pl1;
        List list = null;
        for (int j = 0; j < rlen; j++) {
            pl1 = r[j];
            Geo ret = segmentsIntersectOrNear(s1, s2, pl0, pl1, near);

            if (ret != null) {
                if (list == null) {
                    list = new LinkedList();
                }

                list.add(ret);
            }

            pl0 = pl1;
        }
        return list;
    }

    /**
     * Does the point s come within 'near' radians of the boarder of
     * the region defined by the polygon in r[*]?
     */
    public static final boolean isPointNearPoly(Geo s, Geo[] r, double near) {
        int rlen = r.length;
        Geo pl0 = r[rlen - 1];
        Geo pl1;
        for (int j = 0; j < rlen; j++) {
            pl1 = r[j];
            if (pl0.isInside(pl1, near, s)) {
                return true; // near enough to a region edge
            }
            pl0 = pl1;
        }
        return false;
    }

    /**
     * Is one region's boundary within 'near' range of a region? Note:
     * good practice is s describes a smaller area than r.
     * 
     * @return the Geo location where the condition was first met,
     *         null if the condition wasn't met.
     */
    public static final Geo isPolyNearPoly(Geo[] s, Geo[] r, double near) {
        int rlen = r.length;
        int slen = s.length;
        Geo pl0 = r[rlen - 1];
        Geo pl1;
        Geo sl0 = s[slen - 1];
        Geo sl1;
        for (int j = 0; j < rlen; j++) {
            pl1 = r[j];
            for (int i = 0; i < slen; i++) {
                sl1 = s[i];
                Geo ret = segmentsIntersectOrNear(sl0, sl1, pl0, pl1, near);

                if (ret != null) {
                    return ret;
                }
                sl0 = sl1;
            }
            pl0 = pl1;
        }
        return null;
    }

    /**
     * Is one region's boundary within 'near' range of a region? Note:
     * good practice is s describes a smaller area than r.
     * 
     * @return a List where the polys intersect within the range, null
     *         if the condition wasn't met.
     */
    public static final List polyNearPoly(Geo[] s, Geo[] r, double near) {
        int rlen = r.length;
        int slen = s.length;
        Geo pl0 = r[rlen - 1];
        Geo pl1;
        Geo sl0 = s[slen - 1];
        Geo sl1;
        List list = null;
        for (int j = 0; j < rlen; j++) {
            pl1 = r[j];
            for (int i = 0; i < slen; i++) {
                sl1 = s[i];
                Geo ret = segmentsIntersectOrNear(sl0, sl1, pl0, pl1, near);

                if (ret != null) {
                    if (list == null) {
                        list = new LinkedList();
                    }
                    list.add(ret);
                }
                sl0 = sl1;
            }
            pl0 = pl1;
        }

        return list;
    }

    /**
     * @return a Geo location iff the great circle segments defined by
     *         a1-a2 and b1-b2 intersect. the angles between the
     *         segments must be < PI or the results are
     *         ambiguous.Returns null if the segments don't interset
     *         within the range.
     */
    public static Geo segmentsIntersect(Geo a1, Geo a2, Geo b1, Geo b2) {
        return segmentsIntersectOrNear(a1, a2, b1, b2, 0);
    }

    /**
     * @return a Geo location iff the great circle segments defined by
     *         a1-a2 and b1-b2 come within the range (r, radians) of
     *         each other. The angles between the segments must be <
     *         PI or the results are ambiguous. Returns null if the
     *         segments don't interset within the range.
     */
    public static Geo segmentsIntersectOrNear(Geo a1, Geo a2, Geo b1, Geo b2,
                                              double r) {

        if (a1 == null || a2 == null || b1 == null || b2 == null) {
            return null;
        }

        // ac and bc are the unit vectors normal to the two great
        // circles defined by the segments
        Geo ac = a1.crossNormalize(a2);
        Geo bc = b1.crossNormalize(b2);

        // aL and bL are the lengths (in radians) of the segments
        double aL = a1.distance(a2) + r;
        double bL = b1.distance(b2) + r;

        // i is one of the two points where the two great circles
        // intersect.
        Geo i = ac.crossNormalize(bc);

        // if i is not on A
        if (!(i.distance(a1) <= aL && i.distance(a2) <= aL)) {
            i = i.antipode(); // switch to the antipode instead
            if (!(i.distance(a1) <= aL && i.distance(a2) <= aL)) { // check
                // again
                // nope - neither i nor i' is on A, so we'll bail out
                return null;
            }
        }
        // i is intersection or anti-intersection point now.

        // Now see if it intersects with b
        if (i.distance(b1) <= bL && i.distance(b2) <= bL) {
            return i;
        } else {
            return null;
        }
    }

    public static void main(String[] args) {
        /**
         * Produces output: (1)=53.130104, -100.0 (2)=3.4028235E38,
         * -3.4028235E38 intersects=true polyIntersect=true
         * dist=655.4312 b3=true
         */

        float lat1 = 60;
        float lon1 = -130;
        float lat2 = 30;
        float lon2 = -70;

        float lat3 = 60;
        float lon3 = -70;
        float lat4 = 30;
        float lon4 = -130;

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

        System.out.println("(1)=" + ll[0] + ", " + (-ll[1]));
        System.out.println("(2)=" + ll[2] + ", " + (-ll[3]));

        boolean b1 = intersects(lat1,
                -lon1,
                lat2,
                -lon2,
                lat3,
                -lon3,
                lat4,
                -lon4);

        System.out.println("intersects=" + b1);

        float[] polypoints1 = new float[] { 38, -27, -46, 165 };

        float[] polypoints2 = new float[] { 51, -42, 55, -17, 11, -23, 51, -42 };

        boolean b2 = polyIntersect(polypoints1, polypoints2);

        System.out.println("polyIntersect=" + b2);
    }
}