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 <[email protected]> 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 [email protected] -nbproject/build-impl.xml.data.CRC32=2eb6a452 +nbproject/build-impl.xml.data.CRC32=0881b25a nbproject/build-impl.xml.script.CRC32=27d6eb56 nbproject/[email protected] 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,
