extentindeximpl.java

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

//**********************************************************************
//
//<copyright>
//
//BBN Technologies, a Verizon Company
//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: ExtentIndexImpl.java,v $
//$Revision: 1.1.2.4 $
//$Date: 2005/08/29 22:19:24 $
//$Author: dietrick $
//
//**********************************************************************

package com.bbn.openmap.geo;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * Separable indexed database for Regional BoundingCircles. This is
 * currently a simple longitude coverage map of the world, broken into
 * buckets covering 1 degrees. A given BoundingCircle will show up in
 * every bucket that it touches or comes within the margin.
 */
public class ExtentIndexImpl 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 List buckets[];

    /** all is a collection of everything successfully indexed. */
    protected final List all = new ArrayList(2000);
    /**
     * polar is a bucket for anything that is near enough to either
     * pole to cover more than 1/2 the buckets.
     */
    protected final List polar = new ArrayList();

    protected final List discarded = new ArrayList();

    public ExtentIndexImpl() {
        nbuckets = D_NBUCKETS;
        margin = D_MARGIN;
        buckets = new List[nbuckets];
    }

    public ExtentIndexImpl(int nb) {
        nbuckets = nb;
        margin = D_MARGIN;
        buckets = new List[nbuckets];
    }

    public ExtentIndexImpl(int nb, double m) {
        nbuckets = nb;
        margin = m;
        buckets = new List[nbuckets];
    }

    public ExtentIndexImpl(double m) {
        nbuckets = D_NBUCKETS;
        margin = m;
        buckets = new List[nbuckets];
    }

    /**
     * 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;
                            List b = buckets[x];
                            if (b == null) {
                                b = new ArrayList(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);
    }

    /**
     * Called when you want to get the regions in the buckets, but you
     * want to further filter on objects that can intersect based on
     * the bounding circle provided.
     * 
     * @param left left-most (west) bucket value.
     * @param right right-most (east) bucket value.
     * @param bc Bounding circle to do another filter check, if null,
     *        everything in a bucket will be returned.
     * @return Iterator over regions in buckets that cover range
     *         provided that intersect with the BoundingCircle (if one
     *         is provided).
     */
    protected Iterator lookup(double left, double right, BoundingCircle bc) {
        Set s = new HashSet();
        int lb = bucketFor(left);
        int rb = bucketFor(right);
        if (rb < lb)
            rb = rb + nbuckets;
        for (int i = lb; i <= rb; i++) {
            List b = buckets[i % nbuckets];
            if (b != null) {
                if (bc == null) {
                    s.addAll(b);
                } else {
                    for (Iterator it = b.iterator(); it.hasNext();) {
                        GeoRegion region = (GeoRegion) it.next();
                        if (bc.intersects(region.getBoundingCircle())) {
                            s.add(region);
                        }
                    }
                }
            }
        }
        s.addAll(polar); // add all the polar regions, just in case
        return s.iterator();
    }

    /**
     * Method to call to remove a region from the index.
     * 
     * @return true if the region was found and removed.
     */
    public boolean removeExtent(GeoExtent region) {
        boolean ret = false;
        try {

            BoundingCircle bc = region.getBoundingCircle();
            if (bc == null) {
                discarded.add(region);
                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.remove(region);
            } else {
                all.remove(region); // remove from 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.remove(region);
                    ret = true;
                } else {
                    double xd = (rnm + margin) / latfactor;
                    /*
                     * margin = xd "extra degrees" at the center's
                     * latitude
                     */
                    if (xd >= 45) {
                        polar.remove(region);
                        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;
                            List b = buckets[x];
                            if (b == null) {
                                b = new ArrayList(5);
                                buckets[x] = b;
                            }
                            b.remove(region);
                            ret = true;
                        }
                    }
                }
            }
        } catch (Exception e) {
        }
        return ret;
    }

    /**
     * Method to call to clear out the index.
     */
    public void clear() {
        all.clear();
        polar.clear();
        discarded.clear();
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] != null) {
                buckets[i].clear();
            }
        }
    }

    /**
     * RegionIndex parameter method.
     * 
     * @return horizontal range in nautical miles for matches.
     */
    public double indexHorizontalRange() {
        return margin;
    }

    public Iterator lookupBySegment(GeoSegment segment) {
        Geo[] pts = segment.getSeg();
        double[] lons = normalizeLons(new double[] { pts[0].getLongitude(),
                pts[1].getLongitude() });
        return lookup(lons[0], lons[1], segment.getBoundingCircle());
    }

    public Iterator lookupByPath(GeoPath path) {
        Set results = new HashSet();
        GeoPath.SegmentIterator pit = path.segmentIterator();
        while (pit.hasNext()) {
            GeoSegment seg = pit.nextSegment();
            for (Iterator it = lookupBySegment(seg); it.hasNext();) {
                results.add(it.next());
            }
        }
        return results.iterator();
    }

    public Iterator lookupByBoundingCircle(BoundingCircle bc) {
        double cLon = bc.getCenter().getLongitude();
        double rNM = Geo.nm(bc.getRadius()); // radius in nm at
        // equator
        double npd = Geo.npdAtLat(bc.getCenter().getLatitude());
        if (npd == 0) { // avoid divide by zero - polar region
            return iterator();
        } else {
            double rdeg = rNM / npd;
            if (rdeg >= 180) {
                return iterator(); // radius covers the whole world
            } else {
                return lookup(cLon - rdeg, cLon + rdeg, bc);
            }
        }
    }

    /**
     * @return an Iterator over BoundingCircle objects in the
     *         Collection where the GExtent may be related to them.
     */
    public Iterator iterator(GeoExtent o) {
        if (o instanceof GeoSegment) {
            return lookupBySegment((GeoSegment) o);
        } else if (o instanceof GeoPath) {
            return lookupByPath((GeoPath) o);
        } else if (o instanceof GeoPoint) {
            return lookupByBoundingCircle(new BoundingCircle.Impl(((GeoPoint) o).getPoint(), 0));
        } else {
            return lookupByBoundingCircle(o.getBoundingCircle());
        }
    }

    /**
     * @return Iterator over all entries in Collection.
     */
    public Iterator iterator() {
        return all.iterator();
    }

    /**
     * @return number of all entries in Collection.
     */
    public int size() {
        return all.size();
    }

    //
    // metrics
    //

    public String toString() {
        int entc = 0;
        int empties = 0;
        for (int i = 0; i < nbuckets; i++) {
            List l = buckets[i];
            if (l != null) {
                entc += l.size();
            } else {
                empties++;
            }
        }

        return "RegionIndexImpl[" + size() + " -" + discarded.size() + " E"
                + (entc / ((float) nbuckets)) + "]";
    }
}