sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject [sis] branch geoapi-4.0 updated: Move QuadTree implementation into KDTree after generalization to the n-dimensional case. Tested in two-dimensional case but not yet with higher dimensions. For now the maximal number of dimensions is 6.
Date Tue, 14 Jan 2020 22:29:42 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


The following commit(s) were added to refs/heads/geoapi-4.0 by this push:
     new c2a2897  Move QuadTree implementation into KDTree after generalization to the n-dimensional case. Tested in two-dimensional case but not yet with higher dimensions. For now the maximal number of dimensions is 6.
c2a2897 is described below

commit c2a2897095a96cdbc6b233aee1731a818e18e57a
Author: Martin Desruisseaux <martin.desruisseaux@geomatys.com>
AuthorDate: Tue Jan 14 20:12:18 2020 +0100

    Move QuadTree implementation into KDTree after generalization to the n-dimensional case.
    Tested in two-dimensional case but not yet with higher dimensions.
    For now the maximal number of dimensions is 6.
---
 .../java/org/apache/sis/index/tree/KDTree.java     | 181 ++++++++++++++++++++-
 .../java/org/apache/sis/index/tree/KDTreeNode.java | 131 ++++++++++++++-
 .../org/apache/sis/index/tree/NodeIterator.java    | 165 ++++++++++++-------
 .../java/org/apache/sis/index/tree/QuadTree.java   | 140 +---------------
 .../org/apache/sis/index/tree/QuadTreeNode.java    |  81 +++------
 .../apache/sis/index/tree/NodeIteratorTest.java    | 112 +++++++++++++
 .../apache/sis/index/tree/QuadTreeNodeTest.java    |  56 -------
 .../org/apache/sis/index/tree/QuadTreeTest.java    |  32 ++--
 .../apache/sis/test/suite/StorageTestSuite.java    |   2 +-
 9 files changed, 562 insertions(+), 338 deletions(-)

diff --git a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
index c3bfef5..61cb721 100644
--- a/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
+++ b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTree.java
@@ -16,10 +16,17 @@
  */
 package org.apache.sis.index.tree;
 
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+import java.util.function.Function;
+import org.opengis.geometry.Envelope;
+import org.apache.sis.util.ArgumentChecks;
+import org.apache.sis.util.resources.Errors;
+
 
 /**
- * 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.
+ * A <var>k</var>-dimensional tree index for points. For <var>k</var>=2, this is a point {@link QuadTree}.
+ * For <var>k</var>=3, this is an point {@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
@@ -33,10 +40,174 @@ package org.apache.sis.index.tree;
  * @since 1.1
  * @module
  */
-abstract class KDTree<E> {
+class KDTree<E> {
+    /**
+     * The root node of this <var>k</var>-dimensional tree.
+     */
+    final KDTreeNode root;
+
+    /**
+     * The maximal capacity of each node in this tree. It 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 children nodes.
+     */
+    private final int capacity;
+
+    /**
+     * Number of elements in this <var>k</var>-dimensional tree.
+     */
+    private int count;
+
+    /**
+     * The regions covered by this tree, encoded as a center and a size.
+     * This array contains two parts:
+     *
+     * <ul>
+     *   <li>The first half contains coordinates of the point in the center of the region covered by this tree.</li>
+     *   <li>The second half contains the size of the region along each dimension.</li>
+     * </ul>
+     *
+     * The length of this array is two times the number of dimensions of points in this tree.
+     */
+    final double[] treeRegion;
+
+    /**
+     * The function computing a position for an arbitrary element in this tree.
+     */
+    final Function<? super E, double[]> evaluator;
+
+    /**
+     * Creates an initially empty <var>k</var>-dimensional tree with the given capacity for each node.
+     * The number of dimensions of the given envelope determines the number of dimensions of points in
+     * this tree. The position computed by {@code evaluator} must have the same number of dimensions.
+     *
+     * <p>The given {@code capacity} is a threshold value controlling when the content of a node should
+     * be splited into smaller children nodes. That capacity should be a relatively small number,
+     * for example 10. Determining the most efficient value may require benchmarking.</p>
+     *
+     * @param  bounds     bounds of the region of data to be inserted in the <var>k</var>-dimensional tree.
+     * @param  evaluator  function computing a position for an arbitrary element of this tree.
+     * @param  capacity   the capacity of each node.
+     */
+    KDTree(final Envelope bounds, final Function<? super E, double[]> evaluator, final int capacity) {
+        final int n = bounds.getDimension();
+        if (n < 2) {
+            throw new IllegalArgumentException(Errors.format(Errors.Keys.MismatchedDimension_3, "bounds", 2, n));
+        }
+        if (n > NodeIterator.MAX_DIMENSION) {
+            throw new IllegalArgumentException(Errors.format(Errors.Keys.ExcessiveNumberOfDimensions_1, n));
+        }
+        treeRegion = new double[n*2];
+        for (int i=0; i<n; i++) {
+            treeRegion[i]   = bounds.getMedian(i);
+            treeRegion[i+n] = bounds.getSpan(i);
+        }
+        this.capacity  = Math.max(4, capacity);
+        this.evaluator = evaluator;
+        this.root      = (n == 2) ? new QuadTreeNode() : new KDTreeNode.Default(n);
+    }
+
+    /**
+     * Inserts the specified data into this tree.
+     *
+     * @param  element  the element to insert.
+     * @return always {@code true} in current implementation.
+     */
+    public boolean add(final E element) {
+        ArgumentChecks.ensureNonNull("element", element);
+        insert(root, treeRegion, element);
+        count++;
+        return true;
+    }
+
+    /**
+     * 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  region   region of current node, as the center in first half and size in second half.
+     * @param  element  the element to insert.
+     */
+    @SuppressWarnings("unchecked")
+    private void insert(KDTreeNode parent, double[] region, final E element) {
+        boolean isRegionCopied = false;
+        final double[] point = evaluator.apply(element);
+        for (;;) {
+            final int quadrant = KDTreeNode.quadrant(point, region);
+            final Object child = parent.getChild(quadrant);
+            /*
+             * If the element will be stored in a new quadrant never used before,
+             * create a leaf node for that new quadrant. This is the easiest case.
+             */
+            if (child == null) {
+                parent.setChild(quadrant, new Object[] {element});
+                return;
+            }
+            /*
+             * If the quadrant where to store the element is a parent containing other nodes,
+             * enter in that quadrant and repeat all above checks with that node as the new parent.
+             * We continue down the tree until a leaf node is found.
+             */
+            if (child instanceof KDTreeNode) {
+                if (!isRegionCopied) {
+                    isRegionCopied = true;
+                    region = region.clone();
+                }
+                KDTreeNode.enterQuadrant(region, quadrant);
+                parent = (KDTreeNode) child;
+                continue;
+            }
+            /*
+             * At this point we reached a leaf of the tree. Store the element in that leaf
+             * if there is enough room.
+             */
+            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(quadrant, copy);
+                return;                                     // Leaf node can take the data — done.
+            }
+            /*
+             * 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.
+             */
+            if (!isRegionCopied) {
+                isRegionCopied = true;
+                region = region.clone();
+            }
+            KDTreeNode.enterQuadrant(region, quadrant);
+            final KDTreeNode branch = parent.newInstance();
+            for (final Object e : data) {
+                insert(branch, region, (E) e);
+            }
+            parent.setChild(quadrant, branch);
+            parent = branch;
+        }
+    }
+
+    /**
+     * Returns the number of elements in this tree.
+     *
+     * @return the number of elements in this tree.
+     */
+    public int size() {
+        return count;
+    }
+
     /**
-     * Creates an initially empty tree.
+     * Performs bounding box search.
+     *
+     * @param  searchRegion  envelope representing the rectangular search region.
+     * @return elements that are within the given radius from the point.
      */
-    KDTree() {
+    public Stream<E> queryByBoundingBox(final Envelope searchRegion) {
+        ArgumentChecks.ensureNonNull("searchRegion", searchRegion);
+        ArgumentChecks.ensureDimensionMatches("searchRegion", treeRegion.length >>> 1, 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/KDTreeNode.java b/storage/sis-storage/src/main/java/org/apache/sis/index/tree/KDTreeNode.java
index 1692c35..3edc329 100644
--- 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
@@ -53,22 +53,107 @@ abstract class KDTreeNode {
     }
 
     /**
+     * Returns the quadrant/octant relative to the given point.
+     * Each bit specifies the relative position for a dimension.
+     * For (<var>x</var>, <var>y</var>, <var>z</var>, <var>t</var>) coordinates, the pattern is:
+     *
+     * <ul>
+     *   <li>Bit 0 is the relative position of <var>x</var> coordinate: 0 for East   and 1 for West.</li>
+     *   <li>Bit 1 is the relative position of <var>y</var> coordinate: 0 for North  and 1 for South.</li>
+     *   <li>Bit 2 is the relative position of <var>z</var> coordinate: 0 for up     and 1 for down.</li>
+     *   <li>Bit 3 is the relative position of <var>t</var> coordinate: 0 for future and 1 for past.</li>
+     *   <li><i>etc.</i> for any additional dimensions.</li>
+     * </ul>
+     *
+     * @param  point   data (<var>x</var>, <var>y</var>, …) coordinate.
+     * @param  region  region of current node, as the center in first half and size in second half.
+     * @return an identification of the quadrant where the given point is located.
+     */
+    static int quadrant(final double[] point, final double[] region) {
+        int q = 0;
+        for (int i = region.length >>> 1; --i >= 0;) {          // Iterate only over center coordinates.
+            if (point[i] < region[i]) {
+                q |= (1 << i);
+            }
+        }
+        return q;
+    }
+
+    /**
+     * Modifies in place the specified for describing the coordinates of the specified quadrant.
+     *
+     * @param  region    region of current node, as the center in first half and size in second half.
+     * @param  quadrant  the quadrant as computed by {@link #quadrant(double[], double[])}.
+     */
+    static void enterQuadrant(final double[] region, final int quadrant) {
+        final int n = region.length >>> 1;
+        for (int i = n; --i >= 0;) {
+            region[i] += factor(quadrant, i) * (region[i+n] *= 0.5);    // TODO: use Math.fma with JDK9.
+        }
+    }
+
+    /**
+     * Returns 0.5 if the given quadrant is in the East/North/Up/Future side,
+     * or -0.5 if in the West/South/Down/Past side.
+     *
+     * @param  quadrant   the quadrant as computed by {@link #quadrant(double[], double[])}.
+     * @param  dimension  the dimension index: 0 for <var>x</var>, 1 for <var>y</var>, <i>etc.</i>
+     */
+    static double factor(final int quadrant, final int dimension) {
+        /*
+         * 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 & (1 << dimension))) << (Long.SIZE - 1 - dimension)));
+    }
+
+    /**
+     * Returns the child of this node that resides in the specified quadrant/octant.
+     * The return value 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>
+     *
+     * Any other kind of object is an error.
+     *
+     * @param  quadrant  quadrant/octant of child to get.
+     * @return child in the specified quadrant/octant.
+     * @throws IndexOutOfBoundsException if the specified quadrant/octant is out of bounds.
+     */
+    abstract Object getChild(int quadrant);
+
+    /**
+     * Sets the node's quadrant/octant to the specified child.
+     * The {@code child} value must be one of the types documented in {@link #getChild(int)}.
+     *
+     * @param quadrant  quadrant/octant where the child resides.
+     * @param child     child of this node in the specified quadrant/octant.
+     * @throws IndexOutOfBoundsException if the specified quadrant/octant is out of bounds.
+     */
+    abstract void setChild(int quadrant, Object child);
+
+    /**
+     * Creates a new instance of the same class than this node.
+     */
+    abstract KDTreeNode newInstance();
+
+    /**
      * 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 {
+    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>
+         * Each array element can be null or an instance of one of the classes
+         * documented in {@link KDTreeNode#getChild(int)}.
          */
         private final Object[] children;
 
@@ -80,5 +165,35 @@ abstract class KDTreeNode {
         Default(final int n) {
             children = new Object[n];
         }
+
+        /**
+         * Creates a new instance of the same class than this node.
+         */
+        @Override
+        final KDTreeNode newInstance() {
+            return new Default(children.length);
+        }
+
+        /**
+         * Returns the child of this node that resides in the specified quadrant/octant.
+         *
+         * @param  quadrant  quadrant/octant of child to get.
+         * @return child in the specified quadrant/octant.
+         */
+        @Override
+        final Object getChild(final int quadrant) {
+            return children[quadrant];
+        }
+
+        /**
+         * Sets the node's quadrant/octant to the specified child.
+         *
+         * @param quadrant   quadrant/octant where the child resides.
+         * @param child      child of this node in the specified quadrant/octant.
+         */
+        @Override
+        final void setChild(final int quadrant, final Object child) {
+            children[quadrant] = child;
+        }
     }
 }
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
index 322e724..21952a0 100644
--- 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
@@ -18,17 +18,17 @@ 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;
+import org.opengis.geometry.Envelope;
+import org.apache.sis.internal.util.Numerics;
 
 
 /**
  * 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.
+ * inclusion may be necessary. That additional check is performed by {@link #filter(double[])} and
+ * can be overridden by subclasses.
  *
  * @author  Martin Desruisseaux (Geomatys)
  * @version 1.1
@@ -40,26 +40,40 @@ import java.util.function.Function;
  */
 class NodeIterator<E> implements Spliterator<E> {
     /**
+     * The maximum number of dimensions that this class can support.
+     * This value is determined by the maximal capacity of {@link Cursor#quadrants}:
+     * 2<sup>{@value #MAX_DIMENSION}</sup> ≤ {@value Long#SIZE}.
+     */
+    static final int MAX_DIMENSION = 6;
+
+    /**
      * 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.
+     * The function computing a position for an arbitrary element of the tree.
      */
-    private final Function<? super E, ? extends Point2D> evaluator;
+    private final Function<? super E, double[]> evaluator;
 
     /**
-     * The region on which to iterate.
+     * A mask with a bit set for all quadrants. This is used as the initial value of
+     * {@link Cursor#quadrants} before to clear to bits of quadrants to not search.
      */
-    private final double xmin, ymin, xmax, ymax;
+    private final long bitmask;
+
+    /**
+     * The region on which to iterate. The first half are minimal coordinates
+     * and the second half are maximal coordinates.
+     */
+    private final double[] bounds;
 
     /**
      * 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.
+     * continues until all leaf nodes intersecting the search region have been traversed.
      */
     private Cursor<E> cursor;
 
@@ -82,23 +96,27 @@ class NodeIterator<E> implements Spliterator<E> {
     private Cursor<E> recycle;
 
     /**
-     * Creates a new iterator for the specified bounding box.
+     * Creates a new iterator for the specified search region.
      */
     @SuppressWarnings("ThisEscapedInObjectConstruction")
-    NodeIterator(final QuadTree<E> tree, final Rectangle2D region) {
+    NodeIterator(final KDTree<E> tree, final Envelope searchRegion) {
+        final int n = searchRegion.getDimension();
+        bitmask = Numerics.bitmask(1 << n) - 1;
+        bounds  = new double[n*2];
+        for (int i = n; --i >= 0;) {
+            bounds[i]   = searchRegion.getMinimum(i);
+            bounds[i+n] = searchRegion.getMaximum(i);
+        }
         evaluator = tree.evaluator;
-        xmin   = region.getMinX();
-        ymin   = region.getMinY();
-        xmax   = region.getMaxX();
-        ymax   = region.getMaxY();
-        cursor = new Cursor<>(tree);
+        cursor = new Cursor<>(tree.treeRegion);
+        cursor.node = tree.root;
         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
+     * The starting point is {@link KDTree#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).
      */
@@ -118,7 +136,7 @@ class NodeIterator<E> implements Spliterator<E> {
          * The node for which to iterate over elements. Only the quadrants/octants identified
          * by the {@link #quadrants} bitmask will be traversed.
          */
-        QuadTreeNode node;
+        KDTreeNode node;
 
         /**
          * Bitmask of quadrants/octants on which to iterate. Quadrants/octants are iterated from rightmost
@@ -127,36 +145,28 @@ class NodeIterator<E> implements Spliterator<E> {
          *
          * <p><b>Note:</b> we take "quadrant" name from {@link QuadTree}, but this algorithm can actually
          * be used with more dimensions.</p>
+         *
+         * @see #MAX_DIMENSION
          */
-        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;
+        long quadrants;
 
         /**
-         * Creates a new cursor with all values initialized to zero.
-         * It is caller responsibility to initialize all fields.
+         * (<var>x</var>,<var>y</var>,…) coordinates in the center of {@link #node} node,
+         * followed by (<var>Δx</var>,<var>Δy</var>,…) sizes of the {@link #node} node.
          */
-        private Cursor() {
-        }
+        private final double[] region;
 
         /**
-         * Creates a new cursor initialized to the root node of the given tree.
+         * Creates a new cursor. It is caller responsibility to initialize the {@link #node} field, the
+         * {@link #parent} field if a parent exists, and to invoke {@link #findIntersections(NodeIterator)}.
          */
-        Cursor(final QuadTree<E> tree) {
-            node = tree.root;
-            cx   = tree.centerX;
-            cy   = tree.centerY;
-            dx   = tree.width;
-            dy   = tree.height;
+        Cursor(final double[] region) {
+            this.region = region.clone();       // Must be cloned because this class may modify those values.
         }
 
         /**
          * 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.
+         * must be invoked after {@link #region} values 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.
@@ -164,14 +174,53 @@ class NodeIterator<E> implements Spliterator<E> {
          * @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.
+            final double[] bounds = it.bounds;
+            quadrants = it.bitmask;                                 // Bits initially set for all quadrants.
+            final int n = bounds.length >>> 1;
+            for (int i = n; --i >= 0;) {
+                final double c = region[i];
+                /*
+                 * Example: given xmin and xmax the bounds of the search region in dimension of x,
+                 * and cx the x coordinate of the center of current node, then:
+                 *
+                 *   if !(xmin <= cx) then we want to clear the bits of all quadrants on West side.
+                 *   if !(xmax >= cx) then we want to clear the bits of all quadrants on East side.
+                 *
+                 * Quadrants on the East side are all quadrants with a number where bit 0 is unset.
+                 * Those quadrants are 0, 2, 4, 6, etc. Conversely quadrants on the West side have
+                 * bit 0 set. They are 1, 3, 5, 7, etc.
+                 *
+                 * Applying the same rational on y:
+                 *
+                 *   if !(ymin <= cy) then we want to clear bits of all quadrants on South side.
+                 *   if !(ymax >= cy) then we want to clear bits of all quadrants on North side.
+                 *
+                 * Quadrants on the North side have bit 1 unset:
+                 */
+                if (!(bounds[i]   <= c)) quadrants &=  CLEAR_MASKS[i];      // Use '!' for catching NaN.
+                if (!(bounds[i+n] >= c)) quadrants &= ~CLEAR_MASKS[i];
+            }
         }
 
         /**
+         * Masks for clearing the bits of all quadrants that do not intersect the search region on the left side.
+         * For example for <var>x</var> dimension, this is the mask to apply if the {@code xmin <= cx} condition
+         * is false. In this example {@code CLEAR_MASKS[0]} clears the bits of all quadrants on the West side,
+         * which are quadrants 1, 3, 5, <i>etc.</i>
+         *
+         * <p>The index in this array is the dimension in which the quadrant do not intersect the search region.
+         * The length of this array should be equal to {@link #MAX_DIMENSION}.</p>
+         */
+        private static final long[] CLEAR_MASKS = {
+            0b0101010101010101010101010101010101010101010101010101010101010101L,
+            0b0011001100110011001100110011001100110011001100110011001100110011L,
+            0b0000111100001111000011110000111100001111000011110000111100001111L,
+            0b0000000011111111000000001111111100000000111111110000000011111111L,
+            0b0000000000000000111111111111111100000000000000001111111111111111L,
+            0b0000000000000000000000000000000011111111111111111111111111111111L
+        };
+
+        /**
          * 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
@@ -187,13 +236,13 @@ class NodeIterator<E> implements Spliterator<E> {
         final Cursor<E> push(final NodeIterator<E> it, final int q) {
             Cursor<E> c = it.recycle;
             if (c == null) {
-                c = new Cursor<>();
+                c = new Cursor<>(region);
             } else {
                 it.recycle = c.parent;
+                System.arraycopy(region, 0, c.region, 0, region.length);
             }
+            KDTreeNode.enterQuadrant(c.region, q);
             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;
         }
 
@@ -208,8 +257,7 @@ class NodeIterator<E> implements Spliterator<E> {
          * @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);
+            KDTreeNode.enterQuadrant(region, q);
         }
 
         /**
@@ -227,18 +275,19 @@ class NodeIterator<E> implements Spliterator<E> {
     }
 
     /**
-     * Returns an array of elements that <em>may</em> intersect the area of interest,
+     * Returns an array of elements that <em>may</em> intersect the search region,
      * 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.
+     * if the points are really in the search region; callers may need to filter the
+     * returned array.
      *
-     * @return array of elements that may be in the area of interest (AOI),
+     * @return array of elements that may be in the search region,
      *         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);
+                final int q = Long.numberOfTrailingZeros(cursor.quadrants);
                 cursor.quadrants &= ~(1 << q);
                 final Object child = cursor.node.getChild(q);
                 if (child != null) {
@@ -307,13 +356,15 @@ class NodeIterator<E> implements Spliterator<E> {
      * @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);
+    protected boolean filter(final double[] position) {
+        final int n = bounds.length >>> 1;
+        for (int i = n; --i >= 0;) {
+            final double p = position[i];
+            if (!(p >= bounds[i] && p <= bounds[i+n])) {            // Use '!' for catching NaN.
+                return false;
+            }
         }
-        return false;
+        return true;
     }
 
     /**
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 22c4475..34db1c2 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,16 +16,12 @@
  */
 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.stream.StreamSupport;
-import org.apache.sis.util.ArgumentChecks;
+import org.opengis.geometry.Envelope;
 
 
 /**
- * Implementation of QuadTree Index.
+ * Implementation of a point QuadTree Index.
  * See {@link KDTree} for a note about thread-safety.
  *
  * <p><b>References:</b></p>
@@ -44,140 +40,14 @@ import org.apache.sis.util.ArgumentChecks;
  */
 public final class QuadTree<E> extends KDTree<E> {
     /**
-     * The root node of this QuadTree.
-     */
-    final QuadTreeNode root;
-
-    /**
-     * 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.
-     */
-    private final int capacity;
-
-    /**
-     * Number of elements in this QuadTree.
-     */
-    private int count;
-
-    /**
-     * Coordinates of the point in the center of the area of interest.
-     */
-    final double centerX, centerY;
-
-    /**
-     * Size of the area of interest.
-     */
-    final double width, height;
-
-    /**
-     * The function computing a position for an arbitrary element of this tree.
-     */
-    final Function<? super E, ? extends Point2D> evaluator;
-
-    /**
      * 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.
+     * The given envelope must be two-dimensional.
      *
      * @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.
      */
-    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();
-    }
-
-    /**
-     * Inserts the specified data into this QuadTree.
-     *
-     * @param  element  the element to insert.
-     * @return always {@code true} in current implementation.
-     */
-    public boolean add(final E element) {
-        ArgumentChecks.ensureNonNull("element", element);
-        insert(root, centerX, centerY, width, height, element);
-        count++;
-        return true;
-    }
-
-    /**
-     * 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;
-            }
-            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.
-                }
-                /*
-                 * 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;
-            }
-        }
-    }
-
-    /**
-     * Returns the number of elements in this tree.
-     *
-     * @return the number of elements in this tree.
-     */
-    public int size() {
-        return count;
-    }
-
-    /**
-     * Performs bounding box search.
-     *
-     * @param  searchRegion  envelope representing the rectangular search region.
-     * @return elements that are within the given radius from the point.
-     */
-    public Stream<E> queryByBoundingBox(final Rectangle2D searchRegion) {
-        return StreamSupport.stream(new NodeIterator<>(this, searchRegion), false);
-        // TODO: make parallel after we tested most extensively.
+    public QuadTree(final Envelope bounds, final Function<? super E, double[]> evaluator, final int capacity) {
+        super(bounds, evaluator, capacity);
     }
 }
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 1024768..036db7a 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
@@ -40,62 +40,11 @@ final class QuadTreeNode extends KDTreeNode {
      * </ul>
      *
      * 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.
+     * enumeration is not generalizable).
      */
     static final int NE = 0, NW = 1, SE = 2, SW = 3;
 
     /**
-     * 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.
-     *
-     * 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".
-     */
-    private static final int X_MASK = 1, Y_MASK = 2;
-
-    /**
-     * Returns the quadrant relative to the given point.
-     *
-     * @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.
-     */
-    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;
-    }
-
-    /**
-     * Returns 0.5 if the given quadrant is in the East side, or -0.5 if in the West side.
-     */
-    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)));
-    }
-
-    /**
-     * Returns 0.5 if the given quadrant is in the North side, or -0.5 if in the South side.
-     */
-    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)));
-    }
-
-    /**
      * The child nodes in 4 quadrants of equal size.
      * Quadrants are North-West, North-East, South-East and South-West.
      */
@@ -108,19 +57,28 @@ final class QuadTreeNode extends KDTreeNode {
     }
 
     /**
+     * Creates a new instance of the same class than this node.
+     */
+    @Override
+    final KDTreeNode newInstance() {
+        return new QuadTreeNode();
+    }
+
+    /**
      * Returns the child of this node that resides in the specified quadrant.
      *
-     * @param  q  quadrant of child to get.
+     * @param  quadrant  quadrant of child to get.
      * @return child in the specified quadrant.
      */
-    final Object getChild(final int q) {
+    @Override
+    final Object getChild(final int quadrant) {
         final Object child;
-        switch (q) {
+        switch (quadrant) {
             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);
+            default: throw new IndexOutOfBoundsException(/*quadrant*/);     // TODO: uncomment with JDK9.
         }
         return child;
     }
@@ -128,16 +86,17 @@ final class QuadTreeNode extends KDTreeNode {
     /**
      * Sets the node's quadrant to the specified child.
      *
-     * @param q      quadrant where the child resides.
-     * @param child  child of this node in the specified quadrant.
+     * @param quadrant  quadrant where the child resides.
+     * @param child     child of this node in the specified quadrant.
      */
-    final void setChild(final int q, final Object child) {
-        switch (q) {
+    @Override
+    final void setChild(final int quadrant, final Object child) {
+        switch (quadrant) {
             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);
+            default: throw new IndexOutOfBoundsException(/*quadrant*/);     // TODO: uncomment with JDK9.
         }
     }
 }
diff --git a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/NodeIteratorTest.java b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/NodeIteratorTest.java
new file mode 100644
index 0000000..1fe0e31
--- /dev/null
+++ b/storage/sis-storage/src/test/java/org/apache/sis/index/tree/NodeIteratorTest.java
@@ -0,0 +1,112 @@
+/*
+ * 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.lang.reflect.Field;
+import org.apache.sis.test.TestCase;
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+
+/**
+ * Tests {@link NodeIterator}. Also contains opportunistic tests of {@link QuadTreeNode}
+ * methods that are needed by the iterator.
+ *
+ * @author  Chris Mattmann
+ * @author  Martin Desruisseaux (Geomatys)
+ * @version 1.1
+ * @since   0.1
+ * @module
+ */
+public final strictfp class NodeIteratorTest extends TestCase {
+    /**
+     * Verifies the value of {@link NodeIterator#MAX_DIMENSION}.
+     * That value is restricted by the capacity of {@code long}.
+     */
+    @Test
+    public void verifyMaxDimension() {
+        assertEquals(Long.SIZE, 1 << NodeIterator.MAX_DIMENSION);
+    }
+
+    /**
+     * Tests {@link QuadTreeNode#factor(int,int)} for dimension 0 (X).
+     */
+    @Test
+    public void testFactorX() {
+        assertEquals(+0.5, QuadTreeNode.factor(QuadTreeNode.NE, 0), STRICT);
+        assertEquals(-0.5, QuadTreeNode.factor(QuadTreeNode.NW, 0), STRICT);
+        assertEquals(+0.5, QuadTreeNode.factor(QuadTreeNode.SE, 0), STRICT);
+        assertEquals(-0.5, QuadTreeNode.factor(QuadTreeNode.SW, 0), STRICT);
+    }
+
+    /**
+     * Tests {@link QuadTreeNode#factor(int,int)} for dimension 1 (Y).
+     */
+    @Test
+    public void testFactorY() {
+        assertEquals(+0.5, QuadTreeNode.factor(QuadTreeNode.NE, 1), STRICT);
+        assertEquals(+0.5, QuadTreeNode.factor(QuadTreeNode.NW, 1), STRICT);
+        assertEquals(-0.5, QuadTreeNode.factor(QuadTreeNode.SE, 1), STRICT);
+        assertEquals(-0.5, QuadTreeNode.factor(QuadTreeNode.SW, 1), STRICT);
+    }
+
+    /**
+     * Tests {@link QuadTreeNode#quadrant(double[], double[])}.
+     */
+    @Test
+    public void testQuadrant() {
+        final double[] region = new double[] {200, 300, Double.NaN, Double.NaN};
+        assertEquals(QuadTreeNode.SW, QuadTreeNode.quadrant(new double[] {195, 285}, region));
+        assertEquals(QuadTreeNode.NW, QuadTreeNode.quadrant(new double[] {195, 305}, region));
+        assertEquals(QuadTreeNode.SE, QuadTreeNode.quadrant(new double[] {210, 280}, region));
+        assertEquals(QuadTreeNode.NE, QuadTreeNode.quadrant(new double[] {215, 305}, region));
+    }
+
+    /**
+     * Tests {@link QuadTreeNode#enterQuadrant(double[], int)}.
+     */
+    @Test
+    public void testEnterQuadrant() {
+        final double[] region = new double[] {200, 300, 100, 60};
+        QuadTreeNode.enterQuadrant(region, QuadTreeNode.SE);
+        assertArrayEquals(new double[] {225, 285, 50, 30}, region, STRICT);
+    }
+
+    /**
+     * Verifies {@link org.apache.sis.index.tree.NodeIterator.Cursor#CLEAR_MASKS}.
+     *
+     * @throws ReflectiveOperationException if this test can not access to private field that we want to verify.
+     */
+    @Test
+    public void verifyClearMasks() throws ReflectiveOperationException {
+        final Field f = NodeIterator.class.getDeclaredClasses()[0].getDeclaredField("CLEAR_MASKS");
+        f.setAccessible(true);
+        final long[] masks = (long[]) f.get(null);
+        assertEquals(NodeIterator.MAX_DIMENSION, masks.length);
+        for (int d=0; d<NodeIterator.MAX_DIMENSION; d++) {
+            long expected = 0;
+            final long m = 1L << d;
+            for (int i=0; i<Long.SIZE; i++) {
+                if ((i & m) == 0) {
+                    expected |= (1L << i);
+                }
+            }
+            assertEquals(expected, masks[d]);
+        }
+    }
+}
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
deleted file mode 100644
index 86b4b93..0000000
--- a/storage/sis-storage/src/test/java/org/apache/sis/index/tree/QuadTreeNodeTest.java
+++ /dev/null
@@ -1,56 +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 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
index 016a7cf..f9ebecc 100644
--- 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
@@ -21,10 +21,9 @@ 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.opengis.geometry.Envelope;
+import org.apache.sis.geometry.DirectPosition2D;
+import org.apache.sis.geometry.Envelope2D;
 import org.apache.sis.test.DependsOn;
 import org.apache.sis.test.TestCase;
 import org.apache.sis.test.TestUtilities;
@@ -41,7 +40,7 @@ import static org.junit.Assert.*;
  * @since   1.1
  * @module
  */
-@DependsOn(QuadTreeNodeTest.class)
+@DependsOn(NodeIteratorTest.class)
 public final strictfp class QuadTreeTest extends TestCase {
     /**
      * Bounds of the region where to create points. Intentionally use asymmetric bounds
@@ -66,13 +65,11 @@ public final strictfp class QuadTreeTest extends TestCase {
 
     /**
      * The elements to be added in the {@link QuadTree} to test.
-     * This element extends {@link Point2D} for convenience, but this is not a requirement.
+     * This element extends {@link DirectPosition2D} 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;
-
+    @SuppressWarnings("serial")
+    private static final class Element extends DirectPosition2D {
         /** Creates a new element with random coordinates. */
         Element(final Random random) {
             x = random.nextInt(XMAX - XMIN) + XMIN;
@@ -84,10 +81,10 @@ public final strictfp class QuadTreeTest extends TestCase {
         @Override public String toString() {return "P(" + x + ", " + y + ')';}
 
         @Override public void setLocation(double x, double y) {
-            fail("Location shoulf not be modified.");
+            fail("Location should not be modified.");
         }
 
-        @Override public Object clone() {
+        @Override public DirectPosition2D clone() {
             fail("Location should not be cloned.");
             return super.clone();
         }
@@ -97,8 +94,13 @@ public final strictfp class QuadTreeTest extends TestCase {
      * Creates a tree filled with random values.
      */
     private void createTree() {
+        final Envelope2D region = new Envelope2D();
+        region.x      = XMIN;
+        region.y      = YMIN;
+        region.width  = XMAX - XMIN;
+        region.height = YMAX - YMIN;
         random = TestUtilities.createRandomNumberGenerator();
-        tree = new QuadTree<>(new Rectangle(XMIN, YMIN, XMAX - XMIN, YMAX - YMIN), Function.identity(), 5);
+        tree = new QuadTree<>(region, Element::getCoordinate, 5);
         int count = random.nextInt(100) + 200;
         data = new ArrayList<>(count);
         while (--count >= 0) {
@@ -109,7 +111,7 @@ public final strictfp class QuadTreeTest extends TestCase {
     }
 
     /**
-     * Tests {@link QuadTree#queryByBoundingBox(Rectangle2D)} with random coordinates.
+     * Tests {@link QuadTree#queryByBoundingBox(Envelope)} with random coordinates.
      * This method performs some searches in random regions and compare the results
      * against searches performed by raw force.
      */
@@ -117,7 +119,7 @@ public final strictfp class QuadTreeTest extends TestCase {
     public void testQueryByBoundingBox() {
         createTree();
         final Set<Element> expected = new HashSet<>();
-        final Rectangle2D.Double region = new Rectangle2D.Double();
+        final Envelope2D region = new Envelope2D();
         for (int i=0; i<20; i++) {
             final int xmin = random.nextInt(XMAX - XMIN) + XMIN;
             final int ymin = random.nextInt(YMAX - YMIN) + YMIN;
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 cc09ca9..eadc171 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
@@ -30,7 +30,7 @@ import org.junit.BeforeClass;
  * @module
  */
 @Suite.SuiteClasses({
-    org.apache.sis.index.tree.QuadTreeNodeTest.class,
+    org.apache.sis.index.tree.NodeIteratorTest.class,
     org.apache.sis.index.tree.QuadTreeTest.class,
     org.apache.sis.internal.storage.CodeTypeTest.class,
     org.apache.sis.internal.storage.io.IOUtilitiesTest.class,


Mime
View raw message