apache / apache/sedona-db

ST_Touches and ST_Within misclassify boundary-only line configurations

Open
#1,165 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
503
Forks
61
Avg merge
2d 4h
Merged PRs (30d)
90

Description

Two boundary-only configurations produce wrong answers from the native topology predicates. Both disagree with Shapely/GEOS and PostGIS, and both are silent wrong rows rather than errors.

## 1. `ST_Touches` misses a line whose interior passes through a polygon corner

```sql
SELECT
ST_Touches(
ST_GeomFromText('POLYGON ((0 0, 2 0, 2 2, 0 2, 0 0))'),
ST_GeomFromText('LINESTRING (1 3, 3 1)')) AS touches,
ST_Intersects(
ST_GeomFromText('POLYGON ((0 0, 2 0, 2 2, 0 2, 0 0))'),
ST_GeomFromText('LINESTRING (1 3, 3 1)')) AS intersects;
```

```
touches = false
intersects = true
```

The line passes through the polygon's corner `(2 2)` without entering the interior — the intersection is the single boundary point, so `touches` should be `true` (Shapely returns `true`). `ST_Intersects` correctly sees the intersection, so the pair is classified as intersecting-but-not-touching, which no DE-9IM class supports for this geometry pair.

Notably, a line whose *endpoint* meets the corner (`LINESTRING (2 2, 3 3)`) is handled correctly — the failure is specific to the intersection point lying in the line's interior.

## 2. `ST_Within` wrongly matches a line lying on a hole boundary

```sql
SELECT ST_Within(
ST_GeomFromText('LINESTRING (3 3, 3 7)'),
ST_GeomFromText('POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0), (3 3, 7 3, 7 7, 3 7, 3 3))'));
-- true; Shapely and PostGIS: false
```

The line lies entirely on the boundary of the polygon's hole. `within` requires the interiors to intersect (DE-9IM `T*F**F***`), and a line contained in the boundary never intersects the interior, so the correct answer is `false`.

## Scope checked

These neighbouring configurations are all correct: line endpoint at a corner (`touches`), line along an outer edge (`touches`), polygons sharing a corner (`touches`), point at a corner (`touches`), point inside a hole, point on a hole boundary, line across a hole, and polygon inside a hole (`within`/`contains`/`covers`/`covered_by`). So the defects look like specific gaps in boundary-interior classification rather than a broad relate problem.

## Impact

Both surface through spatial joins as silently missing or extra rows — `sjoin(predicate="touches")` drops the crossing-corner pair, and `sjoin(predicate="within")` fabricates a match for hole-boundary linework.

Found by GeoPandas-parity testing of `sedonadb-geopandas` (#1142); documented there as known engine limitations pending this fix.

Version: `sedonadb` 0.5.0 (source build of current `main`).

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the ST_Touches and ST_Within SQL examples against the native topology predicates, then trace their implementation and existing nearby boundary-case coverage. Add regression coverage for the two configurations and verify the results agree with the stated Shapely/GEOS and PostGIS outcomes without changing the already-correct neighbouring cases.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust, sql
Domain
databases
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
62/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.