uber / h3 / 6710188823

99%

push

github

Alternate polygonToCells algorithm (#785)

This PR implements an alternate algorithm for `polygonToCells`, which provides `polygonToCompactCells` as a byproduct.

### Algorithm Overview
```
let cell = base cell 0
while cell:
  res = getResolution(cell)
  if res == target res:
     if cell is in polygon:
        set output to cell and return
  if res < target res:
     let bbox = boundingBox(cell) // where bbox is padded to contain all descendants
     if bbox intersects polygon:
        if bbox is contained by polygon:
          set output to cell and return
        cell = first child of cell
        continue
  cell = next cell // where "next" is the next sibling, or next sibling of parent, etc
when cell is null we're done
```

### Results
 -  This PR includes an iterator-based algo with full test parity to the current algorithm. In its iterator form, it takes very little memory and that memory does not scale with the size of the output - so we can stream cells out of a very large polyfill process without worrying about memory issues.
- The new algo gives compact (or nearly compact) output by default, so we get `polygonToCellsCompact` effectively for free.
- The performance isn't exactly better or worse than the current algorithm - it just has different characteristics. In benchmarks, it's faster than the current algorithm in roughly 80% of cases

1589 of 1623 branches covered (0.0%)

Branch coverage included in aggregate %.

260 of 260 new or added lines in 5 files covered. (100.0%)

2717 of 2736 relevant lines covered (99.31%)

36322378.43 hits per line