latlonquadtree.java

world wind java sdk 源码

/*
Copyright (C) 2001, 2008 United States Government
as represented by the Administrator of the
National Aeronautics and Space Administration.
All Rights Reserved.
*/
package gov.nasa.worldwind.util;

import gov.nasa.worldwind.geom.LatLon;
import gov.nasa.worldwind.geom.Sector;

import java.util.ArrayList;

/**
 * This class handles the storage and retrieval of geographic objects inside a quadtree.
 *
 * @author Patrick Murris
 * @version $Id: LatLonQuadTree.java 5286 2008-05-05 07:35:54Z patrickmurris $
 */

public class LatLonQuadTree
{
    private static final Sector DEFAULT_SECTOR = Sector.FULL_SPHERE;
    private static final int DEFAULT_MAX_LIST_SIZE = 1000;
    private static final int DEFAULT_MAX_LEVELS = 9;

    private final Sector sector;
    private final int maxListSize;
    private final int maxLevels;

    ArrayList<LatLonEntry> entries;
    LatLonQuadTree[] childs;

    /**
     * Define a quadtree for the default <code>Sector</code> (full sphere), max list size (1000) and levels (9).
     */
    public LatLonQuadTree()
    {
        this(DEFAULT_SECTOR, DEFAULT_MAX_LIST_SIZE, DEFAULT_MAX_LEVELS);
    }

    /**
     * Define a quadtree for the given <code>Sector</code>, with the default max list size (1000) and levels (9).
     *
     * @param sector the <code>Sector</code> covered by this quadtree.
     * @throws IllegalArgumentException if <code>sector</code> is <code>null</code>.
     */
    public LatLonQuadTree(Sector sector)
    {
        this(sector, DEFAULT_MAX_LIST_SIZE, DEFAULT_MAX_LEVELS);
    }

    /**
     * Define a quadtree for the given <code>Sector</code>, max list size and levels.
     *
     * @param sector the <code>Sector</code> covered by this quadtree.
     * @param maxListSize the number of entries for one level before it splits to another level.
     * @param maxLevels the maximum number of levels. Must be greater or equal to one.
     * @throws IllegalArgumentException if <code>sector</code> is <code>null</code> or any of <code>maxListSize</code>
     * or <code>maxLevels</code> is smaller then one.
     */
    public LatLonQuadTree(Sector sector, int maxListSize, int maxLevels)
    {
        if (sector == null)
        {
            String msg = Logging.getMessage("nullValue.SectorIsNull");
            Logging.logger().severe(msg);
            throw new IllegalArgumentException(msg);
        }
        if (maxListSize < 1 || maxLevels < 1)
        {
            String msg = Logging.getMessage("generic.ArgumentOutOfRange");
            Logging.logger().severe(msg);
            throw new IllegalArgumentException(msg);
        }

        this.sector = sector;
        this.maxListSize = maxListSize;
        this.maxLevels = maxLevels;
    }

    public Sector getSector()
    {
        return this.sector;
    }

    public int getMaxListSize()
    {
        return this.maxListSize;
    }

    public int getMaxLevels()
    {
        return this.maxLevels;
    }

    private class LatLonEntry
    {
        private LatLon latLon;
        private Object object;

        public LatLonEntry(LatLon latLon, Object object)
        {
            this.latLon = latLon;
            this.object = object;
        }
    }

    /**
     * Add an object to the quadtree at a given <code>LatLon</code>. If the object was succesfully
     * inserted, returns a reference to the quadtree where the insertion occured. Returns <code>null</code>
     * if it failed (coordinates where likely outside of the quadtree sector).
     *
     * @param object the object reference to keep for the given lat-lon coordinates.
     * @param latLon the <code>LatLon</code> for the object.
     * @return a reference to the <code>LatLonQuadTree</code> where the object was inserted or null if the insertion failed.
     * @throws IllegalArgumentException if <code>object</code> or <code>latLon</code> is <code>null</code>.
     */
    public LatLonQuadTree add(Object object, LatLon latLon)
    {
        if (object == null)
        {
            String msg = Logging.getMessage("nullValue.ObjectIsNull");
            Logging.logger().severe(msg);
            throw new IllegalArgumentException(msg);
        }
        if (latLon == null)
        {
            String msg = Logging.getMessage("nullValue.LatLonIsNull");
            Logging.logger().severe(msg);
            throw new IllegalArgumentException(msg);
        }

        return add(new LatLonEntry(latLon, object));
    }

    private LatLonQuadTree add(LatLonEntry entry)
    {
        if (!this.sector.contains(entry.latLon))
            return null;

        if (this.entries == null)
            this.entries = new ArrayList<LatLonEntry>();

        if (this.childs == null && (this.entries.size() <= this.maxListSize || this.maxLevels == 1))
        {
            // Add entry at this level
            this.entries.add(entry);
            return this;
        }

        // This level is full and maxLevels > 1, add to childs
        if (this.childs == null)
            split();

        LatLonQuadTree qt;
        for (LatLonQuadTree child : childs)
            if ((qt = child.add(entry)) != null)
                   return qt;

        return null;
    }

    private void split()
    {
        // Create child quadtrees
        this.childs = new LatLonQuadTree[4];
        Sector[] sectors = this.sector.subdivide();
        this.childs[0] = new LatLonQuadTree(sectors[0], this.maxListSize, this.maxLevels - 1);
        this.childs[1] = new LatLonQuadTree(sectors[1], this.maxListSize, this.maxLevels - 1);
        this.childs[2] = new LatLonQuadTree(sectors[2], this.maxListSize, this.maxLevels - 1);
        this.childs[3] = new LatLonQuadTree(sectors[3], this.maxListSize, this.maxLevels - 1);

        // Pass entries to the children
        for (LatLonEntry entry : this.entries)
            for (LatLonQuadTree child : childs)
                if (child.add(entry) != null)
                       break;

        // Clear this level entries
        this.entries.clear();
    }

    /**
     * Get a list of objects in a given <code>Sector</code>.
     *
     * @param getSector the <code>Sector</code> encompassing the objects.
     * @return the list of objects contained in the given <code>Sector</code>.
     * @throws IllegalArgumentException if <code>sector</code> is <code>null</code>.
     */
    public ArrayList<Object> get(Sector getSector)
    {
        if (sector == null)
        {
            String msg = Logging.getMessage("nullValue.SectorIsNull");
            Logging.logger().severe(msg);
            throw new IllegalArgumentException(msg);
        }

        if (!this.sector.intersects(getSector))
            return null;

        if (this.entries == null)
            return null;

        ArrayList<Object> list = new ArrayList<Object>();
        ArrayList<Object> childList;
        if (this.childs != null)
        {
            // Get list from childs
            for (LatLonQuadTree child : childs)
                if ((childList = child.get(getSector)) != null)
                    list.addAll(childList);
        }
        else
        {
            // Compose list from this level entries
            if (this.sector.intersection(getSector).equals(this.sector))
            {
                // Whole quadtree is included, add all object
                for (LatLonEntry entry : this.entries)
                    list.add(entry.object);
            }
            else
            {
                // Quadtree is not completly included, test individual objects
                for (LatLonEntry entry : this.entries)
                    if (getSector.contains(entry.latLon))
                        list.add(entry.object);

            }
        }

        return list;
    }

    /**
     * Remove the given object from the quadtree.
     *
     * @param object the object to remove.
     * @param latLon the <code>LatLon</code> of the object when it was added.
     * @return a reference to the <code>LatLonQuadTree</code> where the removal occured or null if the object was not removed.
     * <p>Failure from removal arise if the given coordinates are outside the quadtree sector, or not the
     * ones used when the object was added, or the object was not found at this location.</p>
     * @throws IllegalArgumentException if <code>object</code> or <code>latLon</code> is <code>null</code>.
     */
    public LatLonQuadTree remove(Object object, LatLon latLon)
    {
        if (object == null)
        {
            String msg = Logging.getMessage("nullValue.ObjectIsNull");
            Logging.logger().severe(msg);
            throw new IllegalArgumentException(msg);
        }
        if (latLon == null)
        {
            String msg = Logging.getMessage("nullValue.LatLonIsNull");
            Logging.logger().severe(msg);
            throw new IllegalArgumentException(msg);
        }

        if (!this.sector.contains(latLon))
            return null;

        if (this.entries == null)
            return null;

        // Remove object from childs if any
        LatLonQuadTree qt;
        if (this.childs != null)
            for (LatLonQuadTree child : childs)
                if ((qt = child.remove(object, latLon)) != null)
                    return qt;

        // Remove object from local list
        for (int i = 0; i < entries.size(); i++)
            if (entries.get(i).object == object)
            {
                entries.remove(i);
                return this;
            }

        return null;
    }

    public String toString()
    {
        String s = "LatLonQuadTree: max Levels: " + maxLevels + ", entries: "
                + (entries != null ? entries.size() : "0") + " " + sector;
        if (childs != null)
            for (LatLonQuadTree child : childs)
                s += "\n" + child.toString();
        return s;
    }

    // Tests
    public static void main(String[] args)
    {
        LatLonQuadTree qt = new LatLonQuadTree();
        long startTime, elapsedTime;

        // Test addition
        long numEntries = (long)1e6; // one million entries
        System.out.println("Adding " + numEntries + " entries...");
        startTime = System.nanoTime();
        for (int i = 0; i < 1e6; i++)
        {
            LatLon ll = LatLon.fromDegrees(Math.random() * 180 - 90, Math.random() * 360 - 180);
            qt.add(ll, ll);
        }
        elapsedTime = System.nanoTime() - startTime;
        System.out.println("Elapsed: " + elapsedTime / (long)1e3 + " micro sec. (average " + elapsedTime / numEntries + " ns)");
        System.out.println(qt);

        // Test query
        Sector getSector = Sector.fromDegrees(0, 15, -100, -80);
        startTime = System.nanoTime();
        ArrayList<Object> list = qt.get(getSector);
        elapsedTime = System.nanoTime() - startTime;
        if (list != null)
            System.out.println(list.size() + " objects found inside " + getSector + " in " + elapsedTime / (long)1e3 + " micro sec.");
        else
            System.out.println("No object found inside " + getSector);

        // Test removal
        if (list != null)
        {
            System.out.println("Removing found objects...");
            for (Object o : list)
                qt.remove(o, (LatLon)o);

            // Query again - should yield zero
            startTime = System.nanoTime();
            list = qt.get(getSector);
            elapsedTime = System.nanoTime() - startTime;
            if (list != null)
                System.out.println(list.size() + " objects found inside " + getSector + " in " + elapsedTime / (long)1e3 + " micro sec.");
            else
                System.out.println("No object found inside " + getSector);
        }


    }

}