intersection.java

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

/**
 *                     RESTRICTED RIGHTS LEGEND
 *
 *                        BBNT Solutions LLC
 *                        A Verizon Company
 *                        10 Moulton Street
 *                       Cambridge, MA 02138
 *                         [phone]
 *
 * Copyright BBNT Solutions LLC 2001, 2002 All Rights Reserved
 *
 */

package com.bbn.openmap.geo;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * Contains great circle intersection algorithms and helper methods.
 * Sources: http://williams.best.vwh.net/intersect.htm
 * http://mathforum.org/library/drmath/view/60711.html
 * <P>
 * The Intersection class has been updated to manage query
 * intersections of GeoExtents over other GeoExtents. MatchCollectors
 * and MatchFilters can be used to help optimize the search and manage
 * the results.
 * 
 * @author Sachin Date
 * @author Ken Anderson
 * @version $Revision: 1.4.2.8 $ on $Date: 2005/12/09 20:58:47 $
 */
public class Intersection {

    protected final MatchFilter filter;
    protected final MatchCollector collector;

    /**
     * Create an Intersection class that will use the provided
     * MatchFilter and MatchCollector.
     * 
     * @param filter
     * @param collector
     */
    public Intersection(MatchFilter filter, MatchCollector collector) {
        this.filter = filter;
        this.collector = collector;
    }

    /**
     * Create an Intersection class that will use the
     * MatchFilter.MatchParameters class with STRICT settings, and a
     * MatchCollector.SetMatchCollector.
     */
    public static Intersection intersector() {
        return new Intersection(new MatchFilter.MatchParametersMF(MatchParameters.STRICT), new MatchCollector.SetMatchCollector());
    }

    /**
     * Create an Intersection class that will use the
     * MatchFilter.MatchParameters class with provided settings, and a
     * MatchCollector.SetMatchCollector.
     */
    public static Intersection intersector(MatchParameters params) {
        return new Intersection(new MatchFilter.MatchParametersMF(params), new MatchCollector.SetMatchCollector());

    }

    /**
     * Create an Intersection class that will use the
     * MatchFilter.MatchParameters class with provided settings, and a
     * MatchCollector.CollectionMatchCollector with the provided
     * collector.
     */
    public static Intersection intersector(MatchParameters params,
                                           final Collection c) {
        return new Intersection(new MatchFilter.MatchParametersMF(params), new MatchCollector.CollectionMatchCollector(c));
    }

    /**
     * Create an Intersection class that will use the provided
     * MatchFilter class and the provided MatchCollector.
     */
    public static Intersection intersector(MatchFilter filter,
                                           MatchCollector collector) {
        return new Intersection(filter, collector);
    }

    /**
     * Asks the Intersection class to calcuate the relationships
     * between object a and b. Calls the other consider methods,
     * depending on what a and b are. Consult the MatchCollector for
     * the results.
     * 
     * @param a A GeoExtent object, generally.
     * @param b A ExtentImpl object or GeoExtent object, generally.
     */
    public void consider(Object a, Object b) {
        if (b instanceof Collection) {
            if (a instanceof GeoRegion) {
                considerRegionXRegions((GeoRegion) a, (Collection) b);
            } else if (a instanceof GeoPath) {
                considerPathXRegions((GeoPath) a, (Collection) b);
            } else if (a instanceof GeoPoint) {
                considerPointXRegions((GeoPoint) a, (Collection) b);
            }
        } else if (b instanceof GeoRegion) {
            if (a instanceof GeoRegion) {
                considerRegionXRegion((GeoRegion) a, (GeoRegion) b);
            } else if (a instanceof GeoPath) {
                considerPathXRegion((GeoPath) a, (GeoRegion) b);
            } else if (a instanceof GeoPoint) {
                considerPointXRegion((GeoPoint) a, (GeoRegion) b);
            }
        }
    }

    public void considerRegionXRegions(GeoRegion r, Collection regions) {

        /*
         * since the path is closed we'll check the region index for
         * the whole thing instead of segment-by-segment
         */
        Iterator possibles;
        if (regions instanceof ExtentIndex) {
            // if we've got an index, narrow the set down
            possibles = ((ExtentIndex) regions).iterator(r);
        } else {
            possibles = regions.iterator();
        }

        while (possibles.hasNext()) {
            GeoExtent extent = (GeoExtent) possibles.next();
            if (extent instanceof GeoRegion) {
                considerRegionXRegion(r, (GeoRegion) extent);
            } else if (extent instanceof GeoPath) {
              // This body used to be the following:
              //   considerPathXRegion((GeoPath) extent, r);
              // but this reverses the match order and leads to "r" getting collected
              // instead of extent.  I've inlined the essential body and left it here
              for (GeoPath.SegmentIterator pit = ((GeoPath)extent).segmentIterator(); pit.hasNext();) {
                GeoSegment seg = pit.nextSegment();
                if (filter.preConsider(seg, r)
                    && considerSegmentXRegion(seg, r)) {
                  collector.collect(seg, extent);
                }
              }
            } else {
                BoundingCircle bc = extent.getBoundingCircle();
                BoundingCircle rbc = r.getBoundingCircle();
                if (rbc.intersects(bc.getCenter(), bc.getRadius()
                        + filter.getHRange())) {
                    collector.collect(r, extent);
                }
            }
        }
    }

    public void considerRegionXRegion(GeoRegion r, GeoRegion region) {
        /* these must be cheap! */
        Geo[] regionBoundary = r.toPointArray();
        /* get the first path point */
        Geo pathPoint = regionBoundary[0];
        Geo[] rboundary = region.toPointArray();
        // check for total containment
        if ((rboundary != null && (Intersection.isPointInPolygon(pathPoint,
                rboundary) || Intersection.isPointInPolygon(rboundary[0],
                regionBoundary)))
                || (rboundary == null && (region.isPointInside(pathPoint) ||
                /* first path point is inside the region? */
                Intersection.isPointInPolygon(region.getBoundingCircle()
                        .getCenter(), regionBoundary)))) {
            collector.collect(r, region);
        } else {
            // gotta try harder, so we fall back to segment-by-segment
            // intersections
            for (GeoPath.SegmentIterator pit = r.segmentIterator(); pit.hasNext();) {
                GeoSegment seg = pit.nextSegment();
                if (filter.preConsider(seg, region)
                        && considerSegmentXRegion(seg, region)) {
                    collector.collect(seg, region);
                    // For the default implementation, we just care
                    // about first hit.
                    return;
                }
            }
        }
    }

    public void considerPathXRegions(GeoPath path, Collection regions) {
        /*
         * Since the path is open, then our best bet is to check each
         * segment separately
         */
        for (GeoPath.SegmentIterator pit = path.segmentIterator(); pit.hasNext();) {
            GeoSegment seg = pit.nextSegment();
            Iterator rit;
            if (regions instanceof ExtentIndex) {
                rit = ((ExtentIndex) regions).iterator(seg);
            } else {
                rit = regions.iterator();
            }

            while (rit.hasNext()) {
                GeoExtent extent = (GeoExtent) rit.next();
                if (filter.preConsider(path, extent)) {
                    if (extent instanceof GeoRegion) {
                        GeoRegion region = (GeoRegion) extent;
                        if (considerSegmentXRegion(seg, region)) {
                            collector.collect(seg, region);
                        }
                    } else if (extent instanceof GeoPath) {
                        GeoPath p = (GeoPath) extent;
                        if (isSegmentNearPoly(seg,
                                p.toPointArray(),
                                filter.getHRange()) != null) {
                            collector.collect(seg, p);
                        }
                    } else {
                        BoundingCircle bc = extent.getBoundingCircle();
                        if (isSegmentNearRadialRegion(seg,
                                bc.getCenter(),
                                bc.getRadius(),
                                filter.getHRange())) {
                            collector.collect(seg, extent);
                        }
                    }
                }

            }
        }
    }

    public void considerPathXRegion(GeoPath path, GeoRegion region) {
        for (GeoPath.SegmentIterator pit = path.segmentIterator(); pit.hasNext();) {
            GeoSegment seg = pit.nextSegment();

            if (filter.preConsider(seg, region)
                    && considerSegmentXRegion(seg, region)) {
                collector.collect(seg, region);
                // For the default implementation, we just care about
                // the first contact.
                return;
            }
        }
    }

    public boolean considerSegmentXRegion(GeoSegment seg, GeoRegion region) {
        return region.isSegmentNear(seg, filter.getHRange());
    }

    public void considerPointXRegions(GeoPoint p, Collection regions) {
        Iterator rit;
        if (regions instanceof ExtentIndex) {
            rit = ((ExtentIndex) regions).iterator(p);
        } else {
            rit = regions.iterator();
        }

        while (rit.hasNext()) {
            GeoExtent extent = (GeoExtent) rit.next();
            if (filter.preConsider(p, extent)) {
                if (extent instanceof GeoRegion) {
                    GeoRegion region = (GeoRegion) extent;
                    if (considerPointXRegion(p, region)) {
                        collector.collect(p, region);
                    }
                } else if (extent instanceof GeoPath) {
                    GeoPath path = (GeoPath) extent;
                    if (isPointNearPoly(p.getPoint(),
                            path.toPointArray(),
                            filter.getHRange())) {
                        collector.collect(p, path);
                    }
                } else {
                    BoundingCircle bc = extent.getBoundingCircle();
                    if (p.getPoint().distance(bc.getCenter()) <= bc.getRadius()
                            + filter.getHRange()) {
                        collector.collect(p, extent);
                    }
                }
            }
        }
    }

    public boolean considerPointXRegion(GeoPoint p, GeoRegion region) {
        return isPointInPolygon(p.getPoint(), region.toPointArray());
    }

    //
    // 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()),