You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sedona.apache.org by ji...@apache.org on 2020/12/27 00:37:36 UTC
[incubator-sedona] branch master updated: [SEDONA-1] Move to JTS
1.18 (#500)
This is an automated email from the ASF dual-hosted git repository.
jiayu pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/incubator-sedona.git
The following commit(s) were added to refs/heads/master by this push:
new cfb7817 [SEDONA-1] Move to JTS 1.18 (#500)
cfb7817 is described below
commit cfb781722f4c375f501db0f0fa01ef44bc57a8dc
Author: Jia Yu <ji...@apache.org>
AuthorDate: Sat Dec 26 16:37:30 2020 -0800
[SEDONA-1] Move to JTS 1.18 (#500)
* Update GitHub action
* Cache Maven package
* Separate maven and python test
* Add FlipCoordinate test for RDD API
* Add FlipCoordinate test for RDD API
* Use JTS 1.18
---
.../core/geometryObjects/SpatialIndexSerde.java | 14 +-
.../joinJudgement/DynamicIndexLookupJudgement.java | 4 +-
.../core/knnJudgement/KnnJudgementUsingIndex.java | 4 +-
.../sedona/core/serde/SedonaKryoRegistrator.java | 4 +-
.../spatialPartitioning/RtreePartitioning.java | 6 +-
.../sedona/core/spatialRddTool/IndexBuilder.java | 4 +-
.../sedona/jts/index/quadtree/DoubleBits.java | 152 -----
.../sedona/jts/index/quadtree/IntervalSize.java | 52 --
.../org/apache/sedona/jts/index/quadtree/Key.java | 81 ---
.../org/apache/sedona/jts/index/quadtree/Node.java | 183 ------
.../apache/sedona/jts/index/quadtree/NodeBase.java | 236 --------
.../apache/sedona/jts/index/quadtree/Quadtree.java | 246 --------
.../org/apache/sedona/jts/index/quadtree/Root.java | 99 ----
.../sedona/jts/index/strtree/AbstractNode.java | 136 -----
.../sedona/jts/index/strtree/AbstractSTRtree.java | 484 ----------------
.../apache/sedona/jts/index/strtree/Boundable.java | 30 -
.../sedona/jts/index/strtree/BoundablePair.java | 211 -------
.../strtree/BoundablePairDistanceComparator.java | 65 ---
.../sedona/jts/index/strtree/EnvelopeDistance.java | 120 ----
.../jts/index/strtree/GeometryItemDistance.java | 50 --
.../apache/sedona/jts/index/strtree/Interval.java | 57 --
.../sedona/jts/index/strtree/ItemBoundable.java | 37 --
.../sedona/jts/index/strtree/ItemDistance.java | 47 --
.../apache/sedona/jts/index/strtree/SIRtree.java | 109 ----
.../apache/sedona/jts/index/strtree/STRtree.java | 617 ---------------------
.../jts/index/quadtree/IndexSerde.java | 2 +-
.../jts/index/strtree/IndexSerde.java | 2 +-
.../geometryObjects/SpatialIndexSerdeTest.java | 4 +-
.../sedona/core/spatialRDD/LineStringRDDTest.java | 2 +-
.../sedona/core/spatialRDD/PointRDDTest.java | 2 +-
.../sedona/core/spatialRDD/PolygonRDDTest.java | 2 +-
.../sedona/core/spatialRDD/RectangleRDDTest.java | 2 +-
pom.xml | 2 +-
33 files changed, 27 insertions(+), 3039 deletions(-)
diff --git a/core/src/main/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerde.java b/core/src/main/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerde.java
index ab47d35..a8e5cbe 100644
--- a/core/src/main/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerde.java
+++ b/core/src/main/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerde.java
@@ -24,9 +24,9 @@ import com.esotericsoftware.kryo.Serializer;
import com.esotericsoftware.kryo.io.Input;
import com.esotericsoftware.kryo.io.Output;
import org.apache.log4j.Logger;
-import org.apache.sedona.jts.index.quadtree.IndexSerde;
-import org.apache.sedona.jts.index.quadtree.Quadtree;
-import org.apache.sedona.jts.index.strtree.STRtree;
+import org.locationtech.jts.index.quadtree.IndexSerde;
+import org.locationtech.jts.index.quadtree.Quadtree;
+import org.locationtech.jts.index.strtree.STRtree;
/**
* Provides methods to efficiently serialize and deserialize spatialIndex types.
@@ -69,8 +69,8 @@ public class SpatialIndexSerde
//serialize rtree index
writeType(output, Type.RTREE);
STRtree tree = (STRtree) o;
- org.apache.sedona.jts.index.strtree.IndexSerde indexSerde
- = new org.apache.sedona.jts.index.strtree.IndexSerde();
+ org.locationtech.jts.index.strtree.IndexSerde indexSerde
+ = new org.locationtech.jts.index.strtree.IndexSerde();
indexSerde.write(kryo, output, tree);
}
else {
@@ -89,8 +89,8 @@ public class SpatialIndexSerde
return indexSerde.read(kryo, input);
}
case RTREE: {
- org.apache.sedona.jts.index.strtree.IndexSerde indexSerde =
- new org.apache.sedona.jts.index.strtree.IndexSerde();
+ org.locationtech.jts.index.strtree.IndexSerde indexSerde =
+ new org.locationtech.jts.index.strtree.IndexSerde();
return indexSerde.read(kryo, input);
}
default: {
diff --git a/core/src/main/java/org/apache/sedona/core/joinJudgement/DynamicIndexLookupJudgement.java b/core/src/main/java/org/apache/sedona/core/joinJudgement/DynamicIndexLookupJudgement.java
index 418d319..c1fbcf5 100644
--- a/core/src/main/java/org/apache/sedona/core/joinJudgement/DynamicIndexLookupJudgement.java
+++ b/core/src/main/java/org/apache/sedona/core/joinJudgement/DynamicIndexLookupJudgement.java
@@ -27,13 +27,13 @@ import org.apache.sedona.core.enums.IndexType;
import org.apache.sedona.core.enums.JoinBuildSide;
import org.apache.sedona.core.monitoring.Metric;
import org.apache.sedona.core.utils.TimeUtils;
-import org.apache.sedona.jts.index.quadtree.Quadtree;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.apache.spark.TaskContext;
import org.apache.spark.api.java.function.FlatMapFunction2;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.index.SpatialIndex;
+import org.locationtech.jts.index.quadtree.Quadtree;
+import org.locationtech.jts.index.strtree.STRtree;
import javax.annotation.Nullable;
diff --git a/core/src/main/java/org/apache/sedona/core/knnJudgement/KnnJudgementUsingIndex.java b/core/src/main/java/org/apache/sedona/core/knnJudgement/KnnJudgementUsingIndex.java
index d9299f1..f7a2b10 100644
--- a/core/src/main/java/org/apache/sedona/core/knnJudgement/KnnJudgementUsingIndex.java
+++ b/core/src/main/java/org/apache/sedona/core/knnJudgement/KnnJudgementUsingIndex.java
@@ -19,11 +19,11 @@
package org.apache.sedona.core.knnJudgement;
-import org.apache.sedona.jts.index.strtree.GeometryItemDistance;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.apache.spark.api.java.function.FlatMapFunction;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.index.SpatialIndex;
+import org.locationtech.jts.index.strtree.GeometryItemDistance;
+import org.locationtech.jts.index.strtree.STRtree;
import java.io.Serializable;
import java.util.ArrayList;
diff --git a/core/src/main/java/org/apache/sedona/core/serde/SedonaKryoRegistrator.java b/core/src/main/java/org/apache/sedona/core/serde/SedonaKryoRegistrator.java
index 5fc4535..57894ea 100644
--- a/core/src/main/java/org/apache/sedona/core/serde/SedonaKryoRegistrator.java
+++ b/core/src/main/java/org/apache/sedona/core/serde/SedonaKryoRegistrator.java
@@ -24,8 +24,6 @@ import org.apache.log4j.Logger;
import org.apache.sedona.core.geometryObjects.Circle;
import org.apache.sedona.core.geometryObjects.GeometrySerde;
import org.apache.sedona.core.geometryObjects.SpatialIndexSerde;
-import org.apache.sedona.jts.index.quadtree.Quadtree;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.apache.spark.serializer.KryoRegistrator;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.GeometryCollection;
@@ -35,6 +33,8 @@ import org.locationtech.jts.geom.MultiPoint;
import org.locationtech.jts.geom.MultiPolygon;
import org.locationtech.jts.geom.Point;
import org.locationtech.jts.geom.Polygon;
+import org.locationtech.jts.index.quadtree.Quadtree;
+import org.locationtech.jts.index.strtree.STRtree;
public class SedonaKryoRegistrator
implements KryoRegistrator
diff --git a/core/src/main/java/org/apache/sedona/core/spatialPartitioning/RtreePartitioning.java b/core/src/main/java/org/apache/sedona/core/spatialPartitioning/RtreePartitioning.java
index 758cfdf..d015dfb 100644
--- a/core/src/main/java/org/apache/sedona/core/spatialPartitioning/RtreePartitioning.java
+++ b/core/src/main/java/org/apache/sedona/core/spatialPartitioning/RtreePartitioning.java
@@ -19,10 +19,10 @@
package org.apache.sedona.core.spatialPartitioning;
-import org.apache.sedona.jts.index.strtree.AbstractNode;
-import org.apache.sedona.jts.index.strtree.Boundable;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.locationtech.jts.geom.Envelope;
+import org.locationtech.jts.index.strtree.AbstractNode;
+import org.locationtech.jts.index.strtree.Boundable;
+import org.locationtech.jts.index.strtree.STRtree;
import java.io.Serializable;
import java.util.ArrayList;
diff --git a/core/src/main/java/org/apache/sedona/core/spatialRddTool/IndexBuilder.java b/core/src/main/java/org/apache/sedona/core/spatialRddTool/IndexBuilder.java
index 84a0457..3b3d34e 100644
--- a/core/src/main/java/org/apache/sedona/core/spatialRddTool/IndexBuilder.java
+++ b/core/src/main/java/org/apache/sedona/core/spatialRddTool/IndexBuilder.java
@@ -20,12 +20,12 @@
package org.apache.sedona.core.spatialRddTool;
import org.apache.sedona.core.enums.IndexType;
-import org.apache.sedona.jts.index.quadtree.Quadtree;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.apache.spark.api.java.function.FlatMapFunction;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.index.SpatialIndex;
+import org.locationtech.jts.index.quadtree.Quadtree;
+import org.locationtech.jts.index.strtree.STRtree;
import java.util.HashSet;
import java.util.Iterator;
diff --git a/core/src/main/java/org/apache/sedona/jts/index/quadtree/DoubleBits.java b/core/src/main/java/org/apache/sedona/jts/index/quadtree/DoubleBits.java
deleted file mode 100644
index 33f29b4..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/quadtree/DoubleBits.java
+++ /dev/null
@@ -1,152 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.quadtree;
-
-/**
- * DoubleBits manipulates Double numbers
- * by using bit manipulation and bit-field extraction.
- * For some operations (such as determining the exponent)
- * this is more accurate than using mathematical operations
- * (which suffer from round-off error).
- * <p>
- * The algorithms and constants in this class
- * apply only to IEEE-754 double-precision floating point format.
- *
- * @version 1.7
- */
-public class DoubleBits {
-
- public static final int EXPONENT_BIAS = 1023;
-
- public static double powerOf2(int exp)
- {
- if (exp > 1023 || exp < -1022)
- throw new IllegalArgumentException("Exponent out of bounds");
- long expBias = exp + EXPONENT_BIAS;
- long bits = expBias << 52;
- return Double.longBitsToDouble(bits);
- }
-
- public static int exponent(double d)
- {
- DoubleBits db = new DoubleBits(d);
- return db.getExponent();
- }
-
- public static double truncateToPowerOfTwo(double d)
- {
- DoubleBits db = new DoubleBits(d);
- db.zeroLowerBits(52);
- return db.getDouble();
- }
-
- public static String toBinaryString(double d)
- {
- DoubleBits db = new DoubleBits(d);
- return db.toString();
- }
-
- public static double maximumCommonMantissa(double d1, double d2)
- {
- if (d1 == 0.0 || d2 == 0.0) return 0.0;
-
- DoubleBits db1 = new DoubleBits(d1);
- DoubleBits db2 = new DoubleBits(d2);
-
- if (db1.getExponent() != db2.getExponent()) return 0.0;
-
- int maxCommon = db1.numCommonMantissaBits(db2);
- db1.zeroLowerBits(64 - (12 + maxCommon));
- return db1.getDouble();
- }
-
- private double x;
- private long xBits;
-
- public DoubleBits(double x)
- {
- this.x = x;
- xBits = Double.doubleToLongBits(x);
- }
-
- public double getDouble()
- {
- return Double.longBitsToDouble(xBits);
- }
-
- /**
- * Determines the exponent for the number
- */
- public int biasedExponent()
- {
- int signExp = (int) (xBits >> 52);
- int exp = signExp & 0x07ff;
- return exp;
- }
-
- /**
- * Determines the exponent for the number
- */
- public int getExponent()
- {
- return biasedExponent() - EXPONENT_BIAS;
- }
-
- public void zeroLowerBits(int nBits)
- {
- long invMask = (1L << nBits) - 1L;
- long mask = ~ invMask;
- xBits &= mask;
- }
-
- public int getBit(int i)
- {
- long mask = (1L << i);
- return (xBits & mask) != 0 ? 1 : 0;
- }
-
- /**
- * This computes the number of common most-significant bits in the mantissa.
- * It does not count the hidden bit, which is always 1.
- * It does not determine whether the numbers have the same exponent - if they do
- * not, the value computed by this function is meaningless.
- * @param db
- * @return the number of common most-significant mantissa bits
- */
- public int numCommonMantissaBits(DoubleBits db)
- {
- for (int i = 0; i < 52; i++)
- {
- if (getBit(i) != db.getBit(i))
- return i;
- }
- return 52;
- }
-
- /**
- * A representation of the Double bits formatted for easy readability
- */
- public String toString()
- {
- String numStr = Long.toBinaryString(xBits);
- // 64 zeroes!
- String zero64 = "0000000000000000000000000000000000000000000000000000000000000000";
- String padStr = zero64 + numStr;
- String bitStr = padStr.substring(padStr.length() - 64);
- String str = bitStr.substring(0, 1) + " "
- + bitStr.substring(1, 12) + "(" + getExponent() + ") "
- + bitStr.substring(12)
- + " [ " + x + " ]";
- return str;
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/quadtree/IntervalSize.java b/core/src/main/java/org/apache/sedona/jts/index/quadtree/IntervalSize.java
deleted file mode 100644
index aea891a..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/quadtree/IntervalSize.java
+++ /dev/null
@@ -1,52 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.quadtree;
-
-/**
- * Provides a test for whether an interval is
- * so small it should be considered as zero for the purposes of
- * inserting it into a binary tree.
- * The reason this check is necessary is that round-off error can
- * cause the algorithm used to subdivide an interval to fail, by
- * computing a midpoint value which does not lie strictly between the
- * endpoints.
- *
- * @version 1.7
- */
-public class IntervalSize {
-
- /**
- * This value is chosen to be a few powers of 2 less than the
- * number of bits available in the double representation (i.e. 53).
- * This should allow enough extra precision for simple computations to be correct,
- * at least for comparison purposes.
- */
- public static final int MIN_BINARY_EXPONENT = -50;
-
- /**
- * Computes whether the interval [min, max] is effectively zero width.
- * I.e. the width of the interval is so much less than the
- * location of the interval that the midpoint of the interval cannot be
- * represented precisely.
- */
- public static boolean isZeroWidth(double min, double max)
- {
- double width = max - min;
- if (width == 0.0) return true;
-
- double maxAbs = Math.max(Math.abs(min), Math.abs(max));
- double scaledInterval = width / maxAbs;
- int level = DoubleBits.exponent(scaledInterval);
- return level <= MIN_BINARY_EXPONENT;
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/quadtree/Key.java b/core/src/main/java/org/apache/sedona/jts/index/quadtree/Key.java
deleted file mode 100644
index 79538b1..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/quadtree/Key.java
+++ /dev/null
@@ -1,81 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.quadtree;
-
-import org.locationtech.jts.geom.Coordinate;
-import org.locationtech.jts.geom.Envelope;
-
-/**
- * A Key is a unique identifier for a node in a quadtree.
- * It contains a lower-left point and a level number. The level number
- * is the power of two for the size of the node envelope
- *
- * @version 1.7
- */
-public class Key {
-
- public static int computeQuadLevel(Envelope env)
- {
- double dx = env.getWidth();
- double dy = env.getHeight();
- double dMax = dx > dy ? dx : dy;
- int level = DoubleBits.exponent(dMax) + 1;
- return level;
- }
-
- // the fields which make up the key
- private Coordinate pt = new Coordinate();
- private int level = 0;
- // auxiliary data which is derived from the key for use in computation
- private Envelope env = null;
-
- public Key(Envelope itemEnv)
- {
- computeKey(itemEnv);
- }
-
- public Coordinate getPoint() { return pt; }
- public int getLevel() { return level; }
- public Envelope getEnvelope() { return env; }
-
- public Coordinate getCentre()
- {
- return new Coordinate(
- (env.getMinX() + env.getMaxX()) / 2,
- (env.getMinY() + env.getMaxY()) / 2
- );
- }
- /**
- * return a square envelope containing the argument envelope,
- * whose extent is a power of two and which is based at a power of 2
- */
- public void computeKey(Envelope itemEnv)
- {
- level = computeQuadLevel(itemEnv);
- env = new Envelope();
- computeKey(level, itemEnv);
- // MD - would be nice to have a non-iterative form of this algorithm
- while (! env.contains(itemEnv)) {
- level += 1;
- computeKey(level, itemEnv);
- }
- }
-
- private void computeKey(int level, Envelope itemEnv)
- {
- double quadSize = DoubleBits.powerOf2(level);
- pt.x = Math.floor(itemEnv.getMinX() / quadSize) * quadSize;
- pt.y = Math.floor(itemEnv.getMinY() / quadSize) * quadSize;
- env.init(pt.x, pt.x + quadSize, pt.y, pt.y + quadSize);
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/quadtree/Node.java b/core/src/main/java/org/apache/sedona/jts/index/quadtree/Node.java
deleted file mode 100644
index b891e7a..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/quadtree/Node.java
+++ /dev/null
@@ -1,183 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.quadtree;
-
-import org.locationtech.jts.geom.Envelope;
-import org.locationtech.jts.util.Assert;
-
-/**
- * Represents a node of a {@link Quadtree}. Nodes contain
- * items which have a spatial extent corresponding to the node's position
- * in the quadtree.
- *
- * @version 1.7
- */
-public class Node
- extends NodeBase
-{
- public static Node createNode(Envelope env)
- {
- Key key = new Key(env);
- Node node = new Node(key.getEnvelope(), key.getLevel());
- return node;
- }
-
- public static Node createExpanded(Node node, Envelope addEnv)
- {
- Envelope expandEnv = new Envelope(addEnv);
- if (node != null) expandEnv.expandToInclude(node.env);
-
- Node largerNode = createNode(expandEnv);
- if (node != null) largerNode.insertNode(node);
- return largerNode;
- }
-
- private Envelope env;
- private double centrex;
- private double centrey;
- private int level;
-
- public Node(Envelope env, int level)
- {
- //this.parent = parent;
- this.env = env;
- this.level = level;
- centrex = (env.getMinX() + env.getMaxX()) / 2;
- centrey = (env.getMinY() + env.getMaxY()) / 2;
- }
-
- public Envelope getEnvelope() { return env; }
-
- protected boolean isSearchMatch(Envelope searchEnv)
- {
- if (searchEnv == null) return false;
- return env.intersects(searchEnv);
- }
-
- /**
- * Returns the subquad containing the envelope <tt>searchEnv</tt>.
- * Creates the subquad if
- * it does not already exist.
- *
- * @return the subquad containing the search envelope
- */
- public Node getNode(Envelope searchEnv)
- {
- int subnodeIndex = getSubnodeIndex(searchEnv, centrex, centrey);
- // if subquadIndex is -1 searchEnv is not contained in a subquad
- if (subnodeIndex != -1) {
- // create the quad if it does not exist
- Node node = getSubnode(subnodeIndex);
- // recursively search the found/created quad
- return node.getNode(searchEnv);
- }
- else {
- return this;
- }
- }
-
- /**
- * Returns the smallest <i>existing</i>
- * node containing the envelope.
- */
- public NodeBase find(Envelope searchEnv)
- {
- int subnodeIndex = getSubnodeIndex(searchEnv, centrex, centrey);
- if (subnodeIndex == -1)
- return this;
- if (subnode[subnodeIndex] != null) {
- // query lies in subquad, so search it
- Node node = subnode[subnodeIndex];
- return node.find(searchEnv);
- }
- // no existing subquad, so return this one anyway
- return this;
- }
-
- void insertNode(Node node)
- {
- Assert.isTrue(env == null || env.contains(node.env));
-//System.out.println(env);
-//System.out.println(quad.env);
- int index = getSubnodeIndex(node.env, centrex, centrey);
-//System.out.println(index);
- if (node.level == level - 1) {
- subnode[index] = node;
-//System.out.println("inserted");
- }
- else {
- // the quad is not a direct child, so make a new child quad to contain it
- // and recursively insert the quad
- Node childNode = createSubnode(index);
- childNode.insertNode(node);
- subnode[index] = childNode;
- }
- }
-
- /**
- * get the subquad for the index.
- * If it doesn't exist, create it
- */
- private Node getSubnode(int index)
- {
- if (subnode[index] == null) {
- subnode[index] = createSubnode(index);
- }
- return subnode[index];
- }
-
- private Node createSubnode(int index)
- {
- // create a new subquad in the appropriate quadrant
-
- double minx = 0.0;
- double maxx = 0.0;
- double miny = 0.0;
- double maxy = 0.0;
-
- switch (index) {
- case 0:
- minx = env.getMinX();
- maxx = centrex;
- miny = env.getMinY();
- maxy = centrey;
- break;
- case 1:
- minx = centrex;
- maxx = env.getMaxX();
- miny = env.getMinY();
- maxy = centrey;
- break;
- case 2:
- minx = env.getMinX();
- maxx = centrex;
- miny = centrey;
- maxy = env.getMaxY();
- break;
- case 3:
- minx = centrex;
- maxx = env.getMaxX();
- miny = centrey;
- maxy = env.getMaxY();
- break;
- }
- Envelope sqEnv = new Envelope(minx, maxx, miny, maxy);
- Node node = new Node(sqEnv, level - 1);
- return node;
- }
-
- int getLevel()
- {
- return level;
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/quadtree/NodeBase.java b/core/src/main/java/org/apache/sedona/jts/index/quadtree/NodeBase.java
deleted file mode 100644
index 5b9d6fc..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/quadtree/NodeBase.java
+++ /dev/null
@@ -1,236 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.quadtree;
-
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.Iterator;
-import java.util.List;
-
-import org.locationtech.jts.geom.Envelope;
-import org.locationtech.jts.index.ItemVisitor;
-
-
-/**
- * The base class for nodes in a {@link Quadtree}.
- *
- * @version 1.7
- */
-public abstract class NodeBase implements Serializable {
-
-//DEBUG private static int itemCount = 0; // debugging
-
- /**
- * Gets the index of the subquad that wholly contains the given envelope.
- * If none does, returns -1.
- *
- * @return the index of the subquad that wholly contains the given envelope
- * or -1 if no subquad wholly contains the envelope
- */
- public static int getSubnodeIndex(Envelope env, double centrex, double centrey)
- {
- int subnodeIndex = -1;
- if (env.getMinX() >= centrex) {
- if (env.getMinY() >= centrey) subnodeIndex = 3;
- if (env.getMaxY() <= centrey) subnodeIndex = 1;
- }
- if (env.getMaxX() <= centrex) {
- if (env.getMinY() >= centrey) subnodeIndex = 2;
- if (env.getMaxY() <= centrey) subnodeIndex = 0;
- }
- return subnodeIndex;
- }
-
- protected List items = new ArrayList();
-
- /**
- * subquads are numbered as follows:
- * <pre>
- * 2 | 3
- * --+--
- * 0 | 1
- * </pre>
- */
- protected Node[] subnode = new Node[4];
-
- public NodeBase() {
- }
-
- public List getItems() { return items; }
-
- public boolean hasItems() { return ! items.isEmpty(); }
-
- public void add(Object item)
- {
- items.add(item);
-//DEBUG itemCount++;
-//DEBUG System.out.print(itemCount);
- }
-
- /**
- * Removes a single item from this subtree.
- *
- * @param itemEnv the envelope containing the item
- * @param item the item to remove
- * @return <code>true</code> if the item was found and removed
- */
- public boolean remove(Envelope itemEnv, Object item)
- {
- // use envelope to restrict nodes scanned
- if (! isSearchMatch(itemEnv))
- return false;
-
- boolean found = false;
- for (int i = 0; i < 4; i++) {
- if (subnode[i] != null) {
- found = subnode[i].remove(itemEnv, item);
- if (found) {
- // trim subtree if empty
- if (subnode[i].isPrunable())
- subnode[i] = null;
- break;
- }
- }
- }
- // if item was found lower down, don't need to search for it here
- if (found) return found;
- // otherwise, try and remove the item from the list of items in this node
- found = items.remove(item);
- return found;
- }
-
- public boolean isPrunable()
- {
- return ! (hasChildren() || hasItems());
- }
-
- public boolean hasChildren()
- {
- for (int i = 0; i < 4; i++) {
- if (subnode[i] != null)
- return true;
- }
- return false;
- }
-
- public boolean isEmpty()
- {
- boolean isEmpty = true;
- if (! items.isEmpty()) isEmpty = false;
- else {
- for (int i = 0; i < 4; i++) {
- if (subnode[i] != null) {
- if (!subnode[i].isEmpty()) {
- isEmpty = false;
- break;
- }
- }
- }
- }
- return isEmpty;
- }
-
- //<<TODO:RENAME?>> Sounds like this method adds resultItems to items
- //(like List#addAll). Perhaps it should be renamed to "addAllItemsTo" [Jon Aquino]
- public List addAllItems(List resultItems)
- {
- // this node may have items as well as subnodes (since items may not
- // be wholely contained in any single subnode
- resultItems.addAll(this.items);
- for (int i = 0; i < 4; i++) {
- if (subnode[i] != null) {
- subnode[i].addAllItems(resultItems);
- }
- }
- return resultItems;
- }
- protected abstract boolean isSearchMatch(Envelope searchEnv);
-
- public void addAllItemsFromOverlapping(Envelope searchEnv, List resultItems)
- {
- if (! isSearchMatch(searchEnv))
- return;
-
- // this node may have items as well as subnodes (since items may not
- // be wholely contained in any single subnode
- resultItems.addAll(items);
-
- for (int i = 0; i < 4; i++) {
- if (subnode[i] != null) {
- subnode[i].addAllItemsFromOverlapping(searchEnv, resultItems);
- }
- }
- }
-
- public void visit(Envelope searchEnv, ItemVisitor visitor)
- {
- if (! isSearchMatch(searchEnv))
- return;
-
- // this node may have items as well as subnodes (since items may not
- // be wholely contained in any single subnode
- visitItems(searchEnv, visitor);
-
- for (int i = 0; i < 4; i++) {
- if (subnode[i] != null) {
- subnode[i].visit(searchEnv, visitor);
- }
- }
- }
-
- private void visitItems(Envelope searchEnv, ItemVisitor visitor)
- {
- // would be nice to filter items based on search envelope, but can't until they contain an envelope
- for (Iterator i = items.iterator(); i.hasNext(); ) {
- visitor.visitItem(i.next());
- }
- }
-
-//<<TODO:RENAME?>> In Samet's terminology, I think what we're returning here is
-//actually level+1 rather than depth. (See p. 4 of his book) [Jon Aquino]
- int depth()
- {
- int maxSubDepth = 0;
- for (int i = 0; i < 4; i++) {
- if (subnode[i] != null) {
- int sqd = subnode[i].depth();
- if (sqd > maxSubDepth)
- maxSubDepth = sqd;
- }
- }
- return maxSubDepth + 1;
- }
-
- int size()
- {
- int subSize = 0;
- for (int i = 0; i < 4; i++) {
- if (subnode[i] != null) {
- subSize += subnode[i].size();
- }
- }
- return subSize + items.size();
- }
-
- int getNodeCount()
- {
- int subSize = 0;
- for (int i = 0; i < 4; i++) {
- if (subnode[i] != null) {
- subSize += subnode[i].size();
- }
- }
- return subSize + 1;
- }
-
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/quadtree/Quadtree.java b/core/src/main/java/org/apache/sedona/jts/index/quadtree/Quadtree.java
deleted file mode 100644
index 87d0db2..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/quadtree/Quadtree.java
+++ /dev/null
@@ -1,246 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.quadtree;
-
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.List;
-
-import org.locationtech.jts.geom.Envelope;
-import org.locationtech.jts.geom.Geometry;
-import org.locationtech.jts.index.ArrayListVisitor;
-import org.locationtech.jts.index.ItemVisitor;
-import org.locationtech.jts.index.SpatialIndex;
-/**
- * A Quadtree is a spatial index structure for efficient range querying
- * of items bounded by 2D rectangles.
- * {@link Geometry}s can be indexed by using their
- * {@link Envelope}s.
- * Any type of Object can also be indexed as
- * long as it has an extent that can be represented by an {@link Envelope}.
- * <p>
- * This Quadtree index provides a <b>primary filter</b>
- * for range rectangle queries. The various query methods return a list of
- * all items which <i>may</i> intersect the query rectangle. Note that
- * it may thus return items which do <b>not</b> in fact intersect the query rectangle.
- * A secondary filter is required to test for actual intersection
- * between the query rectangle and the envelope of each candidate item.
- * The secondary filter may be performed explicitly,
- * or it may be provided implicitly by subsequent operations executed on the items
- * (for instance, if the index query is followed by computing a spatial predicate
- * between the query geometry and tree items,
- * the envelope intersection check is performed automatically.
- * <p>
- * This implementation does not require specifying the extent of the inserted
- * items beforehand. It will automatically expand to accommodate any extent
- * of dataset.
- * <p>
- * This data structure is also known as an <i>MX-CIF quadtree</i>
- * following the terminology of Samet and others.
- *
- * @version 1.7
- */
-public class Quadtree
- implements SpatialIndex, Serializable
-{
- private static final long serialVersionUID = -7461163625812743604L;
-
- /**
- * Ensure that the envelope for the inserted item has non-zero extents.
- * Use the current minExtent to pad the envelope, if necessary
- */
- public static Envelope ensureExtent(Envelope itemEnv, double minExtent)
- {
- //The names "ensureExtent" and "minExtent" are misleading -- sounds like
- //this method ensures that the extents are greater than minExtent.
- //Perhaps we should rename them to "ensurePositiveExtent" and "defaultExtent".
- //[Jon Aquino]
- double minx = itemEnv.getMinX();
- double maxx = itemEnv.getMaxX();
- double miny = itemEnv.getMinY();
- double maxy = itemEnv.getMaxY();
- // has a non-zero extent
- if (minx != maxx && miny != maxy) return itemEnv;
-
- // pad one or both extents
- if (minx == maxx) {
- minx = minx - minExtent / 2.0;
- maxx = maxx + minExtent / 2.0;
- }
- if (miny == maxy) {
- miny = miny - minExtent / 2.0;
- maxy = maxy + minExtent / 2.0;
- }
- return new Envelope(minx, maxx, miny, maxy);
- }
-
- private Root root;
- /**
-
- * minExtent is the minimum envelope extent of all items
- * inserted into the tree so far. It is used as a heuristic value
- * to construct non-zero envelopes for features with zero X and/or Y extent.
- * Start with a non-zero extent, in case the first feature inserted has
- * a zero extent in both directions. This value may be non-optimal, but
- * only one feature will be inserted with this value.
- **/
- private double minExtent = 1.0;
-
- /**
- * Constructs a Quadtree with zero items.
- */
- public Quadtree()
- {
- root = new Root();
- }
-
- /**
- * Returns the number of levels in the tree.
- */
- public int depth()
- {
- //I don't think it's possible for root to be null. Perhaps we should
- //remove the check. [Jon Aquino]
- //Or make an assertion [Jon Aquino 10/29/2003]
- if (root != null) return root.depth();
- return 0;
- }
-
- /**
- * Tests whether the index contains any items.
- *
- * @return true if the index does not contain any items
- */
- public boolean isEmpty()
- {
- if (root == null) return true;
- return root.isEmpty();
- }
-
- /**
- * Returns the number of items in the tree.
- *
- * @return the number of items in the tree
- */
- public int size()
- {
- if (root != null) return root.size();
- return 0;
- }
-
- public void insert(Envelope itemEnv, Object item)
- {
- collectStats(itemEnv);
- Envelope insertEnv = ensureExtent(itemEnv, minExtent);
- root.insert(insertEnv, item);
- }
-
- /**
- * Removes a single item from the tree.
- *
- * @param itemEnv the Envelope of the item to be removed
- * @param item the item to remove
- * @return <code>true</code> if the item was found (and thus removed)
- */
- public boolean remove(Envelope itemEnv, Object item)
- {
- Envelope posEnv = ensureExtent(itemEnv, minExtent);
- return root.remove(posEnv, item);
- }
-
-/*
- public List OLDquery(Envelope searchEnv)
- {
- /**
- * the items that are matched are the items in quads which
- * overlap the search envelope
- */
- /*
- List foundItems = new ArrayList();
- root.addAllItemsFromOverlapping(searchEnv, foundItems);
- return foundItems;
- }
-*/
-
- /**
- * Queries the tree and returns items which may lie in the given search envelope.
- * Precisely, the items that are returned are all items in the tree
- * whose envelope <b>may</b> intersect the search Envelope.
- * Note that some items with non-intersecting envelopes may be returned as well;
- * the client is responsible for filtering these out.
- * In most situations there will be many items in the tree which do not
- * intersect the search envelope and which are not returned - thus
- * providing improved performance over a simple linear scan.
- *
- * @param searchEnv the envelope of the desired query area.
- * @return a List of items which may intersect the search envelope
- */
- public List query(Envelope searchEnv)
- {
- /**
- * the items that are matched are the items in quads which
- * overlap the search envelope
- */
- ArrayListVisitor visitor = new ArrayListVisitor();
- query(searchEnv, visitor);
- return visitor.getItems();
- }
-
- /**
- * Queries the tree and visits items which may lie in the given search envelope.
- * Precisely, the items that are visited are all items in the tree
- * whose envelope <b>may</b> intersect the search Envelope.
- * Note that some items with non-intersecting envelopes may be visited as well;
- * the client is responsible for filtering these out.
- * In most situations there will be many items in the tree which do not
- * intersect the search envelope and which are not visited - thus
- * providing improved performance over a simple linear scan.
- *
- * @param searchEnv the envelope of the desired query area.
- * @param visitor a visitor object which is passed the visited items
- */
- public void query(Envelope searchEnv, ItemVisitor visitor)
- {
- /**
- * the items that are matched are the items in quads which
- * overlap the search envelope
- */
- root.visit(searchEnv, visitor);
- }
-
- /**
- * Return a list of all items in the Quadtree
- */
- public List queryAll()
- {
- List foundItems = new ArrayList();
- root.addAllItems(foundItems);
- return foundItems;
- }
-
- private void collectStats(Envelope itemEnv)
- {
- double delX = itemEnv.getWidth();
- if (delX < minExtent && delX > 0.0)
- minExtent = delX;
-
- double delY = itemEnv.getHeight();
- if (delY < minExtent && delY > 0.0)
- minExtent = delY;
- }
-
- Root getRoot()
- {
- return root;
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/quadtree/Root.java b/core/src/main/java/org/apache/sedona/jts/index/quadtree/Root.java
deleted file mode 100644
index 2e3d455..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/quadtree/Root.java
+++ /dev/null
@@ -1,99 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.quadtree;
-
-import org.locationtech.jts.geom.Coordinate;
-import org.locationtech.jts.geom.Envelope;
-import org.locationtech.jts.util.Assert;
-
-/**
- * QuadRoot is the root of a single Quadtree. It is centred at the origin,
- * and does not have a defined extent.
- *
- * @version 1.7
- */
-public class Root
- extends NodeBase
-{
-
- // the singleton root quad is centred at the origin.
- private static final Coordinate origin = new Coordinate(0.0, 0.0);
-
- public Root()
- {
- }
-
- /**
- * Insert an item into the quadtree this is the root of.
- */
- public void insert(Envelope itemEnv, Object item)
- {
- int index = getSubnodeIndex(itemEnv, origin.x, origin.y);
- // if index is -1, itemEnv must cross the X or Y axis.
- if (index == -1) {
- add(item);
- return;
- }
- /**
- * the item must be contained in one quadrant, so insert it into the
- * tree for that quadrant (which may not yet exist)
- */
- Node node = subnode[index];
- /**
- * If the subquad doesn't exist or this item is not contained in it,
- * have to expand the tree upward to contain the item.
- */
-
- if (node == null || ! node.getEnvelope().contains(itemEnv)) {
- Node largerNode = Node.createExpanded(node, itemEnv);
- subnode[index] = largerNode;
- }
- /**
- * At this point we have a subquad which exists and must contain
- * contains the env for the item. Insert the item into the tree.
- */
- insertContained(subnode[index], itemEnv, item);
- //System.out.println("depth = " + root.depth() + " size = " + root.size());
- //System.out.println(" size = " + size());
- }
-
- /**
- * insert an item which is known to be contained in the tree rooted at
- * the given QuadNode root. Lower levels of the tree will be created
- * if necessary to hold the item.
- */
- private void insertContained(Node tree, Envelope itemEnv, Object item)
- {
- Assert.isTrue(tree.getEnvelope().contains(itemEnv));
- /**
- * Do NOT create a new quad for zero-area envelopes - this would lead
- * to infinite recursion. Instead, use a heuristic of simply returning
- * the smallest existing quad containing the query
- */
- boolean isZeroX = IntervalSize.isZeroWidth(itemEnv.getMinX(), itemEnv.getMaxX());
- boolean isZeroY = IntervalSize.isZeroWidth(itemEnv.getMinY(), itemEnv.getMaxY());
- NodeBase node;
- if (isZeroX || isZeroY)
- node = tree.find(itemEnv);
- else
- node = tree.getNode(itemEnv);
- node.add(item);
- }
-
- protected boolean isSearchMatch(Envelope searchEnv)
- {
- return true;
- }
-
-
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/AbstractNode.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/AbstractNode.java
deleted file mode 100644
index 51bfed4..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/AbstractNode.java
+++ /dev/null
@@ -1,136 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.List;
-
-import org.locationtech.jts.util.Assert;
-
-/**
- * A node of an {@link AbstractSTRtree}. A node is one of:
- * <ul>
- * <li>empty
- * <li>an <i>interior node</i> containing child {@link AbstractNode}s
- * <li>a <i>leaf node</i> containing data items ({@link ItemBoundable}s).
- * </ul>
- * A node stores the bounds of its children, and its level within the index tree.
- *
- * @version 1.7
- */
-public abstract class AbstractNode implements Boundable, Serializable {
- /**
- *
- */
- private static final long serialVersionUID = 6493722185909573708L;
-
- private ArrayList childBoundables = new ArrayList();
- private Object bounds = null;
- private int level;
-
- /**
- * Default constructor required for serialization.
- */
- public AbstractNode() {
- }
-
- /**
- * Constructs an AbstractNode at the given level in the tree
- * @param level 0 if this node is a leaf, 1 if a parent of a leaf, and so on; the
- * root node will have the highest level
- */
- public AbstractNode(int level) {
- this.level = level;
- }
-
- /**
- * Returns either child {@link AbstractNode}s, or if this is a leaf node, real data (wrapped
- * in {@link ItemBoundable}s).
- *
- * @return a list of the children
- */
- public List getChildBoundables() {
- return childBoundables;
- }
-
- /**
- * Returns a representation of space that encloses this Boundable,
- * preferably not much bigger than this Boundable's boundary yet fast to
- * test for intersection with the bounds of other Boundables. The class of
- * object returned depends on the subclass of AbstractSTRtree.
- *
- * @return an Envelope (for STRtrees), an Interval (for SIRtrees), or other
- * object (for other subclasses of AbstractSTRtree)
- * @see AbstractSTRtree.IntersectsOp
- */
- protected abstract Object computeBounds();
-
- /**
- * Gets the bounds of this node
- *
- * @return the object representing bounds in this index
- */
- public Object getBounds() {
- if (bounds == null) {
- bounds = computeBounds();
- }
- return bounds;
- }
-
- /**
- * Returns 0 if this node is a leaf, 1 if a parent of a leaf, and so on; the
- * root node will have the highest level
- *
- * @return the node level
- */
- public int getLevel() {
- return level;
- }
-
- /**
- * Gets the count of the {@link Boundable}s at this node.
- *
- * @return the count of boundables at this node
- */
- public int size()
- {
- return childBoundables.size();
- }
-
- /**
- * Tests whether there are any {@link Boundable}s at this node.
- *
- * @return true if there are boundables at this node
- */
- public boolean isEmpty()
- {
- return childBoundables.isEmpty();
- }
-
- /**
- * Adds either an AbstractNode, or if this is a leaf node, a data object
- * (wrapped in an ItemBoundable)
- *
- * @param childBoundable the child to add
- */
- public void addChildBoundable(Boundable childBoundable) {
- Assert.isTrue(bounds == null);
- childBoundables.add(childBoundable);
- }
-
- void setChildBoundables(ArrayList childBoundables)
- {
- this.childBoundables = childBoundables;
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/AbstractSTRtree.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/AbstractSTRtree.java
deleted file mode 100644
index ae17bb7..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/AbstractSTRtree.java
+++ /dev/null
@@ -1,484 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Iterator;
-import java.util.List;
-
-import org.locationtech.jts.index.ItemVisitor;
-import org.locationtech.jts.util.Assert;
-
-/**
- * Base class for STRtree and SIRtree. STR-packed R-trees are described in:
- * P. Rigaux, Michel Scholl and Agnes Voisard. <i>Spatial Databases With
- * Application To GIS.</i> Morgan Kaufmann, San Francisco, 2002.
- * <p>
- * This implementation is based on {@link Boundable}s rather than {@link AbstractNode}s,
- * because the STR algorithm operates on both nodes and
- * data, both of which are treated as Boundables.
- * <p>
- * This class is thread-safe. Building the tree is synchronized,
- * and querying is stateless.
- *
- * @see STRtree
- * @see SIRtree
- *
- * @version 1.7
- */
-public abstract class AbstractSTRtree implements Serializable {
-
- /**
- *
- */
- private static final long serialVersionUID = -3886435814360241337L;
-
- /**
- * A test for intersection between two bounds, necessary because subclasses
- * of AbstractSTRtree have different implementations of bounds.
- */
- protected static interface IntersectsOp {
- /**
- * For STRtrees, the bounds will be Envelopes; for SIRtrees, Intervals;
- * for other subclasses of AbstractSTRtree, some other class.
- * @param aBounds the bounds of one spatial object
- * @param bBounds the bounds of another spatial object
- * @return whether the two bounds intersect
- */
- boolean intersects(Object aBounds, Object bBounds);
- }
-
- protected AbstractNode root;
-
- private boolean built = false;
- /**
- * Set to <tt>null</tt> when index is built, to avoid retaining memory.
- */
- private ArrayList itemBoundables = new ArrayList();
-
- private int nodeCapacity;
-
- private static final int DEFAULT_NODE_CAPACITY = 10;
-
- /**
- * Constructs an AbstractSTRtree with the
- * default node capacity.
- */
- public AbstractSTRtree() {
- this(DEFAULT_NODE_CAPACITY);
- }
-
- /**
- * Constructs an AbstractSTRtree with the specified maximum number of child
- * nodes that a node may have
- *
- * @param nodeCapacity the maximum number of child nodes in a node
- */
- public AbstractSTRtree(int nodeCapacity) {
- Assert.isTrue(nodeCapacity > 1, "Node capacity must be greater than 1");
- this.nodeCapacity = nodeCapacity;
- }
-
- /**
- * Constructs an AbstractSTRtree with the specified maximum number of child
- * nodes that a node may have, and the root node
- * @param nodeCapacity the maximum number of child nodes in a node
- * @param root the root node that links to all other nodes in the tree
- */
- public AbstractSTRtree(int nodeCapacity, AbstractNode root) {
- this(nodeCapacity);
- built = true;
- this.root = root;
- this.itemBoundables = null;
- }
-
- /**
- * Constructs an AbstractSTRtree with the specified maximum number of child
- * nodes that a node may have, and all leaf nodes in the tree
- * @param nodeCapacity the maximum number of child nodes in a node
- * @param itemBoundables the list of leaf nodes in the tree
- */
- public AbstractSTRtree(int nodeCapacity, ArrayList itemBoundables) {
- this(nodeCapacity);
- this.itemBoundables = itemBoundables;
- }
- /**
- * Creates parent nodes, grandparent nodes, and so forth up to the root
- * node, for the data that has been inserted into the tree. Can only be
- * called once, and thus can be called only after all of the data has been
- * inserted into the tree.
- */
- public synchronized void build() {
- if (built) return;
- root = itemBoundables.isEmpty()
- ? createNode(0)
- : createHigherLevels(itemBoundables, -1);
- // the item list is no longer needed
- itemBoundables = null;
- built = true;
- }
-
- protected abstract AbstractNode createNode(int level);
-
- /**
- * Sorts the childBoundables then divides them into groups of size M, where
- * M is the node capacity.
- */
- protected List createParentBoundables(List childBoundables, int newLevel) {
- Assert.isTrue(!childBoundables.isEmpty());
- ArrayList parentBoundables = new ArrayList();
- parentBoundables.add(createNode(newLevel));
- ArrayList sortedChildBoundables = new ArrayList(childBoundables);
- Collections.sort(sortedChildBoundables, getComparator());
- for (Iterator i = sortedChildBoundables.iterator(); i.hasNext(); ) {
- Boundable childBoundable = (Boundable) i.next();
- if (lastNode(parentBoundables).getChildBoundables().size() == getNodeCapacity()) {
- parentBoundables.add(createNode(newLevel));
- }
- lastNode(parentBoundables).addChildBoundable(childBoundable);
- }
- return parentBoundables;
- }
-
- protected AbstractNode lastNode(List nodes) {
- return (AbstractNode) nodes.get(nodes.size() - 1);
- }
-
- protected static int compareDoubles(double a, double b) {
- return a > b ? 1
- : a < b ? -1
- : 0;
- }
-
- /**
- * Creates the levels higher than the given level
- *
- * @param boundablesOfALevel
- * the level to build on
- * @param level
- * the level of the Boundables, or -1 if the boundables are item
- * boundables (that is, below level 0)
- * @return the root, which may be a ParentNode or a LeafNode
- */
- private AbstractNode createHigherLevels(List boundablesOfALevel, int level) {
- Assert.isTrue(!boundablesOfALevel.isEmpty());
- List parentBoundables = createParentBoundables(boundablesOfALevel, level + 1);
- if (parentBoundables.size() == 1) {
- return (AbstractNode) parentBoundables.get(0);
- }
- return createHigherLevels(parentBoundables, level + 1);
- }
-
- /**
- * Gets the root node of the tree.
- *
- * @return the root node
- */
- public AbstractNode getRoot()
- {
- build();
- return root;
- }
-
- /**
- * Returns the maximum number of child nodes that a node may have.
- *
- * @return the node capacity
- */
- public int getNodeCapacity() { return nodeCapacity; }
-
- /**
- * Tests whether the index contains any items.
- * This method does not build the index,
- * so items can still be inserted after it has been called.
- *
- * @return true if the index does not contain any items
- */
- public boolean isEmpty()
- {
- if (! built) return itemBoundables.isEmpty();
- return root.isEmpty();
- }
-
- protected int size() {
- if (isEmpty()) {
- return 0;
- }
- build();
- return size(root);
- }
-
- protected int size(AbstractNode node)
- {
- int size = 0;
- for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
- Boundable childBoundable = (Boundable) i.next();
- if (childBoundable instanceof AbstractNode) {
- size += size((AbstractNode) childBoundable);
- }
- else if (childBoundable instanceof ItemBoundable) {
- size += 1;
- }
- }
- return size;
- }
-
- protected int depth() {
- if (isEmpty()) {
- return 0;
- }
- build();
- return depth(root);
- }
-
- protected int depth(AbstractNode node)
- {
- int maxChildDepth = 0;
- for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
- Boundable childBoundable = (Boundable) i.next();
- if (childBoundable instanceof AbstractNode) {
- int childDepth = depth((AbstractNode) childBoundable);
- if (childDepth > maxChildDepth)
- maxChildDepth = childDepth;
- }
- }
- return maxChildDepth + 1;
- }
-
-
- protected void insert(Object bounds, Object item) {
- Assert.isTrue(!built, "Cannot insert items into an STR packed R-tree after it has been built.");
- itemBoundables.add(new ItemBoundable(bounds, item));
- }
-
- /**
- * Also builds the tree, if necessary.
- */
- protected List query(Object searchBounds) {
- build();
- ArrayList matches = new ArrayList();
- if (isEmpty()) {
- //Assert.isTrue(root.getBounds() == null);
- return matches;
- }
- if (getIntersectsOp().intersects(root.getBounds(), searchBounds)) {
- queryInternal(searchBounds, root, matches);
- }
- return matches;
- }
-
- /**
- * Also builds the tree, if necessary.
- */
- protected void query(Object searchBounds, ItemVisitor visitor) {
- build();
- if (isEmpty()) {
- // nothing in tree, so return
- //Assert.isTrue(root.getBounds() == null);
- return;
- }
- if (getIntersectsOp().intersects(root.getBounds(), searchBounds)) {
- queryInternal(searchBounds, root, visitor);
- }
- }
-
- /**
- * @return a test for intersection between two bounds, necessary because subclasses
- * of AbstractSTRtree have different implementations of bounds.
- * @see IntersectsOp
- */
- protected abstract IntersectsOp getIntersectsOp();
-
- private void queryInternal(Object searchBounds, AbstractNode node, List matches) {
- List childBoundables = node.getChildBoundables();
- for (int i = 0; i < childBoundables.size(); i++) {
- Boundable childBoundable = (Boundable) childBoundables.get(i);
- if (! getIntersectsOp().intersects(childBoundable.getBounds(), searchBounds)) {
- continue;
- }
- if (childBoundable instanceof AbstractNode) {
- queryInternal(searchBounds, (AbstractNode) childBoundable, matches);
- }
- else if (childBoundable instanceof ItemBoundable) {
- matches.add(((ItemBoundable)childBoundable).getItem());
- }
- else {
- Assert.shouldNeverReachHere();
- }
- }
- }
-
- private void queryInternal(Object searchBounds, AbstractNode node, ItemVisitor visitor) {
- List childBoundables = node.getChildBoundables();
- for (int i = 0; i < childBoundables.size(); i++) {
- Boundable childBoundable = (Boundable) childBoundables.get(i);
- if (! getIntersectsOp().intersects(childBoundable.getBounds(), searchBounds)) {
- continue;
- }
- if (childBoundable instanceof AbstractNode) {
- queryInternal(searchBounds, (AbstractNode) childBoundable, visitor);
- }
- else if (childBoundable instanceof ItemBoundable) {
- visitor.visitItem(((ItemBoundable)childBoundable).getItem());
- }
- else {
- Assert.shouldNeverReachHere();
- }
- }
- }
-
- /**
- * Gets a tree structure (as a nested list)
- * corresponding to the structure of the items and nodes in this tree.
- * <p>
- * The returned {@link List}s contain either {@link Object} items,
- * or Lists which correspond to subtrees of the tree
- * Subtrees which do not contain any items are not included.
- * <p>
- * Builds the tree if necessary.
- *
- * @return a List of items and/or Lists
- */
- public List itemsTree()
- {
- build();
-
- List valuesTree = itemsTree(root);
- if (valuesTree == null)
- return new ArrayList();
- return valuesTree;
- }
-
- private List itemsTree(AbstractNode node)
- {
- List valuesTreeForNode = new ArrayList();
- for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
- Boundable childBoundable = (Boundable) i.next();
- if (childBoundable instanceof AbstractNode) {
- List valuesTreeForChild = itemsTree((AbstractNode) childBoundable);
- // only add if not null (which indicates an item somewhere in this tree
- if (valuesTreeForChild != null)
- valuesTreeForNode.add(valuesTreeForChild);
- }
- else if (childBoundable instanceof ItemBoundable) {
- valuesTreeForNode.add(((ItemBoundable)childBoundable).getItem());
- }
- else {
- Assert.shouldNeverReachHere();
- }
- }
- if (valuesTreeForNode.size() <= 0)
- return null;
- return valuesTreeForNode;
- }
-
- /**
- * Removes an item from the tree.
- * (Builds the tree, if necessary.)
- */
- protected boolean remove(Object searchBounds, Object item) {
- build();
- if (getIntersectsOp().intersects(root.getBounds(), searchBounds)) {
- return remove(searchBounds, root, item);
- }
- return false;
- }
-
- private boolean removeItem(AbstractNode node, Object item)
- {
- Boundable childToRemove = null;
- for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
- Boundable childBoundable = (Boundable) i.next();
- if (childBoundable instanceof ItemBoundable) {
- if ( ((ItemBoundable) childBoundable).getItem() == item)
- childToRemove = childBoundable;
- }
- }
- if (childToRemove != null) {
- node.getChildBoundables().remove(childToRemove);
- return true;
- }
- return false;
- }
-
- private boolean remove(Object searchBounds, AbstractNode node, Object item) {
- // first try removing item from this node
- boolean found = removeItem(node, item);
- if (found)
- return true;
-
- AbstractNode childToPrune = null;
- // next try removing item from lower nodes
- for (Iterator i = node.getChildBoundables().iterator(); i.hasNext(); ) {
- Boundable childBoundable = (Boundable) i.next();
- if (!getIntersectsOp().intersects(childBoundable.getBounds(), searchBounds)) {
- continue;
- }
- if (childBoundable instanceof AbstractNode) {
- found = remove(searchBounds, (AbstractNode) childBoundable, item);
- // if found, record child for pruning and exit
- if (found) {
- childToPrune = (AbstractNode) childBoundable;
- break;
- }
- }
- }
- // prune child if possible
- if (childToPrune != null) {
- if (childToPrune.getChildBoundables().isEmpty()) {
- node.getChildBoundables().remove(childToPrune);
- }
- }
- return found;
- }
-
- protected List boundablesAtLevel(int level) {
- ArrayList boundables = new ArrayList();
- boundablesAtLevel(level, root, boundables);
- return boundables;
- }
-
- /**
- * @param level -1 to get items
- */
- private void boundablesAtLevel(int level, AbstractNode top, Collection boundables) {
- Assert.isTrue(level > -2);
- if (top.getLevel() == level) {
- boundables.add(top);
- return;
- }
- for (Iterator i = top.getChildBoundables().iterator(); i.hasNext(); ) {
- Boundable boundable = (Boundable) i.next();
- if (boundable instanceof AbstractNode) {
- boundablesAtLevel(level, (AbstractNode)boundable, boundables);
- }
- else {
- Assert.isTrue(boundable instanceof ItemBoundable);
- if (level == -1) { boundables.add(boundable); }
- }
- }
- return;
- }
-
- protected abstract Comparator getComparator();
-
- ArrayList getItemBoundables()
- {
- return itemBoundables;
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/Boundable.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/Boundable.java
deleted file mode 100644
index 64a6f07..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/Boundable.java
+++ /dev/null
@@ -1,30 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-/**
- * A spatial object in an AbstractSTRtree.
- *
- * @version 1.7
- */
-public interface Boundable {
- /**
- * Returns a representation of space that encloses this Boundable, preferably
- * not much bigger than this Boundable's boundary yet fast to test for intersection
- * with the bounds of other Boundables. The class of object returned depends
- * on the subclass of AbstractSTRtree.
- * @return an Envelope (for STRtrees), an Interval (for SIRtrees), or other object
- * (for other subclasses of AbstractSTRtree)
- */
- Object getBounds();
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/BoundablePair.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/BoundablePair.java
deleted file mode 100644
index bf1b25c..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/BoundablePair.java
+++ /dev/null
@@ -1,211 +0,0 @@
-/*
- * Copyright (c) 2016 Martin Davis.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-import java.util.Iterator;
-import java.util.List;
-import java.util.PriorityQueue;
-
-import org.locationtech.jts.geom.Envelope;
-
-
-/**
- * A pair of {@link Boundable}s, whose leaf items
- * support a distance metric between them.
- * Used to compute the distance between the members,
- * and to expand a member relative to the other
- * in order to produce new branches of the
- * Branch-and-Bound evaluation tree.
- * Provides an ordering based on the distance between the members,
- * which allows building a priority queue by minimum distance.
- *
- * @author Martin Davis
- *
- */
-class BoundablePair
- implements Comparable
-{
- private Boundable boundable1;
- private Boundable boundable2;
- private double distance;
- private ItemDistance itemDistance;
- //private double maxDistance = -1.0;
-
- public BoundablePair(Boundable boundable1, Boundable boundable2, ItemDistance itemDistance)
- {
- this.boundable1 = boundable1;
- this.boundable2 = boundable2;
- this.itemDistance = itemDistance;
- distance = distance();
- }
-
- /**
- * Gets one of the member {@link Boundable}s in the pair
- * (indexed by [0, 1]).
- *
- * @param i the index of the member to return (0 or 1)
- * @return the chosen member
- */
- public Boundable getBoundable(int i)
- {
- if (i == 0) return boundable1;
- return boundable2;
- }
-
- /**
- * Computes the maximum distance between any
- * two items in the pair of nodes.
- *
- * @return the maximum distance between items in the pair
- */
- public double maximumDistance()
- {
- return EnvelopeDistance.maximumDistance(
- (Envelope) boundable1.getBounds(),
- (Envelope) boundable2.getBounds());
- }
-
- /**
- * Computes the distance between the {@link Boundable}s in this pair.
- * The boundables are either composites or leaves.
- * If either is composite, the distance is computed as the minimum distance
- * between the bounds.
- * If both are leaves, the distance is computed by {@link #itemDistance(ItemBoundable, ItemBoundable)}.
- *
- * @return
- */
- private double distance()
- {
- // if items, compute exact distance
- if (isLeaves()) {
- return itemDistance.distance((ItemBoundable) boundable1,
- (ItemBoundable) boundable2);
- }
- // otherwise compute distance between bounds of boundables
- return ((Envelope) boundable1.getBounds()).distance(
- ((Envelope) boundable2.getBounds()));
- }
-
- /**
- * Gets the minimum possible distance between the Boundables in
- * this pair.
- * If the members are both items, this will be the
- * exact distance between them.
- * Otherwise, this distance will be a lower bound on
- * the distances between the items in the members.
- *
- * @return the exact or lower bound distance for this pair
- */
- public double getDistance() { return distance; }
-
- /**
- * Compares two pairs based on their minimum distances
- */
- public int compareTo(Object o)
- {
- BoundablePair nd = (BoundablePair) o;
- if (distance < nd.distance) return -1;
- if (distance > nd.distance) return 1;
- return 0;
- }
-
- /**
- * Tests if both elements of the pair are leaf nodes
- *
- * @return true if both pair elements are leaf nodes
- */
- public boolean isLeaves()
- {
- return ! (isComposite(boundable1) || isComposite(boundable2));
- }
-
- public static boolean isComposite(Object item)
- {
- return (item instanceof AbstractNode);
- }
-
- private static double area(Boundable b)
- {
- return ((Envelope) b.getBounds()).getArea();
- }
-
- /**
- * For a pair which is not a leaf
- * (i.e. has at least one composite boundable)
- * computes a list of new pairs
- * from the expansion of the larger boundable
- * with distance less than minDistance
- * and adds them to a priority queue.
- * <p>
- * Note that expanded pairs may contain
- * the same item/node on both sides.
- * This must be allowed to support distance
- * functions which have non-zero distances
- * between the item and itself (non-zero reflexive distance).
- *
- * @param priQ the priority queue to add the new pairs to
- * @param minDistance the limit on the distance between added pairs
- *
- */
- public void expandToQueue(PriorityQueue priQ, double minDistance)
- {
- boolean isComp1 = isComposite(boundable1);
- boolean isComp2 = isComposite(boundable2);
-
- /**
- * HEURISTIC: If both boundable are composite,
- * choose the one with largest area to expand.
- * Otherwise, simply expand whichever is composite.
- */
- if (isComp1 && isComp2) {
- if (area(boundable1) > area(boundable2)) {
- expand(boundable1, boundable2, false, priQ, minDistance);
- return;
- }
- else {
- expand(boundable2, boundable1, true, priQ, minDistance);
- return;
- }
- }
- else if (isComp1) {
- expand(boundable1, boundable2, false, priQ, minDistance);
- return;
- }
- else if (isComp2) {
- expand(boundable2, boundable1, true, priQ, minDistance);
- return;
- }
-
- throw new IllegalArgumentException("neither boundable is composite");
- }
-
- private void expand(Boundable bndComposite, Boundable bndOther, boolean isFlipped,
- PriorityQueue priQ, double minDistance)
- {
- List children = ((AbstractNode) bndComposite).getChildBoundables();
- for (Iterator i = children.iterator(); i.hasNext(); ) {
- Boundable child = (Boundable) i.next();
- BoundablePair bp;
- if (isFlipped) {
- bp = new BoundablePair(bndOther, child, itemDistance);
- }
- else {
- bp = new BoundablePair(child, bndOther, itemDistance);
- }
- // only add to queue if this pair might contain the closest points
- // MD - it's actually faster to construct the object rather than called distance(child, bndOther)!
- if (bp.getDistance() < minDistance) {
- priQ.add(bp);
- }
- }
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/BoundablePairDistanceComparator.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/BoundablePairDistanceComparator.java
deleted file mode 100644
index 0634fce..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/BoundablePairDistanceComparator.java
+++ /dev/null
@@ -1,65 +0,0 @@
-
-/*
- * Copyright (c) 2017 Jia Yu.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-import java.io.Serializable;
-import java.util.Comparator;
-
-
-/**
- * The Class BoundablePairDistanceComparator. It implements Java comparator and is used
- * as a parameter to sort the BoundablePair list.
- */
-public class BoundablePairDistanceComparator implements Comparator<BoundablePair>, Serializable{
-
- /** The normal order. */
- boolean normalOrder;
-
- /**
- * Instantiates a new boundable pair distance comparator.
- *
- * @param normalOrder true puts the lowest record at the head of this queue.
- * This is the natural order. PriorityQueue peek() will get the least element.
- */
- public BoundablePairDistanceComparator(boolean normalOrder)
- {
- this.normalOrder = normalOrder;
- }
-
- /* (non-Javadoc)
- * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
- */
- public int compare(BoundablePair p1, BoundablePair p2) {
- double distance1 = p1.getDistance();
- double distance2 = p2.getDistance();
- if(this.normalOrder)
- {
- if (distance1 > distance2) {
- return 1;
- } else if (distance1 == distance2) {
- return 0;
- }
- return -1;
- }
- else
- {
- if (distance1 > distance2) {
- return -1;
- } else if (distance1 == distance2) {
- return 0;
- }
- return 1;
- }
-
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/EnvelopeDistance.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/EnvelopeDistance.java
deleted file mode 100644
index 55d99ac..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/EnvelopeDistance.java
+++ /dev/null
@@ -1,120 +0,0 @@
-/*
- * Copyright (c) 2019 Martin Davis.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-import org.locationtech.jts.geom.Envelope;
-
-/**
- * Functions for computing distances between {@link Envelope}s.
- *
- * @author mdavis
- *
- */
-public class EnvelopeDistance
-{
- /**
- * Computes the maximum distance between the points defining two envelopes.
- * It is equal to the length of the diagonal of
- * the envelope containing both input envelopes.
- * This is a coarse upper bound on the distance between
- * geometries bounded by the envelopes.
- *
- * @param env1 an envelope
- * @param env2 an envelope
- * @return the maximum distance between the points defining the envelopes
- */
- public static double maximumDistance(Envelope env1, Envelope env2)
- {
- double minx = Math.min(env1.getMinX(), env2.getMinX());
- double miny = Math.min(env1.getMinY(), env2.getMinY());
- double maxx = Math.max(env1.getMaxX(), env2.getMaxX());
- double maxy = Math.max(env1.getMaxY(), env2.getMaxY());
- return distance(minx, miny, maxx, maxy);
- }
-
- private static double distance(double x1, double y1, double x2, double y2) {
- double dx = x2 - x1;
- double dy = y2 - y1;
- return Math.sqrt(dx * dx + dy * dy);
- }
-
- /**
- * Computes the Min-Max Distance between two {@link Envelope}s.
- * It is equal to the minimum of the maximum distances between all pairs of
- * edge segments from the two envelopes.
- * This is the tight upper bound on the distance between
- * geometric items bounded by the envelopes.
- * <p>
- * Theoretically this bound can be used in the R-tree nearest-neighbour branch-and-bound search
- * instead of {@link #maximumDistance(Envelope, Envelope)}.
- * However, little performance improvement is observed in practice.
- *
- * @param a an envelope
- * @param b an envelope
- * @return the min-max-distance between the envelopes
- */
- public static double minMaxDistance(Envelope a, Envelope b)
- {
- double aminx = a.getMinX();
- double aminy = a.getMinY();
- double amaxx = a.getMaxX();
- double amaxy = a.getMaxY();
- double bminx = b.getMinX();
- double bminy = b.getMinY();
- double bmaxx = b.getMaxX();
- double bmaxy = b.getMaxY();
-
- double dist = maxDistance(aminx, aminy, aminx, amaxy, bminx, bminy, bminx, bmaxy);
- dist = Math.min(dist, maxDistance(aminx, aminy, aminx, amaxy, bminx, bminy, bmaxx, bminy));
- dist = Math.min(dist, maxDistance(aminx, aminy, aminx, amaxy, bmaxx, bmaxy, bminx, bmaxy));
- dist = Math.min(dist, maxDistance(aminx, aminy, aminx, amaxy, bmaxx, bmaxy, bmaxx, bminy));
-
- dist = Math.min(dist, maxDistance(aminx, aminy, amaxx, aminy, bminx, bminy, bminx, bmaxy));
- dist = Math.min(dist, maxDistance(aminx, aminy, amaxx, aminy, bminx, bminy, bmaxx, bminy));
- dist = Math.min(dist, maxDistance(aminx, aminy, amaxx, aminy, bmaxx, bmaxy, bminx, bmaxy));
- dist = Math.min(dist, maxDistance(aminx, aminy, amaxx, aminy, bmaxx, bmaxy, bmaxx, bminy));
-
- dist = Math.min(dist, maxDistance(amaxx, amaxy, aminx, amaxy, bminx, bminy, bminx, bmaxy));
- dist = Math.min(dist, maxDistance(amaxx, amaxy, aminx, amaxy, bminx, bminy, bmaxx, bminy));
- dist = Math.min(dist, maxDistance(amaxx, amaxy, aminx, amaxy, bmaxx, bmaxy, bminx, bmaxy));
- dist = Math.min(dist, maxDistance(amaxx, amaxy, aminx, amaxy, bmaxx, bmaxy, bmaxx, bminy));
-
- dist = Math.min(dist, maxDistance(amaxx, amaxy, amaxx, aminy, bminx, bminy, bminx, bmaxy));
- dist = Math.min(dist, maxDistance(amaxx, amaxy, amaxx, aminy, bminx, bminy, bmaxx, bminy));
- dist = Math.min(dist, maxDistance(amaxx, amaxy, amaxx, aminy, bmaxx, bmaxy, bminx, bmaxy));
- dist = Math.min(dist, maxDistance(amaxx, amaxy, amaxx, aminy, bmaxx, bmaxy, bmaxx, bminy));
-
- return dist;
- }
-
- /**
- * Computes the maximum distance between two line segments.
- *
- * @param ax1 x ordinate of first endpoint of segment 1
- * @param ay1 y ordinate of first endpoint of segment 1
- * @param ax2 x ordinate of second endpoint of segment 1
- * @param ay2 y ordinate of second endpoint of segment 1
- * @param bx1 x ordinate of first endpoint of segment 2
- * @param by1 y ordinate of first endpoint of segment 2
- * @param bx2 x ordinate of second endpoint of segment 2
- * @param by2 y ordinate of second endpoint of segment 2
- * @return maximum distance between the segments
- */
- private static double maxDistance(double ax1, double ay1, double ax2, double ay2,
- double bx1, double by1, double bx2, double by2) {
- double dist = distance(ax1, ay1, bx1, by1);
- dist = Math.max(dist, distance(ax1, ay1, bx2, by2));
- dist = Math.max(dist, distance(ax2, ay2, bx1, by1));
- dist = Math.max(dist, distance(ax2, ay2, bx2, by2));
- return dist;
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/GeometryItemDistance.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/GeometryItemDistance.java
deleted file mode 100644
index dc15175..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/GeometryItemDistance.java
+++ /dev/null
@@ -1,50 +0,0 @@
-/*
- * Copyright (c) 2016 Martin Davis.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-
-package org.apache.sedona.jts.index.strtree;
-
-import org.locationtech.jts.geom.Geometry;
-
-/**
- * An {@link ItemDistance} function for
- * items which are {@link Geometry}s,
- * using the {@link Geometry#distance(Geometry)} method.
- * <p>
- * To make this distance function suitable for
- * using to query a single index tree,
- * the distance metric is <i>anti-reflexive</i>.
- * That is, if the two arguments are the same Geometry object,
- * the distance returned is {@link Double.MAX_VALUE}.
- *
- * @author Martin Davis
- *
- */
-public class GeometryItemDistance
-implements ItemDistance
-{
- /**
- * Computes the distance between two {@link Geometry} items,
- * using the {@link Geometry#distance(Geometry)} method.
- *
- * @param item1 an item which is a Geometry
- * @param item2 an item which is a Geometry
- * @return the distance between the geometries
- * @throws ClassCastException if either item is not a Geometry
- */
- public double distance(ItemBoundable item1, ItemBoundable item2) {
- if (item1 == item2) return Double.MAX_VALUE;
- Geometry g1 = (Geometry) item1.getItem();
- Geometry g2 = (Geometry) item2.getItem();
- return g1.distance(g2);
- }
-}
-
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/Interval.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/Interval.java
deleted file mode 100644
index 7aac19d..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/Interval.java
+++ /dev/null
@@ -1,57 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-import org.locationtech.jts.util.Assert;
-
-/**
- * A contiguous portion of 1D-space. Used internally by SIRtree.
- * @see SIRtree
- *
- * @version 1.7
- */
-public class Interval {
-
- public Interval(Interval other) {
- this(other.min, other.max);
- }
-
- public Interval(double min, double max) {
- Assert.isTrue(min <= max);
- this.min = min;
- this.max = max;
- }
-
- private double min;
- private double max;
-
- public double getCentre() { return (min+max)/2; }
-
- /**
- * @return this
- */
- public Interval expandToInclude(Interval other) {
- max = Math.max(max, other.max);
- min = Math.min(min, other.min);
- return this;
- }
-
- public boolean intersects(Interval other) {
- return !(other.min > max || other.max < min);
- }
- public boolean equals(Object o) {
- if (! (o instanceof Interval)) { return false; }
- Interval other = (Interval) o;
- return min == other.min && max == other.max;
- }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/ItemBoundable.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/ItemBoundable.java
deleted file mode 100644
index 27d5a62..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/ItemBoundable.java
+++ /dev/null
@@ -1,37 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-import java.io.Serializable;
-
-/**
- * Boundable wrapper for a non-Boundable spatial object. Used internally by
- * AbstractSTRtree.
- *
- * @version 1.7
- */
-public class ItemBoundable implements Boundable, Serializable {
- private Object bounds;
- private Object item;
-
- public ItemBoundable(Object bounds, Object item) {
- this.bounds = bounds;
- this.item = item;
- }
-
- public Object getBounds() {
- return bounds;
- }
-
- public Object getItem() { return item; }
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/ItemDistance.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/ItemDistance.java
deleted file mode 100644
index 36ffb14..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/ItemDistance.java
+++ /dev/null
@@ -1,47 +0,0 @@
-/*
- * Copyright (c) 2016 Martin Davis.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-
-package org.apache.sedona.jts.index.strtree;
-
-
-/**
- * A function method which computes the distance
- * between two {@link ItemBoundable}s in an {@link STRtree}.
- * Used for Nearest Neighbour searches.
- * <p>
- * To make a distance function suitable for
- * querying a single index tree
- * via {@link STRtree#nearestNeighbour(ItemDistance)} ,
- * the function should have a non-zero <i>reflexive distance</i>.
- * That is, if the two arguments are the same object,
- * the distance returned should be non-zero.
- * If it is required that only pairs of <b>distinct</b> items be returned,
- * the distance function must be <i>anti-reflexive</i>,
- * and must return {@link Double#MAX_VALUE} for identical arguments.
- *
- * @author Martin Davis
- *
- */
-public interface ItemDistance
-{
- /**
- * Computes the distance between two items.
- *
- * @param item1
- * @param item2
- * @return the distance between the items
- *
- * @throws IllegalArgumentException if the metric is not applicable to the arguments
- */
- double distance(ItemBoundable item1, ItemBoundable item2);
-
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/SIRtree.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/SIRtree.java
deleted file mode 100644
index 44ada7a..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/SIRtree.java
+++ /dev/null
@@ -1,109 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-import java.util.Comparator;
-import java.util.Iterator;
-import java.util.List;
-
-/**
- * One-dimensional version of an STR-packed R-tree. SIR stands for
- * "Sort-Interval-Recursive". STR-packed R-trees are described in:
- * P. Rigaux, Michel Scholl and Agnes Voisard. Spatial Databases With
- * Application To GIS. Morgan Kaufmann, San Francisco, 2002.
- * <p>
- * This class is thread-safe. Building the tree is synchronized,
- * and querying is stateless.
- *
- * @see STRtree
- *
- * @version 1.7
- */
-public class SIRtree extends AbstractSTRtree {
-
- private Comparator comparator = new Comparator() {
- public int compare(Object o1, Object o2) {
- return compareDoubles(
- ((Interval)((Boundable)o1).getBounds()).getCentre(),
- ((Interval)((Boundable)o2).getBounds()).getCentre());
- }
- };
-
- private IntersectsOp intersectsOp = new IntersectsOp() {
- public boolean intersects(Object aBounds, Object bBounds) {
- return ((Interval)aBounds).intersects((Interval)bBounds);
- }
- };
-
- /**
- * Constructs an SIRtree with the default node capacity.
- */
- public SIRtree() { this(10); }
-
- /**
- * Constructs an SIRtree with the given maximum number of child nodes that
- * a node may have
- */
- public SIRtree(int nodeCapacity) {
- super(nodeCapacity);
- }
-
- protected AbstractNode createNode(int level) {
- return new AbstractNode(level) {
- protected Object computeBounds() {
- Interval bounds = null;
- for (Iterator i = getChildBoundables().iterator(); i.hasNext(); ) {
- Boundable childBoundable = (Boundable) i.next();
- if (bounds == null) {
- bounds = new Interval((Interval)childBoundable.getBounds());
- }
- else {
- bounds.expandToInclude((Interval)childBoundable.getBounds());
- }
- }
- return bounds;
- }
- };
- }
-
- /**
- * Inserts an item having the given bounds into the tree.
- */
- public void insert(double x1, double x2, Object item) {
- super.insert(new Interval(Math.min(x1, x2), Math.max(x1, x2)), item);
- }
-
- /**
- * Returns items whose bounds intersect the given value.
- */
- public List query(double x) {
- return query(x, x);
- }
-
- /**
- * Returns items whose bounds intersect the given bounds.
- * @param x1 possibly equal to x2
- */
- public List query(double x1, double x2) {
- return super.query(new Interval(Math.min(x1, x2), Math.max(x1, x2)));
- }
-
- protected IntersectsOp getIntersectsOp() {
- return intersectsOp;
- }
-
- protected Comparator getComparator() {
- return comparator;
- }
-
-}
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/STRtree.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/STRtree.java
deleted file mode 100644
index 98ab3d3..0000000
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/STRtree.java
+++ /dev/null
@@ -1,617 +0,0 @@
-
-/*
- * Copyright (c) 2016 Vivid Solutions.
- *
- * All rights reserved. This program and the accompanying materials
- * are made available under the terms of the Eclipse Public License 2.0
- * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
- * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
- * and the Eclipse Distribution License is available at
- *
- * http://www.eclipse.org/org/documents/edl-v10.php.
- */
-package org.apache.sedona.jts.index.strtree;
-
-import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Iterator;
-import java.util.List;
-import java.util.PriorityQueue;
-
-import org.locationtech.jts.geom.Envelope;
-import org.locationtech.jts.index.ItemVisitor;
-import org.locationtech.jts.index.SpatialIndex;
-import org.locationtech.jts.util.Assert;
-
-
-/**
- * A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm.
- * For two-dimensional spatial data.
- * <P>
- * The STR packed R-tree is simple to implement and maximizes space
- * utilization; that is, as many leaves as possible are filled to capacity.
- * Overlap between nodes is far less than in a basic R-tree. However, once the
- * tree has been built (explicitly or on the first call to #query), items may
- * not be added or removed.
- * <P>
- * Described in: P. Rigaux, Michel Scholl and Agnes Voisard.
- * <i>Spatial Databases With Application To GIS</i>.
- * Morgan Kaufmann, San Francisco, 2002.
- * <p>
- * <b>Note that inserting items into a tree is not thread-safe.</b>
- * Inserting performed on more than one thread must be synchronized externally.
- * <p>
- * Querying a tree is thread-safe.
- * The building phase is done synchronously,
- * and querying is stateless.
- *
- * @version 1.7
- */
-public class STRtree extends AbstractSTRtree
-implements SpatialIndex, Serializable
-{
-
- static final class STRtreeNode extends AbstractNode
- {
- STRtreeNode(int level)
- {
- super(level);
- }
-
- protected Object computeBounds() {
- Envelope bounds = null;
- for (Iterator i = getChildBoundables().iterator(); i.hasNext(); ) {
- Boundable childBoundable = (Boundable) i.next();
- if (bounds == null) {
- bounds = new Envelope((Envelope)childBoundable.getBounds());
- }
- else {
- bounds.expandToInclude((Envelope)childBoundable.getBounds());
- }
- }
- return bounds;
- }
- }
-
- /**
- *
- */
- private static final long serialVersionUID = 259274702368956900L;
-
- private static Comparator xComparator =
- new Comparator() {
- public int compare(Object o1, Object o2) {
- return compareDoubles(
- centreX((Envelope)((Boundable)o1).getBounds()),
- centreX((Envelope)((Boundable)o2).getBounds()));
- }
- };
- private static Comparator yComparator =
- new Comparator() {
- public int compare(Object o1, Object o2) {
- return compareDoubles(
- centreY((Envelope)((Boundable)o1).getBounds()),
- centreY((Envelope)((Boundable)o2).getBounds()));
- }
- };
-
- private static double centreX(Envelope e) {
- return avg(e.getMinX(), e.getMaxX());
- }
-
- private static double centreY(Envelope e) {
- return avg(e.getMinY(), e.getMaxY());
- }
-
- private static double avg(double a, double b) { return (a + b) / 2d; }
-
- private static IntersectsOp intersectsOp = new IntersectsOp() {
- public boolean intersects(Object aBounds, Object bBounds) {
- return ((Envelope)aBounds).intersects((Envelope)bBounds);
- }
- };
-
- /**
- * Creates the parent level for the given child level. First, orders the items
- * by the x-values of the midpoints, and groups them into vertical slices.
- * For each slice, orders the items by the y-values of the midpoints, and
- * group them into runs of size M (the node capacity). For each run, creates
- * a new (parent) node.
- */
- protected List createParentBoundables(List childBoundables, int newLevel) {
- Assert.isTrue(!childBoundables.isEmpty());
- int minLeafCount = (int) Math.ceil((childBoundables.size() / (double) getNodeCapacity()));
- ArrayList sortedChildBoundables = new ArrayList(childBoundables);
- Collections.sort(sortedChildBoundables, xComparator);
- List[] verticalSlices = verticalSlices(sortedChildBoundables,
- (int) Math.ceil(Math.sqrt(minLeafCount)));
- return createParentBoundablesFromVerticalSlices(verticalSlices, newLevel);
- }
-
- private List createParentBoundablesFromVerticalSlices(List[] verticalSlices, int newLevel) {
- Assert.isTrue(verticalSlices.length > 0);
- List parentBoundables = new ArrayList();
- for (int i = 0; i < verticalSlices.length; i++) {
- parentBoundables.addAll(
- createParentBoundablesFromVerticalSlice(verticalSlices[i], newLevel));
- }
- return parentBoundables;
- }
-
- protected List createParentBoundablesFromVerticalSlice(List childBoundables, int newLevel) {
- return super.createParentBoundables(childBoundables, newLevel);
- }
-
- /**
- * @param childBoundables Must be sorted by the x-value of the envelope midpoints
- */
- protected List[] verticalSlices(List childBoundables, int sliceCount) {
- int sliceCapacity = (int) Math.ceil(childBoundables.size() / (double) sliceCount);
- List[] slices = new List[sliceCount];
- Iterator i = childBoundables.iterator();
- for (int j = 0; j < sliceCount; j++) {
- slices[j] = new ArrayList();
- int boundablesAddedToSlice = 0;
- while (i.hasNext() && boundablesAddedToSlice < sliceCapacity) {
- Boundable childBoundable = (Boundable) i.next();
- slices[j].add(childBoundable);
- boundablesAddedToSlice++;
- }
- }
- return slices;
- }
-
- private static final int DEFAULT_NODE_CAPACITY = 10;
-
- /**
- * Constructs an STRtree with the default node capacity.
- */
- public STRtree()
- {
- this(DEFAULT_NODE_CAPACITY);
- }
-
- /**
- * Constructs an STRtree with the given maximum number of child nodes that
- * a node may have.
- * <p>
- * The minimum recommended capacity setting is 4.
- *
- */
- public STRtree(int nodeCapacity) {
- super(nodeCapacity);
- }
-
- /**
- * Constructs an STRtree with the given maximum number of child nodes that
- * a node may have, and the root that links to all other nodes
- * <p>
- * The minimum recommended capacity setting is 4.
- *
- */
- public STRtree(int nodeCapacity, STRtreeNode root) {
- super(nodeCapacity, root);
- }
-
- /**
- * Constructs an STRtree with the given maximum number of child nodes that
- * a node may have, and all leaf nodes in the tree
- * <p>
- * The minimum recommended capacity setting is 4.
- *
- */
- public STRtree(int nodeCapacity, ArrayList itemBoundables) {
- super(nodeCapacity, itemBoundables);
- }
-
- protected AbstractNode createNode(int level) {
- return new STRtreeNode(level);
- }
-
- protected IntersectsOp getIntersectsOp() {
- return intersectsOp;
- }
-
- /**
- * Inserts an item having the given bounds into the tree.
- */
- public void insert(Envelope itemEnv, Object item) {
- if (itemEnv.isNull()) { return; }
- super.insert(itemEnv, item);
- }
-
- /**
- * Returns items whose bounds intersect the given envelope.
- */
- public List query(Envelope searchEnv) {
- //Yes this method does something. It specifies that the bounds is an
- //Envelope. super.query takes an Object, not an Envelope. [Jon Aquino 10/24/2003]
- return super.query(searchEnv);
- }
-
- /**
- * Returns items whose bounds intersect the given envelope.
- */
- public void query(Envelope searchEnv, ItemVisitor visitor) {
- //Yes this method does something. It specifies that the bounds is an
- //Envelope. super.query takes an Object, not an Envelope. [Jon Aquino 10/24/2003]
- super.query(searchEnv, visitor);
- }
-
- /**
- * Removes a single item from the tree.
- *
- * @param itemEnv the Envelope of the item to remove
- * @param item the item to remove
- * @return <code>true</code> if the item was found
- */
- public boolean remove(Envelope itemEnv, Object item) {
- return super.remove(itemEnv, item);
- }
-
- /**
- * Returns the number of items in the tree.
- *
- * @return the number of items in the tree
- */
- public int size()
- {
- return super.size();
- }
-
- /**
- * Returns the number of items in the tree.
- *
- * @return the number of items in the tree
- */
- public int depth()
- {
- return super.depth();
- }
-
- protected Comparator getComparator() {
- return yComparator;
- }
-
- /**
- * Finds the two nearest items in the tree,
- * using {@link ItemDistance} as the distance metric.
- * A Branch-and-Bound tree traversal algorithm is used
- * to provide an efficient search.
- * <p>
- * If the tree is empty, the return value is <code>null</code.
- * If the tree contains only one item,
- * the return value is a pair containing that item.
- * <b>
- * If it is required to find only pairs of distinct items,
- * the {@link ItemDistance} function must be <b>anti-reflexive</b>.
- *
- * @param itemDist a distance metric applicable to the items in this tree
- * @return the pair of the nearest items
- * or <code>null</code> if the tree is empty
- */
- public Object[] nearestNeighbour(ItemDistance itemDist)
- {
- if (isEmpty()) return null;
-
- // if tree has only one item this will return null
- BoundablePair bp = new BoundablePair(this.getRoot(), this.getRoot(), itemDist);
- return nearestNeighbour(bp);
- }
-
- /**
- * Finds the item in this tree which is nearest to the given {@link Object},
- * using {@link ItemDistance} as the distance metric.
- * A Branch-and-Bound tree traversal algorithm is used
- * to provide an efficient search.
- * <p>
- * The query <tt>object</tt> does <b>not</b> have to be
- * contained in the tree, but it does
- * have to be compatible with the <tt>itemDist</tt>
- * distance metric.
- *
- * @param env the envelope of the query item
- * @param item the item to find the nearest neighbour of
- * @param itemDist a distance metric applicable to the items in this tree and the query item
- * @return the nearest item in this tree
- * or <code>null</code> if the tree is empty
- */
- public Object nearestNeighbour(Envelope env, Object item, ItemDistance itemDist)
- {
- Boundable bnd = new ItemBoundable(env, item);
- BoundablePair bp = new BoundablePair(this.getRoot(), bnd, itemDist);
- return nearestNeighbour(bp)[0];
- }
-
- /**
- * Finds the two nearest items from this tree
- * and another tree,
- * using {@link ItemDistance} as the distance metric.
- * A Branch-and-Bound tree traversal algorithm is used
- * to provide an efficient search.
- * The result value is a pair of items,
- * the first from this tree and the second
- * from the argument tree.
- *
- * @param tree another tree
- * @param itemDist a distance metric applicable to the items in the trees
- * @return the pair of the nearest items, one from each tree
- * or <code>null</code> if no pair of distinct items can be found
- */
- public Object[] nearestNeighbour(STRtree tree, ItemDistance itemDist)
- {
- if (isEmpty() || tree.isEmpty()) return null;
- BoundablePair bp = new BoundablePair(this.getRoot(), tree.getRoot(), itemDist);
- return nearestNeighbour(bp);
- }
-
- private Object[] nearestNeighbour(BoundablePair initBndPair)
- {
- double distanceLowerBound = Double.POSITIVE_INFINITY;
- BoundablePair minPair = null;
-
- // initialize search queue
- PriorityQueue priQ = new PriorityQueue();
- priQ.add(initBndPair);
-
- while (! priQ.isEmpty() && distanceLowerBound > 0.0) {
- // pop head of queue and expand one side of pair
- BoundablePair bndPair = (BoundablePair) priQ.poll();
- double pairDistance = bndPair.getDistance();
-
- /**
- * If the distance for the first pair in the queue
- * is >= current minimum distance, other nodes
- * in the queue must also have a greater distance.
- * So the current minDistance must be the true minimum,
- * and we are done.
- */
- if (pairDistance >= distanceLowerBound)
- break;
-
- /**
- * If the pair members are leaves
- * then their distance is the exact lower bound.
- * Update the distanceLowerBound to reflect this
- * (which must be smaller, due to the test
- * immediately prior to this).
- */
- if (bndPair.isLeaves()) {
- // assert: currentDistance < minimumDistanceFound
- distanceLowerBound = pairDistance;
- minPair = bndPair;
- }
- else {
- /**
- * Otherwise, expand one side of the pair,
- * and insert the expanded pairs into the queue.
- * The choice of which side to expand is determined heuristically.
- */
- bndPair.expandToQueue(priQ, distanceLowerBound);
- }
- }
- if (minPair == null)
- return null;
- // done - return items with min distance
- return new Object[] {
- ((ItemBoundable) minPair.getBoundable(0)).getItem(),
- ((ItemBoundable) minPair.getBoundable(1)).getItem()
- };
- }
-
- /**
- * Tests whether some two items from this tree and another tree
- * lie within a given distance.
- * {@link ItemDistance} is used as the distance metric.
- * A Branch-and-Bound tree traversal algorithm is used
- * to provide an efficient search.
- *
- * @param tree another tree
- * @param itemDist a distance metric applicable to the items in the trees
- * @param maxDistance the distance limit for the search
- * @return true if there are items within the distance
- */
- public boolean isWithinDistance(STRtree tree, ItemDistance itemDist, double maxDistance)
- {
- BoundablePair bp = new BoundablePair(this.getRoot(), tree.getRoot(), itemDist);
- return isWithinDistance(bp, maxDistance);
- }
-
- /**
- * Performs a withinDistance search on the tree node pairs.
- * This is a different search algorithm to nearest neighbour.
- * It can utilize the {@link BoundablePair#maximumDistance()} between
- * tree nodes to confirm if two internal nodes must
- * have items closer than the maxDistance,
- * and short-circuit the search.
- *
- * @param initBndPair the initial pair containing the tree root nodes
- * @param maxDistance the maximum distance to search for
- * @return true if two items lie within the given distance
- */
- private boolean isWithinDistance(BoundablePair initBndPair, double maxDistance)
- {
- double distanceUpperBound = Double.POSITIVE_INFINITY;
-
- // initialize search queue
- PriorityQueue priQ = new PriorityQueue();
- priQ.add(initBndPair);
-
- while (! priQ.isEmpty()) {
- // pop head of queue and expand one side of pair
- BoundablePair bndPair = (BoundablePair) priQ.poll();
- double pairDistance = bndPair.getDistance();
-
- /**
- * If the distance for the first pair in the queue
- * is > maxDistance, all other pairs
- * in the queue must have a greater distance as well.
- * So can conclude no items are within the distance
- * and terminate with result = false
- */
- if (pairDistance > maxDistance)
- return false;
-
- /**
- * If the maximum distance between the nodes
- * is less than the maxDistance,
- * than all items in the nodes must be
- * closer than the max distance.
- * Then can terminate with result = true.
- *
- * NOTE: using Envelope MinMaxDistance
- * would provide a tighter bound,
- * but not much performance improvement has been observed
- */
- if (bndPair.maximumDistance() <= maxDistance)
- return true;
- /**
- * If the pair items are leaves
- * then their actual distance is an upper bound.
- * Update the distanceUpperBound to reflect this
- */
- if (bndPair.isLeaves()) {
- // assert: currentDistance < minimumDistanceFound
- distanceUpperBound = pairDistance;
-
- /**
- * If the items are closer than maxDistance
- * can terminate with result = true.
- */
- if (distanceUpperBound <= maxDistance)
- return true;
- }
- else {
- /**
- * Otherwise, expand one side of the pair,
- * and insert the expanded pairs into the queue.
- * The choice of which side to expand is determined heuristically.
- */
- bndPair.expandToQueue(priQ, distanceUpperBound);
- }
- }
- return false;
- }
-
- /**
- * Finds k items in this tree which are the top k nearest neighbors to the given {@code item},
- * using {@code itemDist} as the distance metric.
- * A Branch-and-Bound tree traversal algorithm is used
- * to provide an efficient search.
- * This method implements the KNN algorithm described in the following paper:
- * <p>
- * Roussopoulos, Nick, Stephen Kelley, and Frédéric Vincent. "Nearest neighbor queries."
- * ACM sigmod record. Vol. 24. No. 2. ACM, 1995.
- * <p>
- * The query {@code item} does <b>not</b> have to be
- * contained in the tree, but it does
- * have to be compatible with the {@code itemDist}
- * distance metric.
- *
- * @param env the envelope of the query item
- * @param item the item to find the nearest neighbour of
- * @param itemDist a distance metric applicable to the items in this tree and the query item
- * @param k the K nearest items in kNearestNeighbour
- * @return the K nearest items in this tree
- */
- public Object[] nearestNeighbour(Envelope env, Object item, ItemDistance itemDist,int k)
- {
- Boundable bnd = new ItemBoundable(env, item);
- BoundablePair bp = new BoundablePair(this.getRoot(), bnd, itemDist);
- return nearestNeighbourK(bp,k);
- }
-
- private Object[] nearestNeighbourK(BoundablePair initBndPair, int k)
- {
- return nearestNeighbourK(initBndPair, Double.POSITIVE_INFINITY,k);
- }
-
- private Object[] nearestNeighbourK(BoundablePair initBndPair, double maxDistance, int k)
- {
- double distanceLowerBound = maxDistance;
-
- // initialize internal structures
- PriorityQueue priQ = new PriorityQueue();
-
- // initialize queue
- priQ.add(initBndPair);
-
- PriorityQueue kNearestNeighbors = new PriorityQueue();
-
- while (! priQ.isEmpty() && distanceLowerBound >= 0.0) {
- // pop head of queue and expand one side of pair
- BoundablePair bndPair = (BoundablePair) priQ.poll();
- double pairDistance = bndPair.getDistance();
-
-
- /**
- * If the distance for the first node in the queue
- * is >= the current maximum distance in the k queue , all other nodes
- * in the queue must also have a greater distance.
- * So the current minDistance must be the true minimum,
- * and we are done.
- */
- if (pairDistance >= distanceLowerBound){
- break;
- }
- /**
- * If the pair members are leaves
- * then their distance is the exact lower bound.
- * Update the distanceLowerBound to reflect this
- * (which must be smaller, due to the test
- * immediately prior to this).
- */
- if (bndPair.isLeaves()) {
- // assert: currentDistance < minimumDistanceFound
-
- if(kNearestNeighbors.size()<k){
- kNearestNeighbors.add(bndPair);
- }
- else
- {
-
- BoundablePair bp1 = (BoundablePair) kNearestNeighbors.peek();
- if(bp1.getDistance() > pairDistance) {
- kNearestNeighbors.poll();
- kNearestNeighbors.add(bndPair);
- }
- /*
- * minDistance should be the farthest point in the K nearest neighbor queue.
- */
- BoundablePair bp2 = (BoundablePair) kNearestNeighbors.peek();
- distanceLowerBound = bp2.getDistance();
- }
- }
- else {
- /**
- * Otherwise, expand one side of the pair,
- * (the choice of which side to expand is heuristically determined)
- * and insert the new expanded pairs into the queue
- */
- bndPair.expandToQueue(priQ, distanceLowerBound);
- }
- }
- // done - return items with min distance
-
- return getItems(kNearestNeighbors);
- }
- private static Object[] getItems(PriorityQueue kNearestNeighbors)
- {
- /**
- * Iterate the K Nearest Neighbour Queue and retrieve the item from each BoundablePair
- * in this queue
- */
- Object[] items = new Object[kNearestNeighbors.size()];
- int count=0;
- while( ! kNearestNeighbors.isEmpty() )
- {
- BoundablePair bp = (BoundablePair) kNearestNeighbors.poll();
- items[count]=((ItemBoundable)bp.getBoundable(0)).getItem();
- count++;
- }
- return items;
- }
-}
-
diff --git a/core/src/main/java/org/apache/sedona/jts/index/quadtree/IndexSerde.java b/core/src/main/java/org/locationtech/jts/index/quadtree/IndexSerde.java
similarity index 98%
rename from core/src/main/java/org/apache/sedona/jts/index/quadtree/IndexSerde.java
rename to core/src/main/java/org/locationtech/jts/index/quadtree/IndexSerde.java
index 8f89398..5dd6556 100644
--- a/core/src/main/java/org/apache/sedona/jts/index/quadtree/IndexSerde.java
+++ b/core/src/main/java/org/locationtech/jts/index/quadtree/IndexSerde.java
@@ -11,7 +11,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-package org.apache.sedona.jts.index.quadtree;
+package org.locationtech.jts.index.quadtree;
import com.esotericsoftware.kryo.Kryo;
import com.esotericsoftware.kryo.io.Input;
diff --git a/core/src/main/java/org/apache/sedona/jts/index/strtree/IndexSerde.java b/core/src/main/java/org/locationtech/jts/index/strtree/IndexSerde.java
similarity index 99%
rename from core/src/main/java/org/apache/sedona/jts/index/strtree/IndexSerde.java
rename to core/src/main/java/org/locationtech/jts/index/strtree/IndexSerde.java
index 0ff7007..bf3d308 100644
--- a/core/src/main/java/org/apache/sedona/jts/index/strtree/IndexSerde.java
+++ b/core/src/main/java/org/locationtech/jts/index/strtree/IndexSerde.java
@@ -11,7 +11,7 @@
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-package org.apache.sedona.jts.index.strtree;
+package org.locationtech.jts.index.strtree;
import com.esotericsoftware.kryo.Kryo;
import com.esotericsoftware.kryo.io.Input;
diff --git a/core/src/test/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerdeTest.java b/core/src/test/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerdeTest.java
index 62479c7..b44ee21 100644
--- a/core/src/test/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerdeTest.java
+++ b/core/src/test/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerdeTest.java
@@ -22,14 +22,14 @@ package org.apache.sedona.core.geometryObjects;
import com.esotericsoftware.kryo.Kryo;
import com.esotericsoftware.kryo.io.Input;
import com.esotericsoftware.kryo.io.Output;
-import org.apache.sedona.jts.index.quadtree.Quadtree;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.junit.Test;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.Point;
import org.locationtech.jts.index.SpatialIndex;
+import org.locationtech.jts.index.quadtree.Quadtree;
+import org.locationtech.jts.index.strtree.STRtree;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
diff --git a/core/src/test/java/org/apache/sedona/core/spatialRDD/LineStringRDDTest.java b/core/src/test/java/org/apache/sedona/core/spatialRDD/LineStringRDDTest.java
index cfcb0ae..fe7692e 100644
--- a/core/src/test/java/org/apache/sedona/core/spatialRDD/LineStringRDDTest.java
+++ b/core/src/test/java/org/apache/sedona/core/spatialRDD/LineStringRDDTest.java
@@ -19,12 +19,12 @@
package org.apache.sedona.core.spatialRDD;
import org.apache.sedona.core.enums.IndexType;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.apache.spark.storage.StorageLevel;
import org.junit.AfterClass;
import org.junit.BeforeClass;
import org.junit.Test;
import org.locationtech.jts.geom.Polygon;
+import org.locationtech.jts.index.strtree.STRtree;
import java.util.List;
diff --git a/core/src/test/java/org/apache/sedona/core/spatialRDD/PointRDDTest.java b/core/src/test/java/org/apache/sedona/core/spatialRDD/PointRDDTest.java
index 798e950..bca0563 100644
--- a/core/src/test/java/org/apache/sedona/core/spatialRDD/PointRDDTest.java
+++ b/core/src/test/java/org/apache/sedona/core/spatialRDD/PointRDDTest.java
@@ -19,12 +19,12 @@
package org.apache.sedona.core.spatialRDD;
import org.apache.sedona.core.enums.IndexType;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.apache.spark.storage.StorageLevel;
import org.junit.AfterClass;
import org.junit.BeforeClass;
import org.junit.Test;
import org.locationtech.jts.geom.Point;
+import org.locationtech.jts.index.strtree.STRtree;
import java.util.List;
diff --git a/core/src/test/java/org/apache/sedona/core/spatialRDD/PolygonRDDTest.java b/core/src/test/java/org/apache/sedona/core/spatialRDD/PolygonRDDTest.java
index e1b05ad..dfae6cc 100644
--- a/core/src/test/java/org/apache/sedona/core/spatialRDD/PolygonRDDTest.java
+++ b/core/src/test/java/org/apache/sedona/core/spatialRDD/PolygonRDDTest.java
@@ -20,12 +20,12 @@ package org.apache.sedona.core.spatialRDD;
import org.apache.sedona.core.enums.FileDataSplitter;
import org.apache.sedona.core.enums.IndexType;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.apache.spark.storage.StorageLevel;
import org.junit.AfterClass;
import org.junit.BeforeClass;
import org.junit.Test;
import org.locationtech.jts.geom.Polygon;
+import org.locationtech.jts.index.strtree.STRtree;
import java.io.BufferedReader;
import java.io.FileReader;
diff --git a/core/src/test/java/org/apache/sedona/core/spatialRDD/RectangleRDDTest.java b/core/src/test/java/org/apache/sedona/core/spatialRDD/RectangleRDDTest.java
index c99aaa1..aa63f21 100644
--- a/core/src/test/java/org/apache/sedona/core/spatialRDD/RectangleRDDTest.java
+++ b/core/src/test/java/org/apache/sedona/core/spatialRDD/RectangleRDDTest.java
@@ -19,12 +19,12 @@
package org.apache.sedona.core.spatialRDD;
import org.apache.sedona.core.enums.IndexType;
-import org.apache.sedona.jts.index.strtree.STRtree;
import org.apache.spark.storage.StorageLevel;
import org.junit.AfterClass;
import org.junit.BeforeClass;
import org.junit.Test;
import org.locationtech.jts.geom.Point;
+import org.locationtech.jts.index.strtree.STRtree;
import java.util.List;
diff --git a/pom.xml b/pom.xml
index 9041631..58c1f38 100644
--- a/pom.xml
+++ b/pom.xml
@@ -67,7 +67,7 @@
<geotools.version>24.0</geotools.version>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
<dependency.scope>provided</dependency.scope>
- <jts.version>1.17.1</jts.version>
+ <jts.version>1.18.0</jts.version>
<jts2geojson.version>0.14.3</jts2geojson.version>
</properties>