extentindex.java

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

//**********************************************************************
//
//<copyright>
//
//BBN Technologies
//10 Moulton Street
//Cambridge, MA 02138
//[phone]
//
//Copyright (C) BBNT Solutions LLC. All rights reserved.
//
//</copyright>
//**********************************************************************
//
//$Source:
///cvs/darwars/ambush/aar/src/com/bbn/ambush/mission/MissionHandler.java,v
//$
//$RCSfile: ExtentIndex.java,v $
//$Revision: 1.1.2.4 $
//$Date: 2007/02/13 20:00:52 $
//$Author: dietrick $
//
//**********************************************************************

package com.bbn.openmap.geo;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;

/**
 * A Collection of Regions that supports indexed subsets. That is, in addition
 * to acting like a normal collection, it also allows getting an iterator that
 * will return a superset of all intersecting regions that is a subset of the
 * whole collection.
 * 
 * @author [e-mail]
 */
public interface ExtentIndex extends java.util.Collection {
    /**
     * report on the maximum horizontalRange supported by this index.
     */
    double indexHorizontalRange();

    /**
     * Add a extent to the index.
     * 
     * @param region
     * @return true if Region successfully added, false if not.
     */
    boolean addExtent(GeoExtent region);

    /**
     * Remove a region from the index.
     * 
     * @param region
     * @return true if the region was found and removed.
     */
    boolean removeExtent(GeoExtent region);

    /**
     * Resets the index to an empty state.
     */
    void clear();

    /**
     * return an iterator listing a subset of the whole collection that is a
     * superset of the actual matches. A valid (but inefficient) implementation
     * would return an iterator over the whole collection.
     * 
     * Implementation should match anything that is likely to match - this will
     * generally include, for instance, additional space around the actual
     * segment to accommodate buffer zones around the segment.
     */
    Iterator iterator(GeoExtent extent);

    /**
     * A basic implementation of ExtentIndex that uses Collection-typed buckets.
     * Extending classes must implement #makeBucket(int) to specify an
     * alternative Collection implementation.
     */
    abstract class AbstractExtentIndex extends java.util.AbstractCollection
            implements ExtentIndex {

        /**
         * Default value for #nbuckets if not specified in the call to the
         * constructor.
         */
        public static final int D_NBUCKETS = 360;

        /**
         * Default value for #margin if not specified in the call to the
         * constructor.
         */
        public static final double D_MARGIN = 0.0;

        /**
         * how many buckets in the longitudinal index - 360 means 1 bucket per
         * degree of longitude. More than 360 doesn't seem to add much search
         * speed, less than 180 makes it slower. The sweet spot on current
         * datasets is somewhere in between.
         * 
         * If unspecifed, defaults to #D_NBUCKETS
         */
        public final int nbuckets;

        /**
         * how much of a margin to put around regions for indexing purposes, in
         * nautical miles. This must be at least the largest margin searched for
         * by route (currently 50nmiles) - the larger this value, the larger the
         * average entries/bucket and so, the slower the search.
         * 
         * If unspecfied, defaults to #D_MARGIN
         */
        public final double margin;

        protected final Collection buckets[];

        /** all is a collection of everything successfully indexed. */
        protected final Collection all;
        /**
         * polar is a bucket for anything that is near enough to either pole to
         * cover more than 1/2 the buckets.
         */
        protected final Collection polar;

        protected final Collection discarded;

        public AbstractExtentIndex() {
            this(D_NBUCKETS, D_MARGIN);
        }

        public AbstractExtentIndex(int nb) {
            this(nb, D_MARGIN);
        }

        public AbstractExtentIndex(double m) {
            this(D_NBUCKETS, m);
        }

        public AbstractExtentIndex(int nb, double m) {
            nbuckets = nb;
            margin = m;
            buckets = new Collection[nbuckets];
            all = makeBucket(2000);
            polar = makeBucket();
            discarded = makeBucket();
        }

        protected final Collection makeBucket() {
            return makeBucket(0);
        }

        /**
         * implement to specify the factory to use to create Bucket storage.
         * 
         * @param sizeHint a guess at the number of elements that are likely to
         *        be stored in this bucket or 0 if unknown.
         * @return A Collection instance suitable for use as a bucket
         * 
         */
        abstract protected Collection makeBucket(int sizeHint);

        /**
         * Add an object to the index.
         * 
         * @return true if object is a GeoExtent and was added.
         */
        public boolean add(Object o) {
            if (o instanceof GeoExtent) {
                return addExtent((GeoExtent) o);
            } else {
                return false;
            }
        }

        /**
         * Method to call to add Region object with BoundingCircle to Collection
         * and organize it for later retrieval.
         * 
         * @param extent Region to index
         * @return true if object added, false if it's been discarded.
         */
        public boolean addExtent(GeoExtent extent) {
            boolean ret = false;
            try {

                BoundingCircle bc = extent.getBoundingCircle();
                if (bc == null) {
                    discarded.add(extent);
                    return false;
                }

                Geo center = bc.getCenter();
                double clon = center.getLongitude();
                double clat = center.getLatitude();
                double rnm = Geo.nm(bc.getRadius());

                if ((clat == 90.0 && clon == -180.0) || rnm >= 90 * 60) {
                    discarded.add(extent);
                } else {
                    all.add(extent); // add to the everything list

                    // we need to project the radius away from the
                    // center at the latitude, NOT at the equator!
                    double latfactor = Geo.npdAtLat(clat);
                    if (latfactor == 0) {
                        polar.add(extent);
                        ret = true;
                    } else {
                        double xd = (rnm + margin) / latfactor;
                        /*
                         * margin = xd "extra degrees" at the center's latitude
                         */
                        if (xd >= 45) {
                            polar.add(extent);
                            ret = true;
                        } else {
                            double[] lons = normalizeLons(new double[] {
                                    clon - xd, clon + xd });
                            int lb = bucketFor(lons[0]);
                            int rb = bucketFor(lons[1]);
                            if (rb < lb)
                                rb = rb + nbuckets;
                            for (int i = lb; i <= rb; i++) {
                                int x = i % nbuckets;
                                Collection b = buckets[x];
                                if (b == null) {
                                    b = makeBucket(5);
                                    buckets[x] = b;
                                }
                                b.add(extent);
                                ret = true;
                            }
                        }
                    }
                }
            } catch (Exception e) {
            }
            return ret;
        }

        /** normalize longitude to be at least 0.0 and less than 360 * */
        protected static final double normalizeLon(double lon) {
            // put it into the range of [-360.0, +360.0]
            double n = lon % 360;
            return (n < 0.0) ? n + 360.0 : n;
            // now n is (0.0,+360]
        }

        /**
         * figure out what bucket a particular longitude goes in.
         */
        protected final int bucketFor(double lon) {
            return (int) Math.floor(normalizeLon(lon) / 360.0
                    * (double) nbuckets);
        }

        /*
         * Normalize and sort the argument two element array so that on a
         * north-up globe, a great-circle arc between the points is headed
         * eastward and is less than half-way around the world. @param lons
         * two-element array on longitudes @return the mutated argument.
         */
        protected final static double[] normalizeLons(double[] lons) {
            double a = normalizeLon(lons[0]);
            double b = normalizeLon(lons[1]);
            // if wide and east or narrow and west, swap
            if ((Math.abs(b - a) > 180.0) == (b > a)) {
                lons[0] = b;
                lons[1] = a;
            } else {
                lons[0] = a;
                lons[1] = b;
            }
            return lons;
        }

        /**
         * Called when you want everything in each bucket between the
         * coordinates.
         * 
         * @param left left-most (west) bucket value.
         * @param right right-most (east) bucket value.
         * @return Iterator over regions in buckets that cover range provided.
         */
        protected Iterator lookup(double left, double right) {
            return lookup(left, right, null);