google / google/s2geometry

S2Cell(S2CellId(p)).Contains(p) requires expansion of (1.125 + eps) * eps

Open
#463 10 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
2.7k
Forks
357
Avg merge
11h 4m
Merged PRs (30d)
1

Description

`S2Cell(S2CellId(p)).Contains(p) ` should always hold, and there is a test to verify this, but there are counterexamples, causing flaky tests.

https://github.com/google/s2geometry/blob/ead4b7a4bfca58067bd473de04f2f9cc5da70250/src/s2/s2cell_test.cc#L494-L500

Is the expansion amount just wrong here?

https://github.com/google/s2geometry/blob/ead4b7a4bfca58067bd473de04f2f9cc5da70250/src/s2/s2cell.cc#L299-L306

We can empirically determine the amount that makes it pass (I think it was around 1.5 ε, maybe smaller), but it would be good to have the correct error analysis.

See also discussion in https://github.com/golang/geo/issues/120.

@ericveach

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.