sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject [sis] 04/04: Refactor QuadTree: - Remove the assumption that coordinates are geographic. - Remove hard-coded constants for Earth radius. - Remove requirement that values implement QuadTreeData. - Allow any kind of Object specified by generic type. - Perform search with parallelizable streams. - Prepare for generalization to k-dimensions.
Date Tue, 14 Jan 2020 13:29:23 GMT
This is an automated email from the ASF dual-hosted git repository.

desruisseaux pushed a commit to branch geoapi-4.0
in repository https://gitbox.apache.org/repos/asf/sis.git

commit e4dba0713c7b5216a160f9e9ce7eef7b219400f7
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Sat Jan 11 12:25:05 2020 +0100

    Refactor QuadTree:
    - Remove the assumption that coordinates are geographic.
    - Remove hard-coded constants for Earth radius.
    - Remove requirement that values implement QuadTreeData.
    - Allow any kind of Object specified by generic type.
    - Perform search with parallelizable streams.
    - Prepare for generalization to k-dimensions.
    
    The Quadrant enumeration is replaced by integer values because it can be generalized to k-dimensional case using bit shifts & masks.
    The extension to K-dimensional case will be the subject of a later commit.
---
 ide-project/NetBeans/nbproject/genfiles.properties |   2 +-
 ide-project/NetBeans/nbproject/project.xml         |   1 +
 .../sis/index/tree/{NodeType.java => KDTree.java}  |  26 +-
 .../java/org/apache/sis/index/tree/KDTreeNode.java |  84 +++
 .../apache/sis/index/tree/LatLonPointRadius.java   | 138 -----
 .../org/apache/sis/index/tree/NodeIterator.java    | 344 +++++++++++
 .../java/org/apache/sis/index/tree/QuadTree.java   | 663 ++++-----------------
 .../org/apache/sis/index/tree/QuadTreeData.java    |  59 --
 .../org/apache/sis/index/tree/QuadTreeNode.java    | 201 +++----
 .../java/org/apache/sis/index/tree/Quadrant.java   |  62 --
 .../org/apache/sis/index/tree/package-info.java    |   9 +-
 .../apache/sis/index/tree/QuadTreeNodeTest.java    |  56 ++
 .../org/apache/sis/index/tree/QuadTreeTest.java    | 145 +++++
 .../apache/sis/index/tree/TestQuadTreeNode.java    |  31 -
 .../apache/sis/test/suite/StorageTestSuite.java    |   4 +-
 15 files changed, 855 insertions(+), 970 deletions(-)

diff --git a/ide-project/NetBeans/nbproject/genfiles.properties b/ide-project/NetBeans/nbproject/genfiles.properties
index de86b0d..b988909 100644
--- a/ide-project/NetBeans/nbproject/genfiles.properties
+++ b/ide-project/NetBeans/nbproject/genfiles.properties
@@ -3,6 +3,6 @@
 build.xml.data.CRC32=58e6b21c
 build.xml.script.CRC32=462eaba0
 build.xml.stylesheet.CRC32=28e38971@1.53.1.46
-nbproject/build-impl.xml.data.CRC32=2eb6a452
+nbproject/build-impl.xml.data.CRC32=0881b25a
 nbproject/build-impl.xml.script.CRC32=27d6eb56
 nbproject/build-impl.xml.stylesheet.CRC32=f89f7d21@1.93.0.48
diff --git a/ide-project/NetBeans/nbproject/project.xml b/ide-project/NetBeans/nbproject/project.xml
index c77ad63..da775d0 100644
--- a/ide-project/NetBeans/nbproject/project.xml
+++ b/ide-project/NetBeans/nbproject/project.xml
@@ -124,6 +124,7 @@
             <word>programmatically</word>
             <word>recursivity</word>
             <word>scanline</word>
+            <word>splited</word>
             <word>spliterator</word>
             <word>subsampled</word>
             <word>subsampling</word>
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeType.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
similarity index 56%
rename from storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeType.java
rename to storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
index 65c164c..c3bfef5 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeType.java
+++ b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
@@ -16,13 +16,27 @@
  */
 package org.apache.sis.index.tree;
 
+
 /**
- * Enum to represent node type of quad tree. Black means node contains data.
- * White means node is empty. Gray means node is parent.
+ * Base class of <var>k</var>-dimensional tree index. For <var>k</var>=2, this is a {@link QuadTree}.
+ * For <var>k</var>=3, this is an {@code Octree}. Higher dimensions are also accepted.
+ *
+ * <h2>Thread-safety</h2>
+ * This class is not thread-safe when the tree content is modified. But if the tree is kept unmodified
+ * after construction, then multiple read operations in concurrent threads are safe.
+ *
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ *
+ * @param  <E>  the type of elements stored in this tree.
  *
- * <div class="warning"><b>Note on future work:</b> this enumeration may change in incompatible way
- * in a future Apache SIS release, or may be replaced by new API.</div>
+ * @since 1.1
+ * @module
  */
-public enum NodeType {
-  BLACK, WHITE, GRAY
+abstract class KDTree<E> {
+    /**
+     * Creates an initially empty tree.
+     */
+    KDTree() {
+    }
 }
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java
new file mode 100644
index 0000000..1692c35
--- /dev/null
+++ b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java
@@ -0,0 +1,84 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sis.index.tree;
+
+
+/**
+ * A node in a {@link KDTree} which is the parent of other nodes. The number of child nodes depends on
+ * the number of dimensions of the tree: 4 children with two-dimensional {@link QuadTree}, 8 children
+ * with three-dimensional {@code Octree}, <i>etc</i>. The child node can be another {@link KDTreeNode}
+ * if that node is itself the parent of more nodes. Otherwise (i.e. if the child node is leaf) the child
+ * is an instance of {@code Object[]}.
+ *
+ * <p>Features of arbitrary types are stored in {@code Object[]} arrays. Those arrays should be small:
+ * if the number of elements in a leaf exceeds a maximal capacity specified by the {@link KDTree},
+ * then the leaf is replaced by a new {@link KDTreeNode} and the {@code Object[]} content is distributed
+ * between the new child nodes.</p>
+ *
+ * <p>Addition of new features in {@code Object[]} arrays uses a <cite>copy-on-write</cite> strategy
+ * in order to keep memory usage minimal (a tree may have thousands of small arrays) and for making
+ * easier to ensure thread-safety during concurrent read/write operations.</p>
+ *
+ * <h2>Design note</h2>
+ * Trees may have huge amount of nodes. For that reason, the nodes should contain as few fields as possible.
+ * We should also avoid classes that are just wrappers around arrays. This is the reason why leaf nodes are
+ * stored directly as {@link Object[]} arrays instead than using a more object-oriented approach with some
+ * {@code TreeNodeLeaf} class.
+ *
+ * @author  Chris Mattmann
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ * @since   1.1
+ * @module
+ */
+abstract class KDTreeNode {
+    /**
+     * Constructs an initially empty {@link KDTree} node.
+     */
+    KDTreeNode() {
+    }
+
+    /**
+     * Default implementation of {@link KDTreeNode} when no specialized class is available.
+     * This default implementation stores children in an array. The usage of arrays allows
+     * arbitrary lengths, but implies one more object to be created for each node instance.
+     * Since this class should be used only for relatively large numbers of dimensions,
+     * the cost of arrays creation should be less significant compared to array length.
+     */
+    private static final class Default extends KDTreeNode {
+        /**
+         * The nodes or element values in each quadrant/octant of this node.
+         * Each array element can be null or an instance of one of those two classes:
+         *
+         * <ul>
+         *   <li>Another {@link KDTreeNode} if the node in a quadrant/octant is itself a parent of other children.</li>
+         *   <li>{@code Object[]} if the node in a quadrant/octant is a leaf. In such case, the array contains elements.
+         *       We do not wrap the leaf in another {@link KDTreeNode} for reducing the number of objects created.</li>
+         * </ul>
+         */
+        private final Object[] children;
+
+        /**
+         * Constructs an initially empty {@link KDTree} node.
+         *
+         * @param  n  must be 2<sup>k</sup> where <var>k</var> is the number of dimensions.
+         */
+        Default(final int n) {
+            children = new Object[n];
+        }
+    }
+}
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/LatLonPointRadius.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/LatLonPointRadius.java
deleted file mode 100644
index 82a0429..0000000
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/LatLonPointRadius.java
+++ /dev/null
@@ -1,138 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.sis.index.tree;
-
-import java.awt.geom.Area;
-import java.awt.geom.Path2D;
-import java.awt.geom.Rectangle2D;
-import org.opengis.geometry.DirectPosition;
-import org.apache.sis.measure.Longitude;
-import org.apache.sis.referencing.CommonCRS;
-import org.apache.sis.referencing.GeodeticCalculator;
-
-/**
- * Represents a 2D point associated with a radius to enable great circle
- * estimation on earth surface.
- */
-final class LatLonPointRadius {
-  private static final double HALF_EARTH_CIRCUMFERENCE = 20037.58; // in km
-
-  private final DirectPosition center;
-  private final double radius;
-
-  /**
-   * Creates a representation of point-radius search region.
-   *
-   * @param center
-   *          the center of the search region
-   * @param radius
-   *          the radius of the search region
-   */
-  LatLonPointRadius(DirectPosition center, double radius) {
-    this.center = center;
-    this.radius = radius;
-  }
-
-  /**
-   * Calculates the rectangular region enclosing the circular search region.
-   *
-   * @param numberOfPoints
-   *          the number of points used to estimate the circular search region
-   * @return Java Rectangle2D object that bounds the circlar search region
-   */
-  Rectangle2D getRectangularRegionApproximation(int numberOfPoints) {
-    if (radius >= HALF_EARTH_CIRCUMFERENCE) {
-      return new Rectangle2D.Double(0.0, 0.0, 360.0, 180.0);
-    }
-    int numberOfCrossOvers = 0;
-
-    final GeodeticCalculator calculator = GeodeticCalculator.create(CommonCRS.SPHERE.geographic());
-    calculator.setStartGeographicPoint(center.getOrdinate(1), center.getOrdinate(0));
-
-    Path2D path = new Path2D.Double();
-    double initX = Double.NaN, previousX = Double.NaN;
-    calculator.setGeodesicDistance(radius);
-    for (int i = 0; i < 360; i++) {
-      calculator.setStartingAzimuth(i);
-      DirectPosition pt = calculator.getEndPoint();
-      double x = pt.getOrdinate(1) + 180.0;
-      double y = pt.getOrdinate(0) + 90.0;
-      if (i == 0) {
-        initX = Longitude.normalize(x);
-        path.moveTo(x, y);
-      } else {
-        path.lineTo(x, y);
-        if (dateLineCrossOver(previousX, previousX = Longitude.normalize(x))) {
-          numberOfCrossOvers++;
-        }
-      }
-    }
-    if (dateLineCrossOver(previousX, initX)) {
-      numberOfCrossOvers++;
-    }
-    /**
-     * If the path crosses the dateline once, it's a special case, so take care
-     * of it differently. It will need to include areas around the pole.
-     */
-    if (numberOfCrossOvers == 1) {
-      Rectangle2D r = path.getBounds2D();
-      Rectangle2D lowerHalf = new Rectangle2D.Double(0.0, 0.0, 360.0, r.getMaxY());
-      if (lowerHalf.contains(center.getOrdinate(0) + 180.0, center.getOrdinate(1) + 90.0)) {
-        return lowerHalf;
-      } else {
-        return new Rectangle2D.Double(0.0, r.getMinY(), 360.0, 180.0 - r.getMinY());
-      }
-    }
-
-    if (path.contains(center.getOrdinate(0) + 180.0, center.getOrdinate(1) + 90.0)) {
-      Rectangle2D r = path.getBounds2D();
-      if ((r.getMaxX() - r.getMinX()) > 359.0) {
-        return new Rectangle2D.Double(0.0, 0.0, 360.0, 180.0);
-      } else if (r.getMinX() < 0 || r.getMaxX() > 360.0) {
-        /**
-         * For circles that crosses the dateline instead of splitting in half
-         * and having to go down the tree twice, for first version span
-         * longitude 360.0 and use the exact height of the box
-         */
-        return new Rectangle2D.Double(0.0, r.getY(), 360.0, r.getHeight());
-      } else {
-        return path.getBounds2D();
-      }
-    } else {
-      Area pathArea = new Area(path);
-      Area wholeMap = new Area(new Rectangle2D.Double(0.0, 0.0, 360.0, 180.0));
-      wholeMap.subtract(pathArea);
-      return wholeMap.getBounds2D();
-    }
-  }
-
-  /**
-   * Returns true if the line segment connecting the two specified longitudes
-   * crosses the international dateline.
-   *
-   * @param longitude1
-   *          first longitude
-   * @param longitude2
-   *          second longitude
-   * @return true if the line segment crosses the internation dateline, false
-   *         otherwise
-   */
-  private static boolean dateLineCrossOver(double longitude1, double longitude2) {
-    return (Math.abs(longitude1 - longitude2) > 180.0);
-  }
-}
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java
new file mode 100644
index 0000000..322e724
--- /dev/null
+++ b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/NodeIterator.java
@@ -0,0 +1,344 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sis.index.tree;
+
+import java.util.Spliterator;
+import java.util.function.Consumer;
+import java.awt.geom.Point2D;
+import java.awt.geom.Rectangle2D;
+import java.util.function.Function;
+
+
+/**
+ * An iterator over the elements contained in a {@link KDTreeNode}.
+ * The iterator applies a first filtering of elements by traversing only the nodes that <em>may</em>
+ * intersect the Area Of Interest (AOI). But after a node has been retained, an additional check for
+ * inclusion may be necessary. That additional check is performed by {@link #filter(Point2D)}
+ * and can be overridden by subclasses.
+ *
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ *
+ * @param  <E>  the type of elements stored in the {@link QuadTree}.
+ *
+ * @since 1.1
+ * @module
+ */
+class NodeIterator<E> implements Spliterator<E> {
+    /**
+     * Sentinel value meaning that iteration is over.
+     */
+    private static final Object[] FINISHED = new Object[0];
+
+    /**
+     * The function computing a position for an arbitrary element of this tree.
+     */
+    private final Function<? super E, ? extends Point2D> evaluator;
+
+    /**
+     * The region on which to iterate.
+     */
+    private final double xmin, ymin, xmax, ymax;
+
+    /**
+     * The object to use for updating the {@link #current} field, or {@code null} if none.
+     * This {@code NodeIterator} starts by returning elements in the {@link #current} array.
+     * When iteration over {@link #current} array is finished, {@code NodeIterator} uses the
+     * {@link Cursor} for changing the array reference to the next array. The iteration then
+     * continues until all leaf nodes intersecting the area of interest (AOI) have been traversed.
+     */
+    private Cursor<E> cursor;
+
+    /**
+     * The elements for a current quadrant/octant in current node. After iteration over this
+     * array is finished, this field is updated with elements for next quadrant/octant until
+     * all nodes have been traversed.
+     */
+    private Object[] current;
+
+    /**
+     * Index of the next element to return from the {@link #current} array.
+     */
+    private int nextIndex;
+
+    /**
+     * A cursor that can be recycled, or {@code null} if none. Used for reducing the number
+     * of {@link Cursor} allocations during tree traversal.
+     */
+    private Cursor<E> recycle;
+
+    /**
+     * Creates a new iterator for the specified bounding box.
+     */
+    @SuppressWarnings("ThisEscapedInObjectConstruction")
+    NodeIterator(final QuadTree<E> tree, final Rectangle2D region) {
+        evaluator = tree.evaluator;
+        xmin   = region.getMinX();
+        ymin   = region.getMinY();
+        xmax   = region.getMaxX();
+        ymax   = region.getMaxY();
+        cursor = new Cursor<>(tree);
+        cursor.findIntersections(this);
+        current = next();
+    }
+
+    /**
+     * A provider for arrays of elements of child nodes contained in a {@link KDTreeNode}.
+     * The starting point is {@link QuadTree#root}. A new {@link Cursor} instance is created
+     * for each level when the node at next level is itself a parent of at least two nodes
+     * (if there is only one child node, then this implementation takes a shortcut).
+     */
+    private static final class Cursor<E> {
+        /**
+         * The cursor that created this cursor, or {@code null} if none. If non-null, we will
+         * continue iteration with that parent after this {@link Cursor} finished to return
+         * all element arrays.
+         *
+         * <p>If this {@link Cursor} instance is not used anymore (for now) and is made available
+         * for recycling, then this field is instead used for storing the next recyclable instance
+         * that may be used after this one, with no child-parent relationship.</p>
+         */
+        private Cursor<E> parent;
+
+        /**
+         * The node for which to iterate over elements. Only the quadrants/octants identified
+         * by the {@link #quadrants} bitmask will be traversed.
+         */
+        QuadTreeNode node;
+
+        /**
+         * Bitmask of quadrants/octants on which to iterate. Quadrants/octants are iterated from rightmost
+         * bit to leftmost bit. Bits are cleared when the corresponding quadrant/octant become the current
+         * one. A value of 0 means that there is no more quadrant to iterate for the {@linkplain #node}.
+         *
+         * <p><b>Note:</b> we take "quadrant" name from {@link QuadTree}, but this algorithm can actually
+         * be used with more dimensions.</p>
+         */
+        int quadrants;
+
+        /**
+         * (<var>x</var>,<var>y</var>) coordinate in the center of {@link #node} node,
+         * and (<var>Δx</var>,<var>Δy</var>) size of the {@link #node} node.
+         */
+        private double cx, cy, dx, dy;
+
+        /**
+         * Creates a new cursor with all values initialized to zero.
+         * It is caller responsibility to initialize all fields.
+         */
+        private Cursor() {
+        }
+
+        /**
+         * Creates a new cursor initialized to the root node of the given tree.
+         */
+        Cursor(final QuadTree<E> tree) {
+            node = tree.root;
+            cx   = tree.centerX;
+            cy   = tree.centerY;
+            dx   = tree.width;
+            dy   = tree.height;
+        }
+
+        /**
+         * Computes a bitmask of all quadrants/octants that intersect the search area. This method
+         * must be invoked after {@link #cx}, {@link #cy}, {@link #dx}, {@link #dy} fields changed.
+         *
+         * @todo the computation performed in this method is not necessary when the caller knows that
+         *       the node is fully included in the AOI. We should carry a flag for this common case.
+         *
+         * @param  it  the iterator which defines the area of interest.
+         */
+        final void findIntersections(final NodeIterator<E> it) {
+            quadrants = (1 << 4) - 1;                                                               // Bits initially set for all quadrants.
+            if (!(it.xmin <= cx)) quadrants &= ~((1 << QuadTreeNode.NW) | (1 << QuadTreeNode.SW));  // Clear bits of all quadrant on West side.
+            if (!(it.xmax >= cx)) quadrants &= ~((1 << QuadTreeNode.NE) | (1 << QuadTreeNode.SE));  // Clear bits of all quadrant on East side.
+            if (!(it.ymin <= cy)) quadrants &= ~((1 << QuadTreeNode.SE) | (1 << QuadTreeNode.SW));  // Clear bits of all quadrant on South side.
+            if (!(it.ymax >= cy)) quadrants &= ~((1 << QuadTreeNode.NE) | (1 << QuadTreeNode.NW));  // Clear bits of all quadrant on North side.
+        }
+
+        /**
+         * Creates a new {@code Cursor} for getting element arrays in the {@linkplain #node} quadrant/octant,
+         * without changing the state of this {@code Cursor}. This method is invoked when there is a need to
+         * iterate in two more more children, in which case we can not yet discard the information contained
+         * in this {@code Cursor} instance.
+         *
+         * <p>Caller is responsible to update the {@link #node} field after this method call
+         * and to invoke {@link #findIntersections(NodeIterator)}.</p>
+         *
+         * @param  it  the enclosing iterator.
+         * @param  q   the quadrant/octant in which to iterate.
+         * @return the cursor to use for getting element arrays in the specified quadrant/octant.
+         */
+        final Cursor<E> push(final NodeIterator<E> it, final int q) {
+            Cursor<E> c = it.recycle;
+            if (c == null) {
+                c = new Cursor<>();
+            } else {
+                it.recycle = c.parent;
+            }
+            c.parent = this;
+            c.cx = cx + QuadTreeNode.factorX(q) * (c.dx = dx * 0.5);      // TODO: use Math.fma with JDK9.
+            c.cy = cy + QuadTreeNode.factorY(q) * (c.dy = dy * 0.5);
+            return c;
+        }
+
+        /**
+         * Changes the state of this {@code Cursor} for getting elements in the specified quadrant/octant.
+         * This method is invoked when there is no need to keep current {@code Cursor} information anymore,
+         * because there is no other quadrant/octant than the specified one in which to iterate.
+         *
+         * <p>Caller is responsible to update the {@link #node} field after this method call
+         * and to invoke {@link #findIntersections(NodeIterator)}.</p>
+         *
+         * @param  q  the quadrant/octant in which to iterate.
+         */
+        final void moveDown(final int q) {
+            cx += QuadTreeNode.factorX(q) * (dx *= 0.5);        // Center and size of the child node.
+            cy += QuadTreeNode.factorY(q) * (dy *= 0.5);
+        }
+
+        /**
+         * Marks this {@link Cursor} as available for recycling and returns its parent.
+         *
+         * @param  it  the enclosing iterator.
+         * @return the parent of this {@code Cursor}, or {@code null} if none.
+         */
+        final Cursor<E> getParentAndRecycle(final NodeIterator<E> it) {
+            final Cursor<E> p = parent;
+            parent = it.recycle;
+            it.recycle = this;
+            return p;
+        }
+    }
+
+    /**
+     * Returns an array of elements that <em>may</em> intersect the area of interest,
+     * or {@link #FINISHED} if the iteration is finished. This method does not verify
+     * if the points are really in the AOI; callers may need to filter the returned array.
+     *
+     * @return array of elements that may be in the area of interest (AOI),
+     *         or {@link #FINISHED} if the iteration is finished.
+     */
+    @SuppressWarnings("ReturnOfCollectionOrArrayField")
+    private Object[] next() {
+        while (cursor != null) {
+            while (cursor.quadrants != 0) {
+                final int q = Integer.numberOfTrailingZeros(cursor.quadrants);
+                cursor.quadrants &= ~(1 << q);
+                final Object child = cursor.node.getChild(q);
+                if (child != null) {
+                    if (child instanceof Object[]) {
+                        return (Object[]) child;
+                    }
+                    /*
+                     * Need to iterate down in at least one child. If the `quadrants` mask said that there is
+                     * maybe other children to check, build a chain of cursors for following the iterators of
+                     * all children.
+                     */
+                    if (cursor.quadrants != 0) {
+                        cursor = cursor.push(this, q);
+                    } else {
+                        /*
+                         * At this point we know that there is exactly one child. Redo the same analysis on
+                         * that unique child. This allows us to avoid consuming stack with recursive method
+                         * calls. This case is common at least at beginning of search, when the tree nodes
+                         * are still much bigger than the AOI.
+                         */
+                        cursor.moveDown(q);
+                    }
+                    cursor.node = (QuadTreeNode) child;
+                    cursor.findIntersections(this);
+                }
+            }
+            /*
+             * No more intersection in this node. Continue with parent node.
+             */
+            cursor = cursor.getParentAndRecycle(this);
+        }
+        return FINISHED;
+    }
+
+    /**
+     * If a remaining element exists, performs the given action on it and returns {@code true}.
+     * Otherwise returns {@code false}.
+     *
+     * @param  action  the action to execute on the next element.
+     * @return {@code false} if no remaining elements exist.
+     */
+    @Override
+    public final boolean tryAdvance(final Consumer<? super E> action) {
+        for (;;) {
+            while (nextIndex >= current.length) {
+                if (current == FINISHED) {
+                    return false;
+                }
+                current = next();
+                nextIndex = 0;
+            }
+            @SuppressWarnings("unchecked")
+            final E element = (E) current[nextIndex++];
+            if (filter(evaluator.apply(element))) {
+                action.accept(element);
+                return true;
+            }
+        }
+    }
+
+    /**
+     * Returns whether the given position is included in the search region.
+     * The default implementation verifies if the point is included in the bounding box.
+     * Subclasses may override, for example for restricting the points to a radius around a central location.
+     *
+     * @param  position  the position to check for inclusion.
+     * @return whether the position is in the search region.
+     */
+    protected boolean filter(final Point2D position) {
+        final double x = position.getX();
+        if (x >= xmin && x <= xmax) {
+            final double y = position.getY();
+            return (y >= ymin && y <= ymax);
+        }
+        return false;
+    }
+
+    /**
+     * If this iterator can be partitioned, returns an iterator covering a strict prefix of the elements.
+     *
+     * @todo Checks {@link Cursor#quadrants} and take half of the bits.
+     */
+    @Override
+    public final Spliterator<E> trySplit() {
+        return null;
+    }
+
+    /**
+     * Returns an estimate of the number of elements or {@link Long#MAX_VALUE} if too expensive to compute.
+     */
+    @Override
+    public final long estimateSize() {
+        return Long.MAX_VALUE;
+    }
+
+    /**
+     * Returns a set of characteristics of this iterator and its elements.
+     */
+    @Override
+    public final int characteristics() {
+        return ORDERED | NONNULL;
+    }
+}
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTree.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTree.java
index bda627c..22c4475 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTree.java
+++ b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTree.java
@@ -16,607 +16,168 @@
  */
 package org.apache.sis.index.tree;
 
+import java.util.stream.Stream;
+import java.util.function.Function;
+import java.awt.geom.Point2D;
 import java.awt.geom.Rectangle2D;
-import java.util.ArrayList;
-import java.util.List;
+import java.util.stream.StreamSupport;
+import org.apache.sis.util.ArgumentChecks;
 
-import org.apache.sis.geometry.DirectPosition2D;
-import org.apache.sis.geometry.Envelope2D;
-import org.apache.sis.referencing.CommonCRS;
-import org.apache.sis.referencing.GeodeticCalculator;
 
 /**
- * Implementation of Quad Tree Index. Insertion algorithm implemented based on
- * design of quad tree index in H. Samet, The Design and Analysis of Spatial
- * Data Structures. Massachusetts: Addison Wesley Publishing Company, 1989.
+ * Implementation of QuadTree Index.
+ * See {@link KDTree} for a note about thread-safety.
  *
- * <div class="warning"><b>Note on future work:</b> this class may change in
- * incompatible way in a future Apache SIS release, or may be replaced by new
- * API.</div>
+ * <p><b>References:</b></p>
+ * Insertion algorithm implemented based on design of QuadTree index
+ * in H. Samet, The Design and Analysis of Spatial Data Structures.
+ * Massachusetts: Addison Wesley Publishing Company, 1989.
+ *
+ * @author  Chris Mattmann
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ *
+ * @param  <E>  the type of elements stored in this tree.
+ *
+ * @since 0.1
+ * @module
  */
-public class QuadTree {
-
-    // assume map is shifted to be in positive coordinate
-    private static final double EARTH_MIN_X = 0;
-    private static final double EARTH_MIN_Y = 0;
-    private static final double EARTH_MAX_X = 360;
-    private static final double EARTH_MAX_Y = 180;
-    private static final double EARTH_MID_X = (EARTH_MAX_X - EARTH_MIN_X) / 2;
-    private static final double EARTH_MID_Y = (EARTH_MAX_Y - EARTH_MIN_Y) / 2;
-    private static final double[] xf = new double[] { -0.25, 0.25, -0.25, 0.25 };
-    private static final double[] yf = new double[] { 0.25, 0.25, -0.25, -0.25 };
-
-    private final QuadTreeNode root;
-    private int size;
-    private int nodeSize;
-
-    private int maxDepth;
-    private int capacity;
-
-    private final GeodeticCalculator calculator;
-
+public final class QuadTree<E> extends KDTree<E> {
     /**
-     * Creates a quad tree.
-     *
-     * @param capacity
-     *            the capacity of each node in the quad tree
-     * @param maxDepth
-     *            the maximum depth of the tree
+     * The root node of this QuadTree.
      */
-    public QuadTree(int capacity, int maxDepth) {
-        this();
-        this.capacity = capacity;
-        this.maxDepth = maxDepth;
-    }
+    final QuadTreeNode root;
 
     /**
-     * Creates a quad tree with 0 capacity and depth. Useful when user wants to
-     * set the capacity and depth after quad tree construction.
+     * The maximal capacity of each node in this tree. Should be a relatively small number.
+     * If the number of elements in a leaf node exceeds this capacity, then the node will be
+     * transformed into a parent node with 4 children.
      */
-    public QuadTree() {
-        root = new QuadTreeNode(NodeType.GRAY, this.nodeSize);
-        calculator = GeodeticCalculator.create(CommonCRS.SPHERE.geographic());
-    }
+    private final int capacity;
 
     /**
-     * Inserts the specified data into the quad tree.
-     *
-     * @param data
-     *            specified data to be inserted
-     * @return true if the data was inserted into the quad tree; false if data
-     *         cannot be inserted because the capacity of the node has been
-     *         exceeded and the depth of the tree will be exceeded if we insert
-     *         this data
+     * Number of elements in this QuadTree.
      */
-    public boolean insert(QuadTreeData data) {
-        if (insert(data, this.root)) {
-            this.size++;
-            return true;
-        } else {
-            return false;
-        }
-    }
-
-    /**
-     * Calculates the quadrant that the data lies in.
-     *
-     * @param data
-     *            specifed data
-     * @param x
-     *            the x-midpoint of the current node
-     * @param y
-     *            the y-midpoint of the current node
-     * @return the quadrant that the data lies in
-     */
-    private Quadrant compare(final QuadTreeData data, final double x, final double y) {
-        if (data.getX() < x)
-            if (data.getY() < y)
-                return Quadrant.SW;
-            else
-                return Quadrant.NW;
-        else if (data.getY() < y)
-            return Quadrant.SE;
-        else
-            return Quadrant.NE;
-    }
-
-    /**
-     * Inserts the data into the quad tree with the specified root.
-     *
-     * @param data
-     *            data to be inserted
-     * @param root
-     *            root of quadtree
-     * @return true if data was inserted, false otherwise
-     */
-    private boolean insert(final QuadTreeData data, final QuadTreeNode root) {
-        int currentDepth = 0;
-
-        QuadTreeNode r = root;
-        double x = EARTH_MID_X;
-        double y = EARTH_MID_Y;
-        double lx = EARTH_MAX_X;
-        double ly = EARTH_MAX_Y;
-
-        QuadTreeNode u;
-        QuadTreeNode t;
-        Quadrant q, uq;
-        t = r;
-        q = compare(data, x, y);
-        currentDepth++;
-        while (t.getChild(q) != null && t.getChild(q).getNodeType() == NodeType.GRAY) {
-            t = t.getChild(q);
-            x = x + xf[q.index()] * lx;
-            lx = lx / 2.0;
-            y = y + yf[q.index()] * ly;
-            ly = ly / 2.0;
-            q = compare(data, x, y);
-            currentDepth++;
-
-            if (currentDepth > this.maxDepth)
-                return false;
-        }
-        if (t.getChild(q) == null) {
-            QuadTreeNode newlyCreated = new QuadTreeNode(++this.nodeSize, this.capacity);
-            newlyCreated.addData(data);
-            t.setChild(newlyCreated, q);
-        } else {
-            u = t.getChild(q);
-            if (u.getCount() < this.capacity) {
-                u.addData(data);
-                return true;
-            } else {
-                QuadTreeData[] originalData = u.getData();
-
-                if (!maxDepthExceeded(originalData, data, x, y, lx, ly, q, currentDepth)) {
-                    t.setChild(new QuadTreeNode(NodeType.GRAY, u.getId()), q);
-                    t = t.getChild(q);
-                    x = x + xf[q.index()] * lx;
-                    lx = lx / 2.0;
-
-                    y = y + yf[q.index()] * ly;
-                    ly = ly / 2.0;
-                    q = compare(data, x, y);
-                    currentDepth++;
-                    if (currentDepth > this.maxDepth)
-                        return false;
-                    while (isSimilarQuad(originalData, data, x, y, q)) {
-                        t.setChild(new QuadTreeNode(NodeType.GRAY, ++this.nodeSize), q);
-                        t = t.getChild(q);
-                        x = x + xf[q.index()] * lx;
-                        lx = lx / 2.0;
-
-                        y = y + yf[q.index()] * ly;
-                        ly = ly / 2.0;
-                        q = compare(data, x, y);
-                        currentDepth++;
-                        if (currentDepth > this.maxDepth)
-                            return false;
-                    }
-
-                    if (t.getChild(q) == null) {
-                        QuadTreeNode newlyCreated = new QuadTreeNode(++this.nodeSize, this.capacity);
-                        newlyCreated.addData(data);
-                        t.setChild(newlyCreated, q);
-                    } else {
-                        t.getChild(q).addData(data);
-                    }
-
-                    for (int i = 0; i < originalData.length; i++) {
-                        uq = compare(originalData[i], x, y);
-                        if (t.getChild(uq) == null) {
-                            QuadTreeNode newlyCreated = new QuadTreeNode(++this.nodeSize, this.capacity);
-                            newlyCreated.addData(originalData[i]);
-                            t.setChild(newlyCreated, uq);
-                        } else {
-                            t.getChild(uq).addData(originalData[i]);
-                        }
-                    }
-                } else {
-                    return false;
-                }
-            }
-        }
-        return true;
-    }
+    private int count;
 
     /**
-     * Determines if insertion of the data will cause the depth of the quad tree
-     * to be exceeded.
-     *
-     * @param originalData
-     *            array containing the data that is already stored in the node
-     * @param toBeAddedData
-     *            data to be added to the node
-     * @param originalX
-     *            the x-midpoint of the node
-     * @param originalY
-     *            the y-midpoint of the node
-     * @param originalLX
-     *            the width of the node
-     * @param originalLY
-     *            the height of the node
-     * @param originalQ
-     *            the quadrant that all data currently lies in
-     * @param depth
-     *            the current depth
-     * @return true if the depth will be exceeded, false otherwise
+     * Coordinates of the point in the center of the area of interest.
      */
-    private boolean maxDepthExceeded(final QuadTreeData[] originalData, final QuadTreeData toBeAddedData,
-            final double originalX, final double originalY, final double originalLX, final double originalLY,
-            final Quadrant originalQ, final int depth) {
-        int currentDepth = depth;
-        double x = originalX;
-        double lx = originalLX;
-        double y = originalY;
-        double ly = originalLY;
-        Quadrant q = originalQ;
-
-        x = x + xf[q.index()] * lx;
-        lx = lx / 2.0;
-
-        y = y + yf[q.index()] * ly;
-        ly = ly / 2.0;
-        q = compare(toBeAddedData, x, y);
-        currentDepth++;
-        if (currentDepth > this.maxDepth)
-            return true;
-        while (isSimilarQuad(originalData, toBeAddedData, x, y, q)) {
-            x = x + xf[q.index()] * lx;
-            lx = lx / 2.0;
-
-            y = y + yf[q.index()] * ly;
-            ly = ly / 2.0;
-            q = compare(toBeAddedData, x, y);
-            currentDepth++;
-            if (currentDepth > this.maxDepth)
-                return true;
-        }
-        return false;
-    }
+    final double centerX, centerY;
 
     /**
-     * Returns true if all data (new and old) have to be stored in the same
-     * quadrant of the node.
-     *
-     * @param originalData
-     *            array of data already stored in the node
-     * @param newNode
-     *            the node in which data is stored
-     * @param x
-     *            the x midpoint of the node
-     * @param y
-     *            the y midpoint of the node
-     * @param q
-     *            the quadrant that the new data lies in
-     * @return true if all data lies in the quadrant, false otherwise
+     * Size of the area of interest.
      */
-    private boolean isSimilarQuad(QuadTreeData[] originalData, QuadTreeData newNode, double x, double y, Quadrant q) {
-        Quadrant quad = compare(originalData[0], x, y);
-        if (q != quad)
-            return false;
-        for (int i = 1; i < originalData.length; i++) {
-            if (compare(originalData[i], x, y) != quad)
-                return false;
-        }
-        return true;
-    }
+    final double width, height;
 
     /**
-     * Performs point radius search.
-     *
-     * @param point
-     *            the center of the circular region
-     * @param radiusKM
-     *            the radius in kilometers
-     * @return a list of QuadTreeData that are within the given radius from the
-     *         point
+     * The function computing a position for an arbitrary element of this tree.
      */
-    public List<QuadTreeData> queryByPointRadius(final DirectPosition2D point, final double radiusKM) {
-        LatLonPointRadius pr = new LatLonPointRadius(point, radiusKM);
-        return queryByPointRadius(point, radiusKM, this.root,
-                new Rectangle2D.Double(EARTH_MIN_X, EARTH_MIN_Y, EARTH_MAX_X, EARTH_MAX_Y),
-                pr.getRectangularRegionApproximation(360));
-    }
+    final Function<? super E, ? extends Point2D> evaluator;
 
     /**
-     * Performs point radius search.
+     * Creates an initially empty QuadTree with the given capacity for each node.
+     * The capacity should be a relatively small number. If the number of elements
+     * in a leaf node exceeds this capacity, then the node will be transformed into
+     * a parent node with 4 children.
      *
-     * @param point
-     *            the center of the circular region
-     * @param radiusKM
-     *            the radius in kilometers
-     * @param node
-     *            quad tree root node
-     * @param nodeRegion
-     *            Rectangle2D representing the circular node region
-     * @param searchRegion
-     *            Rectangle2D representing the circular search region
-     * @return a list of QuadTreeData that are within the given radius from the
-     *         point
+     * @param  bounds     bounds of the region of data to be inserted in the QuadTree.
+     * @param  evaluator  function computing a position for an arbitrary element of this tree.
+     * @param  capacity   the capacity of each node.
      */
-    private List<QuadTreeData> queryByPointRadius(final DirectPosition2D point, final double radiusKM,
-            final QuadTreeNode node, final Rectangle2D nodeRegion, final Rectangle2D searchRegion) {
-        List<QuadTreeData> matches = new ArrayList<QuadTreeData>();
-        if (node == null) {
-            return matches;
-        } else if (node.getNodeType() != NodeType.GRAY) {
-            if (node.getNodeType() == NodeType.WHITE) {
-                return matches;
-            } else {
-                QuadTreeData[] data = node.getData();
-                for (int i = 0; i < node.getCount(); i++) {
-                    DirectPosition2D latLon = data[i].getLatLon();
-                    double distance;
-                    synchronized (calculator) {
-                        calculator.setStartGeographicPoint(latLon.y, latLon.x);
-                        calculator.setEndGeographicPoint(point.y, point.x);
-                        distance = calculator.getGeodesicDistance();
-                    }
-                    if (distance <= radiusKM) {
-                        matches.add(data[i]);
-                    }
-                }
-                return matches;
-            }
-        } else {
-            Rectangle2D swRectangle = new Rectangle2D.Double(nodeRegion.getX(), nodeRegion.getY(),
-                    nodeRegion.getWidth() / 2, nodeRegion.getHeight() / 2);
-            Rectangle2D seRectangle = new Rectangle2D.Double(nodeRegion.getX() + nodeRegion.getWidth() / 2,
-                    nodeRegion.getY(), nodeRegion.getWidth() / 2, nodeRegion.getHeight() / 2);
-            Rectangle2D nwRectangle = new Rectangle2D.Double(nodeRegion.getX(),
-                    nodeRegion.getY() + nodeRegion.getHeight() / 2, nodeRegion.getWidth() / 2,
-                    nodeRegion.getHeight() / 2);
-            Rectangle2D neRectangle = new Rectangle2D.Double(nodeRegion.getX() + nodeRegion.getWidth() / 2,
-                    nodeRegion.getY() + nodeRegion.getHeight() / 2, nodeRegion.getWidth() / 2,
-                    nodeRegion.getHeight() / 2);
-
-            if (swRectangle.intersects(searchRegion)) {
-                List<QuadTreeData> swMatches = queryByPointRadius(point, radiusKM, node.getChild(Quadrant.SW),
-                        swRectangle, searchRegion);
-                for (QuadTreeData q : swMatches) {
-                    matches.add(q);
-                }
-            }
-            if (seRectangle.intersects(searchRegion)) {
-                List<QuadTreeData> seMatches = queryByPointRadius(point, radiusKM, node.getChild(Quadrant.SE),
-                        seRectangle, searchRegion);
-                for (QuadTreeData q : seMatches) {
-                    matches.add(q);
-                }
-            }
-            if (nwRectangle.intersects(searchRegion)) {
-                List<QuadTreeData> nwMatches = queryByPointRadius(point, radiusKM, node.getChild(Quadrant.NW),
-                        nwRectangle, searchRegion);
-                for (QuadTreeData q : nwMatches) {
-                    matches.add(q);
-                }
-            }
-            if (neRectangle.intersects(searchRegion)) {
-                List<QuadTreeData> neMatches = queryByPointRadius(point, radiusKM, node.getChild(Quadrant.NE),
-                        neRectangle, searchRegion);
-                for (QuadTreeData q : neMatches) {
-                    matches.add(q);
-                }
-            }
-        }
-        return matches;
+    public QuadTree(final Rectangle2D bounds, final Function<? super E, ? extends Point2D> evaluator, final int capacity) {
+        this.centerX   = bounds.getCenterX();
+        this.centerY   = bounds.getCenterY();
+        this.width     = bounds.getWidth();
+        this.height    = bounds.getHeight();
+        this.capacity  = Math.max(4, capacity);
+        this.evaluator = evaluator;
+        this.root      = new QuadTreeNode();
     }
 
     /**
-     * Performs bounding box search.
+     * Inserts the specified data into this QuadTree.
      *
-     * @param searchRegion
-     *            Envelope representing the rectangular search region
-     * @return a list of QuadTreeData that are within the given radius from the
-     *         point
+     * @param  element  the element to insert.
+     * @return always {@code true} in current implementation.
      */
-    public List<QuadTreeData> queryByBoundingBox(final Envelope2D searchRegion) {
-        Rectangle2D.Double[] rectArray = searchRegion.toRectangles();
-        for (final Rectangle2D.Double r : rectArray) {
-            r.x += 180;
-            r.y += 90;
-        }
-        if (rectArray.length == 1) {
-            // traverse tree once because region does not cross dateline
-            return queryByBoundingBox(rectArray[0]);
-
-        } else if (rectArray.length == 2) {
-            // traverse tree twice since region crosses dateline
-            List<QuadTreeData> firstMatches = queryByBoundingBox(rectArray[0]);
-            List<QuadTreeData> secondMatches = queryByBoundingBox(rectArray[1]);
-
-            // merge two lists and return
-            for (QuadTreeData q : secondMatches) {
-                if (!firstMatches.contains(q)) {
-                    firstMatches.add(q);
-                }
-            }
-            return firstMatches;
-        } else {
-            return null;
-        }
-    }
-
-    /**
-     * Performs bounding box search.
-     *
-     * @param searchRegion
-     *            Rectangle2D representing the rectangular search region
-     * @return a list of QuadTreeData that are within the given radius from the
-     *         point
-     */
-    private List<QuadTreeData> queryByBoundingBox(final Rectangle2D searchRegion) {
-        return queryByBoundingBox(this.root, new Rectangle2D.Double(EARTH_MIN_X, EARTH_MIN_Y, EARTH_MAX_X, EARTH_MAX_Y),
-                searchRegion);
+    public boolean add(final E element) {
+        ArgumentChecks.ensureNonNull("element", element);
+        insert(root, centerX, centerY, width, height, element);
+        count++;
+        return true;
     }
 
     /**
-     * Performs bounding box search.
-     *
-     * @param node
-     *            quad tree root node
-     * @param nodeRegion
-     *            Rectangle2D representing the rectangular node region
-     * @param searchRegion
-     *            Rectangle2D representing the rectangular search region
-     * @return a list of QuadTreeData that are within the given radius from the
-     *         point
-     */
-    private List<QuadTreeData> queryByBoundingBox(final QuadTreeNode node, final Rectangle2D nodeRegion,
-            final Rectangle2D searchRegion) {
-
-        List<QuadTreeData> matches = new ArrayList<QuadTreeData>();
-        if (node == null) {
-            return matches;
-        } else if (node.getNodeType() != NodeType.GRAY) {
-            if (node.getNodeType() == NodeType.WHITE)
-                return matches;
-            else {
-                QuadTreeData[] data = node.getData();
-                for (int i = 0; i < node.getCount(); i++) {
-                    if (searchRegion.contains(data[i].getX(), data[i].getY())) {
-                        matches.add(data[i]);
-                    }
-                }
-                return matches;
+     * Inserts the specified data into the given node. This method will iterate through node children
+     * until a suitable node is found. This method may invoke itself recursively.
+     *
+     * @param  parent   the parent where to add the given data.
+     * @param  cx       <var>x</var> coordinate in the center of {@code parent} node.
+     * @param  cy       <var>y</var> coordinate in the center of {@code parent} node.
+     * @param  dx       size of the {@code parent} node along the <var>x</var> axis.
+     * @param  dy       size of the {@code parent} node along the <var>y</var> axis.
+     * @param  element  the element to insert.
+     */
+    @SuppressWarnings("unchecked")
+    private void insert(QuadTreeNode parent, double cx, double cy, double dx, double dy, final E element) {
+        final Point2D position = evaluator.apply(element);
+        final double x = position.getX();
+        final double y = position.getY();
+        for (;;) {
+            final int q = QuadTreeNode.quadrant(x, y, cx, cy);
+            final Object child = parent.getChild(q);
+            if (child == null) {
+                // New quadrant created in an existing parent (easy case).
+                parent.setChild(q, new Object[] {element});
+                break;
             }
-
-        } else {
-            Rectangle2D swRectangle = new Rectangle2D.Double(nodeRegion.getX(), nodeRegion.getY(),
-                    nodeRegion.getWidth() / 2, nodeRegion.getHeight() / 2);
-            Rectangle2D seRectangle = new Rectangle2D.Double(nodeRegion.getX() + nodeRegion.getWidth() / 2,
-                    nodeRegion.getY(), nodeRegion.getWidth() / 2, nodeRegion.getHeight() / 2);
-            Rectangle2D nwRectangle = new Rectangle2D.Double(nodeRegion.getX(),
-                    nodeRegion.getY() + nodeRegion.getHeight() / 2, nodeRegion.getWidth() / 2,
-                    nodeRegion.getHeight() / 2);
-            Rectangle2D neRectangle = new Rectangle2D.Double(nodeRegion.getX() + nodeRegion.getWidth() / 2,
-                    nodeRegion.getY() + nodeRegion.getHeight() / 2, nodeRegion.getWidth() / 2,
-                    nodeRegion.getHeight() / 2);
-
-            if (swRectangle.intersects(searchRegion)) {
-                List<QuadTreeData> swMatches = queryByBoundingBox(node.getChild(Quadrant.SW), swRectangle,
-                        searchRegion);
-                for (QuadTreeData q : swMatches) {
-                    matches.add(q);
-                }
-            }
-            if (seRectangle.intersects(searchRegion)) {
-                List<QuadTreeData> seMatches = queryByBoundingBox(node.getChild(Quadrant.SE), seRectangle,
-                        searchRegion);
-                for (QuadTreeData q : seMatches) {
-                    matches.add(q);
-                }
-            }
-            if (nwRectangle.intersects(searchRegion)) {
-                List<QuadTreeData> nwMatches = queryByBoundingBox(node.getChild(Quadrant.NW), nwRectangle,
-                        searchRegion);
-                for (QuadTreeData q : nwMatches) {
-                    matches.add(q);
+            cx += QuadTreeNode.factorX(q) * (dx *= 0.5);        // Center and size of the child node.
+            cy += QuadTreeNode.factorY(q) * (dy *= 0.5);        // TODO: use Math.fma with JDK9.
+            if (child instanceof QuadTreeNode) {
+                parent = (QuadTreeNode) child;                  // Continue until leaf node is found.
+            } else {
+                final Object[] data = (Object[]) child;
+                final int n = data.length;
+                if (n < capacity) {
+                    final Object[] copy = new Object[n+1];
+                    System.arraycopy(data, 0, copy, 0, n);
+                    copy[n] = element;
+                    parent.setChild(q, copy);
+                    break;                                      // Leaf node can take the data — done.
                 }
-            }
-            if (neRectangle.intersects(searchRegion)) {
-                List<QuadTreeData> neMatches = queryByBoundingBox(node.getChild(Quadrant.NE), neRectangle,
-                        searchRegion);
-                for (QuadTreeData q : neMatches) {
-                    matches.add(q);
+                /*
+                 * Leaf can not add the given element because the leaf has reached its maximal capacity.
+                 * Replace the leaf node by a parent node and add all previous elements into it. After
+                 * data has been copied, continue attempts to insert the element given to this method.
+                 */
+                final QuadTreeNode branch = new QuadTreeNode();
+                for (final Object e : data) {
+                    insert(branch, cx, cy, dx, dy, (E) e);
                 }
+                parent.setChild(q, branch);
+                parent = branch;
             }
         }
-        return matches;
     }
 
     /**
-     * Returns the size of the quad tree.
+     * Returns the number of elements in this tree.
      *
-     * @return size of the quad tree.
+     * @return the number of elements in this tree.
      */
     public int size() {
-        return this.size;
-    }
-
-    /**
-     * Returns the root node of the quad tree.
-     *
-     * @return root node of the quad tree.
-     */
-    final QuadTreeNode getRoot() {
-        return this.root;
+        return count;
     }
 
     /**
-     * Sets the size of the quad tree.
-     *
-     * @param size
-     *            The new quad tree size.
-     */
-    public void setSize(int size) {
-        this.size = size;
-    }
-
-    /**
-     * Returns the size of the quad tree.
-     *
-     * @return size of quad tree
-     */
-    public int getSize() {
-        return this.size;
-    }
-
-    /**
-     * Sets the node size of the quad tree.
-     *
-     * @param nodeSize
-     *            The new node size.
-     */
-    public void setNodeSize(int nodeSize) {
-        this.nodeSize = nodeSize;
-    }
-
-    /**
-     * Returns the node size of the quad tree.
-     *
-     * @return node size of the quad tree.
-     */
-    public int getNodeSize() {
-        return this.nodeSize;
-    }
-
-    /**
-     * Returns the capacity of node in the quad tree.
-     *
-     * @return capacity of node in the quad tree.
-     */
-    public int getCapacity() {
-        return this.capacity;
-    }
-
-    /**
-     * Returns the maximum depth of the quad tree.
-     *
-     * @return maximum depth of the quad tree.
-     */
-    public int getDepth() {
-        return this.maxDepth;
-    }
-
-    /**
-     * Sets the capacity of node in the quad tree.
-     *
-     * @param capacity
-     *            the capacity of node in the quad tree.
-     */
-    public void setCapacity(int capacity) {
-        this.capacity = capacity;
-    }
-
-    /**
-     * Sets the maximum depth of the quad tree.
+     * Performs bounding box search.
      *
-     * @param depth
-     *            the maximum depth of the quad tree.
+     * @param  searchRegion  envelope representing the rectangular search region.
+     * @return elements that are within the given radius from the point.
      */
-    public void setDepth(int depth) {
-        this.maxDepth = depth;
+    public Stream<E> queryByBoundingBox(final Rectangle2D searchRegion) {
+        return StreamSupport.stream(new NodeIterator<>(this, searchRegion), false);
+        // TODO: make parallel after we tested most extensively.
     }
 }
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeData.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeData.java
deleted file mode 100644
index 3a37ae9..0000000
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeData.java
+++ /dev/null
@@ -1,59 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.sis.index.tree;
-
-//SIS imports
-import org.apache.sis.geometry.DirectPosition2D;
-
-/**
- * Interface representing data stored in quad tree. All data to be stored in
- * quad tree must implement this interface, so that quad tree can access
- * location and store name of file in which data is saved.
- *
- * <div class="warning"><b>Note on future work:</b> this interface may change in
- * incompatible way in a future Apache SIS release, or may be replaced by new
- * API.</div>
- */
-public interface QuadTreeData {
-    /**
-     * Returns the Java 2D x-coordinate for the longitude.
-     *
-     * @return the Java 2D x-coordinate
-     */
-    public double getX();
-
-    /**
-     * Returns the Java 2D y-coordinate for the latitude.
-     *
-     * @return the Java 2D y-coordinate
-     */
-    public double getY();
-
-    /**
-     * Returns the latitude/longitude pair.
-     *
-     * @return the latitude/longitude pair.
-     */
-    public DirectPosition2D getLatLon();
-
-    /**
-     * Returns the name of the file where the entry's info is saved.
-     *
-     * @return the name of the file where the entry's info is saved
-     */
-    public String getFileName();
-}
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
index 5078deb..1024768 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
+++ b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/QuadTreeNode.java
@@ -16,163 +16,128 @@
  */
 package org.apache.sis.index.tree;
 
+
 /**
- * Implementation of quad tree node.
+ * A node in a {@link QuadTree} which is the parent of other nodes.
+ * This class is a specialization of {@link KDTree} for the two-dimensional case.
+ * This specialization is provided for reducing the number of objects to create,
+ * by storing the 4 quadrants as fields instead than in an array.
  *
+ * @author  Chris Mattmann
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ * @since   0.1
+ * @module
  */
-final class QuadTreeNode {
-
-    private QuadTreeData[] data;
-    private QuadTreeNode nw;
-    private QuadTreeNode ne;
-    private QuadTreeNode se;
-    private QuadTreeNode sw;
-    private NodeType type;
-    private int id;
-    private int capacity;
-    private int dataCount;
-    private static final int MIN_CAPACITY = 10;
-
+final class QuadTreeNode extends KDTreeNode {
     /**
-     * Constructs a quad tree node that can store data
+     * The 4 quadrants of a {@link QuadTreeNode}: North-West (NW), North-East (NE),
+     * South-West (SW) and South-East (SE). Numerical values follow this bit pattern:
      *
-     * @param id
-     *            node's id
-     * @param capacity
-     *            node's capcacity
-     */
-    public QuadTreeNode(int id, int capacity) {
-        this.capacity = capacity > 0 ? capacity : MIN_CAPACITY;
-        this.dataCount = 0;
-        this.data = new QuadTreeData[this.capacity];
-        this.type = NodeType.BLACK;
-        this.nw = null;
-        this.ne = null;
-        this.sw = null;
-        this.se = null;
-        this.id = id;
-    }
-
-    /**
-     * Constructs a quad tree node that acts as a parent.
+     * <ul>
+     *   <li>Bit 0 is the sign of <var>x</var> coordinates: 0 for East  and 1 for West.</li>
+     *   <li>Bit 1 is the sign of <var>y</var> coordinates: 0 for North and 1 for South.</li>
+     * </ul>
      *
-     * @param type
-     *            node's type
-     * @param id
-     *            node's id
+     * This pattern is generalizable to <var>n</var> dimensions (by contrast, the use of a {@code Quadrant}
+     * enumeration is not generalizable). Current implementation uses only 2 dimensions, but a future version
+     * may generalize.
      */
-    public QuadTreeNode(NodeType type, int id) {
-        this.type = type;
-        this.nw = null;
-        this.ne = null;
-        this.sw = null;
-        this.se = null;
-        this.data = null;
-        this.id = id;
-    }
+    static final int NE = 0, NW = 1, SE = 2, SW = 3;
 
     /**
-     * Add data to the node.
+     * The mask to apply on quadrant values for getting the sign of <var>x</var> and <var>y</var>
+     * values relative to the center of a node.
      *
-     * @param data
-     *            data to be added
+     * Also used as bit position + 1 (this is possible only for mask values 1 and 2).
+     * If we generalize to 3 or more dimensions, we will need to differentiate those
+     * "bit positions" from "mask values".
      */
-    public void addData(QuadTreeData data) {
-        if (this.dataCount < this.capacity) {
-            this.data[dataCount] = data;
-            this.dataCount++;
-        }
-    }
+    private static final int X_MASK = 1, Y_MASK = 2;
 
     /**
-     * Gets the number of data stored in the node
+     * Returns the quadrant relative to the given point.
      *
-     * @return number of data stored in the node
+     * @param  x   data <var>x</var> coordinate.
+     * @param  y   data <var>y</var> coordinate.
+     * @param  cx  center of current node along <var>x</var> axis.
+     * @param  cy  center of current node along <var>y</var> axis.
+     * @return one of {@link #NE}, {@link #NW}, {@link #SE} or {@link #SW} constants.
      */
-    public int getCount() {
-        return this.dataCount;
+    static int quadrant(final double x, final double y, final double cx, final double cy) {
+        int q = 0;
+        if (x < cx) q  = X_MASK;
+        if (y < cy) q |= Y_MASK;
+        // Same for z and all other dimensions.
+        return q;
     }
 
     /**
-     * Gets the node type.
-     *
-     * @return node type
+     * Returns 0.5 if the given quadrant is in the East side, or -0.5 if in the West side.
      */
-    public NodeType getNodeType() {
-        return this.type;
+    static double factorX(final int quadrant) {
+        /*
+         * The 3FE0000000000000 long value is the bit pattern of 0.5. The leftmost bit at (Long.SIZE - 1)
+         * is the sign, which we set to the sign encoded in the quadrant value. This approach allow us to
+         * get the value efficiently, without jump instructions.
+         */
+        return Double.longBitsToDouble(0x3FE0000000000000L | (((long) quadrant) << (Long.SIZE - X_MASK)));
     }
 
     /**
-     * Sets the node's quadrant to point to the specified child.
-     *
-     * @param child
-     *            child of this node
-     * @param q
-     *            quadrant where the child resides
+     * Returns 0.5 if the given quadrant is in the North side, or -0.5 if in the South side.
      */
-    public void setChild(QuadTreeNode child, Quadrant q) {
-        switch (q) {
-        case NW:
-            this.nw = child;
-            break;
-        case NE:
-            this.ne = child;
-            break;
-        case SW:
-            this.sw = child;
-            break;
-        case SE:
-            this.se = child;
-            break;
-        }
+    static double factorY(final int quadrant) {
+        /*
+         * Same approach than for factorY, except that we need to clear the bits on the right side of
+         * the Y mask (it was not necessary for X because they were no bit on the right side of X mask).
+         */
+        return Double.longBitsToDouble(0x3FE0000000000000L | (((long) (quadrant & Y_MASK)) << (Long.SIZE - Y_MASK)));
     }
 
     /**
-     * Returns the child of this node that resides in the specified quadrant.
-     *
-     * @param q
-     *            specified quadrant
-     * @return child in the specified quadrant
+     * The child nodes in 4 quadrants of equal size.
+     * Quadrants are North-West, North-East, South-East and South-West.
      */
-    public QuadTreeNode getChild(Quadrant q) {
-        switch (q) {
-        case NW:
-            return this.nw;
-        case NE:
-            return this.ne;
-        case SW:
-            return this.sw;
-        case SE:
-            return this.se;
-        default:
-            return null;
-        }
-    }
+    private Object nw, ne, se, sw;
 
     /**
-     * Returns the data stored in this node.
-     *
-     * @return data stored in this node
+     * Constructs an initially empty parent node.
      */
-    public QuadTreeData[] getData() {
-        return this.data;
+    QuadTreeNode() {
     }
 
     /**
-     * Returns node's id.
+     * Returns the child of this node that resides in the specified quadrant.
      *
-     * @return node's id
+     * @param  q  quadrant of child to get.
+     * @return child in the specified quadrant.
      */
-    public int getId() {
-        return this.id;
+    final Object getChild(final int q) {
+        final Object child;
+        switch (q) {
+            case NW: child = nw; break;
+            case NE: child = ne; break;
+            case SW: child = sw; break;
+            case SE: child = se; break;
+            default: throw new AssertionError(q);
+        }
+        return child;
     }
 
     /**
-     * Returns node's capacity.
+     * Sets the node's quadrant to the specified child.
      *
-     * @return node's capacity
+     * @param q      quadrant where the child resides.
+     * @param child  child of this node in the specified quadrant.
      */
-    public int getCapacity() {
-        return this.capacity;
+    final void setChild(final int q, final Object child) {
+        switch (q) {
+            case NW: nw = child; break;
+            case NE: ne = child; break;
+            case SW: sw = child; break;
+            case SE: se = child; break;
+            default: throw new AssertionError(q);
+        }
     }
 }
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/Quadrant.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/Quadrant.java
deleted file mode 100644
index 5b534e4..0000000
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/Quadrant.java
+++ /dev/null
@@ -1,62 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.sis.index.tree;
-
-/**
- * Enum to represent the 4 quadrants of a quad tree node.
- *
- */
-enum Quadrant {
-
-  NW(0), NE(1), SW(2), SE(3);
-  private final int index;
-
-  private Quadrant(int index) {
-    this.index = index;
-  }
-
-  /**
-   * Returns the index of the quadrant.
-   *
-   * @return index of the quadrant
-   */
-  public int index() {
-    return index;
-  }
-
-  /**
-   * Retrieves the quadrant matching specified index.
-   *
-   * @param index
-   *          specified index
-   * @return quadrant matching specified index
-   */
-  public static Quadrant getQuadrant(int index) {
-    switch (index) {
-    case 0:
-      return NW;
-    case 1:
-      return NE;
-    case 2:
-      return SW;
-    case 3:
-      return SE;
-    default:
-      return null;
-    }
-  }
-}
diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/package-info.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/package-info.java
index 46736b7..3425d92 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/package-info.java
+++ b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/package-info.java
@@ -16,9 +16,12 @@
  */
 
 /**
- * A simple quadtree implementation.
+ * A simple QuadTree implementation.
  *
- * <div class="warning"><b>Note on future work:</b> this package may change in incompatible way
- * in a future Apache SIS release, or may be replaced by new API.</div>
+ * @author  Chris Mattmann
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ * @since   1.1
+ * @module
  */
 package org.apache.sis.index.tree;
diff --git a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeNodeTest.java b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeNodeTest.java
new file mode 100644
index 0000000..86b4b93
--- /dev/null
+++ b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeNodeTest.java
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sis.index.tree;
+
+import org.apache.sis.test.TestCase;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+
+/**
+ * Tests {@link QuadTreeNode}.
+ *
+ * @author  Chris Mattmann
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ * @since   0.1
+ * @module
+ */
+public final strictfp class QuadTreeNodeTest extends TestCase {
+    /**
+     * Tests {@link QuadTreeNode#factorX(int)}.
+     */
+    @Test
+    public void testFactorX() {
+        assertEquals(+0.5, QuadTreeNode.factorX(QuadTreeNode.NE), STRICT);
+        assertEquals(-0.5, QuadTreeNode.factorX(QuadTreeNode.NW), STRICT);
+        assertEquals(+0.5, QuadTreeNode.factorX(QuadTreeNode.SE), STRICT);
+        assertEquals(-0.5, QuadTreeNode.factorX(QuadTreeNode.SW), STRICT);
+    }
+
+    /**
+     * Tests {@link QuadTreeNode#factorY(int)}.
+     */
+    @Test
+    public void testFactorY() {
+        assertEquals(+0.5, QuadTreeNode.factorY(QuadTreeNode.NE), STRICT);
+        assertEquals(+0.5, QuadTreeNode.factorY(QuadTreeNode.NW), STRICT);
+        assertEquals(-0.5, QuadTreeNode.factorY(QuadTreeNode.SE), STRICT);
+        assertEquals(-0.5, QuadTreeNode.factorY(QuadTreeNode.SW), STRICT);
+    }
+}
diff --git a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java
new file mode 100644
index 0000000..016a7cf
--- /dev/null
+++ b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeTest.java
@@ -0,0 +1,145 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sis.index.tree;
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Set;
+import java.util.HashSet;
+import java.util.Random;
+import java.util.function.Function;
+import java.awt.Rectangle;
+import java.awt.geom.Point2D;
+import java.awt.geom.Rectangle2D;
+import org.apache.sis.test.DependsOn;
+import org.apache.sis.test.TestCase;
+import org.apache.sis.test.TestUtilities;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+
+/**
+ * Tests {@link QuadTree}.
+ *
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ * @since   1.1
+ * @module
+ */
+@DependsOn(QuadTreeNodeTest.class)
+public final strictfp class QuadTreeTest extends TestCase {
+    /**
+     * Bounds of the region where to create points. Intentionally use asymmetric bounds
+     * for increasing the chances to detect bugs in node region computations.
+     */
+    private static final int XMIN = -1000, YMIN = -2000, XMAX = 1500, YMAX = 3000;
+
+    /**
+     * The random number generator to use for generating points and search regions.
+     */
+    private Random random;
+
+    /**
+     * The tree to test.
+     */
+    private QuadTree<Element> tree;
+
+    /**
+     * All data added to the {@link #tree}, for comparison purpose.
+     */
+    private List<Element> data;
+
+    /**
+     * The elements to be added in the {@link QuadTree} to test.
+     * This element extends {@link Point2D} for convenience, but this is not a requirement.
+     * The point is unmodifiable; attempt to modify a coordinate will cause the test to fail.
+     */
+    private static final class Element extends Point2D {
+        /** The coordinate values. */
+        private final int x, y;
+
+        /** Creates a new element with random coordinates. */
+        Element(final Random random) {
+            x = random.nextInt(XMAX - XMIN) + XMIN;
+            y = random.nextInt(YMAX - YMIN) + YMIN;
+        }
+
+        @Override public double getX()     {return x;}
+        @Override public double getY()     {return y;}
+        @Override public String toString() {return "P(" + x + ", " + y + ')';}
+
+        @Override public void setLocation(double x, double y) {
+            fail("Location shoulf not be modified.");
+        }
+
+        @Override public Object clone() {
+            fail("Location should not be cloned.");
+            return super.clone();
+        }
+    }
+
+    /**
+     * Creates a tree filled with random values.
+     */
+    private void createTree() {
+        random = TestUtilities.createRandomNumberGenerator();
+        tree = new QuadTree<>(new Rectangle(XMIN, YMIN, XMAX - XMIN, YMAX - YMIN), Function.identity(), 5);
+        int count = random.nextInt(100) + 200;
+        data = new ArrayList<>(count);
+        while (--count >= 0) {
+            final Element e = new Element(random);
+            assertEquals(data.add(e), tree.add(e));
+            assertEquals(data.size(), tree.size());
+        }
+    }
+
+    /**
+     * Tests {@link QuadTree#queryByBoundingBox(Rectangle2D)} with random coordinates.
+     * This method performs some searches in random regions and compare the results
+     * against searches performed by raw force.
+     */
+    @Test
+    public void testQueryByBoundingBox() {
+        createTree();
+        final Set<Element> expected = new HashSet<>();
+        final Rectangle2D.Double region = new Rectangle2D.Double();
+        for (int i=0; i<20; i++) {
+            final int xmin = random.nextInt(XMAX - XMIN) + XMIN;
+            final int ymin = random.nextInt(YMAX - YMIN) + YMIN;
+            final int xmax = random.nextInt(XMAX - xmin) + xmin;
+            final int ymax = random.nextInt(YMAX - ymin) + ymin;
+            region.x      = xmin - 0.25;
+            region.y      = ymin - 0.25;
+            region.width  = xmax - xmin + 0.5;
+            region.height = ymax - ymin + 0.5;
+            data.stream().filter(region::contains).forEach(expected::add);
+            tree.queryByBoundingBox(region).forEach((p) -> {
+                if (!expected.remove(p)) {
+                    fail(String.format("Unexpected point in result stream: %s%n"
+                            + "Search region is x: [%d … %d] and y: [%d … %d]%n",
+                            p, xmin, xmax, ymin, ymax));
+                }
+            });
+            if (!expected.isEmpty()) {
+                fail(String.format("Missing points in result stream: %s%n"
+                        + "Search region is x: [%d … %d] and y: [%d … %d]%n",
+                        expected, xmin, xmax, ymin, ymax));
+            }
+        }
+    }
+}
diff --git a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/TestQuadTreeNode.java b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/TestQuadTreeNode.java
deleted file mode 100644
index 30f4394..0000000
--- a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/TestQuadTreeNode.java
+++ /dev/null
@@ -1,31 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.sis.index.tree;
-
-import junit.framework.TestCase;
-
-public class TestQuadTreeNode extends TestCase{
-
-	/**
-	 * @since SIS-39
-	 */
-	public void testCapacityGreaterThanZero(){
-		QuadTreeNode node = new QuadTreeNode(-1, -5);
-		assertNotNull(node);
-		assertTrue(node.getCapacity() > 0);
-	}
-}
diff --git a/storage/sis-storage/src/test/java/org/apache/sis/test/suite/StorageTestSuite.java b/storage/sis-storage/src/test/java/org/apache/sis/test/suite/StorageTestSuite.java
index afa697e..cc09ca9 100644
--- a/storage/sis-storage/src/test/java/org/apache/sis/test/suite/StorageTestSuite.java
+++ b/storage/sis-storage/src/test/java/org/apache/sis/test/suite/StorageTestSuite.java
@@ -25,11 +25,13 @@ import org.junit.BeforeClass;
  * All tests from the {@code sis-storage} module, in rough dependency order.
  *
  * @author  Martin Desruisseaux (Geomatys)
- * @version 1.0
+ * @version 1.1
  * @since   0.3
  * @module
  */
 @Suite.SuiteClasses({
+    org.apache.sis.index.tree.QuadTreeNodeTest.class,
+    org.apache.sis.index.tree.QuadTreeTest.class,
     org.apache.sis.internal.storage.CodeTypeTest.class,
     org.apache.sis.internal.storage.io.IOUtilitiesTest.class,
     org.apache.sis.internal.storage.io.ChannelDataInputTest.class,


Mime
View raw message