S2RegionCoverer with fixed level - does it give the minimal covering?

22 views
Skip to first unread message

Ethan Van Andel

unread,
Jan 8, 2020, 7:40:17 PM1/8/20
to s2geometry-io
Hi folks,

Quick question. Let's say I have an S2RegionCoverer with a fixed level "L" (max level = min level = L). https://github.com/google/s2geometry/blob/master/src/s2/s2region_coverer.h#L133

Are the coverings generated by said RC guaranteed to be the minimal cover, that is the set of all cells at level L that intersect the region? That is, is there any chance that the approximation algorithm will return more or less than this set, either including cells that don't intersect or omitting cells that do?

Thanks in advance,

Ethan

Eric Engle

unread,
Jan 8, 2020, 7:55:03 PM1/8/20
to Ethan Van Andel, s2geometry-io
Obviously a tight, or minimal set, is ideal. That's what we aim for. But as the docs note, the output is not guaranteed to be stable.

In particular, software changes over time may alter the precise set of cells you get back, in any scenario. This gives us the option of trading precision for performance, or trading off different kinds of precision. Very hypothetically, if we found a way to make things 10x faster but it would include 1% more cells, we at least want the API freedom to do that.

Also, even if you had exactly the set of cells at level L for which S2Region::MayIntersect is true, that method can certainly return true when it's more convenient to say yes than figure out an exact answer. The S2Regions mostly do a good job here, e.g. S2Polygon::MayIntersect is quite precise, but this can in general drag in more cells by itself.

--
You received this message because you are subscribed to the Google Groups "s2geometry-io" group.
To unsubscribe from this group and stop receiving emails from it, send an email to s2geometry-i...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/s2geometry-io/6864717b-57ee-4a38-ad20-330505912cc8%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages