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 2023/04/18 02:18:18 UTC
[sedona] branch master updated: [SEDONA-274] transplant subdivider and simplifier to sedona-common (#818)
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/sedona.git
The following commit(s) were added to refs/heads/master by this push:
new e9e41809 [SEDONA-274] transplant subdivider and simplifier to sedona-common (#818)
e9e41809 is described below
commit e9e418095237b9ce2c0baa6add9e017df84e0854
Author: zongsi.zhang <kr...@gmail.com>
AuthorDate: Tue Apr 18 10:18:13 2023 +0800
[SEDONA-274] transplant subdivider and simplifier to sedona-common (#818)
---
.../sedona/common/simplify/BaseSimplifier.java | 20 +++
.../sedona/common/simplify/CircleSimplifier.java | 23 +++
.../sedona/common/simplify/CoordinateSplitter.java | 96 ++++++++++++
.../common/simplify/CoordinatesSimplifier.java | 69 +++++++++
.../simplify/GeometryCollectionSimplifier.java | 62 ++++++++
.../sedona/common/simplify/GeometrySimplifier.java | 33 ++++
.../common/simplify/LineStringSimplifier.java | 37 +++++
.../sedona/common/simplify/PolygonSimplifier.java | 49 ++++++
.../simplify/ZeroToleranceGeometrySimplifier.java | 55 +++++++
.../common/subDivide/GeometrySubDivider.java | 172 +++++++++++++++++++++
.../sedona/common/subDivide/PivotFinder.java | 65 ++++++++
.../apache/sedona/common/subDivide/SubBoxes.java | 33 ++++
.../sedona/common/subDivide/SubDivideExtent.java | 77 +++++++++
.../org/apache/sedona/common/utils/GeomUtils.java | 8 +-
.../sql/sedona_sql/expressions/Functions.scala | 3 +-
.../expressions/simplify/CircleSimplifier.scala | 27 ----
.../simplify/CoordinatesSimplifier.scala | 69 ---------
.../expressions/simplify/CoordinatesSplitter.scala | 82 ----------
.../simplify/GeometryCollectionSimplifier.scala | 52 -------
.../expressions/simplify/GeometrySimplifier.scala | 50 ------
.../simplify/LinestringSimplifier.scala | 42 -----
.../expressions/simplify/PolygonSimplifier.scala | 50 ------
.../simplify/SimplifyingParameters.scala | 24 ---
.../expressions/subdivide/GeometrySubDivider.scala | 148 ------------------
.../GeometrySubDividerConfiguration.scala | 28 ----
.../expressions/subdivide/PivotFinder.scala | 50 ------
.../sedona_sql/expressions/subdivide/Stack.scala | 40 -----
.../expressions/subdivide/SubdivideExtent.scala | 35 -----
.../ZeroToleranceGeometrySimplifier.scala | 65 --------
.../sql/functions/TestGeometrySimplify.scala | 2 +-
.../sedona/sql/functions/TestStSubDivide.scala | 8 +-
31 files changed, 804 insertions(+), 770 deletions(-)
diff --git a/common/src/main/java/org/apache/sedona/common/simplify/BaseSimplifier.java b/common/src/main/java/org/apache/sedona/common/simplify/BaseSimplifier.java
new file mode 100644
index 00000000..7b04ef4f
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/simplify/BaseSimplifier.java
@@ -0,0 +1,20 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.simplify;
+
+import org.locationtech.jts.geom.GeometryFactory;
+
+public abstract class BaseSimplifier {
+ protected static GeometryFactory geometryFactory = new GeometryFactory();
+}
diff --git a/common/src/main/java/org/apache/sedona/common/simplify/CircleSimplifier.java b/common/src/main/java/org/apache/sedona/common/simplify/CircleSimplifier.java
new file mode 100644
index 00000000..3b8d6e62
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/simplify/CircleSimplifier.java
@@ -0,0 +1,23 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.simplify;
+
+import org.apache.sedona.common.geometryObjects.Circle;
+import org.locationtech.jts.geom.Geometry;
+
+public class CircleSimplifier {
+ public static Geometry simplify(Circle geom, boolean preserveCollapsed, double epsilon) {
+ return geom;
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/simplify/CoordinateSplitter.java b/common/src/main/java/org/apache/sedona/common/simplify/CoordinateSplitter.java
new file mode 100644
index 00000000..1c33b894
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/simplify/CoordinateSplitter.java
@@ -0,0 +1,96 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.simplify;
+
+import org.locationtech.jts.geom.Coordinate;
+
+public class CoordinateSplitter {
+
+ private static final double DBL_EPSILON = 2.2204460492503131e-16;
+
+ public static SplitInPlace splitInPlace(
+ Coordinate[] geom,
+ int itFirst,
+ int itLast,
+ double maxDistanceSquared
+ ) {
+ int split = itFirst;
+ double maxDistance = maxDistanceSquared;
+ if ((itFirst - itLast) < 2) new SplitInPlace(geom, itFirst);
+ Coordinate pointA = geom[itFirst];
+ Coordinate pointB = geom[itLast];
+ if (calculateSquaredDistance(pointA, pointB) < DBL_EPSILON){
+ for (int itk = itFirst + 1; itk < itLast ; itk++){
+ Coordinate pk = geom[itk];
+ double squaredDistance = calculateSquaredDistance(pk, pointA);
+ if (squaredDistance > maxDistance){
+ split = itk;
+ maxDistance = squaredDistance;
+ }
+ }
+ }
+
+ double ba_x = pointB.x - pointA.x;
+ double ba_y = pointB.y - pointA.y;
+ double ab_length_sqr = (ba_x * ba_x + ba_y * ba_y);
+ maxDistance *= ab_length_sqr;
+ for (int itk = itFirst + 1; itk < itLast; itk++){
+ Coordinate c = geom[itk];
+ double distance_sqr = 0.0;
+ double ca_x = c.x - pointA.x;
+ double ca_y = c.y - pointA.y;
+ double dot_ac_ab = (ca_x * ba_x + ca_y * ba_y);
+ if (dot_ac_ab <= 0.0) {
+ distance_sqr = calculateSquaredDistance(c, pointA) * ab_length_sqr;
+ }
+ else if (dot_ac_ab >= ab_length_sqr) {
+ distance_sqr = calculateSquaredDistance(c, pointB) * ab_length_sqr;
+ }
+ else {
+ double s_numerator = ca_x * ba_y - ca_y * ba_x;
+ distance_sqr = s_numerator * s_numerator;
+ }
+ if (distance_sqr > maxDistance)
+ {
+ split = itk;
+ maxDistance = distance_sqr;
+ }
+ }
+ return new SplitInPlace(geom, split);
+ }
+
+ private static double calculateSquaredDistance(Coordinate geomA, Coordinate geomB) {
+ double distance = geomA.distance(geomB);
+ return distance * distance;
+ }
+
+ public static class SplitInPlace {
+ private Coordinate[] geom;
+
+ private int split;
+
+ public SplitInPlace(Coordinate[] geom, int split) {
+ this.geom = geom;
+ this.split = split;
+ }
+
+ public Coordinate[] getGeom() {
+ return geom;
+ }
+
+ public int getSplit() {
+ return split;
+ }
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/simplify/CoordinatesSimplifier.java b/common/src/main/java/org/apache/sedona/common/simplify/CoordinatesSimplifier.java
new file mode 100644
index 00000000..f7b87f2b
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/simplify/CoordinatesSimplifier.java
@@ -0,0 +1,69 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.simplify;
+
+import org.locationtech.jts.geom.Coordinate;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Stack;
+
+public class CoordinatesSimplifier {
+ public static Coordinate[] simplifyInPlace(Coordinate[] geom, double tolerance, int minPointsExternal) {
+ if (geom.length < 3 || geom.length <= minPointsExternal) {
+ return geom;
+ } else if (tolerance == 0 && minPointsExternal <= 2) {
+ return ZeroToleranceGeometrySimplifier.simplifyInPlaceTolerance0(geom);
+ } else {
+ boolean[] kept_points = new boolean[geom.length];
+ kept_points[0] = true;
+ int itLast = geom.length - 1;
+ kept_points[itLast] = true;
+ int keptn = 2;
+ Stack<Integer> iteratorStack = new Stack<Integer>();
+ iteratorStack.push(0);
+ int itFirst = 0;
+ double toleranceSquared = tolerance * tolerance;
+ double itTool = keptn >= minPointsExternal ? toleranceSquared : -1.0;
+
+ while (!iteratorStack.isEmpty()){
+ CoordinateSplitter.SplitInPlace splitInPlaceRes = CoordinateSplitter.splitInPlace(
+ geom,
+ itFirst,
+ itLast,
+ itTool
+ );
+ if (splitInPlaceRes.getSplit() == itFirst){
+ itFirst = itLast;
+ itLast = iteratorStack.pop();
+ }
+ else {
+ kept_points[splitInPlaceRes.getSplit()] = true;
+ keptn = keptn + 1;
+
+ iteratorStack.push(itLast);
+ itLast = splitInPlaceRes.getSplit();
+ itTool = keptn >= minPointsExternal ? toleranceSquared : -1.0;
+ }
+ }
+ List<Coordinate> result = new ArrayList<>();
+ for (int i = 0; i < kept_points.length; i++) {
+ if (kept_points[i]) {
+ result.add(geom[i]);
+ }
+ }
+ return result.toArray(new Coordinate[0]);
+ }
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/simplify/GeometryCollectionSimplifier.java b/common/src/main/java/org/apache/sedona/common/simplify/GeometryCollectionSimplifier.java
new file mode 100644
index 00000000..ec259a20
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/simplify/GeometryCollectionSimplifier.java
@@ -0,0 +1,62 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.simplify;
+
+import org.apache.sedona.common.geometryObjects.Circle;
+import org.apache.sedona.common.utils.GeomUtils;
+import org.locationtech.jts.geom.*;
+
+import java.util.Arrays;
+import java.util.Objects;
+
+public class GeometryCollectionSimplifier extends BaseSimplifier{
+
+ public static Geometry simplify(GeometryCollection geom, boolean preserveCollapsed, double epsilon) {
+
+ Geometry[] simplifiedSubGeoms = Arrays.stream(GeomUtils.getSubGeometries(geom)).map(
+ subGeom -> {
+ if (subGeom instanceof Circle) {
+ return CircleSimplifier.simplify( (Circle) subGeom, preserveCollapsed, epsilon);
+ }
+ else if (subGeom instanceof LineString) {
+ return LineStringSimplifier.simplify((LineString) subGeom, preserveCollapsed, epsilon);
+ }
+ else if (subGeom instanceof Point) {
+ return subGeom;
+ }
+ else if (subGeom instanceof Polygon) {
+ return PolygonSimplifier.simplify((Polygon) subGeom, preserveCollapsed, epsilon);
+ }
+ else if (subGeom instanceof GeometryCollection) {
+ return simplify((GeometryCollection) subGeom, preserveCollapsed, epsilon);
+ } else {
+ return null;
+ }
+ }
+ ).filter(Objects::nonNull).toArray(Geometry[]::new);
+
+ String[] distinctGeometries = Arrays.stream(simplifiedSubGeoms).map(Geometry::getGeometryType).distinct().toArray(String[]::new);
+ if (distinctGeometries.length == 1){
+ switch (distinctGeometries[0]) {
+ case Geometry.TYPENAME_LINESTRING:
+ return geometryFactory.createMultiLineString(Arrays.stream(simplifiedSubGeoms).map(x -> (LineString) x).toArray(LineString[]::new));
+ case Geometry.TYPENAME_POLYGON:
+ return geometryFactory.createMultiPolygon(Arrays.stream(simplifiedSubGeoms).map(x -> (Polygon) x).toArray(Polygon[]::new));
+ case Geometry.TYPENAME_POINT:
+ return geometryFactory.createMultiPoint(Arrays.stream(simplifiedSubGeoms).map(x -> (Point) x).toArray(Point[]::new));
+ }
+ }
+ return geometryFactory.createGeometryCollection(simplifiedSubGeoms);
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/simplify/GeometrySimplifier.java b/common/src/main/java/org/apache/sedona/common/simplify/GeometrySimplifier.java
new file mode 100644
index 00000000..23313ba6
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/simplify/GeometrySimplifier.java
@@ -0,0 +1,33 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.simplify;
+
+import org.apache.sedona.common.geometryObjects.Circle;
+import org.locationtech.jts.geom.*;
+
+public class GeometrySimplifier {
+ public static Geometry simplify(Geometry geom, boolean preserveCollapsed, double epsilon) {
+ if (geom instanceof Circle) {
+ return CircleSimplifier.simplify((Circle) geom, preserveCollapsed, epsilon);
+ } else if (geom instanceof GeometryCollection) {
+ return GeometryCollectionSimplifier.simplify((GeometryCollection) geom, preserveCollapsed, epsilon);
+ } else if (geom instanceof LineString) {
+ return LineStringSimplifier.simplify(geom, preserveCollapsed, epsilon);
+ } else if (geom instanceof Polygon) {
+ return PolygonSimplifier.simplify((Polygon) geom, preserveCollapsed, epsilon);
+ }else {
+ return geom;
+ }
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/simplify/LineStringSimplifier.java b/common/src/main/java/org/apache/sedona/common/simplify/LineStringSimplifier.java
new file mode 100644
index 00000000..4915692f
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/simplify/LineStringSimplifier.java
@@ -0,0 +1,37 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.simplify;
+
+import org.apache.commons.lang3.ArrayUtils;
+import org.locationtech.jts.geom.Coordinate;
+import org.locationtech.jts.geom.Geometry;
+
+public class LineStringSimplifier extends BaseSimplifier {
+
+ public static Geometry simplify(Geometry geom, boolean preserveCollapsed, double epsilon) {
+ Coordinate[] simplified = CoordinatesSimplifier.simplifyInPlace(geom.getCoordinates(), epsilon, 2);
+
+ if (simplified.length == 1){
+ if (preserveCollapsed) return geometryFactory.createLineString(ArrayUtils.addAll(simplified, simplified));
+ else return geometryFactory.createLineString(simplified);
+ }
+ else if (simplified.length == 2 && !preserveCollapsed){
+ if (simplified[0] == simplified[1]) return geometryFactory.createLineString(simplified);
+ else return geometryFactory.createLineString(simplified);
+ }
+ else {
+ return geometryFactory.createLineString(simplified);
+ }
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/simplify/PolygonSimplifier.java b/common/src/main/java/org/apache/sedona/common/simplify/PolygonSimplifier.java
new file mode 100644
index 00000000..6638e3fb
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/simplify/PolygonSimplifier.java
@@ -0,0 +1,49 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.simplify;
+
+import org.locationtech.jts.geom.Coordinate;
+import org.locationtech.jts.geom.Geometry;
+import org.locationtech.jts.geom.LinearRing;
+import org.locationtech.jts.geom.Polygon;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.sedona.common.simplify.BaseSimplifier.geometryFactory;
+
+public class PolygonSimplifier {
+ public static Geometry simplify(Polygon geom, boolean preserveCollapsed, double epsilon) {
+ LinearRing exteriorRing = geom.getExteriorRing();
+ int minPointsExternal = preserveCollapsed ? 4 : 0;
+
+ LinearRing simplifiedExterior =
+ geometryFactory.createLinearRing(CoordinatesSimplifier.simplifyInPlace(exteriorRing.getCoordinates(), epsilon, minPointsExternal));
+
+ if (simplifiedExterior.getNumPoints() < 4) {
+ return simplifiedExterior;
+ }
+ else {
+ List<LinearRing> interiorRings = new ArrayList<>();
+ for (int i = 0; i < geom.getNumInteriorRing() ; i++) {
+ LinearRing interiorRing = geom.getInteriorRingN(i);
+ Coordinate[] simplifiedInterior = CoordinatesSimplifier.simplifyInPlace(interiorRing.getCoordinates(), epsilon, minPointsExternal);
+ if (simplifiedInterior.length >= 4) {
+ interiorRings.add(geometryFactory.createLinearRing(simplifiedInterior));
+ }
+ }
+ return geometryFactory.createPolygon(simplifiedExterior, interiorRings.toArray(new LinearRing[0]));
+ }
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/simplify/ZeroToleranceGeometrySimplifier.java b/common/src/main/java/org/apache/sedona/common/simplify/ZeroToleranceGeometrySimplifier.java
new file mode 100644
index 00000000..e945c41f
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/simplify/ZeroToleranceGeometrySimplifier.java
@@ -0,0 +1,55 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.simplify;
+
+import org.locationtech.jts.geom.Coordinate;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class ZeroToleranceGeometrySimplifier {
+ public static Coordinate[] simplifyInPlaceTolerance0(Coordinate[] geom) {
+ List<Coordinate> resultArray = new ArrayList<>();
+ int currentIndex = 1;
+ int lastIndex = geom.length - 1;
+ Coordinate keptPoint = geom[0];
+ int keptIt = 0;
+ while (currentIndex < lastIndex) {
+ Coordinate currPt = geom[currentIndex];
+ Coordinate nextPt = geom[currentIndex + 1];
+ double ba_x = nextPt.x - keptPoint.x;
+ double ba_y = nextPt.y - keptPoint.y;
+ double ab_length_sqr = ba_x * ba_x + ba_y * ba_y;
+
+ double ca_x = currPt.x - keptPoint.x;
+ double ca_y = currPt.y - keptPoint.y;
+ double dot_ac_ab = ca_x * ba_x + ca_y * ba_y;
+ double s_numerator = ca_x * ba_y - ca_y * ba_x;
+
+ boolean isEligible = dot_ac_ab < 0.0 || dot_ac_ab > ab_length_sqr || s_numerator != 0;
+
+ if (keptIt != currentIndex && isEligible) resultArray.add(keptPoint);
+ if (isEligible) keptPoint = currPt;
+ if (isEligible) keptIt = keptIt + 1;
+ currentIndex = currentIndex + 1;
+ }
+ if (keptIt != currentIndex) {
+ resultArray.add(keptPoint);
+ resultArray.add(geom[lastIndex]);
+ } else {
+ resultArray.add(geom[lastIndex]);
+ }
+ return resultArray.toArray(new Coordinate[0]);
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/subDivide/GeometrySubDivider.java b/common/src/main/java/org/apache/sedona/common/subDivide/GeometrySubDivider.java
new file mode 100644
index 00000000..d069fb92
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/subDivide/GeometrySubDivider.java
@@ -0,0 +1,172 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.subDivide;
+
+import org.apache.commons.lang3.ArrayUtils;
+import org.apache.sedona.common.simplify.GeometrySimplifier;
+import org.geotools.geometry.jts.JTS;
+import org.locationtech.jts.geom.*;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+public class GeometrySubDivider {
+ private static GeometryFactory geometryFactory = new GeometryFactory();
+
+ private static final double FP_TOLERANCE = 1e-12;
+
+ private static final int maxDepth = 50;
+
+ public static final int minMaxVertices = 5;
+
+ public static boolean equalValue(double value, double pivot) {
+ return Math.abs(value - pivot) > FP_TOLERANCE;
+ }
+
+ public static Geometry[] subDivideRecursive(
+ Geometry geom,
+ int dimension,
+ int maxVertices,
+ int depth,
+ Geometry[] geometries
+ ) {
+ if (geom == null) {
+ return geometries;
+ }
+ int numberOfVertices = geom.getNumPoints();
+ Envelope geometryBbox = geom.getEnvelope().getEnvelopeInternal();
+ double width = geometryBbox.getWidth();
+ double height = geometryBbox.getHeight();
+ Envelope geometryBboxAligned = null;
+ if (width == 0) {
+ geometryBboxAligned = new Envelope(
+ geometryBbox.getMinX() - FP_TOLERANCE,
+ geometryBbox.getMaxX() + FP_TOLERANCE,
+ geometryBbox.getMinY(),
+ geometryBbox.getMaxY()
+ );
+ } else if (height == 0) {
+ geometryBboxAligned = new Envelope(
+ geometryBbox.getMinX(),
+ geometryBbox.getMaxX(),
+ geometryBbox.getMinY() - FP_TOLERANCE,
+ geometryBbox.getMaxY() + FP_TOLERANCE
+ );
+ } else {
+ geometryBboxAligned = geometryBbox;
+ }
+ if (geom.getDimension() < dimension || numberOfVertices == 0) {
+ return geometries;
+ } else if (width == 0.0 && height == 0.0) {
+ if (geom instanceof Point) {
+ if (dimension == 0) {
+ return ArrayUtils.addAll(
+ new Geometry[] {geom},
+ geometries
+ );
+ } else {
+ return geometries;
+ }
+ } else {
+ return geometries;
+ }
+ } else if (geom instanceof GeometryCollection && !geom.getGeometryType().contains("Point")) {
+ GeometryCollection geometryCollection = (GeometryCollection) geom;
+ List<Geometry> dividedGeoms = new ArrayList<>();
+ for (int i = 0; i < geometryCollection.getNumGeometries(); i++) {
+ dividedGeoms.addAll(
+ Arrays.asList(
+ subDivideRecursive(
+ geometryCollection.getGeometryN(i),
+ dimension,
+ maxVertices,
+ depth,
+ geometries
+ )
+ )
+ );
+ }
+ return dividedGeoms.toArray(new Geometry[0]);
+ } else {
+ if (numberOfVertices <= maxVertices || depth > maxDepth) {
+ return ArrayUtils.addAll(
+ new Geometry[] {geom},
+ geometries
+ );
+ } else {
+ boolean splitOrdinate = (width <= height);
+ double center = splitOrdinate ?
+ (geometryBboxAligned.getMinY() + geometryBboxAligned.getMaxY()) / 2 :
+ (geometryBboxAligned.getMinX() + geometryBboxAligned.getMaxX()) / 2;
+ double pivot = PivotFinder.findPivot(geom, splitOrdinate, center, numberOfVertices);
+ SubBoxes subBoxes = getSubBoxes(splitOrdinate, new SubDivideExtent(geometryBboxAligned), pivot, center);
+ Geometry intersectedSimplified = getIntersectionGeometries(subBoxes.getSubBox(), geom);
+ Geometry intersectedIter2Simplified = getIntersectionGeometries(subBoxes.getSubBox2(), geom);
+
+ if (intersectedSimplified != null && !intersectedSimplified.isEmpty() && intersectedIter2Simplified != null && !intersectedIter2Simplified.isEmpty()) {
+ return ArrayUtils.addAll(
+ subDivideRecursive(intersectedSimplified, dimension, maxVertices, depth + 1, geometries),
+ subDivideRecursive(intersectedIter2Simplified, dimension, maxVertices, depth + 1, geometries)
+ );
+ } else if (intersectedSimplified != null && !intersectedSimplified.isEmpty()) {
+ return subDivideRecursive(intersectedSimplified, dimension, maxVertices, depth + 1, geometries);
+ } else if (intersectedIter2Simplified != null && !intersectedIter2Simplified.isEmpty()) {
+ return subDivideRecursive(intersectedIter2Simplified, dimension, maxVertices, depth + 1, geometries);
+ } else {
+ return geometries;
+ }
+ }
+ }
+ }
+ private static SubBoxes getSubBoxes(boolean splitOrdinate, SubDivideExtent subbox, double pivot, double center) {
+ if (splitOrdinate) {
+ if (equalValue(subbox.getyMax(), pivot) && equalValue(subbox.getyMin(), pivot))
+ return new SubBoxes(
+ subbox.copy().setyMax(pivot),
+ subbox.copy().setyMin(pivot)
+ );
+ else
+ return new SubBoxes(subbox.copy().setyMax(center), subbox.copy().setyMin(center));
+ } else {
+ if (equalValue(subbox.getxMax(), pivot) && equalValue(subbox.getxMin(), pivot))
+ return new SubBoxes(
+ subbox.copy().setxMax(pivot),
+ subbox.copy().setxMin(pivot)
+ );
+ else
+ return new SubBoxes(subbox.copy().setxMax(center), subbox.copy().setxMin(center));
+ }
+ }
+
+ private static Geometry getIntersectionGeometries(SubDivideExtent extent, Geometry geom) {
+ Envelope subBox = new Envelope(
+ extent.getxMin(),
+ extent.getxMax(),
+ extent.getyMin(),
+ extent.getyMax()
+ );
+ Geometry intersected = geom.intersection(JTS.toGeometry(subBox));
+ Geometry res = GeometrySimplifier.simplify(intersected, true, 0.0);
+ return res;
+ }
+
+ public static Geometry[] subDivide(Geometry geom, int maxVertices) {
+ if (geom == null || maxVertices < minMaxVertices) {
+ return new Geometry[0];
+ }
+ return subDivideRecursive(geom, geom.getDimension(), maxVertices, 0, new Geometry[0]);
+ }
+
+}
diff --git a/common/src/main/java/org/apache/sedona/common/subDivide/PivotFinder.java b/common/src/main/java/org/apache/sedona/common/subDivide/PivotFinder.java
new file mode 100644
index 00000000..f135ad91
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/subDivide/PivotFinder.java
@@ -0,0 +1,65 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.subDivide;
+
+import org.locationtech.jts.geom.Geometry;
+import org.locationtech.jts.geom.GeometryFactory;
+import org.locationtech.jts.geom.LinearRing;
+import org.locationtech.jts.geom.Polygon;
+
+public class PivotFinder {
+
+ private static final double DBL_MAX = Double.MAX_VALUE;
+
+ private static GeometryFactory geometryFactory = new GeometryFactory();
+
+ public static double findPivot(
+ Geometry geom,
+ boolean splitOrdinate,
+ double center,
+ int numberOfVertices
+ ) {
+ double pivot = DBL_MAX;
+ if (geom instanceof Polygon) {
+ double pivotEps = DBL_MAX;
+ double ptEps;
+ Polygon lwPoly = (Polygon) geom.copy();
+ // by default use the shell
+ LinearRing ringToTrim = lwPoly.getExteriorRing();
+ // if the shell is too small, use the largest hole
+ if (numberOfVertices >= 2 * lwPoly.getExteriorRing().getNumPoints()) {
+ // find the hole with largest area and assign to ringtotrim
+ double maxArea = geometryFactory.createPolygon(lwPoly.getExteriorRing()).getArea();
+ for (int i = 0; i < lwPoly.getNumInteriorRing(); i++) {
+ LinearRing curHole = lwPoly.getInteriorRingN(i);
+ double holeArea = geometryFactory.createPolygon(curHole).getArea();
+ if (holeArea > maxArea) {
+ maxArea = holeArea;
+ ringToTrim = curHole;
+ }
+ }
+ }
+ for (int i = 0;i < ringToTrim.getNumPoints(); i++) {
+ double pt = splitOrdinate ? ringToTrim.getPointN(i).getY() : ringToTrim.getPointN(i).getX();
+ ptEps = Math.abs(pt - center);
+ if (pivotEps > ptEps) {
+ pivot = pt;
+ pivotEps = ptEps;
+ }
+ }
+ }
+ if (pivot == DBL_MAX) return center;
+ else return pivot;
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/subDivide/SubBoxes.java b/common/src/main/java/org/apache/sedona/common/subDivide/SubBoxes.java
new file mode 100644
index 00000000..d367a81b
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/subDivide/SubBoxes.java
@@ -0,0 +1,33 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.subDivide;
+
+public class SubBoxes {
+ private SubDivideExtent subBox;
+
+ private SubDivideExtent subBox2;
+
+ public SubBoxes(SubDivideExtent subBox, SubDivideExtent subBox2) {
+ this.subBox = subBox;
+ this.subBox2 = subBox2;
+ }
+
+ public SubDivideExtent getSubBox() {
+ return subBox;
+ }
+
+ public SubDivideExtent getSubBox2() {
+ return subBox2;
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/subDivide/SubDivideExtent.java b/common/src/main/java/org/apache/sedona/common/subDivide/SubDivideExtent.java
new file mode 100644
index 00000000..f822f40d
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/subDivide/SubDivideExtent.java
@@ -0,0 +1,77 @@
+/**
+ * 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
+ * <p>
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * <p>
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.sedona.common.subDivide;
+
+import org.locationtech.jts.geom.Envelope;
+
+public class SubDivideExtent {
+ private double xMin;
+ private double xMax;
+ private double yMin;
+ private double yMax;
+
+ public SubDivideExtent(double xMin, double xMax, double yMin, double yMax) {
+ this.xMin = xMin;
+ this.xMax = xMax;
+ this.yMin = yMin;
+ this.yMax = yMax;
+ }
+
+ public SubDivideExtent(Envelope clip) {
+ this.xMin = clip.getMinX();
+ this.xMax = clip.getMaxX();
+ this.yMin = clip.getMinY();
+ this.yMax = clip.getMaxY();
+ }
+
+ public SubDivideExtent copy() {
+ return new SubDivideExtent(this.xMin, this.xMax, this.yMin, this.yMax);
+ }
+
+ public double getxMin() {
+ return xMin;
+ }
+
+ public SubDivideExtent setxMin(double xMin) {
+ this.xMin = xMin;
+ return this;
+ }
+
+ public double getxMax() {
+ return xMax;
+ }
+
+ public SubDivideExtent setxMax(double xMax) {
+ this.xMax = xMax;
+ return this;
+ }
+
+ public double getyMin() {
+ return yMin;
+ }
+
+ public SubDivideExtent setyMin(double yMin) {
+ this.yMin = yMin;
+ return this;
+ }
+
+ public double getyMax() {
+ return yMax;
+ }
+
+ public SubDivideExtent setyMax(double yMax) {
+ this.yMax = yMax;
+ return this;
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/utils/GeomUtils.java b/common/src/main/java/org/apache/sedona/common/utils/GeomUtils.java
index 98d11e60..58191e94 100644
--- a/common/src/main/java/org/apache/sedona/common/utils/GeomUtils.java
+++ b/common/src/main/java/org/apache/sedona/common/utils/GeomUtils.java
@@ -404,5 +404,11 @@ public class GeomUtils {
return leafs;
}
-
+ public static Geometry[] getSubGeometries(Geometry geom) {
+ Geometry[] geometries = new Geometry[geom.getNumGeometries()];
+ for ( int i = 0; i < geom.getNumGeometries() ; i++) {
+ geometries[i] = geom.getGeometryN(i);
+ }
+ return geometries;
+ }
}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
index 9de64be9..a75b044f 100644
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
+++ b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
@@ -19,7 +19,7 @@
package org.apache.spark.sql.sedona_sql.expressions
import org.apache.sedona.common.Functions
-import org.apache.sedona.sql.utils.GeometrySerializer
+import org.apache.sedona.common.subDivide.GeometrySubDivider
import org.apache.spark.sql.catalyst.InternalRow
import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
import org.apache.spark.sql.catalyst.expressions.{Expression, Generator, ImplicitCastInputTypes}
@@ -27,7 +27,6 @@ import org.apache.spark.sql.catalyst.util.ArrayData
import org.apache.spark.sql.sedona_sql.UDT.GeometryUDT
import org.apache.spark.sql.sedona_sql.expressions.collect.Collect
import org.apache.spark.sql.sedona_sql.expressions.implicits._
-import org.apache.spark.sql.sedona_sql.expressions.subdivide.GeometrySubDivider
import org.apache.spark.sql.types._
import org.apache.spark.unsafe.types.UTF8String
import org.locationtech.jts.algorithm.MinimumBoundingCircle
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CircleSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CircleSimplifier.scala
deleted file mode 100644
index 05e8adc8..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CircleSimplifier.scala
+++ /dev/null
@@ -1,27 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.simplify
-
-import org.apache.sedona.common.geometryObjects.Circle
-import org.locationtech.jts.geom.Geometry
-
-object CircleSimplifier {
- def simplify(geom: Circle, preserveCollapsed: Boolean, epsilon: Double): Geometry = geom
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSimplifier.scala
deleted file mode 100644
index 0b04223c..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSimplifier.scala
+++ /dev/null
@@ -1,69 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.simplify
-
-import org.apache.spark.sql.sedona_sql.expressions.subdivide.{Stack, ZeroToleranceGeometrySimplifier}
-import org.locationtech.jts.geom.Coordinate
-
-import scala.collection.mutable.ArrayBuffer
-
-object CoordinatesSimplifier {
- def simplifyInPlace(geom: Array[Coordinate], tolerance: Double, minPointsExternal: Int): Array[Coordinate] = {
- if (geom.length < 3 || geom.length <= minPointsExternal) {
- geom
- }
- else if (tolerance == 0 && minPointsExternal <= 2) {
- ZeroToleranceGeometrySimplifier.simplifyInPlaceTolerance0(geom)
- }
- else {
- val kept_points = ArrayBuffer.fill(geom.length)(false)
- kept_points(0) = true
- var itLast = geom.length - 1
- kept_points(itLast) = true
- var keptn = 2
- val iteratorStack = new Stack[Int]()
- iteratorStack.push(0)
- var itFirst = 0
-
- val toleranceSquared = tolerance * tolerance
- var itTool = if (keptn >= minPointsExternal) toleranceSquared else -1.0
-
- while (!iteratorStack.isEmpty){
- val splitInPlaceRes = CoordinatesSplitter.splitInPlace(geom, itFirst = itFirst, itLast, itTool)
- if (splitInPlaceRes.split == itFirst){
- itFirst = itLast
- itLast = iteratorStack.pull()
- }
- else {
- kept_points(splitInPlaceRes.split) = true
- keptn = keptn + 1
-
- iteratorStack.push(itLast)
- itLast = splitInPlaceRes.split
- itTool = if (keptn >= minPointsExternal) toleranceSquared else -1.0
- }
- }
-
- geom.zipWithIndex.filter{
- case (element, index) => kept_points(index)
- }.map(_._1)
- }
- }
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSplitter.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSplitter.scala
deleted file mode 100644
index f993ff32..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/CoordinatesSplitter.scala
+++ /dev/null
@@ -1,82 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.simplify
-
-import org.locationtech.jts.geom.Coordinate
-
-object CoordinatesSplitter extends SimplifyingParameters{
- def splitInPlace(geom: Array[Coordinate],
- itFirst: Int,
- itLast: Int,
- maxDistanceSquared: Double): SplitInPlace = {
- var split = itFirst
- var maxDistance = maxDistanceSquared
- if ((itFirst - itLast) < 2) SplitInPlace(geom, itFirst)
- val pointA = geom(itFirst)
- val pointB = geom(itLast)
- if (calcualteSquaredDistance(pointA, pointB) < DBL_EPSILON){
- for (itk <- Range(itFirst + 1, itLast)){
- val pk = geom(itk)
- val squaredDistance = calcualteSquaredDistance(pk, pointA)
- if (squaredDistance > maxDistance){
- split = itk
- maxDistance = squaredDistance
- }
- }
- }
-
- val ba_x = pointB.x - pointA.x
- val ba_y = pointB.y - pointA.y
- val ab_length_sqr = (ba_x * ba_x + ba_y * ba_y)
- maxDistance *= ab_length_sqr
- for (itk <- Range(itFirst + 1, itLast)){
- val c = geom(itk)
- var distance_sqr = 0.0
- val ca_x = c.x - pointA.x
- val ca_y = c.y - pointA.y
- val dot_ac_ab = (ca_x * ba_x + ca_y * ba_y)
- if (dot_ac_ab <= 0.0) {
- distance_sqr = calcualteSquaredDistance(c, pointA) * ab_length_sqr;
- }
- else if (dot_ac_ab >= ab_length_sqr) {
- distance_sqr = calcualteSquaredDistance(c, pointB) * ab_length_sqr;
- }
- else {
- val s_numerator = ca_x * ba_y - ca_y * ba_x
- distance_sqr = s_numerator * s_numerator
- }
-
- if (distance_sqr > maxDistance)
- {
- split = itk
- maxDistance = distance_sqr
- }
- }
-
- SplitInPlace(geom, split)
- }
-
- private def calcualteSquaredDistance(geomA: Coordinate, geomB: Coordinate): Double = {
- val distance = geomA.distance(geomB)
- distance * distance
- }
-
- case class SplitInPlace(geom: Array[Coordinate], split: Int)
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometryCollectionSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometryCollectionSimplifier.scala
deleted file mode 100644
index 2ab2d098..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometryCollectionSimplifier.scala
+++ /dev/null
@@ -1,52 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.simplify
-
-import org.apache.sedona.common.geometryObjects.Circle
-import org.locationtech.jts.geom.{Geometry, GeometryCollection, GeometryFactory, LineString, Point, Polygon}
-
-object GeometryCollectionSimplifier {
- private val geometryFactory = new GeometryFactory()
-
- def simplify(geom: GeometryCollection, preserveCollapsed: Boolean, epsilon: Double): Geometry = {
-
- val numberOfGeometries = geom.getNumGeometries
- val geometries = (0 until numberOfGeometries).map(
- geom.getGeometryN
- ).map {
- case circle: Circle => CircleSimplifier.simplify(circle, preserveCollapsed, epsilon)
- case string: LineString => LinestringSimplifier.simplify(string, epsilon, preserveCollapsed)
- case point: Point => point
- case polygon: Polygon => PolygonSimplifier.simplify(polygon, preserveCollapsed, epsilon)
- case collection: GeometryCollection => simplify(collection, preserveCollapsed, epsilon)
- case _ => null
- }.filter(_!=null).toArray
-
- val distinctGeometries = geometries.map(_.getGeometryType).distinct
- if (distinctGeometries.length ==1){
- distinctGeometries.head match {
- case "LineString" => geometryFactory.createMultiLineString(geometries.map(x => x.asInstanceOf[LineString]))
- case "Polygon" => geometryFactory.createMultiPolygon(geometries.map(x => x.asInstanceOf[Polygon]))
- case "Point" => geometryFactory.createMultiPoint(geometries.map(x => x.asInstanceOf[Point]))
- }
- }
- else geometryFactory.createGeometryCollection(geometries)
- }
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometrySimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometrySimplifier.scala
deleted file mode 100644
index 8ef8dc9d..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/GeometrySimplifier.scala
+++ /dev/null
@@ -1,50 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.simplify
-
-import org.apache.sedona.common.geometryObjects.Circle
-import org.locationtech.jts.geom._
-
-object GeometrySimplifier {
-
- def simplify(geom: Geometry, preserveCollapsed: Boolean, epsilon: Double): Geometry = geom match {
- case circle: Circle => simplifyCircle(circle, preserveCollapsed, epsilon)
- case collection: GeometryCollection => simplifyGeometryCollection(collection, preserveCollapsed, epsilon)
- case string: LineString => simplifyLineString(string, epsilon, preserveCollapsed)
- case point: Point => point
- case polygon: Polygon => simplifyPolygon(polygon, preserveCollapsed, epsilon)
- case geom: Geometry => geom
- }
-
- private def simplifyLineString(geom: LineString, epsilon: Double, preserveCollapsed: Boolean): Geometry =
- LinestringSimplifier.simplify(geom, epsilon, preserveCollapsed)
-
- private def simplifyPolygon(geom: Polygon, preserveCollapsed: Boolean, epsilon: Double): Geometry =
- PolygonSimplifier.simplify(geom, preserveCollapsed, epsilon)
-
- private def simplifyCircle(geom: Circle, preserveCollapsed: Boolean, epsilon: Double): Geometry =
- CircleSimplifier.simplify(geom, preserveCollapsed, epsilon)
-
- private def simplifyGeometryCollection(geom: GeometryCollection,
- preserveCollapsed: Boolean,
- epsilon: Double): Geometry =
- GeometryCollectionSimplifier.simplify(geom, preserveCollapsed, epsilon)
-
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/LinestringSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/LinestringSimplifier.scala
deleted file mode 100644
index e24b2a1b..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/LinestringSimplifier.scala
+++ /dev/null
@@ -1,42 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.simplify
-
-import org.locationtech.jts.geom.{Geometry, GeometryFactory, LineString}
-
-object LinestringSimplifier {
- private val geometryFactory = new GeometryFactory()
-
- def simplify(geom: LineString, epsilon: Double, preserveCollapsed: Boolean): Geometry = {
- val simplified = CoordinatesSimplifier.simplifyInPlace(geom.getCoordinates, epsilon, 2)
-
- if (simplified.length == 1){
- if (preserveCollapsed) geometryFactory.createLineString(simplified ++ simplified)
- else geometryFactory.createLineString(simplified)
- }
- else if (simplified.length == 2 && !preserveCollapsed){
- if (simplified(0) == simplified(1)) geometryFactory.createLineString(simplified)
- else geometryFactory.createLineString(simplified)
- }
- else {
- geometryFactory.createLineString(simplified)
- }
- }
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/PolygonSimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/PolygonSimplifier.scala
deleted file mode 100644
index e85604bc..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/PolygonSimplifier.scala
+++ /dev/null
@@ -1,50 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.simplify
-
-import org.apache.spark.sql.sedona_sql.expressions.simplify.CoordinatesSimplifier.simplifyInPlace
-import org.locationtech.jts.geom.{Geometry, GeometryFactory, Polygon}
-
-object PolygonSimplifier {
- private val geometryFactory = new GeometryFactory()
-
- def simplify(geom: Polygon, preserveCollapsed: Boolean, epsilon: Double): Geometry = {
- val exteriorRing = geom.getExteriorRing
- val minPointsExternal = if (preserveCollapsed) 4 else 0
-
- val simplifiedExterior =
- geometryFactory.createLinearRing(simplifyInPlace(exteriorRing.getCoordinates, epsilon, minPointsExternal))
-
- if (simplifiedExterior.getNumPoints < 4) {
- simplifiedExterior
- }
- else {
- val exteriorRings = (0 until geom.getNumInteriorRing).map(index => geom.getInteriorRingN(index))
- .map(geom => simplifyInPlace(geom.getCoordinates, epsilon, minPointsExternal))
- .filter(_.length >= 4)
- .map(geometryFactory.createLinearRing)
- .filter(_.getNumPoints >= 4)
-
-
- geometryFactory.createPolygon(simplifiedExterior, exteriorRings.toArray)
-
- }
- }
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/SimplifyingParameters.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/SimplifyingParameters.scala
deleted file mode 100644
index 642a3379..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/simplify/SimplifyingParameters.scala
+++ /dev/null
@@ -1,24 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.simplify
-
-trait SimplifyingParameters {
- val DBL_EPSILON = 2.2204460492503131e-16
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDivider.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDivider.scala
deleted file mode 100644
index 5a995b55..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDivider.scala
+++ /dev/null
@@ -1,148 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.subdivide
-
-import org.apache.spark.sql.sedona_sql.expressions.simplify.GeometrySimplifier
-import org.geotools.geometry.jts.JTS
-import org.locationtech.jts.geom.{Envelope, Geometry, GeometryCollection, GeometryFactory, Point}
-import org.apache.spark.sql.sedona_sql.expressions.implicits.GeometryEnhancer
-
-object GeometrySubDivider {
-
- val geometryFactory = new GeometryFactory()
-
- import GeometrySubDividerConfiguration._
-
- def equalValue(value: Double, pivot: Double): Boolean = {
- math.abs(value - pivot) > FP_TOLERANCE
- }
-
- def subDivideRecursive(
- geom: Geometry,
- dimension: Int,
- maxVertices: Int,
- depth: Int,
- geometries: Seq[Geometry]
- ): Seq[Geometry] = {
-
- val numberOfVertices = geom.getNumPoints
- val geometryBbox = geom.getEnvelope.getEnvelopeInternal
- val width = geometryBbox.getWidth
- val height = geometryBbox.getHeight
- val geometryBboxAligned = if (width == 0) new Envelope(
- geometryBbox.getMinX - FP_TOLERANCE,
- geometryBbox.getMaxX + FP_TOLERANCE,
- geometryBbox.getMinY,
- geometryBbox.getMaxY
- ) else if (height == 0) new Envelope(
- geometryBbox.getMinX,
- geometryBbox.getMaxX,
- geometryBbox.getMinY - FP_TOLERANCE,
- geometryBbox.getMaxY + FP_TOLERANCE
- ) else geometryBbox
- if (
- geom == null || geom.getDimension < dimension || numberOfVertices == 0 || geometryBboxAligned == null
- ) geometries
- else if (width == 0.0 && height == 0.0) geom match {
- case point: Point => if (dimension == 0) geom +: geometries else geometries
- case polygon: Geometry => geometries
- }
- else if (geom.isInstanceOf[GeometryCollection] && !geom.getGeometryType.contains("Point")) {
- val collection = geom.asInstanceOf[GeometryCollection]
- val numberOfGeometries = collection.getNumGeometries
- (0 until numberOfGeometries).map(
- i => subDivideRecursive(collection.getGeometryN(i), dimension, maxVertices, depth, geometries)
- ).reduce(_ ++ _)
- }
- else {
- if (numberOfVertices <= maxVertices || depth > maxDepth) {
- geom +: geometries
- }
- else {
- val split_ordinate = if (width > height) 0 else 1
-
- val center = if (split_ordinate == 0) (geometryBboxAligned.getMinX + geometryBboxAligned.getMaxX) / 2
- else (geometryBboxAligned.getMinY + geometryBboxAligned.getMaxY) / 2
-
- val pivot = PivotFinder.findPivot(geom, split_ordinate, center, numberOfVertices)
-
- val subBoxes = getSubBoxes(split_ordinate, SubdivideExtent.fromClip(geometryBboxAligned), pivot, center)
-
- val intersectedSimplified = getIntersectionGeometries(subBoxes.subBox, geom)
- val intersectedIter2Simplfied = getIntersectionGeometries(subBoxes.subBox2, geom)
-
- if (intersectedSimplified.isNonEmpty && intersectedIter2Simplfied.isNonEmpty) {
- subDivideRecursive(intersectedSimplified, dimension, maxVertices, depth + 1, geometries) ++
- subDivideRecursive(intersectedIter2Simplfied, dimension, maxVertices, depth + 1, geometries)
- } else if (intersectedSimplified.isNonEmpty) {
- subDivideRecursive(intersectedSimplified, dimension, maxVertices, depth + 1, geometries)
- } else if (intersectedIter2Simplfied.isNonEmpty) {
- subDivideRecursive(intersectedIter2Simplfied, dimension, maxVertices, depth + 1, geometries)
- }
- else {
- geometries
- }
-
- }
- }
- }
-
- private def getSubBoxes(split_ordinate: Int, subbox: SubdivideExtent, pivot: Double, center: Double): SubBoxes = {
- if (split_ordinate == 0) {
- if (equalValue(subbox.xmax, pivot) && equalValue(subbox.xmin, pivot))
- SubBoxes(subbox.copy(xmax = pivot), subbox.copy(xmin = pivot))
- else
- SubBoxes(subbox.copy(xmax = center), subbox.copy(xmin = center))
- }
- else {
- if (equalValue(subbox.ymax, pivot) && equalValue(subbox.ymin, pivot))
- SubBoxes(subbox.copy(ymax = pivot), subbox.copy(ymin = pivot))
- else
- SubBoxes(subbox.copy(ymax = center), subbox.copy(ymin = center))
- }
- }
-
- private def getIntersectionGeometries(extent: SubdivideExtent, geom: Geometry): Geometry = {
- val subBox = new Envelope(extent.xmin, extent.xmax, extent.ymin, extent.ymax)
- val intersected = geom.intersection(JTS.toGeometry(subBox))
- GeometrySimplifier.simplify(intersected, true, 0.0)
- }
-
- def subDividePrecise(geom: Geometry, maxVertices: Int): Seq[Geometry] = {
- if (geom == null) {
- Seq()
- }
- else {
- if (maxVertices < minMaxVertices) {
- Seq()
- }
- else {
- subDivideRecursive(geom, geom.getDimension, maxVertices, startDepth, Seq())
- }
- }
-
- }
-
- def subDivide(geom: Geometry, maxVertices: Int): Seq[Geometry] = {
- subDividePrecise(geom, maxVertices)
- }
-
-}
-
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDividerConfiguration.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDividerConfiguration.scala
deleted file mode 100644
index 90e9666d..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/GeometrySubDividerConfiguration.scala
+++ /dev/null
@@ -1,28 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.subdivide
-
-object GeometrySubDividerConfiguration {
- val maxDepth: Int = 50
- val minMaxVertices = 5
- val startDepth = 0
- val DBL_MAX: Double = Double.MaxValue
- val FP_TOLERANCE: Double = 1e-12
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/PivotFinder.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/PivotFinder.scala
deleted file mode 100644
index 2489d942..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/PivotFinder.scala
+++ /dev/null
@@ -1,50 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.subdivide
-
-import org.apache.spark.sql.sedona_sql.expressions.subdivide.GeometrySubDivider.geometryFactory
-import org.apache.spark.sql.sedona_sql.expressions.subdivide.GeometrySubDividerConfiguration.DBL_MAX
-import org.locationtech.jts.geom.{Geometry, Polygon}
-
-object PivotFinder {
- def findPivot(geom: Geometry, split_ordinate: Int, center: Double, numberOfVertices: Int): Double = {
- var pivot = DBL_MAX;
- if (geom.isInstanceOf[Polygon]) {
- var pivot_eps = DBL_MAX
- var ptEps = DBL_MAX
- val lwPoly = geom.copy().asInstanceOf[Polygon]
- val ringToTrim = if (numberOfVertices >= 2 * lwPoly.getExteriorRing.getNumPoints)
- (geometryFactory.createPolygon(lwPoly.getExteriorRing).getArea +: (0 until lwPoly.getNumInteriorRing)
- .map(lwPoly.getInteriorRingN)
- .map(x => geometryFactory.createPolygon(x).getArea)).zipWithIndex.maxBy(_._1)._2 else 0
-
- val pointArray = if (ringToTrim == 0) lwPoly.getExteriorRing else lwPoly.getInteriorRingN(ringToTrim - 1)
- for (i <- 0 until pointArray.getNumPoints) {
- val pt = if (split_ordinate == 0) pointArray.getPointN(i).getX else pointArray.getPointN(i).getY
- ptEps = math.abs(pt - center)
- if (pivot_eps > ptEps) {
- pivot = pt
- pivot_eps = ptEps
- }
- }
- }
- if (pivot == DBL_MAX) center else pivot
- }
-}
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/Stack.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/Stack.scala
deleted file mode 100644
index 711fba20..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/Stack.scala
+++ /dev/null
@@ -1,40 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.subdivide
-
-import scala.collection.mutable.ArrayBuffer
-
-class Stack[T]{
-
- private val elements: ArrayBuffer[T] = ArrayBuffer.empty[T]
-
- def push(element: T): T = {
- elements += element
- element
- }
-
- def pull(): T = {
- val last = elements.last
- elements.remove(elements.length-1)
- last
- }
-
- def isEmpty: Boolean = elements.isEmpty
-}
\ No newline at end of file
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/SubdivideExtent.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/SubdivideExtent.scala
deleted file mode 100644
index e50cf00f..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/SubdivideExtent.scala
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.subdivide
-
-import org.locationtech.jts.geom.Envelope
-
-case class SubdivideExtent(xmin: Double, xmax: Double, ymin: Double, ymax: Double)
-
-object SubdivideExtent {
- def fromClip(clip: Envelope): SubdivideExtent = SubdivideExtent(
- xmin = clip.getMinX,
- xmax = clip.getMaxX,
- ymin = clip.getMinY,
- ymax = clip.getMaxY
- )
-}
-
-case class SubBoxes(subBox: SubdivideExtent, subBox2: SubdivideExtent)
\ No newline at end of file
diff --git a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/ZeroToleranceGeometrySimplifier.scala b/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/ZeroToleranceGeometrySimplifier.scala
deleted file mode 100644
index 85305df7..00000000
--- a/sql/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/subdivide/ZeroToleranceGeometrySimplifier.scala
+++ /dev/null
@@ -1,65 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-
-package org.apache.spark.sql.sedona_sql.expressions.subdivide
-
-import org.locationtech.jts.geom.Coordinate
-
-import scala.annotation.tailrec
-
-object ZeroToleranceGeometrySimplifier {
-
- def simplifyInPlaceTolerance0(geom: Array[Coordinate]): Array[Coordinate] =
- simplifyInPlaceHelper(geom, Seq(), 1, geom.length - 1, geom(0), 0).toArray
-
- @tailrec
- private def simplifyInPlaceHelper(geom: Array[Coordinate],
- resultArray: Seq[Coordinate],
- currentIndex: Int,
- lastIndex: Int,
- keptPoint: Coordinate,
- keptIt: Int
- ): Seq[Coordinate] = {
- if (currentIndex == lastIndex) if (keptIt != lastIndex) resultArray :+ keptPoint :+ geom(lastIndex)
- else resultArray :+ geom(lastIndex)
- else {
- val currPt = geom(currentIndex)
- val nextPt = geom(currentIndex + 1)
- val ba_x = nextPt.x - keptPoint.x
- val ba_y = nextPt.y - keptPoint.y
- val ab_length_sqr = ba_x * ba_x + ba_y * ba_y
-
- val ca_x = currPt.x - keptPoint.x
- val ca_y = currPt.y - keptPoint.y
- val dot_ac_ab = ca_x * ba_x + ca_y * ba_y;
- val s_numerator = ca_x * ba_y - ca_y * ba_x
-
- val isEligible = dot_ac_ab < 0.0 || dot_ac_ab > ab_length_sqr || s_numerator != 0
-
- simplifyInPlaceHelper(
- geom = geom,
- resultArray = if (keptIt != currentIndex && isEligible) resultArray :+ keptPoint else resultArray,
- currentIndex + 1,
- lastIndex = lastIndex,
- keptPoint = if (isEligible) currPt else keptPoint,
- keptIt = if (isEligible) keptIt + 1 else keptIt
- )
- }
- }
-}
diff --git a/sql/src/test/scala/org/apache/sedona/sql/functions/TestGeometrySimplify.scala b/sql/src/test/scala/org/apache/sedona/sql/functions/TestGeometrySimplify.scala
index 9b005529..1cb6c265 100644
--- a/sql/src/test/scala/org/apache/sedona/sql/functions/TestGeometrySimplify.scala
+++ b/sql/src/test/scala/org/apache/sedona/sql/functions/TestGeometrySimplify.scala
@@ -18,7 +18,7 @@
*/
package org.apache.sedona.sql.functions
-import org.apache.spark.sql.sedona_sql.expressions.simplify.GeometrySimplifier
+import org.apache.sedona.common.simplify.GeometrySimplifier
import org.locationtech.jts.geom.Geometry
import org.scalatest.funsuite.AnyFunSuite
import org.scalatest.matchers.should.Matchers
diff --git a/sql/src/test/scala/org/apache/sedona/sql/functions/TestStSubDivide.scala b/sql/src/test/scala/org/apache/sedona/sql/functions/TestStSubDivide.scala
index abf3ea97..10d4dd5c 100644
--- a/sql/src/test/scala/org/apache/sedona/sql/functions/TestStSubDivide.scala
+++ b/sql/src/test/scala/org/apache/sedona/sql/functions/TestStSubDivide.scala
@@ -19,7 +19,7 @@
package org.apache.sedona.sql.functions
-import org.apache.spark.sql.sedona_sql.expressions.subdivide.{GeometrySubDivider, GeometrySubDividerConfiguration}
+import org.apache.sedona.common.subDivide.GeometrySubDivider
import org.locationtech.jts.geom.Geometry
import org.scalatest.funsuite.AnyFunSuite
import org.scalatest.matchers.should.Matchers
@@ -79,9 +79,9 @@ class TestStSubDivide extends AnyFunSuite with Matchers with TableDrivenProperty
val geometriesWithNumberOfVerticesLowerThanThreshold: TableFor3[String, String, Int] = Table(
("geometryType", "inputWkt", "numberOfVertices"),
- ("point", "POINT(4 43)", GeometrySubDividerConfiguration.minMaxVertices - 1),
- ("polygon", "POLYGON((0 0, 0 1, 1 1, 1 0, 0 0))", GeometrySubDividerConfiguration.minMaxVertices - 1),
- ("linestring", "LINESTRING(1 1, 2 2, 3 2)", GeometrySubDividerConfiguration.minMaxVertices - 1)
+ ("point", "POINT(4 43)", GeometrySubDivider.minMaxVertices - 1),
+ ("polygon", "POLYGON((0 0, 0 1, 1 1, 1 0, 0 0))", GeometrySubDivider.minMaxVertices - 1),
+ ("linestring", "LINESTRING(1 1, 2 2, 3 2)", GeometrySubDivider.minMaxVertices - 1)
)
val testPolygons: TableFor4[String, String, Int, Seq[String]] = Table(