All committers have signed the CLA.

coverage: 98.794% (-0.2%) from 99.013%
when pulling c3f3089 on holoskii:geodesic_coverage
into 8085979 on uber:master.

Thanks @holoskii for the contribution! Geodesic polyfill is an exciting addition that I think a lot of folks would use, myself included!

Please bear with us as we try to find the time to properly review this PR. Some initial questions from my end:

• Is it fair to characterize this PR as providing two major improvements:
  1. geodesic mode for "polyfill", for polygons that would otherwise already be well-handled in the existing planar mode in polygonToCellsExperimental, and
  2. the ability to do polyfill on polygons larger or tricker (e.g. around poles or the antimeridian) than those that could be handled in the previous algorithm (and, if so, would these improvements also generalize to the existing planar mode?)
• This may become obvious after I'm able to review more closely, but how much code can we share between the planar and geodesic algorithms?
• Is it necessary to expose Vec3d and GeodesicCellBoundary in the public api (h3api.h.in), or can we keep those structs internal?
• You mentioned that this mode is slower than the existing algorithm. How much slower? Do you have any example benchmarks you could share?
• Any thoughts on what to do about the failing CI checks? Or would you like some input from the team?

Fixes / changes

1. Introduce an explicit epsilon for the SphereCap check. The previous iteration relied on tolerance built into precomputed cosine values; in practice, we also need an additional epsilon.
2. Use GeodesicPolygon* instead of void* in the iterator structure.
3. Fix the MSVC build by using a macro instead of a constant.
4. Move GeodesicCellBoundary and Vec3d to their own headers instead of defining them in the public API header.
5. Move internal headers to the include directory.
6. Add a new geodesic benchmark.
7. Rebase on the latest master.

Performance

I added a dedicated geodesic benchmark that exercises small, medium, and large shapes.

• Small cells: up to 60× slower.
• Medium cells / large shapes: ~20×.
• “Primary” geodesic use case (huge shapes + large cells, e.g., NY ↔ London great-circle path): ~2.5×.

Notes:

• At Yellowbrick Data, we’ve seen ~10× performance improvements by pushing heavy inlining (by moving code to headers), branch hints, etc. I avoided invasive changes here to keep code style intact; the current PR aims for minimal intrusion.

Thanks @holoskii for the contribution! Geodesic polyfill is an exciting addition that I think a lot of folks would use, myself included!

Please bear with us as we try to find the time to properly review this PR. Some initial questions from my end:

* Is it fair to characterize this PR as providing two major improvements:
  
  1. geodesic mode for "polyfill", for polygons that would otherwise already be well-handled in the existing planar mode in `polygonToCellsExperimental`, and
  2. the ability to do polyfill on polygons larger or tricker (e.g. around poles or the antimeridian) than those that could be handled in the previous algorithm (and, if so, would these improvements also generalize to the existing planar mode?)

* This may become obvious after I'm able to review more closely, but how much code can we share between the planar and geodesic algorithms?

* Is it necessary to expose `Vec3d` and `GeodesicCellBoundary` in the public api (`h3api.h.in`), or can we keep those structs internal?

* You mentioned that this mode is slower than the existing algorithm. How much slower? Do you have any example benchmarks you could share?

* Any thoughts on what to do about the failing CI checks? Or would you like some input from the team?

1.1 - Yes.

1.2 - The geodesic approach behaves better for large polygons and near poles/antimeridian due to great-circle behavior, but it’s architecturally different from the planar path; there isn’t a practical feature we can “back-port” without re-implementing substantial pieces.

2 - We only share FaceIjk and iterator code between the two implementations. Intersection/containment logic and related optimization structures are written from scratch for the geodesic mode.

3 - Performance metrics are now included in the main PR comment (see “Performance” above) with the new benchmark.

A few small fixes for the CI:

• examples did not compile because of "constants.h" included in h3api.h. Removed that include to keep api header standalone
• fuzzer hit a legitimate timeout. Fixed this by limiting resolution and number of points for geodesic runs

@isaacbrodsky was right, separate fuzzer is a way to go. Old fuzzers left not enough time until timeout in each iteration. In the last commit I've added a separate geodesic fuzzer. PR is now fully ready for review

Hi @nrabinowitz @dfellis @isaacbrodsky - friendly bump on this.
Current state: fixed CI issues, added benchmarks, answered questions and addressed the comments.

Hi @nrabinowitz @dfellis @isaacbrodsky - friendly bump on this. Current state: fixed CI issues, added benchmarks, answered questions and addressed the comments.

Thanks for updating the PR and for the bump! We appreciate the contribution and know we need to review this, so it's just a matter of finding time to read through it in depth. We would like to bring this in for the next release of H3.

@holoskii Thanks for the update! I think CI is failing on the formatting assertion (needs make format with clang-format-14)

@holoskii Thanks for the update! I think CI is failing on the formatting assertion (needs make format with clang-format-14)

My update is a bit overdue, this year has been very busy so far 😅
I will address a few more comments (missed them in my first push), and then will use the correct formatter (I probably used wrong version)

Resolved final issues, formatted with version 14. Should be ready for the CI

2 small issues to raise after this PR is merged:

• deduplicate populateGeoLoop: Geodesic polygon coverage #1052 (comment)
• add more modes to geodesic coverage Geodesic polygon coverage #1052 (comment)

Windows workflow failed because on 32-bit Windows systems, the math library doesn't handle NaN inputs correctly. Instead of ignoring NaN data when building a bounding box, it lets the NaN poison the BBOX. This leads to us hitting NaN down the road and failing later.

I added a check at the very beginning, during polygon creation to catch invalid coordinates (NaN or Infinity). Now, we reject bad input right away with a clear error code (E_DOMAIN) instead of letting it break things further down the line.