intersection.java

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

     * Does the segment come within near radians of the region defined by the
     * polygon in r[*]? Catches segments within poly region and returns after
     * first hit, which is why it returns boolean.
     */
    public static final boolean isSegmentNearPolyRegion(GeoSegment segment,
                                                        GeoArray r, double near) {
        Geo[] s = segment.getSeg();
        if (s != null && s.length == 2) {
            return isSegmentNearPolyRegion(s[0], s[1], r, near);
        }
        return false;
    }

    /**
     * Does the segment s1-s2 come within near radians of the region defined by
     * the polygon in r[*]? Catches segments within poly region and returns
     * after first hit, which is why it returns boolean.
     */
    public static final boolean isSegmentNearPolyRegion(Geo s1, Geo s2,
                                                        GeoArray r, double near) {

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

    /**
     * Where is a segment within range of a region?
     */
    public static final Geo isSegmentNearPoly(GeoSegment segment, GeoArray 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, GeoArray r,
                                              double near) {

        int rlen = r.getSize();
        Geo pl0 = r.get(rlen - 1, new Geo());
        Geo pl1 = new Geo();
        // check will be returned as ret, but we only allocate one per this
        // method call, instead of one per loop, since we are returning if ret
        // is not null.
        Geo check = new Geo();
        for (int j = 0; j < rlen; j++) {
            pl1 = r.get(j, pl1);
            Geo ret = segmentsIntersectOrNear(s1, s2, pl0, pl1, near, check);

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

            pl0.initialize(pl1);
        }
        return null;
    }

    /**
     * Where is a segment within range of a region?
     */
    public static final List segmentNearPoly(GeoSegment segment, GeoArray 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, GeoArray r,
                                             double near) {
        int rlen = r.getSize();
        Geo pl0 = r.get(rlen - 1, new Geo());
        Geo pl1 = new Geo();
        List list = null;
        Geo check = new Geo();
        for (int j = 0; j < rlen; j++) {
            r.get(j, pl1);
            Geo ret = segmentsIntersectOrNear(s1, s2, pl0, pl1, near, check);

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

                list.add(ret);
                // ret is actually the last created check. This mechanism limits
                // the creation of Geos to only hits + 1.
                check = new Geo();
            }

            pl0.initialize(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, GeoArray r, double near) {
        int rlen = r.getSize();
        Geo pl0 = r.get(rlen - 1, new Geo());
        Geo pl1 = new Geo();
        for (int j = 0; j < rlen; j++) {
            r.get(j, pl1);
            if (pl0.isInside(pl1, near, s)) {
                return true; // near enough to a region edge
            }
            pl0.initialize(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(GeoArray s, GeoArray r, double near) {
        int rlen = r.getSize();
        int slen = s.getSize();
        Geo pl0 = r.get(rlen - 1);
        Geo pl1 = new Geo();
        Geo sl0 = s.get(slen - 1);
        Geo sl1 = new Geo();
        for (int j = 0; j < rlen; j++) {
            pl1 = r.get(j, pl1);
            for (int i = 0; i < slen; i++) {
                sl1 = s.get(i, sl1);
                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(GeoArray s, GeoArray r, double near) {
        int rlen = r.getSize();
        int slen = s.getSize();
        Geo pl0 = r.get(rlen - 1);
        Geo pl1 = new Geo();
        Geo sl0 = s.get(slen - 1);
        Geo sl1 = new Geo();
        List list = null;
        for (int j = 0; j < rlen; j++) {
            pl1 = r.get(j, pl1);
            for (int i = 0; i < slen; i++) {
                sl1 = s.get(i, sl1);
                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. Since we don't use bc anymore, let's reuse it for i, gets
        // passed back from crossNormalize as the second argument.
        Geo i = ac.crossNormalize(bc, bc);

        // if i is not on A
        if (!(i.distance(a1) <= aL && i.distance(a2) <= aL)) {
            i = i.antipode(i); // switch to the antipode instead, reuse i
            // object for new values.
            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;
        }
    }

    /**
     * @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, Geo ret) {

        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. ret is returned from crossNormalize
        // as bc.
        Geo ac = a1.crossNormalize(a2);
        Geo bc = b1.crossNormalize(b2, ret);

        // 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. Since we don't use bc anymore, let's reuse it for i, gets
        // passed back from crossNormalize as the second argument.
        Geo i = ac.crossNormalize(bc, bc);

        // if i is not on A
        if (!(i.distance(a1) <= aL && i.distance(a2) <= aL)) {
            i = i.antipode(ret); // switch to the antipode instead, reuse ret
            // yet again.
            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) {
            // remember ret -> bc -> i, so i == ret
            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);
    }
}