Kontinuation commented on code in PR #2051: URL: https://github.com/apache/sedona/pull/2051#discussion_r2191709765
########## common/src/main/java/org/apache/sedona/common/S2Geography/Accessors.java: ########## @@ -0,0 +1,294 @@ +/* + * 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.sedona.common.S2Geography; + +import com.google.common.geometry.*; + +public class Accessors { + + public Accessors() {} + + public boolean S2_isEmpty(S2Geography s2Geography) { + for (int i = 0; i < s2Geography.numShapes(); i++) { + S2Shape shape = s2Geography.shape(i); + if (!shape.isEmpty()) return false; + } + return true; + } + + public boolean S2_isCollection(PolygonGeography polygonGeography) { + int numOuterLoops = 0; + for (int i = 0; i < polygonGeography.polygon.numLoops(); i++) { + S2Loop loop = polygonGeography.polygon.loop(i); + if (loop.depth() == 0 && ++numOuterLoops > 10) { + return true; + } + } + return false; + } + + /** + * Returns true if `geog` is a “collection” (i.e. multi‐point, multi‐linestring, or multi‐polygon) + * rather than a single simple feature. + */ + public boolean s2IsCollection(S2Geography geog) { + int dim = S2_dimension(geog); + if (dim == -1) { + return false; + } + + switch (dim) { + case 0: + // point‐collection if more than one point + return S2_numPoints(geog) > 1; + + case 1: + // multi‐linestring: more than one chain across all shapes + int chainCount = 0; + for (int i = 0, n = geog.numShapes(); i < n; ++i) { + S2Shape shape = geog.shape(i); + chainCount += shape.numChains(); + if (chainCount > 1) { + return true; + } + } + return false; + + default: + { + // polygons (or mixed): delegate to the polygon routine + if (geog instanceof PolygonGeography) { + return S2_isCollection((PolygonGeography) geog); + } + // not yet a PolygonGeography → build one, then test + // TODO:build + // PolygonGeography built = S2Builder.buildPolygon(geog); + // return isCollection(built); + } + } + return false; + } + + public int S2_dimension(S2Geography s2Geography) { + int dimension = s2Geography.dimension(); + if (dimension != -1) return dimension; + + for (int i = 0; i < s2Geography.numShapes(); i++) { + S2Shape shape = s2Geography.shape(i); + if (shape.dimension() > dimension) dimension = shape.dimension(); + } + return dimension; + } + + public int S2_numPoints(S2Geography s2Geography) { + int numPoints = 0; + for (int i = 0; i < s2Geography.numShapes(); i++) { + S2Shape shape = s2Geography.shape(i); + switch (shape.dimension()) { + case 0: + case 2: + numPoints += shape.numEdges(); + break; + case 1: + numPoints += shape.numEdges() + shape.numChains(); + break; + } + } + return numPoints; + } + + double S2_area(S2Geography geog) { + if (S2_dimension(geog) != 2) return 0; + + switch (geog.kind) { + case POLYGON: + if (geog != null) return S2_area((PolygonGeography) geog); + case GEOGRAPHY_COLLECTION: + if (geog != null) return S2_area((GeographyCollection) geog); + } + // TODO: build + return 0; Review Comment: I cannot figure out why we need to build a polygon geography to compute its area here: https://github.com/paleolimbot/s2geography/blob/main/src/s2geography/accessors.cc#L127-L128 @paleolimbot ########## common/src/main/java/org/apache/sedona/common/S2Geography/Accessors.java: ########## @@ -0,0 +1,294 @@ +/* + * 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.sedona.common.S2Geography; + +import com.google.common.geometry.*; + +public class Accessors { + + public Accessors() {} + + public boolean S2_isEmpty(S2Geography s2Geography) { + for (int i = 0; i < s2Geography.numShapes(); i++) { + S2Shape shape = s2Geography.shape(i); + if (!shape.isEmpty()) return false; + } + return true; + } + + public boolean S2_isCollection(PolygonGeography polygonGeography) { + int numOuterLoops = 0; + for (int i = 0; i < polygonGeography.polygon.numLoops(); i++) { + S2Loop loop = polygonGeography.polygon.loop(i); + if (loop.depth() == 0 && ++numOuterLoops > 10) { Review Comment: I guess the correct code should be: ```suggestion if (loop.depth() == 0 && ++numOuterLoops > 1) { ``` ########## common/src/main/java/org/apache/sedona/common/S2Geography/Accessors.java: ########## @@ -0,0 +1,294 @@ +/* + * 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.sedona.common.S2Geography; + +import com.google.common.geometry.*; + +public class Accessors { + + public Accessors() {} + + public boolean S2_isEmpty(S2Geography s2Geography) { + for (int i = 0; i < s2Geography.numShapes(); i++) { + S2Shape shape = s2Geography.shape(i); + if (!shape.isEmpty()) return false; + } + return true; + } + + public boolean S2_isCollection(PolygonGeography polygonGeography) { + int numOuterLoops = 0; + for (int i = 0; i < polygonGeography.polygon.numLoops(); i++) { + S2Loop loop = polygonGeography.polygon.loop(i); + if (loop.depth() == 0 && ++numOuterLoops > 10) { + return true; + } + } + return false; + } + + /** + * Returns true if `geog` is a “collection” (i.e. multi‐point, multi‐linestring, or multi‐polygon) + * rather than a single simple feature. + */ + public boolean s2IsCollection(S2Geography geog) { Review Comment: Why don't we name it as `S2_isCollection` as well? Function overloading with sub type as parameter is allowed in Java. ########## common/src/main/java/org/apache/sedona/common/S2Geography/Distance.java: ########## @@ -0,0 +1,192 @@ +/* + * 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.sedona.common.S2Geography; + +import static com.google.common.geometry.S2EdgeUtil.robustCrossing; +import static com.google.common.geometry.S2EdgeUtil.updateMinDistance; + +import com.google.common.geometry.*; +import java.util.Optional; +import org.apache.commons.lang3.tuple.Pair; + +public class Distance { + + public double S2_distance(ShapeIndexGeography geo1, ShapeIndexGeography geo2) { + S2ShapeIndex index1 = geo1.shapeIndex; + S2ShapeIndex index2 = geo2.shapeIndex; + + S2ClosestEdgeQuery query = S2ClosestEdgeQuery.builder().build(index1); + S2ClosestEdgeQuery.ShapeIndexTarget queryTarget = + S2ClosestEdgeQuery.createShapeIndexTarget(index2); + + Optional<S2BestEdgesQueryBase.Result> resultVisitor = query.findClosestEdge(queryTarget); + // If there are no edges at all, return infinity + if (!resultVisitor.isPresent()) { + return Double.POSITIVE_INFINITY; + } + + // Extract the Result: it contains two points (one on each shape) + // and the chord‐angle distance between them. + S2ClosestEdgeQuery.Result result = resultVisitor.get(); + S1ChordAngle chordAngle = + (S1ChordAngle) result.distance(); // a specialized spherical‐distance type + return chordAngle.toAngle().radians(); + } + + public double S2_maxDistance(ShapeIndexGeography geo1, ShapeIndexGeography geo2) { + S2ShapeIndex index1 = geo1.shapeIndex; + S2ShapeIndex index2 = geo2.shapeIndex; + + S2FurthestEdgeQuery query = S2FurthestEdgeQuery.builder().build(index1); + S2FurthestEdgeQuery.ShapeIndexTarget queryTarget = + S2FurthestEdgeQuery.createShapeIndexTarget(index2); + + Optional<S2FurthestEdgeQuery.Result> resultVisitor = query.findFurthestEdge(queryTarget); + // If there are no edges at all, return infinity + if (!resultVisitor.isPresent()) { + return Double.POSITIVE_INFINITY; + } + + // Extract the Result: it contains two points (one on each shape) + // and the chord‐angle distance between them. + S2FurthestEdgeQuery.Result result = resultVisitor.get(); + S1ChordAngle chordAngle = (S1ChordAngle) result.distance(); + return chordAngle.toAngle().radians(); + } + + public S2Point S2_closestPoint(ShapeIndexGeography geo1, ShapeIndexGeography geo2) + throws Exception { + return S2_minimumClearanceLineBetween(geo1, geo2).getLeft(); + } + + // returns the shortest possible line between x and y + // This method finds the two points—one on each geometry—that lie at the minimal great-circle + // (angular) distance, and returns them as a pair. + public Pair<S2Point, S2Point> S2_minimumClearanceLineBetween( + ShapeIndexGeography geo1, ShapeIndexGeography geo2) throws Exception { + S2ShapeIndex index1 = geo1.shapeIndex; + S2ShapeIndex index2 = geo2.shapeIndex; + + S2ClosestEdgeQuery query = + S2ClosestEdgeQuery.builder().setIncludeInteriors(false).build(index1); + S2ClosestEdgeQuery.ShapeIndexTarget queryTarget = + S2ClosestEdgeQuery.createShapeIndexTarget(index2); + + Optional<S2BestEdgesQueryBase.Result> resultVisitor = query.findClosestEdge(queryTarget); + + if (resultVisitor.get().edgeId() == -1) { Review Comment: Should test if `resultVisitor` is present since `resultVisitor` is an Optional. ########## common/src/main/java/org/apache/sedona/common/S2Geography/Predicates.java: ########## @@ -0,0 +1,87 @@ +/* + * 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.sedona.common.S2Geography; + +import com.google.common.geometry.*; +import com.google.common.geometry.Projection; +import java.util.ArrayList; +import java.util.List; +import org.apache.sedona.common.S2Geography.Accessors.*; + +public class Predicates { + + public boolean S2_intersects( + ShapeIndexGeography geo1, ShapeIndexGeography geo2, S2BooleanOperation.Options options) { + return S2BooleanOperation.intersects(geo1.shapeIndex, geo2.shapeIndex, options); + } + + public boolean S2_equals( + ShapeIndexGeography geo1, ShapeIndexGeography geo2, S2BooleanOperation.Options options) { + return S2BooleanOperation.equals(geo1.shapeIndex, geo2.shapeIndex, options); + } + + public boolean S2_contains( + ShapeIndexGeography geo1, ShapeIndexGeography geo2, S2BooleanOperation.Options options) { + if (new Accessors().S2_isEmpty(geo2)) return false; + return S2BooleanOperation.contains(geo1.shapeIndex, geo2.shapeIndex, options); + } + + public boolean S2_intersectsBox( + ShapeIndexGeography geo1, + S2LatLngRect rect, + S2BooleanOperation.Options options, + double tolerance) { + // 1) Set up a PlateCarreeProjection and tessellator + Projection.PlateCarreeProjection projection = new Projection.PlateCarreeProjection(180); + S2EdgeTessellator tessellator = new S2EdgeTessellator(projection, S1Angle.degrees(tolerance)); + + // 2) Compute the four corners in R2Vector + R2Vector lb = new R2Vector(rect.lngLo().degrees(), rect.latLo().degrees()); + R2Vector rb = new R2Vector(rect.lngHi().degrees(), rect.latLo().degrees()); + R2Vector rt = new R2Vector(rect.lngHi().degrees(), rect.latHi().degrees()); + R2Vector lt = new R2Vector(rect.lngLo().degrees(), rect.latHi().degrees()); + + // 3) Walk the four edges (bottom, right, top, left) + List<S2Point> vertices = new ArrayList<>(); + tessellator.appendUnprojected(lb, rb, vertices); + tessellator.appendUnprojected(rb, rt, vertices); + tessellator.appendUnprojected(rt, lt, vertices); + tessellator.appendUnprojected(lt, lb, vertices); + + // c++ using S2LaxLoopShape which is missing in Java + // S2LaxLoopShape represents a closed loop of edges surrounding an interior + // region. It is similar to S2Loop::Shape except that this class allows + // duplicate vertices and edges. Loops may have any number of vertices, + // including 0, 1, or 2. (A one-vertex loop defines a degenerate edge + // consisting of a single point.) + S2Loop loop = new S2Loop(vertices); + S2Polygon polygon = new S2Polygon(loop); + PolygonGeography polygonGeography = new PolygonGeography(polygon); + // c++ is using MutableS2ShapeIndex which is missing in Java + // MutableS2ShapeIndex is a class for in-memory indexing of polygonal geometry. + // The objects in the index are known as "shapes", and may consist of points, + // polylines, and/or polygons, possibly overlapping. The index makes it very + // fast to answer queries such as finding nearby shapes, measuring distances, + // testing for intersection and containment, etc. It is one of several + // implementations of the S2ShapeIndex interface (see EncodedS2ShapeIndex). + GeographyIndex geographyIndex = new GeographyIndex(); + geographyIndex.add(polygonGeography, 0); Review Comment: `S2ShapeIndex` is already mutable. Does this simplified version work? ```java S2ShapeIndex index = new S2ShapeIndex(); index.add(loop); ``` ########## common/src/main/java/org/apache/sedona/common/S2Geography/Distance.java: ########## @@ -0,0 +1,192 @@ +/* + * 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.sedona.common.S2Geography; + +import static com.google.common.geometry.S2EdgeUtil.robustCrossing; +import static com.google.common.geometry.S2EdgeUtil.updateMinDistance; + +import com.google.common.geometry.*; +import java.util.Optional; +import org.apache.commons.lang3.tuple.Pair; + +public class Distance { + + public double S2_distance(ShapeIndexGeography geo1, ShapeIndexGeography geo2) { + S2ShapeIndex index1 = geo1.shapeIndex; + S2ShapeIndex index2 = geo2.shapeIndex; + + S2ClosestEdgeQuery query = S2ClosestEdgeQuery.builder().build(index1); + S2ClosestEdgeQuery.ShapeIndexTarget queryTarget = + S2ClosestEdgeQuery.createShapeIndexTarget(index2); + + Optional<S2BestEdgesQueryBase.Result> resultVisitor = query.findClosestEdge(queryTarget); + // If there are no edges at all, return infinity + if (!resultVisitor.isPresent()) { + return Double.POSITIVE_INFINITY; + } + + // Extract the Result: it contains two points (one on each shape) + // and the chord‐angle distance between them. + S2ClosestEdgeQuery.Result result = resultVisitor.get(); + S1ChordAngle chordAngle = + (S1ChordAngle) result.distance(); // a specialized spherical‐distance type + return chordAngle.toAngle().radians(); + } + + public double S2_maxDistance(ShapeIndexGeography geo1, ShapeIndexGeography geo2) { + S2ShapeIndex index1 = geo1.shapeIndex; + S2ShapeIndex index2 = geo2.shapeIndex; + + S2FurthestEdgeQuery query = S2FurthestEdgeQuery.builder().build(index1); + S2FurthestEdgeQuery.ShapeIndexTarget queryTarget = + S2FurthestEdgeQuery.createShapeIndexTarget(index2); + + Optional<S2FurthestEdgeQuery.Result> resultVisitor = query.findFurthestEdge(queryTarget); + // If there are no edges at all, return infinity + if (!resultVisitor.isPresent()) { + return Double.POSITIVE_INFINITY; + } + + // Extract the Result: it contains two points (one on each shape) + // and the chord‐angle distance between them. + S2FurthestEdgeQuery.Result result = resultVisitor.get(); + S1ChordAngle chordAngle = (S1ChordAngle) result.distance(); + return chordAngle.toAngle().radians(); + } + + public S2Point S2_closestPoint(ShapeIndexGeography geo1, ShapeIndexGeography geo2) + throws Exception { + return S2_minimumClearanceLineBetween(geo1, geo2).getLeft(); + } + + // returns the shortest possible line between x and y + // This method finds the two points—one on each geometry—that lie at the minimal great-circle + // (angular) distance, and returns them as a pair. + public Pair<S2Point, S2Point> S2_minimumClearanceLineBetween( + ShapeIndexGeography geo1, ShapeIndexGeography geo2) throws Exception { + S2ShapeIndex index1 = geo1.shapeIndex; + S2ShapeIndex index2 = geo2.shapeIndex; + + S2ClosestEdgeQuery query = + S2ClosestEdgeQuery.builder().setIncludeInteriors(false).build(index1); + S2ClosestEdgeQuery.ShapeIndexTarget queryTarget = + S2ClosestEdgeQuery.createShapeIndexTarget(index2); + + Optional<S2BestEdgesQueryBase.Result> resultVisitor = query.findClosestEdge(queryTarget); + + if (resultVisitor.get().edgeId() == -1) { + return Pair.of(new S2Point(0, 0, 0), new S2Point(0, 0, 0)); + } + + // Get the edge from index1 (edge1) that is closest to index2. + S2BestEdgesQueryBase.Result edge = resultVisitor.get(); + int shapeId = edge.shapeId(); + int edgeNum = edge.edgeId(); + S2Shape.MutableEdge mutableEdge = new S2Shape.MutableEdge(); + index1.getShapes().get(shapeId).getEdge(edgeNum, mutableEdge); + S2Edge s2edge = (S2Edge) new S2Edge(mutableEdge.getStart(), mutableEdge.getEnd()); + + // Now find the edge from index2 (edge2) that is closest to edge1. + S2ClosestEdgeQuery queryReverse = + S2ClosestEdgeQuery.builder().setIncludeInteriors(false).build(index2); + S2ClosestEdgeQuery.EdgeTarget queryTargetReverse = + new S2ClosestEdgeQuery.EdgeTarget<>(s2edge.getStart(), s2edge.getEnd()); + Optional<S2BestEdgesQueryBase.Result> resultVisitorReverse = + queryReverse.findClosestEdge(queryTargetReverse); + + if (resultVisitorReverse.get().isInterior()) { + throw new Exception("S2ClosestEdgeQuery result is interior!"); + } + S2ClosestEdgeQuery.Result edge2 = resultVisitorReverse.get(); + int shapeId2 = edge2.shapeId(); + int edgeNum2 = edge2.edgeId(); + S2Shape.MutableEdge mutableEdge2 = new S2Shape.MutableEdge(); + index2.getShapes().get(shapeId2).getEdge(edgeNum2, mutableEdge2); + S2Edge s2edge2 = new S2Edge(mutableEdge2.getStart(), mutableEdge2.getEnd()); + S2Edge s2edgeReverse = new S2Edge(s2edge2.getStart(), s2edge2.getEnd()); + + return getEdgePairClosestPoints( + s2edge.getStart(), s2edge.getEnd(), s2edgeReverse.getStart(), s2edgeReverse.getEnd()); + } + + /** + * The Java equivalent of: + * + * <p>std::pair<S2Point,S2Point> GetEdgePairClosestPoints(a0,a1,b0,b1) # returns the shortest + * possible line between x and y + */ + public static Pair<S2Point, S2Point> getEdgePairClosestPoints( + S2Point a0, S2Point a1, S2Point b0, S2Point b1) { Review Comment: Why not directly use `S2EdgeUtil.getEdgePairClosestPoints`? -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
