/** *                     RESTRICTED RIGHTS LEGEND * *                        BBNT Solutions LLC *                        A Verizon Company *                        10 Moulton Street *                       Cambridge, MA 02138 *                         (617) 873-3000 * * 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()),