uber / h3-java

Java bindings for H3, a hierarchical hexagonal geospatial indexing system
https://uber.github.io/h3/
Apache License 2.0
283 stars 54 forks source link

Compact Cells Failing on Certain Large Polygons #131

Open aburtch1 opened 1 year ago

aburtch1 commented 1 year ago

We have observed that after version 3.7.0 that certain large polygons are failing the compactCells methods with the following error: `com.uber.h3core.exceptions.H3Exception: Resolution argument was outside of acceptable range

at com.uber.h3core.NativeMethods.compactCells(Native Method)
at com.uber.h3core.H3Core.compactCells(H3Core.java:781)`

We are using a resolution of 6 which produces the same error but has 1.5 million in the collection. Here is the collection Long we are sending to compactCells on resolution 1: [581487719465615359, 582222193232969727, 581193050349371391, 582613619372457983, 581927524116725759, 581584476488859647, 581241428860993535, 581289807372615679, 581681233512103935, 581729612023726079, 581434942907482111, 582169416674836479, 581483321419104255, 582217795186458623, 581188652302860287, 581923126070214655, 581580078442348543, 581237030814482431, 581285409326104575, 581676835465592831, 581725213977214975, 581087497233104895, 582165018628325375, 581478923372593151, 581184254256349183, 582604823279435775, 581918728023703551, 581575680395837439, 581232632767971327, 582015485046947839, 581672437419081727, 581720815930703871, 581426146814459903, 581083099186593791, 581474525326082047, 581179856209838079, 581571282349326335, 581228234721460223, 581716417884192767, 581078701140082687, 581470127279570943, 582204601046925311, 581566884302815231, 581223836674949119, 582006688953925631, 581663641326059519, 581712019837681663, 581025924581949439, 581074303093571583, 582200203000414207, 582248581512036351, 581219438628438015, 581659243279548415, 580973148023816191, 581707621791170559, 581461331186548735, 582244183465525247, 581215040581926911, 581654845233037311, 581311797605171199, 582389319000391679, 581017128488927231, 581945116302770175, 581650447186526207, 581307399558660095, 581698825698148351, 581012730442416127, 581452535093526527, 581940718256259071, 581646049140015103, 581303001512148991, 581694427651637247, 581008332395905023, 581448137047015423, 581201846442393599, 581936320209747967, 581593272581881855, 581641651093503999, 581298603465637887, 581690029605126143, 581003934349393919, 581443739000504319, 581100691372638207, 582178212767858687, 582226591279480831, 581197448395882495, 581931922163236863, 581588874535370751, 582323348302725119, 581637253046992895, 581294205419126783, 581685631558615039, 581734010070237183, 581439340953993215]

isaacbrodsky commented 1 year ago

I can confirm I'm able to reproduce on master with the following test, and that this does not fail on 3.x h3-py:

  @Test
  public void testCompactReported() {
    Collection<String> start =
        ImmutableList.of(
            "811dbffffffffff",
            "81477ffffffffff",
            "810cfffffffffff",
            "815dbffffffffff",
            "8136bffffffffff",
            "81233ffffffffff",
            "810fbffffffffff",
            "81127ffffffffff",
            "8128bffffffffff",
            "812b7ffffffffff",
            "811abffffffffff",
            "81447ffffffffff",
            "811d7ffffffffff",
            "81473ffffffffff",
            "810cbffffffffff",
            "81367ffffffffff",
            "8122fffffffffff",
            "810f7ffffffffff",
            "81123ffffffffff",
            "81287ffffffffff",
            "812b3ffffffffff",
            "8106fffffffffff",
            "81443ffffffffff",
            "811d3ffffffffff",
            "810c7ffffffffff",
            "815d3ffffffffff",
            "81363ffffffffff",
            "8122bffffffffff",
            "810f3ffffffffff",
            "813bbffffffffff",
            "81283ffffffffff",
            "812afffffffffff",
            "811a3ffffffffff",
            "8106bffffffffff",
            "811cfffffffffff",
            "810c3ffffffffff",
            "81227ffffffffff",
            "810efffffffffff",
            "812abffffffffff",
            "81067ffffffffff",
            "811cbffffffffff",
            "81467ffffffffff",
            "81223ffffffffff",
            "810ebffffffffff",
            "813b3ffffffffff",
            "8127bffffffffff",
            "812a7ffffffffff",
            "81037ffffffffff",
            "81063ffffffffff",
            "81463ffffffffff",
            "8148fffffffffff",
            "810e7ffffffffff",
            "81277ffffffffff",
            "81007ffffffffff",
            "812a3ffffffffff",
            "811c3ffffffffff",
            "8148bffffffffff",
            "810e3ffffffffff",
            "81273ffffffffff",
            "8113bffffffffff",
            "8150fffffffffff",
            "8102fffffffffff",
            "8137bffffffffff",
            "8126fffffffffff",
            "81137ffffffffff",
            "8129bffffffffff",
            "8102bffffffffff",
            "811bbffffffffff",
            "81377ffffffffff",
            "8126bffffffffff",
            "81133ffffffffff",
            "81297ffffffffff",
            "81027ffffffffff",
            "811b7ffffffffff",
            "810d7ffffffffff",
            "81373ffffffffff",
            "8123bffffffffff",
            "81267ffffffffff",
            "8112fffffffffff",
            "81293ffffffffff",
            "81023ffffffffff",
            "811b3ffffffffff",
            "8107bffffffffff",
            "8144fffffffffff",
            "8147bffffffffff",
            "810d3ffffffffff",
            "8136fffffffffff",
            "81237ffffffffff",
            "814d3ffffffffff",
            "81263ffffffffff",
            "8112bffffffffff",
            "8128fffffffffff",
            "812bbffffffffff",
            "811afffffffffff");
    h3.compactCellAddresses(start);
  }

I wasn't able to test on h3-py 4.x as it does not include the fix for a previous issue with compactCells (in 4.0.1). So I used the following test in the C core library, also on current master:

    TEST(compactCells_reported) {
        H3Index cells[] = {
            581487719465615359, 582222193232969727, 581193050349371391,
            582613619372457983, 581927524116725759, 581584476488859647,
            581241428860993535, 581289807372615679, 581681233512103935,
            581729612023726079, 581434942907482111, 582169416674836479,
            581483321419104255, 582217795186458623, 581188652302860287,
            581923126070214655, 581580078442348543, 581237030814482431,
            581285409326104575, 581676835465592831, 581725213977214975,
            581087497233104895, 582165018628325375, 581478923372593151,
            581184254256349183, 582604823279435775, 581918728023703551,
            581575680395837439, 581232632767971327, 582015485046947839,
            581672437419081727, 581720815930703871, 581426146814459903,
            581083099186593791, 581474525326082047, 581179856209838079,
            581571282349326335, 581228234721460223, 581716417884192767,
            581078701140082687, 581470127279570943, 582204601046925311,
            581566884302815231, 581223836674949119, 582006688953925631,
            581663641326059519, 581712019837681663, 581025924581949439,
            581074303093571583, 582200203000414207, 582248581512036351,
            581219438628438015, 581659243279548415, 580973148023816191,
            581707621791170559, 581461331186548735, 582244183465525247,
            581215040581926911, 581654845233037311, 581311797605171199,
            582389319000391679, 581017128488927231, 581945116302770175,
            581650447186526207, 581307399558660095, 581698825698148351,
            581012730442416127, 581452535093526527, 581940718256259071,
            581646049140015103, 581303001512148991, 581694427651637247,
            581008332395905023, 581448137047015423, 581201846442393599,
            581936320209747967, 581593272581881855, 581641651093503999,
            581298603465637887, 581690029605126143, 581003934349393919,
            581443739000504319, 581100691372638207, 582178212767858687,
            582226591279480831, 581197448395882495, 581931922163236863,
            581588874535370751, 582323348302725119, 581637253046992895,
            581294205419126783, 581685631558615039, 581734010070237183,
            581439340953993215};
        H3Index out[94];
        t_assert(H3_EXPORT(compactCells)(cells, out, 94) == E_RES_DOMAIN,
                 "expected");
    }

This test showed that this behavior (returning an error on this input) exists in the core library and is not binding specific.

Since all the cells in your test appear to be valid resolution 1 cells with no duplicates, this will require additional debugging to get to the bottom of it.