intersection.java

OpenMap是一个基于JavaBeansTM的开发工具包。利用OpenMap你就能够快速构建用于访问legacy数据库的应用程序与applets。OpenMap提供了允许用户查看和操作地理空间信息的

/**
 *                     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.13 $ on $Date: 2007/10/09 20:39:11 $
 */
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);
    }

    /**
     * Retrieve the MatchCollector that contains the results from the
     * Intersection query.
     * 
     * @return
     */
    public MatchCollector getCollector() {
        return collector;
    }

    /**
     * Retrieve the MatchFilter that can be used to control which GeoExtents are
     * considered for Intersection queries.
     * 
     * @return
     */
    public MatchFilter getFilter() {
        return filter;
    }

    /**
     * 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);
            }
        }
    }

    /**
     * Loads the collector with regions from the Collection that intesect with
     * r.
     * 
     * @param r the region in question
     * @param regions a Collection of GeoRegions.
     */
    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 {
                // usually, getting here means poly region vs radial region
                BoundingCircle bc = extent.getBoundingCircle();
                BoundingCircle rbc = r.getBoundingCircle();
                // first pass check - the bounding circles intersect
                if (rbc.intersects(bc.getCenter(), bc.getRadius()
                        + filter.getHRange())) {
                    GeoArray pts = r.getPoints();
                    if (isPointInPolygon(bc.getCenter(), pts)) {
                        // the center of extent is inside r
                        collector.collect(r, extent);
                    } else if (isPointNearPoly(bc.getCenter(),
                            pts,
                            bc.getRadius() + filter.getHRange())) {
                        // Center+radius of extent is within range an edge of
                        // the r
                        collector.collect(r, extent);
                    } // else no intersection
                }
            }
        }
    }

    /**
     * Puts the region in the Collector if r intersects with it.
     * 
     * @param r
     * @param region
     */
    public void considerRegionXRegion(GeoRegion r, GeoRegion region) {
        /* these must be cheap! */
        GeoArray rBoundary = r.getPoints();
        /* get the first path point */
        Geo rPoint = rBoundary.get(0, new Geo());
        GeoArray regionBoundary = region.getPoints();
        Geo regionPoint = regionBoundary.get(0, new Geo());

        // check for total containment
        if (Intersection.isPointInPolygon(rPoint, regionBoundary)
                || Intersection.isPointInPolygon(regionPoint, rBoundary)
        // || Intersection.isPointInPolygon(region.getBoundingCircle()
        // .getCenter(), rBoundary)
        // || Intersection.isPointInPolygon(r.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;
                }
            }
        }
    }

    /**
     * Puts regions in the Collector if they intersect the path.
     * 
     * @param path
     * @param regions
     */
    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.getPoints(),
                                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);
                        }
                    }
                }

            }
        }
    }

    /**
     * Puts the region in the Collector if it intersects with the path.
     * 
     * @param path
     * @param region
     */
    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;
            }
        }
    }

    /**
     * Returns true if the segment intersects with the region. The range of the
     * query is determined by the filter set on this Intersection object.
     * 
     * @param seg
     * @param region
     * @return
     */
    public boolean considerSegmentXRegion(GeoSegment seg, GeoRegion region) {
        return region.isSegmentNear(seg, filter.getHRange());
    }

    /**
     * Adds regions to the Collector if the GeoPoint p is on or in the regions
     * of the Collection.
     * 
     * @param p
     * @param regions
     */
    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.getPoints(),
                            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);
                    }
                }
            }
        }
    }

    /**
     * @param p
     * @param region