Add support for full containment and overlapping modes in polygonToCellsExperimental by nrabinowitz · Pull Request #796 · uber/h3

nrabinowitz · 2023-11-04T01:08:37Z

Adds support for full containment mode and overlapping modes in polygonToCellsExperimental.

Defines an enum for the containment modes. My assumption here is that the lowest 4 bits of the 32-bit flag are reserved for containment modes (not sure that we'd need more than 7, but wanted to be on the safe side), and that we'd use them as an integer, not as bitwise flags, since the modes are mutually exclusive.
Implements the check for containment in iterStepPolygonCompact. This was very straightforward as we already have cellBoundaryInsidePolygon polygon available.
Implements the check for overlapping cells in iterStepPolygonCompact. This checks center point inclusion first, then shares code with the full containment check, substituting a new cellBoundaryCrossesPolygon check for cellBoundaryInsidePolygon.
Adds some very basic tests, which essentially just duplicate existing polyfill tests with full containment and overlapping turned on, substituting an empirically determined result and checking that it's reasonable compared to the center containment mode.
Updates all tests to use modes instead of 0 for flags.

TODO:

We should probably clean up the tests and use CENTER_CONTAINMENT instead of 0 for the flag value in existing tests.
There are a couple of error branches here that I think we can get coverage on by sticking invalid cells into the iterator object.
I'd love better tests here, though I'm not sure what would make sense.

coveralls · 2023-11-04T01:12:37Z

coverage: 98.806% (+0.02%) from 98.784%
when pulling f0f1b45 on nrabinowitz:polyfill-contained
into 6c1b003 on uber:master.

nrabinowitz · 2023-11-04T21:59:14Z

scripts/make_countries.js

+
+  BENCHMARK(polygonToCells_AllCountries4, 5, {
+    for (int index = 0; index < ${polygons.length}; index++) {
+      H3_EXPORT(polygonToCellsExperimental)(&COUNTRIES[index], res, OVERLAPPING, hexagons);


The new modes are slower than center containment, unsurprisingly, but still manage to be faster than the old algo in some cases:

Res 0 -- polygonToCells_AllCountries1: 198222.000000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries2: 42474.800000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries3: 247580.600000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries4: 282227.200000 microseconds per iteration (5 iterations) Res 1 -- polygonToCells_AllCountries1: 324889.800000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries2: 18640.000000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries3: 72821.200000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries4: 89494.400000 microseconds per iteration (5 iterations) Res 2 -- polygonToCells_AllCountries1: 257009.400000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries2: 66020.600000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries3: 143866.400000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries4: 181394.600000 microseconds per iteration (5 iterations) Res 3 -- polygonToCells_AllCountries1: 424776.400000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries2: 280514.200000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries3: 442108.400000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries4: 545078.600000 microseconds per iteration (5 iterations) Res 4 -- polygonToCells_AllCountries1: 2035545.200000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries2: 1462475.200000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries3: 1969331.600000 microseconds per iteration (5 iterations) -- polygonToCells_AllCountries4: 2559085.000000 microseconds per iteration (5 iterations)

isaacbrodsky · 2023-11-05T15:10:12Z

src/h3lib/include/polygon.h

+typedef enum {
+    CENTER_CONTAINMENT = 0,
+    FULL_CONTAINMENT = 1,
+    OVERLAPPING = 2,
+    INVALID_CONTAINMENT = 3
+} ContainmentMode;


we may want to prefix the enun names with something here (POLYGON_CENTER_CONTAINMENT?) so that it is clear a valid enum is being fed into polygonToCells.

That makes sense - leaning towards CONTAINMENT_ as the prefix, so we'd have

CONTAINMENT_CENTER

CONTAINMENT_FULL

CONTAINMENT_OVERLAPPING

CONTAINMENT_INVALID

One thought here is that we might apply the same modes to circles or bounding boxes at some point, so I don't necessarily think we want to bake POLYGON into the name.

isaacbrodsky · 2023-11-05T15:11:37Z

src/h3lib/include/polygon.h

+    CENTER_CONTAINMENT = 0,
+    FULL_CONTAINMENT = 1,
+    OVERLAPPING = 2,
+    INVALID_CONTAINMENT = 3


Suggested change

CENTER_CONTAINMENT = 0,

FULL_CONTAINMENT = 1,

OVERLAPPING = 2,

INVALID_CONTAINMENT = 3

CENTER_CONTAINMENT = 0, ///< Cells are included if their center is in the polygon

FULL_CONTAINMENT = 1, ///< Cells are included if they are entirely contained in the polygon

OVERLAPPING = 2, ///< Cells are included if any part of them overlaps the polygon

INVALID_CONTAINMENT = 3 ///< This mode is invalid and should not be used.

isaacbrodsky · 2023-11-12T18:36:54Z

src/h3lib/lib/polyfill.c

+                    iterErrorPolygonCompact(iter, centerErr);
+                    return;


This (and similar case below) are uncovered in test, but look like they should be testable by setting an invalid cell on the iterator and then calling this function.

Yes, I'll try to add coverage here today or tomorrow.

isaacbrodsky · 2023-11-12T18:37:27Z

src/h3lib/lib/polyfill.c

+                if (bboxErr) {
+                    iterErrorPolygonCompact(iter, bboxErr);
+                    return;
+                }


This case may not be testable because presumably the boundary error above would not be E_SUCCESS? Perhaps there exists some index for which cellToBoundary returns 0 but cellToBbox returns non-0?

Related question, do we have fuzzer question of these functions?

Not sure if this is coverable, will switch to NEVER if I can't figure out an approach.

We don't have a fuzzer for polygonToCellsExperimental, but I can add one - that's probably best in a separate PR.

I would be happy to help getting a fuzzer added. Agreed doing that in a separate PR would make the most sense.

…verage

nrabinowitz · 2023-11-25T22:45:54Z

@isaacbrodsky I believe the latest commit should close the holes in coverage.

michaelbrichko · 2023-12-11T16:29:19Z

Thanks for adding this functionality !!
How mature is it? Are there any knows issues for overlapping functionality? Any known gaps ?

nrabinowitz · 2023-12-11T18:11:41Z

Thanks for adding this functionality !! How mature is it? Are there any knows issues for overlapping functionality? Any known gaps ?

Well, you can see it was merged two weeks ago, so that's how mature it is :). But we've done a fair amount of testing against the older algo, and it seems to behave as expected. Overlapping mode seems to work as expected, we aren't aware of any issues, but it's hard to extensively test this. The main (expected) issue is that overlapping mode is slower than the other modes, as discussed in this PR.

michaelbrichko · 2023-12-12T08:37:46Z

Ok, thanks for quick answer !

brendan-morin · 2024-01-25T17:59:49Z

Look great! Has this been released yet? If not, is there a stable tag we could reference? We use the h3-py bindings and it looks like it’s been a bit since the last release.

rmx90210 · 2024-04-02T18:19:30Z

Hello H3 friends! 👋

I use H3 often and this PR would be tremendously helpful. Is there any timeline for when a new release might come out with the new polyfill modes?

Thank you for all of the hard work that went into this!

This adds new fuzzers for the `polygonToCellsExperimental` function, based on the existing functions. Since #796 (this PR is based on that branch) adds containment modes, this updates the existing fuzzers to exercise those options too. The estimation functions are adjusted so that the fuzzers pass. This may reduce performance of the new algorithms somewhat, but avoids potential buffer problems. This can be revisited to get them back to how they were intended to work. --------- Co-authored-by: Nick Rabinowitz <nick@unfolded.ai>

Nick Rabinowitz added 2 commits November 3, 2023 17:50

Add support for full containment mode in polygonToCells

de71b07

Add tests

45255d5

nrabinowitz requested review from ajfriend, dfellis and isaacbrodsky November 4, 2023 01:08

Implement OVERLAPPING mode, update tests to use mode flags

61d3e5b

nrabinowitz changed the title ~~Add support for full containment mode in polygonToCellsExperimental~~ Add support for full and overlapping containment modes in polygonToCellsExperimental Nov 4, 2023

nrabinowitz changed the title ~~Add support for full and overlapping containment modes in polygonToCellsExperimental~~ Add support for full containment and overlapping modes in polygonToCellsExperimental Nov 4, 2023

nrabinowitz commented Nov 4, 2023

View reviewed changes

isaacbrodsky reviewed Nov 5, 2023

View reviewed changes

Nick Rabinowitz added 4 commits November 6, 2023 10:25

Rename containment enum values

585f497

Fix and test for case where OVERLAPPING cell contains polygon

1a44627

Possibly fix test

edaa901

Fixture fix

fedaa5f

isaacbrodsky reviewed Nov 12, 2023

View reviewed changes

isaacbrodsky mentioned this pull request Nov 16, 2023

Polygon to cells experimental fuzzer #800

Merged

Nick Rabinowitz added 2 commits November 25, 2023 08:49

Additional test coverage for error cases

a2adc04

Test coverage for one more error, excluding unreachable block from co…

f0f1b45

…verage

isaacbrodsky approved these changes Nov 26, 2023

View reviewed changes

isaacbrodsky mentioned this pull request Nov 27, 2023

polyfill flags isaacbrodsky/h3-duckdb#75

Closed

nrabinowitz merged commit 9af7218 into uber:master Nov 27, 2023

nrabinowitz deleted the polyfill-contained branch November 27, 2023 19:28

This was referenced Nov 27, 2023

Add additional modes for polygonToCells #775

Closed

About RFC: Polyfill modes release plan #772

Closed

Support different polyfill mode #275

Closed

Alternate maxPolygonToCellsSize implementation #805

Merged

rgbongocan mentioned this pull request Jan 23, 2024

feat: Bound dataset query to location search results worldbank/worldex#99

Merged

2 tasks

nrabinowitz mentioned this pull request Apr 12, 2024

polyfill - how to get all intersected h3 polygons uber/h3-py#354

Closed

zachasme mentioned this pull request Oct 11, 2024

Feature Request: h3_coverage or similar / Documentation update warning of centroid behavior postgis/h3-pg#158

Closed

Conversation

nrabinowitz commented Nov 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

coveralls commented Nov 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

nrabinowitz commented Nov 25, 2023

Uh oh!

michaelbrichko commented Dec 11, 2023

Uh oh!

nrabinowitz commented Dec 11, 2023

Uh oh!

michaelbrichko commented Dec 12, 2023

Uh oh!

brendan-morin commented Jan 25, 2024

Uh oh!

rmx90210 commented Apr 2, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

nrabinowitz commented Nov 4, 2023 •

edited

Loading

coveralls commented Nov 4, 2023 •

edited

Loading