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/18 08:07:04 UTC
[incubator-sedona] branch master updated: [SEDONA-3] First release:
Set up POM for uploading snapshots and releases (#495)
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 1cf775d [SEDONA-3] First release: Set up POM for uploading snapshots and releases (#495)
1cf775d is described below
commit 1cf775dc94ef549f4913c0297b848d55e70ad4d9
Author: Jia Yu <ji...@apache.org>
AuthorDate: Fri Dec 18 00:02:09 2020 -0800
[SEDONA-3] First release: Set up POM for uploading snapshots and releases (#495)
* Update GitHub action
* Cache Maven package
* Separate maven and python test
* Update the pom, setup py
* Remove JTS SNAPSHOT dependency and copy 5 JTS files to Sedona
* Update POM
* Update POM
* Update POM
* Update scalastyle
* Update POM
* Update POM
* Change the scope of all dependencies to provided. Put necessary compile dependencies to Python adapter. Rename copied JTS files under org.apache.sedona.jts.index
* Change the scope of all dependencies to provided. Put necessary compile dependencies to Python adapter. Rename copied JTS files under org.apache.sedona.jts.index
* Change the scope of all dependencies to provided. Put necessary compile dependencies to Python adapter. Rename copied JTS files under org.apache.sedona.jts.index
* Change the scope of all dependencies to provided. Put necessary compile dependencies to Python adapter. Rename copied JTS files under org.apache.sedona.jts.index
* Change the scope of all dependencies to provided. Put necessary compile dependencies to Python adapter. Rename copied JTS files under org.apache.sedona.jts.index
---
.github/workflows/java.yml | 2 +-
.github/workflows/python.yml | 2 +-
.gitmodules | 2 +-
core/pom.xml | 113 +---
.../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/IndexSerde.java | 2 +-
.../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 ++
.../sedona}/jts/index/strtree/IndexSerde.java | 2 +-
.../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 +++++++++++++++++++++
.../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 | 314 +++++++----
python-adapter/pom.xml | 92 ++-
python/LICENSE | 201 -------
python/setup.py | 6 +-
.../scalastyle_config.xml => scalastyle_config.xml | 0
sql/pom.xml | 58 +-
viz/pom.xml | 59 +-
viz/src/test/resources/scalastyle_config.xml | 187 -------
44 files changed, 3334 insertions(+), 766 deletions(-)
diff --git a/.github/workflows/java.yml b/.github/workflows/java.yml
index d75f89d..e9b758e 100644
--- a/.github/workflows/java.yml
+++ b/.github/workflows/java.yml
@@ -41,7 +41,7 @@ jobs:
- env:
SPARK_VERSION: ${{ matrix.spark }}
SCALA_VERSION: ${{ matrix.scala }}
- run: mvn -q clean install -Dscala.compat.version=${SCALA_VERSION:0:4} -Dscala.version=$SCALA_VERSION -Dspark.compat.version=${SPARK_VERSION:0:3} -Dspark.version=$SPARK_VERSION
+ run: mvn -q clean install -Dscala=${SCALA_VERSION:0:4} -Dspark=${SPARK_VERSION:0:3}
- run: mkdir staging
- run: cp core/target/sedona-*.jar staging
- run: cp sql/target/sedona-*.jar staging
diff --git a/.github/workflows/python.yml b/.github/workflows/python.yml
index ef66649..1f980f3 100644
--- a/.github/workflows/python.yml
+++ b/.github/workflows/python.yml
@@ -49,7 +49,7 @@ jobs:
- env:
SPARK_VERSION: ${{ matrix.spark }}
SCALA_VERSION: ${{ matrix.scala }}
- run: mvn -q clean install -DskipTests -Dscala.compat.version=${SCALA_VERSION:0:4} -Dscala.version=$SCALA_VERSION -Dspark.compat.version=${SPARK_VERSION:0:3} -Dspark.version=$SPARK_VERSION
+ run: mvn -q clean install -DskipTests -Dscala=${SCALA_VERSION:0:4} -Dspark=${SPARK_VERSION:0:3}
- env:
SPARK_VERSION: ${{ matrix.spark }}
run: wget https://archive.apache.org/dist/spark/spark-${SPARK_VERSION}/spark-${SPARK_VERSION}-bin-hadoop2.7.tgz
diff --git a/.gitmodules b/.gitmodules
index 9c44d36..be6ffe7 100644
--- a/.gitmodules
+++ b/.gitmodules
@@ -1,3 +1,3 @@
[submodule "contrib/R"]
path = contrib/R
- url = https://github.com/harryprince/geospark
\ No newline at end of file
+ url = https://github.com/harryprince/geospark
diff --git a/core/pom.xml b/core/pom.xml
index 5f18c55..d7fae36 100644
--- a/core/pom.xml
+++ b/core/pom.xml
@@ -17,8 +17,7 @@
~ under the License.
-->
-<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0"
- xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<parent>
<groupId>org.apache.sedona</groupId>
@@ -29,122 +28,30 @@
<artifactId>sedona-core_${scala.compat.version}</artifactId>
<name>${project.groupId}:${project.artifactId}</name>
- <description>A cluster computing system for processing large-scale spatial data: RDD API</description>
+ <description>A cluster computing system for processing large-scale spatial data: RDD API. Apache Sedona is an effort undergoing incubation at The Apache Software Foundation (ASF), sponsored by the Apache Incubator. Incubation is required of all newly accepted projects until a further review indicates that the infrastructure, communications, and decision making process have stabilized in a manner consistent with other successful ASF projects. While incubation status is not necessarily [...]
<url>http://sedona.apache.org/</url>
<packaging>jar</packaging>
<dependencies>
+ <!-- Test -->
<dependency>
- <groupId>org.locationtech.jts</groupId>
- <artifactId>jts-core</artifactId>
- <version>1.18.0-SNAPSHOT</version>
- <scope>compile</scope>
- </dependency>
- <dependency>
- <groupId>org.wololo</groupId>
- <artifactId>jts2geojson</artifactId>
- <version>0.14.3</version>
- <exclusions>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- <exclusion>
- <groupId>com.fasterxml.jackson.module</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!--The following GeoTools dependencies use GNU Lesser General Public License and thus are excluded from the binary distribution-->
- <!-- Users have to include them by themselves manually -->
- <!-- See https://www.apache.org/legal/resolved.html#category-x -->
- <!-- See https://github.com/geotools/geotools#license -->
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-main</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.vividsolutions</groupId>
- <artifactId>jts</artifactId>
- </exclusion>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-referencing</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-epsg-hsql</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-epsg-extension</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
+ <groupId>org.apache.hadoop</groupId>
+ <artifactId>hadoop-minicluster</artifactId>
+ <version>2.7.4</version>
+ <scope>test</scope>
</dependency>
- <!--for Shapefile reader-->
<dependency>
<groupId>org.geotools</groupId>
<artifactId>gt-shapefile</artifactId>
<version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.vividsolutions</groupId>
- <artifactId>jts</artifactId>
- </exclusion>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!-- Test -->
- <dependency>
- <groupId>org.apache.hadoop</groupId>
- <artifactId>hadoop-minicluster</artifactId>
- <version>2.8.2</version>
<scope>test</scope>
<exclusions>
<exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
+ <groupId>org.locationtech.jts</groupId>
+ <artifactId>jts-core</artifactId>
</exclusion>
<exclusion>
- <groupId>com.fasterxml.jackson.module</groupId>
+ <groupId>com.fasterxml.jackson.core</groupId>
<artifactId>*</artifactId>
</exclusion>
</exclusions>
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 a8e5cbe..ab47d35 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.locationtech.jts.index.quadtree.IndexSerde;
-import org.locationtech.jts.index.quadtree.Quadtree;
-import org.locationtech.jts.index.strtree.STRtree;
+import org.apache.sedona.jts.index.quadtree.IndexSerde;
+import org.apache.sedona.jts.index.quadtree.Quadtree;
+import org.apache.sedona.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.locationtech.jts.index.strtree.IndexSerde indexSerde
- = new org.locationtech.jts.index.strtree.IndexSerde();
+ org.apache.sedona.jts.index.strtree.IndexSerde indexSerde
+ = new org.apache.sedona.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.locationtech.jts.index.strtree.IndexSerde indexSerde =
- new org.locationtech.jts.index.strtree.IndexSerde();
+ org.apache.sedona.jts.index.strtree.IndexSerde indexSerde =
+ new org.apache.sedona.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 c1fbcf5..418d319 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 f7a2b10..d9299f1 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 57894ea..5fc4535 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,6 +24,8 @@ 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;
@@ -33,8 +35,6 @@ 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 d015dfb..758cfdf 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 3b3d34e..84a0457 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
new file mode 100644
index 0000000..33f29b4
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/quadtree/DoubleBits.java
@@ -0,0 +1,152 @@
+
+/*
+ * 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/locationtech/jts/index/quadtree/IndexSerde.java b/core/src/main/java/org/apache/sedona/jts/index/quadtree/IndexSerde.java
similarity index 98%
rename from core/src/main/java/org/locationtech/jts/index/quadtree/IndexSerde.java
rename to core/src/main/java/org/apache/sedona/jts/index/quadtree/IndexSerde.java
index 5dd6556..8f89398 100644
--- a/core/src/main/java/org/locationtech/jts/index/quadtree/IndexSerde.java
+++ b/core/src/main/java/org/apache/sedona/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.locationtech.jts.index.quadtree;
+package org.apache.sedona.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/quadtree/IntervalSize.java b/core/src/main/java/org/apache/sedona/jts/index/quadtree/IntervalSize.java
new file mode 100644
index 0000000..aea891a
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/quadtree/IntervalSize.java
@@ -0,0 +1,52 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..79538b1
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/quadtree/Key.java
@@ -0,0 +1,81 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..b891e7a
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/quadtree/Node.java
@@ -0,0 +1,183 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..5b9d6fc
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/quadtree/NodeBase.java
@@ -0,0 +1,236 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..87d0db2
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/quadtree/Quadtree.java
@@ -0,0 +1,246 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..2e3d455
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/quadtree/Root.java
@@ -0,0 +1,99 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..51bfed4
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/AbstractNode.java
@@ -0,0 +1,136 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..ae17bb7
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/AbstractSTRtree.java
@@ -0,0 +1,484 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..64a6f07
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/Boundable.java
@@ -0,0 +1,30 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..bf1b25c
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/BoundablePair.java
@@ -0,0 +1,211 @@
+/*
+ * 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
new file mode 100644
index 0000000..0634fce
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/BoundablePairDistanceComparator.java
@@ -0,0 +1,65 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..55d99ac
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/EnvelopeDistance.java
@@ -0,0 +1,120 @@
+/*
+ * 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
new file mode 100644
index 0000000..dc15175
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/GeometryItemDistance.java
@@ -0,0 +1,50 @@
+/*
+ * 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/locationtech/jts/index/strtree/IndexSerde.java b/core/src/main/java/org/apache/sedona/jts/index/strtree/IndexSerde.java
similarity index 99%
rename from core/src/main/java/org/locationtech/jts/index/strtree/IndexSerde.java
rename to core/src/main/java/org/apache/sedona/jts/index/strtree/IndexSerde.java
index bf3d308..0ff7007 100644
--- a/core/src/main/java/org/locationtech/jts/index/strtree/IndexSerde.java
+++ b/core/src/main/java/org/apache/sedona/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.locationtech.jts.index.strtree;
+package org.apache.sedona.jts.index.strtree;
import com.esotericsoftware.kryo.Kryo;
import com.esotericsoftware.kryo.io.Input;
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
new file mode 100644
index 0000000..7aac19d
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/Interval.java
@@ -0,0 +1,57 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..27d5a62
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/ItemBoundable.java
@@ -0,0 +1,37 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..36ffb14
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/ItemDistance.java
@@ -0,0 +1,47 @@
+/*
+ * 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
new file mode 100644
index 0000000..44ada7a
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/SIRtree.java
@@ -0,0 +1,109 @@
+
+/*
+ * 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
new file mode 100644
index 0000000..98ab3d3
--- /dev/null
+++ b/core/src/main/java/org/apache/sedona/jts/index/strtree/STRtree.java
@@ -0,0 +1,617 @@
+
+/*
+ * 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/test/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerdeTest.java b/core/src/test/java/org/apache/sedona/core/geometryObjects/SpatialIndexSerdeTest.java
index b44ee21..62479c7 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 fe7692e..cfcb0ae 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 bca0563..798e950 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 dfae6cc..e1b05ad 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 aa63f21..c99aaa1 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 5543877..9041631 100644
--- a/pom.xml
+++ b/pom.xml
@@ -1,15 +1,41 @@
-<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0"
- xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+<!--
+ ~ Licensed to the Apache Software Foundation (ASF) under one
+ ~ or more contributor license agreements. See the NOTICE file
+ ~ distributed with this work for additional information
+ ~ regarding copyright ownership. The ASF licenses this file
+ ~ to you under the Apache License, Version 2.0 (the
+ ~ "License"); you may not use this file except in compliance
+ ~ with the License. You may obtain a copy of the License at
+ ~
+ ~ http://www.apache.org/licenses/LICENSE-2.0
+ ~
+ ~ Unless required by applicable law or agreed to in writing,
+ ~ software distributed under the License is distributed on an
+ ~ "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ ~ KIND, either express or implied. See the License for the
+ ~ specific language governing permissions and limitations
+ ~ under the License.
+ -->
+<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
<modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.apache</groupId>
+ <artifactId>apache</artifactId>
+ <version>23</version>
+ <relativePath></relativePath>
+ </parent>
<groupId>org.apache.sedona</groupId>
<artifactId>sedona-parent</artifactId>
<version>1.0.0-incubator-SNAPSHOT</version>
<packaging>pom</packaging>
<name>sedona-parent</name>
<url>http://sedona.apache.org/</url>
- <description>A cluster computing system for processing large-scale spatial data</description>
+ <description>Apache Sedona is a cluster computing system for processing large-scale spatial data. Apache Sedona is an effort undergoing incubation at The Apache Software Foundation (ASF), sponsored by the Apache Incubator. Incubation is required of all newly accepted projects until a further review indicates that the infrastructure, communications, and decision making process have stabilized in a manner consistent with other successful ASF projects. While incubation status is not nec [...]
+ </description>
+ <developers>
+ <developer><name>Apache Sedona</name></developer>
+ </developers>
<modules>
- <module>jts/modules/core</module>
<module>core</module>
<module>sql</module>
<module>viz</module>
@@ -34,22 +60,110 @@
<connection>scm:git:https://github.com/apache/incubator-sedona.git</connection>
<developerConnection>scm:git:https://github.com/apache/incubator-sedona.git</developerConnection>
<url>https://github.com/apache/incubator-sedona</url>
+ <tag>HEAD</tag>
</scm>
<properties>
- <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
- <scala.version>2.12.8</scala.version>
- <scala.compat.version>2.12</scala.compat.version>
<geotools.version>24.0</geotools.version>
- <spark.version>3.0.1</spark.version>
- <spark.compat.version>3.0</spark.compat.version>
+ <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
+ <dependency.scope>provided</dependency.scope>
+ <jts.version>1.17.1</jts.version>
+ <jts2geojson.version>0.14.3</jts2geojson.version>
</properties>
+
<dependencies>
<dependency>
+ <groupId>com.fasterxml.jackson.core</groupId>
+ <artifactId>jackson-databind</artifactId>
+ <version>${jackson.version}</version>
+ <scope>${dependency.scope}</scope>
+ </dependency>
+ <dependency>
+ <groupId>com.fasterxml.jackson.core</groupId>
+ <artifactId>jackson-core</artifactId>
+ <version>${jackson.version}</version>
+ <scope>${dependency.scope}</scope>
+ </dependency>
+ <dependency>
+ <groupId>org.wololo</groupId>
+ <artifactId>jts2geojson</artifactId>
+ <version>${jts2geojson.version}</version>
+ <exclusions>
+ <exclusion>
+ <groupId>org.locationtech.jts</groupId>
+ <artifactId>jts-core</artifactId>
+ </exclusion>
+ <exclusion>
+ <groupId>com.fasterxml.jackson.core</groupId>
+ <artifactId>*</artifactId>
+ </exclusion>
+ </exclusions>
+ <scope>${dependency.scope}</scope>
+ </dependency>
+ <dependency>
+ <groupId>org.locationtech.jts</groupId>
+ <artifactId>jts-core</artifactId>
+ <version>${jts.version}</version>
+ <scope>${dependency.scope}</scope>
+ </dependency>
+ <dependency>
+ <groupId>org.datasyslab</groupId>
+ <artifactId>sernetcdf</artifactId>
+ <version>0.1.0</version>
+ <scope>${dependency.scope}</scope>
+ </dependency>
+ <!--The following GeoTools dependencies use GNU Lesser General Public License and thus are excluded from the binary distribution-->
+ <!-- Users have to include them by themselves manually -->
+ <!-- See https://www.apache.org/legal/resolved.html#category-x -->
+ <!-- See https://github.com/geotools/geotools#license -->
+ <!--for CRS transformation-->
+ <dependency>
+ <groupId>org.geotools</groupId>
+ <artifactId>gt-main</artifactId>
+ <version>${geotools.version}</version>
+ <scope>${dependency.scope}</scope>
+ <exclusions>
+ <exclusion>
+ <groupId>org.locationtech.jts</groupId>
+ <artifactId>jts-core</artifactId>
+ </exclusion>
+ <exclusion>
+ <groupId>com.fasterxml.jackson.core</groupId>
+ <artifactId>*</artifactId>
+ </exclusion>
+ </exclusions>
+ </dependency>
+ <!--for CRS transformation-->
+ <dependency>
+ <groupId>org.geotools</groupId>
+ <artifactId>gt-referencing</artifactId>
+ <version>${geotools.version}</version>
+ <scope>${dependency.scope}</scope>
+ <exclusions>
+ <exclusion>
+ <groupId>com.fasterxml.jackson.core</groupId>
+ <artifactId>*</artifactId>
+ </exclusion>
+ </exclusions>
+ </dependency>
+ <!--for CRS transformation-->
+ <dependency>
+ <groupId>org.geotools</groupId>
+ <artifactId>gt-epsg-hsql</artifactId>
+ <version>${geotools.version}</version>
+ <scope>${dependency.scope}</scope>
+ <exclusions>
+ <exclusion>
+ <groupId>com.fasterxml.jackson.core</groupId>
+ <artifactId>*</artifactId>
+ </exclusion>
+ </exclusions>
+ </dependency>
+ <dependency>
<groupId>org.apache.spark</groupId>
<artifactId>spark-core_${scala.compat.version}</artifactId>
<version>${spark.version}</version>
- <scope>provided</scope>
+ <scope>${dependency.scope}</scope>
<exclusions>
<exclusion>
<groupId>org.apache.hadoop</groupId>
@@ -61,25 +175,25 @@
<groupId>org.apache.spark</groupId>
<artifactId>spark-sql_${scala.compat.version}</artifactId>
<version>${spark.version}</version>
- <scope>provided</scope>
+ <scope>${dependency.scope}</scope>
</dependency>
<dependency>
<groupId>org.apache.hadoop</groupId>
<artifactId>hadoop-mapreduce-client-core</artifactId>
<version>2.8.2</version>
- <scope>provided</scope>
+ <scope>${dependency.scope}</scope>
</dependency>
<dependency>
<groupId>org.apache.hadoop</groupId>
<artifactId>hadoop-common</artifactId>
<version>2.8.2</version>
- <scope>provided</scope>
+ <scope>${dependency.scope}</scope>
</dependency>
<dependency>
<groupId>org.apache.hadoop</groupId>
<artifactId>hadoop-hdfs</artifactId>
<version>2.8.2</version>
- <scope>provided</scope>
+ <scope>${dependency.scope}</scope>
<exclusions>
<exclusion>
<groupId>log4j</groupId>
@@ -91,12 +205,6 @@
</exclusion>
</exclusions>
</dependency>
- <dependency>
- <groupId>org.datasyslab</groupId>
- <artifactId>sernetcdf</artifactId>
- <version>0.1.0</version>
- <scope>provided</scope>
- </dependency>
<!-- Test -->
<dependency>
<groupId>junit</groupId>
@@ -134,15 +242,6 @@
<enabled>true</enabled>
</releases>
</repository>
- <repository>
- <id>osgeo-alt</id>
- <url>https://repo.osgeo.org/repository/release/</url>
- </repository>
- <repository>
- <id>geomajas</id>
- <name>Geomajas Maven Repository</name>
- <url>http://maven.geomajas.org/(http://maven.geomajas.org/)</url>
- </repository>
</repositories>
<build>
<pluginManagement>
@@ -179,7 +278,6 @@
</args>
</configuration>
</execution>
-
</executions>
</plugin>
<plugin>
@@ -187,8 +285,8 @@
<artifactId>maven-compiler-plugin</artifactId>
<version>3.1</version>
<configuration>
- <source>1.7</source>
- <target>1.7</target>
+ <source>1.8</source>
+ <target>1.8</target>
</configuration>
</plugin>
</plugins>
@@ -276,88 +374,26 @@
</execution>
</executions>
</plugin>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-javadoc-plugin</artifactId>
+ <version>2.10.4</version>
+ <executions>
+ <execution>
+ <id>attach-javadocs</id>
+ <goals>
+ <goal>jar</goal>
+ </goals>
+ </execution>
+ </executions>
+ <configuration>
+ <additionalparam>-Xdoclint:none</additionalparam>
+ </configuration>
+ </plugin>
</plugins>
</build>
<profiles>
<profile>
- <id>release-sign-artifacts</id>
- <activation>
- <property>
- <name>performRelease</name>
- <value>true</value>
- </property>
- </activation>
- <distributionManagement>
- <snapshotRepository>
- <id>ossrh</id>
- <url>https://oss.sonatype.org/content/repositories/snapshots</url>
- </snapshotRepository>
- <repository>
- <id>ossrh</id>
- <url>https://oss.sonatype.org/service/local/staging/deploy/maven2/</url>
- </repository>
- </distributionManagement>
- <build>
- <plugins>
- <plugin>
- <groupId>org.sonatype.plugins</groupId>
- <artifactId>nexus-staging-maven-plugin</artifactId>
- <version>1.6.7</version>
- <extensions>true</extensions>
- <configuration>
- <serverId>ossrh</serverId>
- <nexusUrl>https://oss.sonatype.org/</nexusUrl>
- <stagingProfileId>21756750b51471</stagingProfileId>
- <autoReleaseAfterClose>true</autoReleaseAfterClose>
- </configuration>
- </plugin>
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-gpg-plugin</artifactId>
- <executions>
- <execution>
- <id>sign-artifacts</id>
- <phase>verify</phase>
- <goals>
- <goal>sign</goal>
- </goals>
- </execution>
- </executions>
- </plugin>
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-source-plugin</artifactId>
- <version>3.0.1</version>
- <executions>
- <execution>
- <id>attach-sources</id>
- <goals>
- <goal>jar</goal>
- </goals>
- </execution>
- </executions>
- </plugin>
-
- <plugin>
- <groupId>org.apache.maven.plugins</groupId>
- <artifactId>maven-javadoc-plugin</artifactId>
- <version>2.10.4</version>
- <executions>
- <execution>
- <id>attach-javadocs</id>
- <goals>
- <goal>jar</goal>
- </goals>
- </execution>
- </executions>
- <configuration>
- <additionalparam>-Xdoclint:none</additionalparam>
- </configuration>
- </plugin>
- </plugins>
- </build>
- </profile>
- <profile>
<id>allow-snapshots</id>
<activation>
<activeByDefault>true</activeByDefault>
@@ -375,5 +411,63 @@
</repository>
</repositories>
</profile>
+ <profile>
+ <id>spark3.0</id>
+ <activation>
+ <property>
+ <name>spark</name>
+ <value>3.0</value>
+ </property>
+ <activeByDefault>true</activeByDefault>
+ </activation>
+ <properties>
+ <spark.version>3.0.1</spark.version>
+ <spark.compat.version>3.0</spark.compat.version>
+ <jackson.version>2.10.0</jackson.version>
+ </properties>
+ </profile>
+ <profile>
+ <id>spark2.4</id>
+ <activation>
+ <property>
+ <name>spark</name>
+ <value>2.4</value>
+ </property>
+ <activeByDefault>false</activeByDefault>
+ </activation>
+ <properties>
+ <spark.version>2.4.7</spark.version>
+ <spark.compat.version>2.4</spark.compat.version>
+ <jackson.version>2.6.7</jackson.version>
+ </properties>
+ </profile>
+ <profile>
+ <id>scala2.12</id>
+ <activation>
+ <property>
+ <name>scala</name>
+ <value>2.12</value>
+ </property>
+ <activeByDefault>true</activeByDefault>
+ </activation>
+ <properties>
+ <scala.version>2.12.8</scala.version>
+ <scala.compat.version>2.12</scala.compat.version>
+ </properties>
+ </profile>
+ <profile>
+ <id>scala2.11</id>
+ <activation>
+ <property>
+ <name>scala</name>
+ <value>2.11</value>
+ </property>
+ <activeByDefault>false</activeByDefault>
+ </activation>
+ <properties>
+ <scala.version>2.11.8</scala.version>
+ <scala.compat.version>2.11</scala.compat.version>
+ </properties>
+ </profile>
</profiles>
</project>
diff --git a/python-adapter/pom.xml b/python-adapter/pom.xml
index 940b687..a8edf64 100644
--- a/python-adapter/pom.xml
+++ b/python-adapter/pom.xml
@@ -1,17 +1,48 @@
-<?xml version="1.0" encoding="UTF-8"?>
-<project xmlns="http://maven.apache.org/POM/4.0.0"
- xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
- xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+<!--
+ ~ Licensed to the Apache Software Foundation (ASF) under one
+ ~ or more contributor license agreements. See the NOTICE file
+ ~ distributed with this work for additional information
+ ~ regarding copyright ownership. The ASF licenses this file
+ ~ to you under the Apache License, Version 2.0 (the
+ ~ "License"); you may not use this file except in compliance
+ ~ with the License. You may obtain a copy of the License at
+ ~
+ ~ http://www.apache.org/licenses/LICENSE-2.0
+ ~
+ ~ Unless required by applicable law or agreed to in writing,
+ ~ software distributed under the License is distributed on an
+ ~ "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ ~ KIND, either express or implied. See the License for the
+ ~ specific language governing permissions and limitations
+ ~ under the License.
+ -->
+
+<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
<parent>
<artifactId>sedona-parent</artifactId>
<groupId>org.apache.sedona</groupId>
<version>1.0.0-incubator-SNAPSHOT</version>
</parent>
- <modelVersion>4.0.0</modelVersion>
-
<artifactId>sedona-python-adapter-${spark.compat.version}_${scala.compat.version}</artifactId>
+
+ <name>${project.groupId}:${project.artifactId}</name>
+ <description>A cluster computing system for processing large-scale spatial data: Python Adapter. Apache Sedona is an effort undergoing incubation at The Apache Software Foundation (ASF), sponsored by the Apache Incubator. Incubation is required of all newly accepted projects until a further review indicates that the infrastructure, communications, and decision making process have stabilized in a manner consistent with other successful ASF projects. While incubation status is not nece [...]
+ <url>http://sedona.apache.org/</url>
+ <packaging>jar</packaging>
+
<dependencies>
<dependency>
+ <groupId>org.locationtech.jts</groupId>
+ <artifactId>jts-core</artifactId>
+ <version>${jts.version}</version>
+ </dependency>
+ <dependency>
+ <groupId>org.wololo</groupId>
+ <artifactId>jts2geojson</artifactId>
+ <version>${jts2geojson.version}</version>
+ </dependency>
+ <dependency>
<groupId>org.apache.sedona</groupId>
<artifactId>sedona-core_${scala.compat.version}</artifactId>
<version>${project.version}</version>
@@ -28,8 +59,8 @@
<version>${geotools.version}</version>
<exclusions>
<exclusion>
- <groupId>com.vividsolutions</groupId>
- <artifactId>jts</artifactId>
+ <groupId>org.locationtech.jts</groupId>
+ <artifactId>jts-core</artifactId>
</exclusion>
<exclusion>
<groupId>com.fasterxml.jackson.core</groupId>
@@ -73,22 +104,33 @@
</exclusion>
</exclusions>
</dependency>
- <!--for Shapefile reader-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-shapefile</artifactId>
- <version>${geotools.version}</version>
- <exclusions>
- <exclusion>
- <groupId>com.vividsolutions</groupId>
- <artifactId>jts</artifactId>
- </exclusion>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
</dependencies>
-
+ <build>
+ <sourceDirectory>src/main/scala</sourceDirectory>
+ <plugins>
+ <plugin>
+ <groupId>org.scalastyle</groupId>
+ <artifactId>scalastyle-maven-plugin</artifactId>
+ <version>1.0.0</version>
+ <configuration>
+ <verbose>false</verbose>
+ <failOnViolation>true</failOnViolation>
+ <includeTestSourceDirectory>true</includeTestSourceDirectory>
+ <failOnWarning>false</failOnWarning>
+ <sourceDirectory>${project.basedir}/src/main/scala</sourceDirectory>
+ <testSourceDirectory>${project.basedir}/src/test/scala</testSourceDirectory>
+ <configLocation>${project.basedir}/../scalastyle_config.xml</configLocation>
+ <outputFile>${project.basedir}/target/scalastyle-output.xml</outputFile>
+ <outputEncoding>UTF-8</outputEncoding>
+ </configuration>
+ <executions>
+ <execution>
+ <goals>
+ <goal>check</goal>
+ </goals>
+ </execution>
+ </executions>
+ </plugin>
+ </plugins>
+ </build>
</project>
diff --git a/python/LICENSE b/python/LICENSE
deleted file mode 100644
index 261eeb9..0000000
--- a/python/LICENSE
+++ /dev/null
@@ -1,201 +0,0 @@
- Apache License
- Version 2.0, January 2004
- http://www.apache.org/licenses/
-
- TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
-
- 1. Definitions.
-
- "License" shall mean the terms and conditions for use, reproduction,
- and distribution as defined by Sections 1 through 9 of this document.
-
- "Licensor" shall mean the copyright owner or entity authorized by
- the copyright owner that is granting the License.
-
- "Legal Entity" shall mean the union of the acting entity and all
- other entities that control, are controlled by, or are under common
- control with that entity. For the purposes of this definition,
- "control" means (i) the power, direct or indirect, to cause the
- direction or management of such entity, whether by contract or
- otherwise, or (ii) ownership of fifty percent (50%) or more of the
- outstanding shares, or (iii) beneficial ownership of such entity.
-
- "You" (or "Your") shall mean an individual or Legal Entity
- exercising permissions granted by this License.
-
- "Source" form shall mean the preferred form for making modifications,
- including but not limited to software source code, documentation
- source, and configuration files.
-
- "Object" form shall mean any form resulting from mechanical
- transformation or translation of a Source form, including but
- not limited to compiled object code, generated documentation,
- and conversions to other media types.
-
- "Work" shall mean the work of authorship, whether in Source or
- Object form, made available under the License, as indicated by a
- copyright notice that is included in or attached to the work
- (an example is provided in the Appendix below).
-
- "Derivative Works" shall mean any work, whether in Source or Object
- form, that is based on (or derived from) the Work and for which the
- editorial revisions, annotations, elaborations, or other modifications
- represent, as a whole, an original work of authorship. For the purposes
- of this License, Derivative Works shall not include works that remain
- separable from, or merely link (or bind by name) to the interfaces of,
- the Work and Derivative Works thereof.
-
- "Contribution" shall mean any work of authorship, including
- the original version of the Work and any modifications or additions
- to that Work or Derivative Works thereof, that is intentionally
- submitted to Licensor for inclusion in the Work by the copyright owner
- or by an individual or Legal Entity authorized to submit on behalf of
- the copyright owner. For the purposes of this definition, "submitted"
- means any form of electronic, verbal, or written communication sent
- to the Licensor or its representatives, including but not limited to
- communication on electronic mailing lists, source code control systems,
- and issue tracking systems that are managed by, or on behalf of, the
- Licensor for the purpose of discussing and improving the Work, but
- excluding communication that is conspicuously marked or otherwise
- designated in writing by the copyright owner as "Not a Contribution."
-
- "Contributor" shall mean Licensor and any individual or Legal Entity
- on behalf of whom a Contribution has been received by Licensor and
- subsequently incorporated within the Work.
-
- 2. Grant of Copyright License. Subject to the terms and conditions of
- this License, each Contributor hereby grants to You a perpetual,
- worldwide, non-exclusive, no-charge, royalty-free, irrevocable
- copyright license to reproduce, prepare Derivative Works of,
- publicly display, publicly perform, sublicense, and distribute the
- Work and such Derivative Works in Source or Object form.
-
- 3. Grant of Patent License. Subject to the terms and conditions of
- this License, each Contributor hereby grants to You a perpetual,
- worldwide, non-exclusive, no-charge, royalty-free, irrevocable
- (except as stated in this section) patent license to make, have made,
- use, offer to sell, sell, import, and otherwise transfer the Work,
- where such license applies only to those patent claims licensable
- by such Contributor that are necessarily infringed by their
- Contribution(s) alone or by combination of their Contribution(s)
- with the Work to which such Contribution(s) was submitted. If You
- institute patent litigation against any entity (including a
- cross-claim or counterclaim in a lawsuit) alleging that the Work
- or a Contribution incorporated within the Work constitutes direct
- or contributory patent infringement, then any patent licenses
- granted to You under this License for that Work shall terminate
- as of the date such litigation is filed.
-
- 4. Redistribution. You may reproduce and distribute copies of the
- Work or Derivative Works thereof in any medium, with or without
- modifications, and in Source or Object form, provided that You
- meet the following conditions:
-
- (a) You must give any other recipients of the Work or
- Derivative Works a copy of this License; and
-
- (b) You must cause any modified files to carry prominent notices
- stating that You changed the files; and
-
- (c) You must retain, in the Source form of any Derivative Works
- that You distribute, all copyright, patent, trademark, and
- attribution notices from the Source form of the Work,
- excluding those notices that do not pertain to any part of
- the Derivative Works; and
-
- (d) If the Work includes a "NOTICE" text file as part of its
- distribution, then any Derivative Works that You distribute must
- include a readable copy of the attribution notices contained
- within such NOTICE file, excluding those notices that do not
- pertain to any part of the Derivative Works, in at least one
- of the following places: within a NOTICE text file distributed
- as part of the Derivative Works; within the Source form or
- documentation, if provided along with the Derivative Works; or,
- within a display generated by the Derivative Works, if and
- wherever such third-party notices normally appear. The contents
- of the NOTICE file are for informational purposes only and
- do not modify the License. You may add Your own attribution
- notices within Derivative Works that You distribute, alongside
- or as an addendum to the NOTICE text from the Work, provided
- that such additional attribution notices cannot be construed
- as modifying the License.
-
- You may add Your own copyright statement to Your modifications and
- may provide additional or different license terms and conditions
- for use, reproduction, or distribution of Your modifications, or
- for any such Derivative Works as a whole, provided Your use,
- reproduction, and distribution of the Work otherwise complies with
- the conditions stated in this License.
-
- 5. Submission of Contributions. Unless You explicitly state otherwise,
- any Contribution intentionally submitted for inclusion in the Work
- by You to the Licensor shall be under the terms and conditions of
- this License, without any additional terms or conditions.
- Notwithstanding the above, nothing herein shall supersede or modify
- the terms of any separate license agreement you may have executed
- with Licensor regarding such Contributions.
-
- 6. Trademarks. This License does not grant permission to use the trade
- names, trademarks, service marks, or product names of the Licensor,
- except as required for reasonable and customary use in describing the
- origin of the Work and reproducing the content of the NOTICE file.
-
- 7. Disclaimer of Warranty. Unless required by applicable law or
- agreed to in writing, Licensor provides the Work (and each
- Contributor provides its Contributions) on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
- implied, including, without limitation, any warranties or conditions
- of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
- PARTICULAR PURPOSE. You are solely responsible for determining the
- appropriateness of using or redistributing the Work and assume any
- risks associated with Your exercise of permissions under this License.
-
- 8. Limitation of Liability. In no event and under no legal theory,
- whether in tort (including negligence), contract, or otherwise,
- unless required by applicable law (such as deliberate and grossly
- negligent acts) or agreed to in writing, shall any Contributor be
- liable to You for damages, including any direct, indirect, special,
- incidental, or consequential damages of any character arising as a
- result of this License or out of the use or inability to use the
- Work (including but not limited to damages for loss of goodwill,
- work stoppage, computer failure or malfunction, or any and all
- other commercial damages or losses), even if such Contributor
- has been advised of the possibility of such damages.
-
- 9. Accepting Warranty or Additional Liability. While redistributing
- the Work or Derivative Works thereof, You may choose to offer,
- and charge a fee for, acceptance of support, warranty, indemnity,
- or other liability obligations and/or rights consistent with this
- License. However, in accepting such obligations, You may act only
- on Your own behalf and on Your sole responsibility, not on behalf
- of any other Contributor, and only if You agree to indemnify,
- defend, and hold each Contributor harmless for any liability
- incurred by, or claims asserted against, such Contributor by reason
- of your accepting any such warranty or additional liability.
-
- END OF TERMS AND CONDITIONS
-
- APPENDIX: How to apply the Apache License to your work.
-
- To apply the Apache License to your work, attach the following
- boilerplate notice, with the fields enclosed by brackets "[]"
- replaced with your own identifying information. (Don't include
- the brackets!) The text should be enclosed in the appropriate
- comment syntax for the file format. We also recommend that a
- file or class name and description of purpose be included on the
- same "printed page" as the copyright notice for easier
- identification within third-party archives.
-
- Copyright [yyyy] [name of copyright owner]
-
- Licensed under the Apache License, Version 2.0 (the "License");
- you may not use this file except in compliance with the License.
- You may obtain a copy of the License at
-
- http://www.apache.org/licenses/LICENSE-2.0
-
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
diff --git a/python/setup.py b/python/setup.py
index 74197d3..7c5f1d1 100644
--- a/python/setup.py
+++ b/python/setup.py
@@ -10,10 +10,10 @@ with open("README.md", "r") as fh:
setup(
name='sedona',
version=version,
- description='Apache Sedona Python',
+ description='Apache Sedona is a cluster computing system for processing large-scale spatial data. Apache Sedona is an effort undergoing incubation at The Apache Software Foundation (ASF), sponsored by the Apache Incubator. Incubation is required of all newly accepted projects until a further review indicates that the infrastructure, communications, and decision making process have stabilized in a manner consistent with other successful ASF projects. While incubation status is not nec [...]
url='https://github.com/apache/incubator-sedona',
- author='Pawel Kocinski',
- author_email='pawel93kocinski@gmail.com',
+ author='Apache Sedona',
+ author_email='dev@sedona.apache.org',
packages=find_packages(exclude=["*.tests", "*.tests.*", "tests.*", "tests"]),
long_description=long_description,
long_description_content_type="text/markdown",
diff --git a/sql/src/test/resources/scalastyle_config.xml b/scalastyle_config.xml
similarity index 100%
rename from sql/src/test/resources/scalastyle_config.xml
rename to scalastyle_config.xml
diff --git a/sql/pom.xml b/sql/pom.xml
index d814989..574278e 100644
--- a/sql/pom.xml
+++ b/sql/pom.xml
@@ -17,8 +17,7 @@
~ under the License.
-->
-<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
- xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<parent>
<groupId>org.apache.sedona</groupId>
@@ -29,7 +28,7 @@
<artifactId>sedona-sql-${spark.compat.version}_${scala.compat.version}</artifactId>
<name>${project.groupId}:${project.artifactId}</name>
- <description>A cluster computing system for processing large-scale spatial data: SQL API</description>
+ <description>A cluster computing system for processing large-scale spatial data: SQL API. Apache Sedona is an effort undergoing incubation at The Apache Software Foundation (ASF), sponsored by the Apache Incubator. Incubation is required of all newly accepted projects until a further review indicates that the infrastructure, communications, and decision making process have stabilized in a manner consistent with other successful ASF projects. While incubation status is not necessarily a [...]
<url>http://sedona.apache.org/</url>
<packaging>jar</packaging>
@@ -40,57 +39,10 @@
<version>${project.version}</version>
<scope>provided</scope>
</dependency>
- <!--The following GeoTools dependencies use GNU Lesser General Public License and thus are excluded from the binary distribution-->
- <!-- Users have to include them by themselves manually -->
- <!-- See https://www.apache.org/legal/resolved.html#category-x -->
- <!-- See https://github.com/geotools/geotools#license -->
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-main</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.vividsolutions</groupId>
- <artifactId>jts</artifactId>
- </exclusion>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-referencing</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-epsg-hsql</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
</dependencies>
<build>
<sourceDirectory>src/main/scala</sourceDirectory>
- <plugins>
+ <plugins>
<plugin>
<groupId>org.scalastyle</groupId>
<artifactId>scalastyle-maven-plugin</artifactId>
@@ -102,7 +54,7 @@
<failOnWarning>false</failOnWarning>
<sourceDirectory>${project.basedir}/src/main/scala</sourceDirectory>
<testSourceDirectory>${project.basedir}/src/test/scala</testSourceDirectory>
- <configLocation>${project.basedir}/src/test/resources/scalastyle_config.xml</configLocation>
+ <configLocation>${project.basedir}/../scalastyle_config.xml</configLocation>
<outputFile>${project.basedir}/target/scalastyle-output.xml</outputFile>
<outputEncoding>UTF-8</outputEncoding>
</configuration>
@@ -114,7 +66,7 @@
</execution>
</executions>
</plugin>
- </plugins>
+ </plugins>
</build>
</project>
diff --git a/viz/pom.xml b/viz/pom.xml
index 6129672..e1eee27 100644
--- a/viz/pom.xml
+++ b/viz/pom.xml
@@ -17,8 +17,7 @@
~ under the License.
-->
-<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
- xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<parent>
<groupId>org.apache.sedona</groupId>
@@ -29,7 +28,7 @@
<artifactId>sedona-viz-${spark.compat.version}_${scala.compat.version}</artifactId>
<name>${project.groupId}:${project.artifactId}</name>
- <description>A cluster computing system for processing large-scale spatial data: RDD and SQL for Viz</description>
+ <description>A cluster computing system for processing large-scale spatial data: RDD and SQL for Viz. Apache Sedona is an effort undergoing incubation at The Apache Software Foundation (ASF), sponsored by the Apache Incubator. Incubation is required of all newly accepted projects until a further review indicates that the infrastructure, communications, and decision making process have stabilized in a manner consistent with other successful ASF projects. While incubation status is not ne [...]
<url>http://sedona.apache.org/</url>
<packaging>jar</packaging>
@@ -55,57 +54,7 @@
<groupId>com.amazonaws</groupId>
<artifactId>aws-java-sdk</artifactId>
<version>1.7.4</version>
- <exclusions>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- <exclusion>
- <groupId>com.fasterxml.jackson.module</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!--The following GeoTools dependencies use GNU Lesser General Public License and thus are excluded from the binary distribution-->
- <!-- Users have to include them by themselves manually -->
- <!-- See https://www.apache.org/legal/resolved.html#category-x -->
- <!-- See https://github.com/geotools/geotools#license -->
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-main</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.vividsolutions</groupId>
- <artifactId>jts</artifactId>
- </exclusion>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-referencing</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
- <exclusions>
- <exclusion>
- <groupId>com.fasterxml.jackson.core</groupId>
- <artifactId>*</artifactId>
- </exclusion>
- </exclusions>
- </dependency>
- <!--for CRS transformation-->
- <dependency>
- <groupId>org.geotools</groupId>
- <artifactId>gt-epsg-hsql</artifactId>
- <version>${geotools.version}</version>
- <scope>provided</scope>
+ <scope>${dependency.scope}</scope>
<exclusions>
<exclusion>
<groupId>com.fasterxml.jackson.core</groupId>
@@ -128,7 +77,7 @@
<failOnWarning>false</failOnWarning>
<sourceDirectory>${project.basedir}/src/main/scala</sourceDirectory>
<testSourceDirectory>${project.basedir}/src/test/scala</testSourceDirectory>
- <configLocation>${project.basedir}/src/test/resources/scalastyle_config.xml</configLocation>
+ <configLocation>${project.basedir}/../scalastyle_config.xml</configLocation>
<outputFile>${project.basedir}/target/scalastyle-output.xml</outputFile>
<outputEncoding>UTF-8</outputEncoding>
</configuration>
diff --git a/viz/src/test/resources/scalastyle_config.xml b/viz/src/test/resources/scalastyle_config.xml
deleted file mode 100644
index 6a95f66..0000000
--- a/viz/src/test/resources/scalastyle_config.xml
+++ /dev/null
@@ -1,187 +0,0 @@
-<scalastyle commentFilter="enabled">
- <name>Scalastyle standard configuration</name>
- <check class="org.scalastyle.file.FileTabChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.file.FileLengthChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="maxFileLength"><![CDATA[800]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.file.HeaderMatchesChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="header"><![CDATA[// Copyright (C) 2011-2012 the original author or authors.
-// See the LICENCE.txt file distributed with this work for additional
-// information regarding copyright ownership.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.SpacesAfterPlusChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.file.WhitespaceEndOfLineChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="ignoreWhitespaceLines"><![CDATA[false]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.SpacesBeforePlusChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.file.FileLineLengthChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="maxLineLength"><![CDATA[160]]></parameter>
- <parameter name="tabSize"><![CDATA[4]]></parameter>
- <parameter name="ignoreImports"><![CDATA[false]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.ClassNamesChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="regex"><![CDATA[^[A-Z][A-Za-z]*$]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.ObjectNamesChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="regex"><![CDATA[^[A-Z][A-Za-z]*$]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.PackageObjectNamesChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="regex"><![CDATA[^[a-z][A-Za-z]*$]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.EqualsHashCodeChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.IllegalImportsChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="illegalImports"><![CDATA[sun._,java.awt._]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.ParameterNumberChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="maxParameters"><![CDATA[8]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.MagicNumberChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="ignore"><![CDATA[-1,0,1,2,3]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.NoWhitespaceBeforeLeftBracketChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.NoWhitespaceAfterLeftBracketChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.ReturnChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.NullChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.NoCloneChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.NoFinalizeChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.CovariantEqualsChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.StructuralTypeChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.file.RegexChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="regex"><![CDATA[println]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.NumberOfTypesChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="maxTypes"><![CDATA[30]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.CyclomaticComplexityChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="maximum"><![CDATA[10]]></parameter>
- <parameter name="countCases"><![CDATA[true]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.UppercaseLChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.SimplifyBooleanExpressionChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.IfBraceChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="singleLineAllowed"><![CDATA[true]]></parameter>
- <parameter name="doubleLineAllowed"><![CDATA[false]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.MethodLengthChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="maxLength"><![CDATA[50]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.MethodNamesChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="regex"><![CDATA[^[a-z][A-Za-z0-9]*(_=)?$]]></parameter>
- <parameter name="ignoreRegex"><![CDATA[^$]]></parameter>
- <parameter name="ignoreOverride"><![CDATA[false]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.NumberOfMethodsInTypeChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="maxMethods"><![CDATA[30]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.PublicMethodsHaveTypeChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="ignoreOverride"><![CDATA[false]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.file.NewLineAtEofChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.file.NoNewLineAtEofChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.WhileChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.VarFieldChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.VarLocalChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.RedundantIfChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.TokenChecker" level="warning" enabled="false">
- <parameters>
- <parameter name="regex"><![CDATA[println]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.DeprecatedJavaChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.OverrideJavaChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.EmptyClassChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.ClassTypeParameterChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="regex"><![CDATA[^[A-Z_]$]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.UnderscoreImportChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.LowercasePatternMatchChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.EmptyInterpolatedStringChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.MultipleStringLiteralsChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="allowed"><![CDATA[2]]></parameter>
- <parameter name="ignoreRegex"><![CDATA[^""$]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.ImportGroupingChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.NotImplementedErrorUsage" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.BlockImportChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.ProcedureDeclarationChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.ForBraceChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.SpaceAfterCommentStartChecker" level="warning" enabled="true"></check>
- <check class="org.scalastyle.scalariform.ScalaDocChecker" level="warning" enabled="false">
- <parameters>
- <parameter name="ignoreRegex"><![CDATA[^$]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.DisallowSpaceAfterTokenChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.DisallowSpaceBeforeTokenChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.EnsureSingleSpaceAfterTokenChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.EnsureSingleSpaceBeforeTokenChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.scalariform.NonASCIICharacterChecker" level="warning" enabled="false"></check>
- <check class="org.scalastyle.file.IndentationChecker" level="warning" enabled="false">
- <parameters>
- <parameter name="tabSize"><![CDATA[2]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.FieldNamesChecker" level="warning" enabled="false">
- <parameters>
- <parameter name="regex"><![CDATA[^[a-z][A-Za-z]*$]]></parameter>
- <parameter name="objectFieldRegex"><![CDATA[^[A-Z][A-Za-z]*$]]></parameter>
- </parameters>
- </check>
- <check class="org.scalastyle.scalariform.TodoCommentChecker" level="warning" enabled="true">
- <parameters>
- <parameter name="words"><![CDATA[TODO|FIXME]]></parameter>
- </parameters>
- </check>
-</scalastyle>
\ No newline at end of file