szehon-ho commented on code in PR #17788: URL: https://github.com/apache/iceberg/pull/17788#discussion_r3858461301
########## core/src/main/java/org/apache/iceberg/SphericalGeographyBoundsBuilder.java: ########## @@ -0,0 +1,359 @@ +/* + * 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.iceberg; + +import java.util.Comparator; +import java.util.List; +import org.apache.iceberg.geospatial.BoundingBox; +import org.apache.iceberg.geospatial.GeospatialBound; +import org.apache.iceberg.relocated.com.google.common.collect.Lists; + +/** Builds an XY bounding box from geography points and minor great-circle edges on a sphere. */ +class SphericalGeographyBoundsBuilder { + private static final double MIN_LONGITUDE = -180.0; + private static final double MAX_LONGITUDE = 180.0; + private static final double MIN_LATITUDE = -90.0; + private static final double MAX_LATITUDE = 90.0; + private static final double LONGITUDE_SPAN = MAX_LONGITUDE - MIN_LONGITUDE; + + // For unit endpoints, |point1 x point2| = sin(central angle). A tiny normal means + // the endpoints are nearly coincident or antipodal, so normalizing the great-circle + // plane is numerically unstable. + private static final double MIN_NORMAL_LENGTH = 1e-12; + + // A point lies on the oriented minor arc when both exact side tests are nonnegative: + // + // point1 -------- point -------- point2 + // (point1 x point) . normal >= 0 + // (point x point2) . normal >= 0 + // + // Permit a small negative result introduced by floating-point rounding. + private static final double ARC_CONTAINMENT_TOLERANCE = 1e-12; + + // A minor great-circle arc can extend beyond both endpoint latitudes: + // + // conservative north bound + // --------------------------------------------- + // ^ margin + // * arc vertex + // .-' '-. + // endpoint * * endpoint + // + // The factor adds a relative 1e-7 margin away from the equator to avoid an + // under-covering bound; the result is then clamped to [-90, 90]. + private static final double LATITUDE_SCALING_FACTOR = 1.0000001; + + private final List<LongitudeInterval> longitudeIntervals = Lists.newArrayList(); + private double minLatitude = Double.POSITIVE_INFINITY; + private double maxLatitude = Double.NEGATIVE_INFINITY; + private State state = State.EMPTY; + + void addPoint(double longitude, double latitude) { + if (!prepareToAccumulate(coordinatesAreValid(longitude, latitude))) { + return; + } + + includeLatitude(latitude); + // All meridians meet at a pole, so a vertex there has no single longitude that constrains + // the box; it contributes latitude only. A geography consisting solely of pole vertices + // leaves longitude unconstrained, which build() reports as the full range. + if (!isPole(latitude)) { + longitudeIntervals.add(new LongitudeInterval(longitude, longitude)); + } Review Comment: Add the pole vertex's stored longitude to `longitudeIntervals` rather than dropping it. The spec's geography X rule is numeric — an object matches if `x >= xmin OR x <= xmax` — and `GeographyEvaluator.intersects` compares the raw x values with no notion that the pole lies on every meridian. So `addPoint(-120, 90)` followed by `addPoint(40, 10)` gives `x=[40, 40]`, a bound that excludes an X value present in the file, and a predicate whose literal bound keeps the pole's longitude (`POINT(-120 90)` → `x=[-120, -120]`) won't intersect it, so the file is pruned even though it holds a matching row. Including the longitude only widens the box, so it stays valid under the spherical reading too. `addEdgeWithPole` drops the pole endpoint's longitude the same way. ########## core/src/main/java/org/apache/iceberg/SphericalGeographyBoundsBuilder.java: ########## @@ -0,0 +1,359 @@ +/* + * 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.iceberg; + +import java.util.Comparator; +import java.util.List; +import org.apache.iceberg.geospatial.BoundingBox; +import org.apache.iceberg.geospatial.GeospatialBound; +import org.apache.iceberg.relocated.com.google.common.collect.Lists; + +/** Builds an XY bounding box from geography points and minor great-circle edges on a sphere. */ +class SphericalGeographyBoundsBuilder { + private static final double MIN_LONGITUDE = -180.0; + private static final double MAX_LONGITUDE = 180.0; + private static final double MIN_LATITUDE = -90.0; + private static final double MAX_LATITUDE = 90.0; + private static final double LONGITUDE_SPAN = MAX_LONGITUDE - MIN_LONGITUDE; + + // For unit endpoints, |point1 x point2| = sin(central angle). A tiny normal means + // the endpoints are nearly coincident or antipodal, so normalizing the great-circle + // plane is numerically unstable. + private static final double MIN_NORMAL_LENGTH = 1e-12; + + // A point lies on the oriented minor arc when both exact side tests are nonnegative: + // + // point1 -------- point -------- point2 + // (point1 x point) . normal >= 0 + // (point x point2) . normal >= 0 + // + // Permit a small negative result introduced by floating-point rounding. + private static final double ARC_CONTAINMENT_TOLERANCE = 1e-12; + + // A minor great-circle arc can extend beyond both endpoint latitudes: + // + // conservative north bound + // --------------------------------------------- + // ^ margin + // * arc vertex + // .-' '-. + // endpoint * * endpoint + // + // The factor adds a relative 1e-7 margin away from the equator to avoid an + // under-covering bound; the result is then clamped to [-90, 90]. + private static final double LATITUDE_SCALING_FACTOR = 1.0000001; + + private final List<LongitudeInterval> longitudeIntervals = Lists.newArrayList(); Review Comment: Merge or compact these intervals as they accumulate instead of appending one per vertex. Nothing is ever removed, so a builder accumulating a whole data file holds one `LongitudeInterval` per vertex, and `longitudeBounds()` then allocates up to four `LongitudeEvent`s per interval and sorts them — a file with 1M polygons at 100 vertices each is 100M edges. `GeometryBoundsBuilder` keeps O(1) state for the same job. ########## core/src/main/java/org/apache/iceberg/SphericalGeographyBoundsBuilder.java: ########## @@ -0,0 +1,359 @@ +/* + * 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.iceberg; + +import java.util.Comparator; +import java.util.List; +import org.apache.iceberg.geospatial.BoundingBox; +import org.apache.iceberg.geospatial.GeospatialBound; +import org.apache.iceberg.relocated.com.google.common.collect.Lists; + +/** Builds an XY bounding box from geography points and minor great-circle edges on a sphere. */ +class SphericalGeographyBoundsBuilder { + private static final double MIN_LONGITUDE = -180.0; + private static final double MAX_LONGITUDE = 180.0; + private static final double MIN_LATITUDE = -90.0; + private static final double MAX_LATITUDE = 90.0; + private static final double LONGITUDE_SPAN = MAX_LONGITUDE - MIN_LONGITUDE; + + // For unit endpoints, |point1 x point2| = sin(central angle). A tiny normal means + // the endpoints are nearly coincident or antipodal, so normalizing the great-circle + // plane is numerically unstable. + private static final double MIN_NORMAL_LENGTH = 1e-12; + + // A point lies on the oriented minor arc when both exact side tests are nonnegative: + // + // point1 -------- point -------- point2 + // (point1 x point) . normal >= 0 + // (point x point2) . normal >= 0 + // + // Permit a small negative result introduced by floating-point rounding. + private static final double ARC_CONTAINMENT_TOLERANCE = 1e-12; + + // A minor great-circle arc can extend beyond both endpoint latitudes: + // + // conservative north bound + // --------------------------------------------- + // ^ margin + // * arc vertex + // .-' '-. + // endpoint * * endpoint + // + // The factor adds a relative 1e-7 margin away from the equator to avoid an + // under-covering bound; the result is then clamped to [-90, 90]. + private static final double LATITUDE_SCALING_FACTOR = 1.0000001; + + private final List<LongitudeInterval> longitudeIntervals = Lists.newArrayList(); + private double minLatitude = Double.POSITIVE_INFINITY; + private double maxLatitude = Double.NEGATIVE_INFINITY; + private State state = State.EMPTY; + + void addPoint(double longitude, double latitude) { + if (!prepareToAccumulate(coordinatesAreValid(longitude, latitude))) { + return; + } + + includeLatitude(latitude); + // All meridians meet at a pole, so a vertex there has no single longitude that constrains + // the box; it contributes latitude only. A geography consisting solely of pole vertices + // leaves longitude unconstrained, which build() reports as the full range. + if (!isPole(latitude)) { + longitudeIntervals.add(new LongitudeInterval(longitude, longitude)); + } + } + + void addEdge(double longitude1, double latitude1, double longitude2, double latitude2) { + if (!prepareToAccumulate( + coordinatesAreValid(longitude1, latitude1) && coordinatesAreValid(longitude2, latitude2))) { + return; + } + + includeLatitude(latitude1); + includeLatitude(latitude2); + + if (addEdgeWithPole(longitude1, latitude1, longitude2, latitude2)) { + return; + } + + longitudeIntervals.add(minimumLongitudeInterval(longitude1, longitude2)); + addInteriorLatitudeExtrema(longitude1, latitude1, longitude2, latitude2); + } + + private boolean addEdgeWithPole( + double longitude1, double latitude1, double longitude2, double latitude2) { + boolean firstIsPole = isPole(latitude1); + boolean secondIsPole = isPole(latitude2); + if (firstIsPole && secondIsPole) { + if (latitude1 != latitude2) { + includeFullWorld(); + } + + return true; + } else if (firstIsPole) { + longitudeIntervals.add(new LongitudeInterval(longitude2, longitude2)); + return true; + } else if (secondIsPole) { + longitudeIntervals.add(new LongitudeInterval(longitude1, longitude1)); + return true; + } + + return false; + } + + private void addInteriorLatitudeExtrema( + double longitude1, double latitude1, double longitude2, double latitude2) { + Vector3 point1 = toUnitVector(longitude1, latitude1); + Vector3 point2 = toUnitVector(longitude2, latitude2); + Vector3 normal = point1.crossProduct(point2); + double normalLength = normal.length(); + if (normalLength <= MIN_NORMAL_LENGTH) { + if (point1.dotProduct(point2) < 0) { + includeFullWorld(); + } + + return; + } + + Vector3 unitNormal = normal.scale(1.0 / normalLength); + double horizontalNormalLength = Math.hypot(unitNormal.xComponent, unitNormal.yComponent); + if (horizontalNormalLength == 0) { + return; + } + + double vertexLatitude = Math.toDegrees(Math.asin(clamp(horizontalNormalLength, 0.0, 1.0))); + Vector3 northVertex = + new Vector3( + -unitNormal.zComponent * unitNormal.xComponent / horizontalNormalLength, + -unitNormal.zComponent * unitNormal.yComponent / horizontalNormalLength, + horizontalNormalLength); + + double endpointMaxLatitude = Math.max(latitude1, latitude2); + if (vertexLatitude > endpointMaxLatitude + && isOnMinorArc(northVertex, point1, point2, unitNormal)) { + // Expand a computed extremum so rounding cannot produce an under-covering bound. + maxLatitude = + Math.max(maxLatitude, Math.min(LATITUDE_SCALING_FACTOR * vertexLatitude, MAX_LATITUDE)); + } + + double endpointMinLatitude = Math.min(latitude1, latitude2); + Vector3 southVertex = northVertex.scale(-1.0); + if (-vertexLatitude < endpointMinLatitude + && isOnMinorArc(southVertex, point1, point2, unitNormal)) { + // Expand a computed extremum so rounding cannot produce an under-covering bound. + minLatitude = + Math.min(minLatitude, Math.max(-LATITUDE_SCALING_FACTOR * vertexLatitude, MIN_LATITUDE)); + } + } + + BoundingBox build() { + if (state == State.EMPTY || state == State.INVALID) { + return null; + } + + LongitudeInterval longitudeBounds = longitudeBounds(); + return new BoundingBox( + GeospatialBound.createXY(longitudeBounds.west, minLatitude), + GeospatialBound.createXY(longitudeBounds.east, maxLatitude)); + } + + private void includeLatitude(double latitude) { + minLatitude = Math.min(minLatitude, latitude); + maxLatitude = Math.max(maxLatitude, latitude); + } + + private void includeFullWorld() { + minLatitude = MIN_LATITUDE; + maxLatitude = MAX_LATITUDE; + longitudeIntervals.clear(); + state = State.FULL_WORLD; + } + + private LongitudeInterval longitudeBounds() { + if (state == State.FULL_WORLD || longitudeIntervals.isEmpty()) { + return new LongitudeInterval(MIN_LONGITUDE, MAX_LONGITUDE); + } + + // The minimum covering circular interval is the complement of the largest uncovered gap. + List<LongitudeEvent> events = Lists.newArrayListWithExpectedSize(2 * longitudeIntervals.size()); + for (LongitudeInterval interval : longitudeIntervals) { + if (interval.west > interval.east) { + events.add(new LongitudeEvent(MIN_LONGITUDE, true)); + events.add(new LongitudeEvent(interval.east, false)); + events.add(new LongitudeEvent(interval.west, true)); + events.add(new LongitudeEvent(MAX_LONGITUDE, false)); + } else { + events.add(new LongitudeEvent(interval.west, true)); + events.add(new LongitudeEvent(interval.east, false)); + } + } + + events.sort( + Comparator.comparingDouble((LongitudeEvent event) -> event.longitude) + .thenComparing(event -> !event.start)); + + double largestGapStart = 0.0; + double largestGapEnd = -1.0; + int overlapCount = 0; + for (int i = 0; i < events.size(); i += 1) { + LongitudeEvent event = events.get(i); + if (event.start) { + if (overlapCount == 0 && i > 0) { + double gapStart = events.get(i - 1).longitude; + if (event.longitude - gapStart > largestGapEnd - largestGapStart) { + largestGapStart = gapStart; + largestGapEnd = event.longitude; + } + } + + overlapCount += 1; + } else { + overlapCount -= 1; + } + } + + double firstLongitude = events.get(0).longitude; + double lastLongitude = events.get(events.size() - 1).longitude; + double antimeridianGap = LONGITUDE_SPAN + firstLongitude - lastLongitude; + if (antimeridianGap >= largestGapEnd - largestGapStart) { + return new LongitudeInterval(firstLongitude, lastLongitude); + } + + return new LongitudeInterval(largestGapEnd, largestGapStart); + } + + private static LongitudeInterval minimumLongitudeInterval(double longitude1, double longitude2) { + // A coordinate on the antimeridian is kept as given: +180 and -180 both name that meridian + // and are preserved rather than folded onto one sign, so the same coordinate yields the same + // interval whether it arrives as a point or a degenerate edge. The interval spans the shorter + // of the two arcs between the endpoints, wrapping past the antimeridian (west > east) when + // that arc is the shorter one. + double west = Math.min(longitude1, longitude2); + double east = Math.max(longitude1, longitude2); + double directGap = east - west; + double antimeridianGap = LONGITUDE_SPAN - directGap; + return antimeridianGap >= directGap + ? new LongitudeInterval(west, east) + : new LongitudeInterval(east, west); + } + + private static boolean coordinatesAreValid(double longitude, double latitude) { + return Double.isFinite(longitude) + && Double.isFinite(latitude) + && longitude >= MIN_LONGITUDE + && longitude <= MAX_LONGITUDE + && latitude >= MIN_LATITUDE + && latitude <= MAX_LATITUDE; + } Review Comment: Skip a NaN coordinate instead of latching `INVALID` for the whole file. `POINT EMPTY` is encoded as `POINT(NaN NaN)`, so a single empty geography costs every other value in the file its bounds. The spec says NaN ordinates are skipped per dimension, and `GeometryBoundsBuilder.DimensionBounds.add` already does that. Suppressing on out-of-range coordinates still makes sense, since the sphere math has no meaning there. ########## core/src/main/java/org/apache/iceberg/SphericalGeographyBoundsBuilder.java: ########## @@ -0,0 +1,359 @@ +/* + * 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.iceberg; + +import java.util.Comparator; +import java.util.List; +import org.apache.iceberg.geospatial.BoundingBox; +import org.apache.iceberg.geospatial.GeospatialBound; +import org.apache.iceberg.relocated.com.google.common.collect.Lists; + +/** Builds an XY bounding box from geography points and minor great-circle edges on a sphere. */ Review Comment: Document the contract here: `build()` returns null for empty input, one invalid coordinate turns bounds off permanently, an ambiguous antipodal edge yields world bounds, the box may wrap with `west > east`, and latitude extrema are deliberately widened so bounds are not tight. These are the details the follow-up integration has to reason about, and `GeometryBoundsBuilder` spells out the equivalent. ########## core/src/test/java/org/apache/iceberg/TestSphericalGeographyBoundsBuilder.java: ########## @@ -0,0 +1,521 @@ +/* + * 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.iceberg; + +import static org.assertj.core.api.Assertions.assertThat; + +import java.util.Random; +import java.util.stream.Stream; +import org.apache.iceberg.geospatial.BoundingBox; +import org.apache.iceberg.geospatial.GeospatialBound; +import org.junit.jupiter.api.Test; +import org.junit.jupiter.params.ParameterizedTest; +import org.junit.jupiter.params.provider.Arguments; +import org.junit.jupiter.params.provider.MethodSource; + +class TestSphericalGeographyBoundsBuilder { + private static final double LATITUDE_TOLERANCE = 1e-9; + private static final double LONGITUDE_TOLERANCE = 1e-9; + + @Test + void capturesInteriorNorthernLatitudeExtremum() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(0.0, 60.0, 90.0, 60.0); + + BoundingBox box = bounds.build(); + assertThat(box.min()).isEqualTo(GeospatialBound.createXY(0.0, 60.0)); + assertThat(box.max().x()).isEqualTo(90.0); + assertThat(box.max().y()).isGreaterThan(67.79234427).isLessThan(67.793); + } + + @Test + void capturesInteriorSouthernLatitudeExtremum() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(0.0, -60.0, 90.0, -60.0); + + BoundingBox box = bounds.build(); + assertThat(box.min().x()).isEqualTo(0.0); + assertThat(box.min().y()).isLessThan(-67.79234427).isGreaterThan(-67.793); + assertThat(box.max()).isEqualTo(GeospatialBound.createXY(90.0, -60.0)); + } + + @Test + void doesNotExpandEndpointLatitude() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(20.0, 10.0, 20.0, 80.0); + + BoundingBox box = bounds.build(); + assertThat(box.min()).isEqualTo(GeospatialBound.createXY(20.0, 10.0)); + assertThat(box.max()).isEqualTo(GeospatialBound.createXY(20.0, 80.0)); + } + + @Test + void representsAntimeridianCrossingAsWrappedInterval() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(170.0, 5.0, -170.0, 8.0); + + BoundingBox box = bounds.build(); + assertThat(box.min().x()).isEqualTo(170.0); + assertThat(box.max().x()).isEqualTo(-170.0); + assertThat(box.min().x()).isGreaterThan(box.max().x()); + } + + @Test + void mergesIntervalsRatherThanOnlyEndpoints() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(100.0, 0.0, -100.0, 0.0); + bounds.addEdge(-10.0, 0.0, 10.0, 0.0); + + BoundingBox box = bounds.build(); + assertThat(longitudeIsContained(180.0, box)).isTrue(); + assertThat(longitudeIsContained(0.0, box)).isTrue(); + assertThat(longitudeIsContained(50.0, box)).isTrue(); + assertThat(longitudeIsContained(-50.0, box)).isFalse(); + } + + @Test + void ignoresPoleLongitudeWhenFiniteLongitudeExists() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addPoint(-120.0, 90.0); + bounds.addPoint(40.0, 10.0); + + BoundingBox box = bounds.build(); + assertThat(box.min()).isEqualTo(GeospatialBound.createXY(40.0, 10.0)); + assertThat(box.max()).isEqualTo(GeospatialBound.createXY(40.0, 90.0)); + } + + @Test + void usesFullLongitudeRangeForPoleOnlyBounds() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addPoint(10.0, 90.0); + bounds.addPoint(-50.0, 90.0); + + assertThat(bounds.build()) + .isEqualTo( + new BoundingBox( + GeospatialBound.createXY(-180.0, 90.0), GeospatialBound.createXY(180.0, 90.0))); + } + + @Test + void usesFullWorldForOppositePoles() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(0.0, -90.0, 30.0, 90.0); + + assertThat(bounds.build()) + .isEqualTo( + new BoundingBox( + GeospatialBound.createXY(-180.0, -90.0), GeospatialBound.createXY(180.0, 90.0))); + } + + @Test + void usesFullWorldForAntipodalEndpoints() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(0.0, 0.0, 180.0, 0.0); + + assertThat(bounds.build()) + .isEqualTo( + new BoundingBox( + GeospatialBound.createXY(-180.0, -90.0), GeospatialBound.createXY(180.0, 90.0))); + } + + @Test + void treatsCoincidentEndpointsAsAPoint() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(12.0, 34.0, 12.0, 34.0); + + assertThat(bounds.build()) + .isEqualTo( + new BoundingBox( + GeospatialBound.createXY(12.0, 34.0), GeospatialBound.createXY(12.0, 34.0))); + } + + @ParameterizedTest(name = "{0}") + @MethodSource("invalidCoordinates") + void invalidCoordinateSuppressesBounds(String description, double longitude, double latitude) { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addPoint(0.0, 0.0); + bounds.addPoint(longitude, latitude); + + assertThat(bounds.build()).isNull(); + } + + @Test + void emptyBuilderHasNoBounds() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + + assertThat(bounds.build()).isNull(); + } + + @ParameterizedTest(name = "({0}, {1}) to ({2}, {3})") + @MethodSource("edgeBoundsCases") + void buildsBoundsForSphericalEdges( + double longitude1, + double latitude1, + double longitude2, + double latitude2, + BoundingBox expected) { + SphericalGeographyBoundsBuilder forward = new SphericalGeographyBoundsBuilder(); + forward.addEdge(longitude1, latitude1, longitude2, latitude2); + assertBoundsCloseTo(forward.build(), expected); + + SphericalGeographyBoundsBuilder reverse = new SphericalGeographyBoundsBuilder(); + reverse.addEdge(longitude2, latitude2, longitude1, latitude1); + assertBoundsCloseTo(reverse.build(), expected); + } + + @ParameterizedTest(name = "{0}") + @MethodSource("lineBoundsCases") + void buildsBoundsForSphericalLines(String description, double[][] points, BoundingBox expected) { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + addLine(bounds, points); + + assertBoundsCloseTo(bounds.build(), expected); + } + + @ParameterizedTest(name = "{0}") + @MethodSource("pointBoundsCases") + void buildsBoundsForPointSets(String description, double[][] points, BoundingBox expected) { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + for (double[] point : points) { + bounds.addPoint(point[0], point[1]); + } + + assertBoundsCloseTo(bounds.build(), expected); + } + + @Test + void mergesBoundsAcrossDisconnectedLines() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + addLine(bounds, new double[][] {{180.0, 10.0}, {170.0, 10.0}}); + addLine(bounds, new double[][] {{20.0, 10.0}, {-150.0, 10.0}, {-180.0, 10.0}}); + addLine(bounds, new double[][] {{160.0, 0.0}, {40.0, 20.0}}); + + assertBoundsCloseTo(bounds.build(), box(40.0, 0.0, 20.0, 63.69752002440885)); + } + + @Test + void coversSampledPointsAlongRandomMinorArcs() { + Random random = new Random(42L); + for (int edge = 0; edge < 2_000; edge += 1) { + double longitude1 = random.nextDouble() * 360.0 - 180.0; + double latitude1 = random.nextDouble() * 140.0 - 70.0; + double longitude2 = normalizeLongitude(longitude1 + random.nextDouble() * 240.0 - 120.0); + double latitude2 = random.nextDouble() * 140.0 - 70.0; Review Comment: Consider widening these ranges to reach the poles and near-180 longitude separations. Latitudes are drawn from ±70 and the separation from ±120, so no sampled arc passes near or over a pole — which is where "the minor arc spans the shorter endpoint longitude difference" is hardest to verify by inspection, since longitude sweeps almost 180° over a short arc there. Only `(5, 10)-(175, 10)` and `(5, 10)-(-175.1, 10)` cover that today. ########## core/src/test/java/org/apache/iceberg/TestSphericalGeographyBoundsBuilder.java: ########## @@ -0,0 +1,521 @@ +/* + * 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.iceberg; + +import static org.assertj.core.api.Assertions.assertThat; + +import java.util.Random; +import java.util.stream.Stream; +import org.apache.iceberg.geospatial.BoundingBox; +import org.apache.iceberg.geospatial.GeospatialBound; +import org.junit.jupiter.api.Test; +import org.junit.jupiter.params.ParameterizedTest; +import org.junit.jupiter.params.provider.Arguments; +import org.junit.jupiter.params.provider.MethodSource; + +class TestSphericalGeographyBoundsBuilder { + private static final double LATITUDE_TOLERANCE = 1e-9; + private static final double LONGITUDE_TOLERANCE = 1e-9; + + @Test + void capturesInteriorNorthernLatitudeExtremum() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(0.0, 60.0, 90.0, 60.0); + + BoundingBox box = bounds.build(); + assertThat(box.min()).isEqualTo(GeospatialBound.createXY(0.0, 60.0)); + assertThat(box.max().x()).isEqualTo(90.0); + assertThat(box.max().y()).isGreaterThan(67.79234427).isLessThan(67.793); + } + + @Test + void capturesInteriorSouthernLatitudeExtremum() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(0.0, -60.0, 90.0, -60.0); + + BoundingBox box = bounds.build(); + assertThat(box.min().x()).isEqualTo(0.0); + assertThat(box.min().y()).isLessThan(-67.79234427).isGreaterThan(-67.793); + assertThat(box.max()).isEqualTo(GeospatialBound.createXY(90.0, -60.0)); + } + + @Test + void doesNotExpandEndpointLatitude() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(20.0, 10.0, 20.0, 80.0); + + BoundingBox box = bounds.build(); + assertThat(box.min()).isEqualTo(GeospatialBound.createXY(20.0, 10.0)); + assertThat(box.max()).isEqualTo(GeospatialBound.createXY(20.0, 80.0)); + } + + @Test + void representsAntimeridianCrossingAsWrappedInterval() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(170.0, 5.0, -170.0, 8.0); + + BoundingBox box = bounds.build(); + assertThat(box.min().x()).isEqualTo(170.0); + assertThat(box.max().x()).isEqualTo(-170.0); + assertThat(box.min().x()).isGreaterThan(box.max().x()); + } + + @Test + void mergesIntervalsRatherThanOnlyEndpoints() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(100.0, 0.0, -100.0, 0.0); + bounds.addEdge(-10.0, 0.0, 10.0, 0.0); + + BoundingBox box = bounds.build(); + assertThat(longitudeIsContained(180.0, box)).isTrue(); + assertThat(longitudeIsContained(0.0, box)).isTrue(); + assertThat(longitudeIsContained(50.0, box)).isTrue(); + assertThat(longitudeIsContained(-50.0, box)).isFalse(); + } + + @Test + void ignoresPoleLongitudeWhenFiniteLongitudeExists() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addPoint(-120.0, 90.0); + bounds.addPoint(40.0, 10.0); + + BoundingBox box = bounds.build(); + assertThat(box.min()).isEqualTo(GeospatialBound.createXY(40.0, 10.0)); + assertThat(box.max()).isEqualTo(GeospatialBound.createXY(40.0, 90.0)); + } + + @Test + void usesFullLongitudeRangeForPoleOnlyBounds() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addPoint(10.0, 90.0); + bounds.addPoint(-50.0, 90.0); + + assertThat(bounds.build()) + .isEqualTo( + new BoundingBox( + GeospatialBound.createXY(-180.0, 90.0), GeospatialBound.createXY(180.0, 90.0))); + } + + @Test + void usesFullWorldForOppositePoles() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(0.0, -90.0, 30.0, 90.0); + + assertThat(bounds.build()) + .isEqualTo( + new BoundingBox( + GeospatialBound.createXY(-180.0, -90.0), GeospatialBound.createXY(180.0, 90.0))); + } + + @Test + void usesFullWorldForAntipodalEndpoints() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(0.0, 0.0, 180.0, 0.0); + + assertThat(bounds.build()) + .isEqualTo( + new BoundingBox( + GeospatialBound.createXY(-180.0, -90.0), GeospatialBound.createXY(180.0, 90.0))); + } + + @Test + void treatsCoincidentEndpointsAsAPoint() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(12.0, 34.0, 12.0, 34.0); + + assertThat(bounds.build()) + .isEqualTo( + new BoundingBox( + GeospatialBound.createXY(12.0, 34.0), GeospatialBound.createXY(12.0, 34.0))); + } + + @ParameterizedTest(name = "{0}") + @MethodSource("invalidCoordinates") + void invalidCoordinateSuppressesBounds(String description, double longitude, double latitude) { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addPoint(0.0, 0.0); + bounds.addPoint(longitude, latitude); + + assertThat(bounds.build()).isNull(); + } + + @Test + void emptyBuilderHasNoBounds() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + + assertThat(bounds.build()).isNull(); + } + + @ParameterizedTest(name = "({0}, {1}) to ({2}, {3})") + @MethodSource("edgeBoundsCases") + void buildsBoundsForSphericalEdges( + double longitude1, + double latitude1, + double longitude2, + double latitude2, + BoundingBox expected) { + SphericalGeographyBoundsBuilder forward = new SphericalGeographyBoundsBuilder(); + forward.addEdge(longitude1, latitude1, longitude2, latitude2); + assertBoundsCloseTo(forward.build(), expected); + + SphericalGeographyBoundsBuilder reverse = new SphericalGeographyBoundsBuilder(); + reverse.addEdge(longitude2, latitude2, longitude1, latitude1); + assertBoundsCloseTo(reverse.build(), expected); + } + + @ParameterizedTest(name = "{0}") + @MethodSource("lineBoundsCases") + void buildsBoundsForSphericalLines(String description, double[][] points, BoundingBox expected) { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + addLine(bounds, points); + + assertBoundsCloseTo(bounds.build(), expected); + } + + @ParameterizedTest(name = "{0}") + @MethodSource("pointBoundsCases") + void buildsBoundsForPointSets(String description, double[][] points, BoundingBox expected) { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + for (double[] point : points) { + bounds.addPoint(point[0], point[1]); + } + + assertBoundsCloseTo(bounds.build(), expected); + } + + @Test + void mergesBoundsAcrossDisconnectedLines() { + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + addLine(bounds, new double[][] {{180.0, 10.0}, {170.0, 10.0}}); + addLine(bounds, new double[][] {{20.0, 10.0}, {-150.0, 10.0}, {-180.0, 10.0}}); + addLine(bounds, new double[][] {{160.0, 0.0}, {40.0, 20.0}}); + + assertBoundsCloseTo(bounds.build(), box(40.0, 0.0, 20.0, 63.69752002440885)); + } + + @Test + void coversSampledPointsAlongRandomMinorArcs() { + Random random = new Random(42L); + for (int edge = 0; edge < 2_000; edge += 1) { + double longitude1 = random.nextDouble() * 360.0 - 180.0; + double latitude1 = random.nextDouble() * 140.0 - 70.0; + double longitude2 = normalizeLongitude(longitude1 + random.nextDouble() * 240.0 - 120.0); + double latitude2 = random.nextDouble() * 140.0 - 70.0; + + double[] point1 = toUnitVector(longitude1, latitude1); + double[] point2 = toUnitVector(longitude2, latitude2); + double centralAngle = centralAngle(longitude1, latitude1, longitude2, latitude2); + if (centralAngle > Math.toRadians(179.0)) { + continue; + } + + SphericalGeographyBoundsBuilder bounds = new SphericalGeographyBoundsBuilder(); + bounds.addEdge(longitude1, latitude1, longitude2, latitude2); + BoundingBox box = bounds.build(); + + for (int sample = 0; sample <= 100; sample += 1) { + double[] point = slerp(point1, point2, sample / 100.0, centralAngle); + double latitude = Math.toDegrees(Math.asin(clamp(point[2], -1.0, 1.0))); + double longitude = Math.toDegrees(Math.atan2(point[1], point[0])); + + assertThat(latitude) + .as("latitude for edge %s sample %s", edge, sample) + .isBetween(box.min().y() - 1e-8, box.max().y() + 1e-8); + assertThat(longitudeIsContained(longitude, box)) + .as("longitude for edge %s sample %s", edge, sample) + .isTrue(); + } + } + } + + private static Stream<Arguments> invalidCoordinates() { + return Stream.of( + Arguments.of("longitude above range", 180.1, 0.0), + Arguments.of("longitude below range", -180.1, 0.0), + Arguments.of("latitude above range", 0.0, 90.1), + Arguments.of("latitude below range", 0.0, -90.1), + Arguments.of("NaN longitude", Double.NaN, 0.0), + Arguments.of("NaN latitude", 0.0, Double.NaN), + Arguments.of("infinite longitude", Double.POSITIVE_INFINITY, 0.0), + Arguments.of("infinite latitude", 0.0, Double.NEGATIVE_INFINITY)); + } + + private static Stream<Arguments> lineBoundsCases() { + return Stream.of( + Arguments.of( + "ordinary polyline", + new double[][] {{1.0, 2.0}, {5.0, 6.0}, {-10.0, -7.0}}, + box(-10.0, -7.0, 5.0, 6.0)), + Arguments.of( + "approaches positive antimeridian", + new double[][] {{180.0, 0.0}, {170.0, 0.0}}, + box(170.0, 0.0, 180.0, 0.0)), + Arguments.of( + "crosses negative antimeridian", + new double[][] {{-180.0, 0.0}, {170.0, 0.0}}, + box(170.0, 0.0, -180.0, 0.0)), + Arguments.of( + "latitude bulge near antimeridian", + new double[][] {{180.0, 10.0}, {170.0, 10.0}}, + box(170.0, 10.0, 180.0, 10.037424049653)), + Arguments.of( + "narrow antimeridian crossing", + new double[][] {{-179.0, 10.0}, {179.0, 10.0}}, + box(179.0, 10.0, -179.0, 10.001493527133333)), + Arguments.of( + "edges cover every longitude", + new double[][] { + {180.0, 10.0}, + {170.0, 10.0}, + {20.0, 10.0}, + {-20.0, 10.0}, + {-160.0, 10.0}, + {-180.0, 10.0} + }, + box(-180.0, 10.0, 180.0, 34.265634937025254)), + Arguments.of( + "wide non-wrapping line", + new double[][] { + {179.0, 10.0}, + {170.0, 10.0}, + {20.0, 10.0}, + {-20.0, 10.0}, + {-160.0, 10.0}, + {-179.0, 10.0} + }, + box(-179.0, 10.0, 179.0, 34.265634937025254)), + Arguments.of( + "line touches north pole", + new double[][] {{10.0, 20.0}, {10.0, 90.0}, {30.0, 20.0}}, + box(10.0, 20.0, 30.0, 90.0)), + Arguments.of( + "line stays on north pole", + new double[][] {{20.0, 90.0}, {10.0, 90.0}, {30.0, 90.0}}, + box(-180.0, 90.0, 180.0, 90.0)), + Arguments.of( + "line stays on south pole", + new double[][] {{20.0, -90.0}, {10.0, -90.0}, {30.0, -90.0}}, + box(-180.0, -90.0, 180.0, -90.0)), + Arguments.of( + "edge connects opposite poles", + new double[][] {{30.0, 90.0}, {10.0, -90.0}}, + box(-180.0, -90.0, 180.0, 90.0)), + Arguments.of( + "line visits both poles", + new double[][] {{10.0, 90.0}, {10.0, 0.0}, {10.0, -90.0}, {20.0, 0.0}, {20.0, 90.0}}, + box(10.0, -90.0, 20.0, 90.0))); + } + + private static Stream<Arguments> edgeBoundsCases() { + return Stream.concat(antimeridianEdgeBoundsCases(), latitudeEdgeBoundsCases()); + } + + private static Stream<Arguments> antimeridianEdgeBoundsCases() { + return Stream.of( + edgeCase(5.0, 10.0, 15.0, 10.0, 5.0, 10.0, 15.0, 10.03742404965304), + edgeCase(5.0, -10.0, 15.0, -10.0, 5.0, -10.037424049653, 15.0, -10.0), + edgeCase(5.0, 10.0, -179.0, 10.0, 5.0, 10.0, -179.0, 78.80444354002829), + edgeCase(5.0, 10.0, -175.1, 10.0, 5.0, 10.0, -175.1, 89.716447231812), + edgeCase(5.0, 10.0, 105.0, -10.0, 5.0, -10.0, 105.0, 10.0), + edgeCase(5.0, 10.0, 25.0, 10.0, 5.0, 10.0, 25.0, 10.15108272615629), + edgeCase(5.0, -10.0, 25.0, -10.0, 5.0, -10.15108272615629, 25.0, -10.0), + edgeCase(-170.0, 10.0, 160.0, 10.0, 160.0, 10.0, -170.0, 10.34527108067699), + edgeCase(-170.0, -10.0, 160.0, -10.0, 160.0, -10.34527108067699, -170.0, -10.0), + edgeCase(-180.0, 10.0, -170.0, 10.0, -180.0, 10.0, -170.0, 10.03742404965304), + edgeCase(180.0, 10.0, 170.0, 10.0, 170.0, 10.0, 180.0, 10.037424049653), + edgeCase(180.0, 10.0, 180.0, 5.0, 180.0, 5.0, 180.0, 10.0), + edgeCase(-180.0, 10.0, -180.0, 5.0, -180.0, 5.0, -180.0, 10.0), + edgeCase(10.0, 90.0, 20.0, 90.0, -180.0, 90.0, 180.0, 90.0), + edgeCase(10.0, -90.0, 20.0, -90.0, -180.0, -90.0, 180.0, -90.0)); + } + + private static Stream<Arguments> latitudeEdgeBoundsCases() { + return Stream.of( + edgeCase(10.0, 90.0, 20.0, -90.0, -180.0, -90.0, 180.0, 90.0), + edgeCase(10.0, 90.0, 10.0, -90.0, -180.0, -90.0, 180.0, 90.0), + edgeCase(10.0, -0.1, 100.0, 1.0, 10.0, -0.1, 100.0, 1.0), + edgeCase(10.0, -1.0, 100.0, 1.0, 10.0, -1.0, 100.0, 1.0), + edgeCase(10.0, 0.0, 120.0, 0.0, 10.0, 0.0, 120.0, 0.0), + edgeCase(10.0, 0.0, 120.0, 1.0, 10.0, 0.0, 120.0, 1.06416356550489), + edgeCase(10.0, 10.0, 20.0, 20.0, 10.0, 10.0, 20.0, 20.0), + edgeCase(10.0, 60.0, 70.0, 70.0, 10.0, 60.0, 70.0, 70.20558550568438), Review Comment: Assert that the bound is at least the true extremum rather than pinning the widened value. `70.20558550568438` is the exact vertex latitude times `LATITUDE_SCALING_FACTOR`, and the 1e-9 tolerance is far tighter than that 7e-6 offset, so tuning the margin means rewriting about ten expectations. -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
