spatialtree.java

来自「world wind java sdk 源码」· Java 代码 · 共 519 行 · 第 1/2 页

/*
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.Sector;
import gov.nasa.worldwind.geom.LatLon;
import gov.nasa.worldwind.render.markers.Marker;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * @author tag
 * @version $Id: SpatialTree.java 6036 2008-08-18 15:58:14Z tgaskins $
 */
public abstract class SpatialTree<S, T>
{
    protected int depth;
    protected int maxDepth;
    protected boolean addToAllLevels;
    protected S coverage;
    protected List<S> subCoverage;
    protected ArrayList<SpatialTree<S, T>> children;
    protected List<T> items = new ArrayList<T>();

    protected abstract boolean intersects(S extent, T item);

    protected abstract boolean intersectsCoverage(S extent1, S extent2);

    protected abstract SpatialTree<S, T> createInstance(S extent, int depth, int maxDepth, boolean addToAllLevels);

    protected abstract boolean contains(S extent, LatLon location);

    protected abstract ArrayList<S> subdivide(S extent, int rows, int cols);

    public SpatialTree(S coverage, int depth, int maxDepth, boolean addToAllLevels) // TODO: arg check
    {
        this(coverage, depth, maxDepth, addToAllLevels, 2, 2);
    }

    public SpatialTree(S coverage, int depth, int maxDepth, boolean addToAllLevels, int rows,
                       int cols) // TODO: arg check
    {
        this.coverage = coverage;
        this.depth = depth;
        this.maxDepth = maxDepth;
        this.addToAllLevels = addToAllLevels;

        if (depth < maxDepth)
        {
            this.subCoverage = this.subdivide(this.coverage, rows, cols);
            children = new ArrayList<SpatialTree<S, T>>(rows * cols);
            for (int i = 0; i < rows * cols; i++)
                children.add(null);
        }
    }

    public boolean add(T item)
    {
        boolean success = false;

        if (depth == maxDepth || addToAllLevels)
        {
            success = maxDepthAdd(item);
        }

        if (depth < maxDepth)
        {
            success = normalAdd(item) || success;
        }

        return success;
    }

    protected boolean normalAdd(T item)
    {
        boolean success = false;

        for (int i = 0; i < subCoverage.size() && !success; i++)
        {
            if (this.intersects(subCoverage.get(i), item))
            {
                if (children.get(i) == null)
                {
                    children.set(i, this.createInstance(subCoverage.get(i), depth + 1, maxDepth, addToAllLevels));
                }
                success = children.get(i).add(item);
            }
        }

        return success;
    }

    protected boolean maxDepthAdd(T item)
    {
        return this.intersects(coverage, item) && items.add(item);
    }

    public boolean remove(Sector itemRegion, T item) // TODO: untested, arg check
    {
        boolean success = false;

        if (depth == maxDepth || addToAllLevels)
        {
            success = maxDepthRemove(item);
        }

        if (depth < maxDepth)
        {
            success = success && normalRemove(itemRegion, item);
        }

        return success;
    }

    protected boolean maxDepthRemove(T item) // TODO: untested
    {
        return items.remove(item);
    }

    protected boolean normalRemove(Sector itemRegion, T item) // TODO: untested
    {
        boolean success = false;
        for (int i = 0; i < subCoverage.size(); i++)
        {
            if (this.intersects(subCoverage.get(i), item))
            {
                if (children.get(i) == null)
                {
                    children.set(i, this.createInstance(subCoverage.get(i), depth + 1, maxDepth, addToAllLevels));
                }
                success = success || children.get(i).remove(itemRegion, item);
            }
        }
        return success;
    }

    public Collection<T> getItems(LatLon location, int depth, Collection<T> itemsOut) // TODO: untested, arg check
    {
        if (!this.contains(this.coverage, location))
        {
            return Collections.emptyList();
        }

        if (this.depth == depth)
        {
            return getAll(itemsOut);
        }
        else if (this.depth < depth)
        {
            for (int i = 0; i < subCoverage.size(); i++)
            {
                if (this.contains(subCoverage.get(i), location))
                {
                    SpatialTree<S, T> child = this.children.get(i);
                    if (child != null)
                    {
                        return child.getItems(location, depth, itemsOut);
                    }
                    return Collections.emptyList();
                }
            }
        }
        return Collections.emptyList();
    }

    public Collection<T> getItems(S extent, Collection<T> itemsOut) // TODO: arg check
    {
        // No interaction with this grid
        if (!this.intersectsCoverage(extent, coverage))
        {
            return Collections.emptyList();
        }

        // Check the case where the input rect equals the coverage area
        if (extent.equals(coverage))
        {
            return getAll(itemsOut);
        }

        if (itemsOut == null)
            itemsOut = new ArrayList<T>();

        // Max Depth Check
        if (this.depth == this.maxDepth)
        {
            for (T item : items)
            {
                if (this.intersects(extent, item))
                    itemsOut.add(item);
            }
        }
        else if (this.depth < this.maxDepth)
        {
            for (int i = 0; i < subCoverage.size(); i++)
            {
                if (intersectsCoverage(extent, subCoverage.get(i)) && children.get(i) != null)
                    children.get(i).getItems(extent, itemsOut);
            }
        }

        return itemsOut;
    }

    public Collection<T> getAll(Collection<T> itemsOut)
    {
        if (addToAllLevels)
        {
            return items;
        }
        else if (this.children == null)
        {
            return items;
        }
        {
            if (itemsOut == null)
                itemsOut = new ArrayList<T>();
            for (SpatialTree<S, T> quad : children)
            {
                if (quad != null)
                {
                    quad.getAll(itemsOut);
                }
            }

            return itemsOut;
        }
    }

    public int getDepth()
    {
        return this.depth;
    }

    public int getMaxDepth()
    {
        return this.maxDepth;
    }

    public S getCoverage()
    {
        return this.coverage;
    }

    private static class ItemInfo<T>
    {
        @SuppressWarnings({"FieldCanBeLocal", "UnusedDeclaration"})
        protected T item;
        protected Sector sector;

        @SuppressWarnings({"UnusedDeclaration"})
        protected ItemInfo(Sector sector, T item)
        {