spatialtree.java

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

            this.item = item;
            this.sector = sector;
        }

        protected boolean intersects(Sector s)
        {
            return this.sector.intersects(s);
        }
    }

    public static class SectorTree<S, T> extends SpatialTree<Sector, ItemInfo<T>> // TODO: untested
    {
        public SectorTree(int maxDepth) // TODO: arg check
        {
            this(Sector.FULL_SPHERE, 0, maxDepth, false);
        }

        public SectorTree(Sector coverage, int maxDepth, boolean addToAllLevels) // TODO: arg check
        {
            this(coverage, 0, maxDepth, addToAllLevels);
        }

        protected SectorTree(Sector coverage, int depth, int maxDepth, boolean addToAllLevels)
        {
            super(coverage, depth, maxDepth, addToAllLevels);
        }

        protected SpatialTree<Sector, ItemInfo<T>> createInstance(Sector sector, int depth, int maxDepth,
                                                                  boolean addToAllLevels)
        {
            return new SectorTree<S, T>(sector, depth, maxDepth, addToAllLevels);
        }

        protected boolean intersects(Sector sector, ItemInfo<T> item)
        {
            return sector.intersects(item.sector);
        }

        protected boolean intersectsCoverage(Sector sector1, Sector sector2)
        {
            return sector1.intersects(sector2);
        }

        protected boolean contains(Sector extent, LatLon location)
        {
            return extent.contains(location);
        }

        protected ArrayList<Sector> subdivide(Sector extent, int rows, int cols)
        {
            ArrayList<Sector> children = new ArrayList<Sector>(rows * cols);

            double width = extent.getDeltaLon().degrees / cols;
            double height = extent.getDeltaLat().degrees / rows;

            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < cols; col++)
                {
                    children.add(Sector.fromDegrees(
                        extent.getMinLatitude().degrees + row * height,
                        extent.getMinLatitude().degrees + (row + 1) * height,
                        extent.getMinLongitude().degrees + col * width,
                        extent.getMinLongitude().degrees + (col + 1) * width));
                }
            }

            return children;
        }
    }

    public static class LocationTree extends SpatialTree<Sector, LatLon>
    {
        public LocationTree(int maxDepth) // TODO: arg check
        {
            this(Sector.FULL_SPHERE, 0, maxDepth, false);
        }

        public LocationTree(Sector coverage, int maxDepth, boolean addToAllLevels) // TODO: arg check
        {
            super(coverage, 0, maxDepth, addToAllLevels);
        }

        protected LocationTree(Sector coverage, int depth, int maxDepth, boolean addToAllLevels)
        {
            super(coverage, depth, maxDepth, addToAllLevels);
        }

        protected SpatialTree<Sector, LatLon> createInstance(Sector sector, int depth, int maxDepth,
                                                             boolean addToAllLevels)
        {
            return new LocationTree(sector, depth, maxDepth, addToAllLevels);
        }

        protected boolean intersects(Sector sector, LatLon location)
        {
            return sector.contains(location);
        }

        protected boolean intersectsCoverage(Sector sector1, Sector sector2)
        {
            return sector1.intersects(sector2);
        }

        protected boolean contains(Sector extent, LatLon location)
        {
            return extent.contains(location);
        }

        protected ArrayList<Sector> subdivide(Sector extent, int rows, int cols)
        {
            ArrayList<Sector> children = new ArrayList<Sector>(rows * cols);

            double width = extent.getDeltaLon().degrees / cols;
            double height = extent.getDeltaLat().degrees / rows;

            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < cols; col++)
                {
                    children.add(Sector.fromDegrees(
                        extent.getMinLatitude().degrees + row * height,
                        extent.getMinLatitude().degrees + (row + 1) * height,
                        extent.getMinLongitude().degrees + col * width,
                        extent.getMinLongitude().degrees + (col + 1) * width));
                }
            }

            return children;
        }
    }

    public static class MarkerTree extends SpatialTree<Sector, Marker>
    {
        public MarkerTree(int maxDepth) // TODO: arg check
        {
            this(Sector.FULL_SPHERE, 0, maxDepth, false);
        }

        public MarkerTree(Sector coverage, int maxDepth, boolean addToAllLevels) // TODO: arg check
        {
            super(coverage, 0, maxDepth, addToAllLevels);
        }

        protected MarkerTree(Sector coverage, int depth, int maxDepth, boolean addToAllLevels)
        {
            super(coverage, depth, maxDepth, addToAllLevels);
        }

        protected SpatialTree<Sector, Marker> createInstance(Sector sector, int depth, int maxDepth,
                                                             boolean addToAllLevels)
        {
            return new MarkerTree(sector, depth, maxDepth, addToAllLevels);
        }

        protected boolean intersects(Sector sector, Marker location)
        {
            return sector.contains(location.getPosition());
        }

        protected boolean intersectsCoverage(Sector sector1, Sector sector2)
        {
            return sector1.intersects(sector2);
        }

        protected boolean contains(Sector extent, LatLon location)
        {
            return extent.contains(location);
        }

        protected ArrayList<Sector> subdivide(Sector extent, int rows, int cols)
        {
            ArrayList<Sector> children = new ArrayList<Sector>(rows * cols);

            double width = extent.getDeltaLon().degrees / cols;
            double height = extent.getDeltaLat().degrees / rows;

            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < cols; col++)
                {
                    children.add(Sector.fromDegrees(
                        extent.getMinLatitude().degrees + row * height,
                        extent.getMinLatitude().degrees + (row + 1) * height,
                        extent.getMinLongitude().degrees + col * width,
                        extent.getMinLongitude().degrees + (col + 1) * width));
                }
            }

            return children;
        }
    }
}
//
//    public static void main(String[] args)
//    {
//        int minLat = 23, maxLat = 50, latDelta = 1;
//        int minLon = -130, maxLon = -70, lonDelta = 1;
//        int depth = 3;
//        LocationTree tree = new LocationTree(Sector.fromDegrees(minLat, maxLat, minLon, maxLon), depth, false);
//
//        int count = 0;
//        int iterCount = 1;
//        long start = System.currentTimeMillis();
//        for (int i = 0; i < iterCount; i++)
//        {
////            SpatialTree<Sector, ItemInfo<String>> tree = new MySectorTree<ItemInfo<String>>(5);
////
////            for (int lat = minLat; lat <= maxLat; lat += latDelta)
////            {
////                for (int lon = minLon; lon <= maxLon; lon += lonDelta)
////                {
////                    tree.add(new ItemInfo<String>(Sector.fromDegrees(lon, lat, lon + lonDelta, lat + latDelta), ""));
////                    ++count;
////                }
////            }
//            count = 0;
//            for (int lat = minLat; lat <= maxLat; lat += latDelta)
//            {
//                for (int lon = minLon; lon <= maxLon; lon += lonDelta)
//                {
////                    double latt = lat + 0.9 * latDelta; double lonn = lon + 0.9 * lonDelta;
//                    tree.add(LatLon.fromDegrees(lat, lon));
//                    ++count;
////                    System.out.printf("Count %d, %d, %s\n", count, tree.getAll().size(), LatLon.fromDegrees(latt, lonn));
//                }
//            }
//        }
//
//        System.out.println("Fill: " + (System.currentTimeMillis() - start) + " ms for " + iterCount + " iterations and "
//                           + count + " locations, depth " + depth);
//
//        System.out.println(tree.getAll().size() + " items");
//        Collection<LatLon> cc = tree.getItems(Sector.fromDegrees(minLat, maxLat, minLon, maxLon));
//        System.out.println("Full sector count " + cc.size());
//
//        start = System.currentTimeMillis();
//        for (int i = 0; i < iterCount; i++)
//        {
//            count = 0;
//            double lateps = 0;
//            for (int lat = minLat; lat < maxLat; lat += latDelta)
//            {
//                double loneps = 0;
//                for (int lon = minLon; lon < maxLon; lon += lonDelta)
//                {
//                    Collection<LatLon> c = tree.getItems(
//                        Sector.fromDegrees(lat + lateps, lat + latDelta, lon + loneps, lon + lonDelta));
//                    count += c.size();
//                    loneps = 0.000001;
//                }
//                lateps = 0.000001;
//            }
//        }
//
//        System.out.println("Find: " + (System.currentTimeMillis() - start) + " ms for " + iterCount + " iterations and "
//                           + count + " locations, depth " + depth);
//    }