apache / apache/sedona

Define deterministic floating-point grid-boundary semantics for RS_AsRaster

Open
#3,256 0 comments 0 reactions 0 assignees View on GitHub
affect public APIs behavior change improvement sedona-common
Dominant language
Java
Stars
2.4k
Forks
784
Avg merge
1d 12h
Merged PRs (30d)
58

Description

## Expected behavior

Rasterization should have a documented, deterministic rule for deciding whether a stored double-precision geometry coordinate represents a pixel grid boundary. The rule should behave consistently across pixel scales and world-coordinate magnitudes, while preserving coordinates that genuinely cross a boundary by a representable positive distance.

## Actual behavior

Grid-boundary handling currently depends on whether the computed inverse affine coordinate happens to be exactly integral as a `double`:

```java
double pixel = (coordinate - origin) / scale;
```

Common decimal and affine construction paths can leave a nonintegral residue for an intended boundary, causing an endpoint-only adjacent cell to be burned. Conversely, division can round a genuine adjacent-double crossing to an integral pixel coordinate, causing a cell with positive-length overlap to be omitted.

Examples:

- Decimal grid: `(0.3 - 0.6) / -0.1 == 2.9999999999999996`.
- Affine-generated value: with origin `0.1` and scale `0.1`, `0.1 + 2 * 0.1 == 0.30000000000000004`, and the inverse result is `2.0000000000000004`.
- Large origin: `(1000000.03 - 1000000.0) / 0.01 == 3.0000000027939677`.
- Rounded quotient in the other direction: `0.030000000000000002 / 0.01 == 3.0`, even though the coordinate is the next representable double above `0.03`.

## Steps to reproduce

### Intended decimal boundary is classified as nonintegral

```sql
SELECT RS_BandAsArray(
RS_AsRaster(
ST_GeomFromWKT('LINESTRING (0.22 0.22, 0.3 0.3)'),
RS_MakeEmptyRaster(1, 'B', 6, 6, 0.0, 0.6, 0.1, -0.1, 0.0, 0.0, 0),
'B', true, 1.0, 0.0, false),
1);
```

Under a policy that accepts the decimal relation as a boundary, the segment traverses only zero-based `(row 3, column 2)` and terminates at the pixel corner. The inverse-coordinate residue additionally burns endpoint-only `(row 2, column 2)`. Under an exact stored-IEEE policy, that tiny extension would instead be considered real; choosing between those interpretations is the decision this issue requests.

### Genuine representable crossing is classified as integral

```sql
SELECT RS_BandAsArray(
RS_AsRaster(
ST_GeomFromWKT('LINESTRING (0.025 0.045, 0.030000000000000002 0.045)'),
RS_MakeEmptyRaster(1, 'B', 6, 6, 0.0, 0.06, 0.01, -0.01, 0.0, 0.0, 0),
'B', true, 1.0, 0.0, false),
1);
```

`0.030000000000000002` is the next representable double above `0.03`, so the line enters column 3 for a positive distance. Sedona burns only zero-based `(row 1, column 2)` because the inverse division rounds the endpoint to exactly `3.0`; zero-based `(row 1, columns 2 and 3)` should be burned under exact stored-double geometry.

## Why a tolerance is not a complete fix

The original source intent is no longer available after parsing or coordinate transformation. For origin `0.1`, scale `0.1`, and boundary index `2`:

```text
decimal boundary = 0.3
binary affine result (0.1 + 2 * 0.1) = 0.30000000000000004
Math.nextUp(0.3) = 0.30000000000000004
```

The same stored bits can mean either an affine-generated boundary or a genuine one-double crossing beyond the decimal boundary. No epsilon can recover those two intents. A fixed or magnitude-scaled tolerance can also swallow real endpoint slivers, while unconditional exact-decimal arithmetic can add per-vertex allocation and CPU cost.

## Decision required

Choose and document the boundary-equivalence policy before implementing it. Candidate policies include:

1. one canonical boundary encoding produced by the raster's actual forward affine transform;
2. an explicit finite set of boundary-equivalent encodings, such as forward-affine and canonical-decimal relations;
3. exact arithmetic over the stored IEEE-754 values, accepting that common decimal relations may not be boundaries.

This is a compatibility policy, not recovery of source intent. If multiple encodings are accepted, adjacent doubles may deliberately be boundary-equivalent and that exception must be documented.

## Acceptance criteria

- Public documentation defines which stored coordinate encodings are treated as grid boundaries.
- Classification is axis-local, direction-independent, and consistent across unit, decimal, fractional, negative-scale, and large-origin grids.
- Values not in the accepted equivalence set preserve their exact mathematical side; quotient rounding alone is not an equality decision.
- Tests cover decimal literals, coordinates produced by the raster's actual affine operation, `1/3`-style scales, large origins, bottom-up rasters, and adjacent `Math.nextDown`/`Math.nextUp` values.
- Tests explicitly document the unavoidable `0.3` versus `0.30000000000000004` policy choice.
- The proposed implementation includes benchmark results for long LineString and Polygon workloads against PR #3251, with any accepted regression limit stated explicitly.
- Clipped endpoints carry explicit boundary/side provenance from the clipper rather than being reclassified solely from rounded coordinates. #3255 should be implemented first.

## Related work

- #3120 tracks the exact-grid-vertex case; #3251 fixes it when the computed pixel coordinate is already exactly integral.
- #3255 should land first so synthetic clipped endpoints do not lose their boundary provenance.

## Settings

- Sedona version: PR #3251 head `72d9cc26541` / `2.0.0-SNAPSHOT`
- API type: SQL and Java
- JRE: 17
- Environment: local development checkout

I searched open and closed issues and did not find a duplicate.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the RS_AsRaster boundary handling described here, then read related work in #3255 and PR #3251 before choosing a boundary-equivalence policy. Use the supplied RS_AsRaster examples and add coverage for the listed scale, origin, direction, and adjacent-double cases; done requires public documentation, clipper provenance, and benchmark results against PR #3251.

Written by the indexing model from the issue text.

Assessment

Tech stack
java, sql
Domain
backend-api-design, database
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.