import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
private void search(Bounds searchBounds, Collection<T> results) {
    if (!mBounds.intersects(searchBounds)) {
        return;
    }

    if (this.mChildren != null) {
        for (PointQuadTree<T> quad : mChildren) {
            quad.search(searchBounds, results);
        }
    } else if (mItems != null) {
        for (T item : mItems) {
            if (searchBounds.contains(item.getPoint())) {
                results.add(item);
            }
        }
    }
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
private void search(Bounds searchBounds, Collection<T> results) {
    if (!mBounds.intersects(searchBounds)) {
        return;
    }

    if (this.mChildren != null) {
        for (PointQuadTree<T> quad : mChildren) {
            quad.search(searchBounds, results);
        }
    } else if (mItems != null) {
        if (searchBounds.contains(mBounds)) {
         results.addAll(mItems);
        } else {
            for (T item : mItems) {
                if (searchBounds.contains(item.getPoint())) {
                    results.add(item);
                }
            }
        }
    }
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
/**
 * Runs a test with 100,000 points.
 * Timing results are averaged.
 */
public void testRandomPoints() {
    Random random = new Random();
    for (int i = 0; i < 100000; i++) {
        mTree.add(new Item(random.nextDouble(), random.nextDouble()));
    }
    searchAll();

    mTree.search(new Bounds(0, 0.5, 0, 0.5));
    mTree.search(new Bounds(0, 0.25, 0, 0.25));
    mTree.search(new Bounds(0, 0.125, 0, 0.125));
    mTree.search(new Bounds(0, 0.999, 0, 0.999));
    mTree.search(new Bounds(0, 1, 0, 0.01));
    mTree.search(new Bounds(0.4, 0.6, 0.4, 0.6));
    mTree.search(new Bounds(0.356, 0.574, 0.678, 0.987));
    mTree.search(new Bounds(0.123, 0.456, 0.456, 0.789));
    mTree.search(new Bounds(0.111, 0.222, 0.333, 0.444));

    mTree.clear();
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
public List<T> search(LatLngBounds latLngBounds) {
    Point ne = PROJECTION.toPoint(latLngBounds.northeast);
    Point sw = PROJECTION.toPoint(latLngBounds.southwest);

    Bounds searchBounds = new Bounds(Math.min(ne.x, sw.x), Math.max(ne.x, sw.x), Math.min(ne.y, sw.y), Math.max(ne.y, sw.y));

    final List<T> items = new ArrayList<T>();
    synchronized (mQuadTree) {
        Collection<SpatialDataSource.QuadItem<T>> found = mQuadTree.search(searchBounds);
        for (SpatialDataSource.QuadItem<T> quadItem : found) {
            items.add(quadItem.getClusterItem());
        }
    }
    return items;
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
private Bounds createBoundsFromSpan(Point p, double span) {
    // TODO: Use a span that takes into account the visual size of the marker, not just its LatLng.
    double halfSpan = span / 2;
    return new Bounds(
            p.x - halfSpan, p.x + halfSpan,
            p.y - halfSpan, p.y + halfSpan);
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
private Bounds getVisibleBounds(int zoom) {
    if (mMapCenter == null) {
        return new Bounds(0, 0, 0, 0);
    }

    Point p = mDataSource.toPoint(mMapCenter);

    final double halfWidthSpan = mScreenWidth / Math.pow(2, zoom) / 256 / 2;
    final double halfHeightSpan = mScreenHeight / Math.pow(2, zoom) / 256 / 2;

    return new Bounds(
            p.x - halfWidthSpan, p.x + halfWidthSpan,
            p.y - halfHeightSpan, p.y + halfHeightSpan);
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
private Bounds createBoundsFromSpan(Point p, double span) {
    // TODO: Use a span that takes into account the visual size of the marker, not just its
    // LatLng.
    double halfSpan = span / 2;
    return new Bounds(
            p.x - halfSpan, p.x + halfSpan,
            p.y - halfSpan, p.y + halfSpan);
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
public void testSearch() {
    for (int i = 0; i < 10000; i++) {
        mTree.add(new Item(i / 20000.0, i / 20000.0));
    }

    assertEquals(10000, searchAll().size());
    assertEquals(1, mTree.search(new Bounds((double) 0, 0.00001, (double) 0, 0.00001)).size());
    assertEquals(0, mTree.search(new Bounds(.7, .8, .7, .8)).size());
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
public void testFourPoints() {
    mTree.add(new Item(0.2, 0.2));
    mTree.add(new Item(0.7, 0.2));
    mTree.add(new Item(0.2, 0.7));
    mTree.add(new Item(0.7, 0.7));

    assertEquals(2, mTree.search(new Bounds(0.0, 0.5, 0.0, 1.0)).size());
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
/**
 * Tests 30,000 items at the same point.
 * Timing results are averaged.
 */
public void testVeryDeepTree() {
    for (int i = 0; i < 30000; i++) {
        mTree.add(new Item(0, 0));
    }

    assertEquals(30000, searchAll().size());
    assertEquals(30000, mTree.search(new Bounds(0, .1, 0, .1)).size());
    assertEquals(0, mTree.search(new Bounds(.1, 1, .1, 1)).size());

    mTree.clear();
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
/**
 * Tests 400,000 points relatively uniformly distributed across the space.
 * Timing results are averaged.
 */
public void testManyPoints() {
    for (double i = 0; i < 200; i++) {
        for (double j = 0; j < 2000; j++) {
            mTree.add(new Item(i / 200.0, j / 2000.0));
        }
    }

    // searching bounds that are exact subtrees of the main quadTree
    assertEquals(400000, searchAll().size());
    assertEquals(100000, mTree.search(new Bounds(0, .5, 0, .5)).size());
    assertEquals(100000, mTree.search(new Bounds(.5, 1, 0, .5)).size());
    assertEquals(25000, mTree.search(new Bounds(0, .25, 0, .25)).size());
    assertEquals(25000, mTree.search(new Bounds(.75, 1, .75, 1)).size());

    // searching bounds that do not line up with main quadTree
    assertEquals(399600, mTree.search(new Bounds(0, 0.999, 0, 0.999)).size());
    assertEquals(4000, mTree.search(new Bounds(0.8, 0.9, 0.8, 0.9)).size());
    assertEquals(4000, mTree.search(new Bounds(0, 1, 0, 0.01)).size());
    assertEquals(16000, mTree.search(new Bounds(0.4, 0.6, 0.4, 0.6)).size());

    // searching bounds that are small / have very exact end points
    assertEquals(1, mTree.search(new Bounds(0, .001, 0, .0001)).size());
    assertEquals(26574, mTree.search(new Bounds(0.356, 0.574, 0.678, 0.987)).size());
    assertEquals(44622, mTree.search(new Bounds(0.123, 0.456, 0.456, 0.789)).size());
    assertEquals(4884, mTree.search(new Bounds(0.111, 0.222, 0.333, 0.444)).size());

    mTree.clear();
    assertEquals(0, searchAll().size());
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
/**
 * Tests 400,000 points relatively uniformly distributed across the space.
 * Timing results are averaged.
 */
public void testManyPoints() {
    for (double i = 0; i < 200; i++) {
        for (double j = 0; j < 2000; j++) {
            mTree.add(new Item(i / 200.0, j / 2000.0));
        }
    }

    // searching bounds that are exact subtrees of the main quadTree
    assertEquals(400000, searchAll().size());
    assertEquals(100000, mTree.search(new Bounds(0, .5, 0, .5)).size());
    assertEquals(100000, mTree.search(new Bounds(.5, 1, 0, .5)).size());
    assertEquals(25000, mTree.search(new Bounds(0, .25, 0, .25)).size());
    assertEquals(25000, mTree.search(new Bounds(.75, 1, .75, 1)).size());

    // searching bounds that do not line up with main quadTree
    assertEquals(399800, mTree.search(new Bounds(0, 0.999, 0, 0.999)).size());
    assertEquals(4221, mTree.search(new Bounds(0.8, 0.9, 0.8, 0.9)).size());
    assertEquals(4200, mTree.search(new Bounds(0, 1, 0, 0.01)).size());
    assertEquals(16441, mTree.search(new Bounds(0.4, 0.6, 0.4, 0.6)).size());

    // searching bounds that are small / have very exact end points
    assertEquals(1, mTree.search(new Bounds(0, .001, 0, .0001)).size());
    assertEquals(26617, mTree.search(new Bounds(0.356, 0.574, 0.678, 0.987)).size());
    assertEquals(44689, mTree.search(new Bounds(0.123, 0.456, 0.456, 0.789)).size());
    assertEquals(4906, mTree.search(new Bounds(0.111, 0.222, 0.333, 0.444)).size());

    mTree.clear();
    assertEquals(0, searchAll().size());
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
@Override
public Set<? extends Cluster<T>> getClusters(double zoom) {
    final int discreteZoom = (int) zoom;

    final double zoomSpecificSpan = MAX_DISTANCE_AT_ZOOM / Math.pow(2, discreteZoom) / 256;

    final HashSet<SpatialDataSource.QuadItem<T>> visitedCandidates = new HashSet<>();
    final Set<Cluster<T>> resultClusters = new HashSet<>();
    final Map<SpatialDataSource.QuadItem<T>, Double> minDistanceToCluster = new HashMap<>();
    final Map<SpatialDataSource.QuadItem<T>, StaticCluster<T>> itemToClusterMapping = new HashMap<>();

    synchronized (mDataSource) {

        Bounds visibleBounds = getVisibleBounds(discreteZoom);

        // first, find all visible nodes
        Collection<SpatialDataSource.QuadItem<T>> visibleNodes = mDataSource.search(visibleBounds);

        for (SpatialDataSource.QuadItem<T> candidate : visibleNodes) {
            // Candidate is already part of a cluster, nothing to do for it
            if (visitedCandidates.contains(candidate)) {
                continue;
            }

            // search items close to this node
            Bounds searchBounds = createBoundsFromSpan(candidate.getPoint(), zoomSpecificSpan);
            Collection<SpatialDataSource.QuadItem<T>> nearbyNodes= mDataSource.search(searchBounds);

            if (nearbyNodes.size() == 1) {
                // Only the current marker is in range. Just add the single item to the resultClusters.
                resultClusters.add(candidate);
                visitedCandidates.add(candidate);
                minDistanceToCluster.put(candidate, 0d); // 0d = its at the center of its N=1 cluster
                continue;
            }

            // build a new cluster around this node
            StaticCluster<T> cluster = new StaticCluster<T>(candidate.getClusterItem().getPosition());
            resultClusters.add(cluster);

            for (SpatialDataSource.QuadItem<T> clusterItem : nearbyNodes) {
                Double existingDistance = minDistanceToCluster.get(clusterItem);
                double distance = distanceSquared(clusterItem.getPoint(), candidate.getPoint());

                boolean itemBelongsToAnotherCluster = existingDistance != null;
                if (itemBelongsToAnotherCluster) {
                    boolean isAlreadyInCloserCluster = existingDistance < distance;
                    if (isAlreadyInCloserCluster) {
                        continue;
                    }

                    // remove item from current cluster
                    itemToClusterMapping.get(clusterItem).remove(clusterItem.getClusterItem());
                }

                minDistanceToCluster.put(clusterItem, distance); // update min distance
                cluster.add(clusterItem.getClusterItem()); // add to new cluster
                itemToClusterMapping.put(clusterItem, cluster); // record mapping
            }

            // record all nearbyNodes as visited
            visitedCandidates.addAll(nearbyNodes);
        }
    }
    return resultClusters;
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
@Override
public Set<? extends Cluster<T>> getClusters(double zoom) {
    final int discreteZoom = (int) zoom;

    final double zoomSpecificSpan = MAX_DISTANCE_AT_ZOOM / Math.pow(2, discreteZoom) / 256;

    final Set<QuadItem<T>> visitedCandidates = new HashSet<QuadItem<T>>();
    final Set<Cluster<T>> results = new HashSet<Cluster<T>>();
    final Map<QuadItem<T>, Double> distanceToCluster = new HashMap<QuadItem<T>, Double>();
    final Map<QuadItem<T>, StaticCluster<T>> itemToCluster = new HashMap<QuadItem<T>, StaticCluster<T>>();

    synchronized (mQuadTree) {
        for (QuadItem<T> candidate : mItems) {
            if (visitedCandidates.contains(candidate)) {
                // Candidate is already part of another cluster.
                continue;
            }

            Bounds searchBounds = createBoundsFromSpan(candidate.getPoint(), zoomSpecificSpan);
            Collection<QuadItem<T>> clusterItems;
            clusterItems = mQuadTree.search(searchBounds);
            if (clusterItems.size() == 1) {
                // Only the current marker is in range. Just add the single item to the results.
                results.add(candidate);
                visitedCandidates.add(candidate);
                distanceToCluster.put(candidate, 0d);
                continue;
            }
            StaticCluster<T> cluster = new StaticCluster<T>(candidate.mClusterItem.getPosition());
            results.add(cluster);

            for (QuadItem<T> clusterItem : clusterItems) {
                Double existingDistance = distanceToCluster.get(clusterItem);
                double distance = distanceSquared(clusterItem.getPoint(), candidate.getPoint());
                if (existingDistance != null) {
                    // Item already belongs to another cluster. Check if it's closer to this cluster.
                    if (existingDistance < distance) {
                        continue;
                    }
                    // Move item to the closer cluster.
                    itemToCluster.get(clusterItem).remove(clusterItem.mClusterItem);
                }
                distanceToCluster.put(clusterItem, distance);
                cluster.add(clusterItem.mClusterItem);
                itemToCluster.put(clusterItem, cluster);
            }
            visitedCandidates.addAll(clusterItems);
        }
    }
    return results;
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
public PointQuadTree(Bounds bounds) {
    this(bounds, 0);
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
/**
 * Calculate a reasonable maximum intensity value to map to maximum color intensity
 *
 * @param points    Collection of LatLngs to put into buckets
 * @param bounds    Bucket boundaries
 * @param radius    radius of convolution
 * @param screenDim larger dimension of screen in pixels (for scale)
 * @return Approximate max value
 */
static double getMaxValue(Collection<WeightedLatLng> points, Bounds bounds, int radius,
                          int screenDim) {
    // Approximate scale as if entire heatmap is on the screen
    // ie scale dimensions to larger of width or height (screenDim)
    double minX = bounds.minX;
    double maxX = bounds.maxX;
    double minY = bounds.minY;
    double maxY = bounds.maxY;
    double boundsDim = (maxX - minX > maxY - minY) ? maxX - minX : maxY - minY;

    // Number of buckets: have diameter sized buckets
    int nBuckets = (int) (screenDim / (2 * radius) + 0.5);
    // Scaling factor to convert width in terms of point distance, to which bucket
    double scale = nBuckets / boundsDim;

    // Make buckets
    // Use a sparse array - use LongSparseArray just in case
    LongSparseArray<LongSparseArray<Double>> buckets = new LongSparseArray<LongSparseArray<Double>>();
    //double[][] buckets = new double[nBuckets][nBuckets];

    // Assign into buckets + find max value as we go along
    double x, y;
    double max = 0;
    for (WeightedLatLng l : points) {
        x = l.getPoint().x;
        y = l.getPoint().y;

        int xBucket = (int) ((x - minX) * scale);
        int yBucket = (int) ((y - minY) * scale);

        // Check if x bucket exists, if not make it
        LongSparseArray<Double> column = buckets.get(xBucket);
        if (column == null) {
            column = new LongSparseArray<Double>();
            buckets.put(xBucket, column);
        }
        // Check if there is already a y value there
        Double value = column.get(yBucket);
        if (value == null) {
            value = 0.0;
        }
        value += l.getIntensity();
        // Yes, do need to update it, despite it being a Double.
        column.put(yBucket, value);

        if (value > max) max = value;
    }

    return max;
}
 

import com.google.maps.android.geometry.Bounds; //导入依赖的package包/类
private Collection<Item> searchAll() {
    return mTree.search(new Bounds(0, 1, 0, 1));
}