Git Product home page Git Product logo

h3's Introduction

H3 Logo

H3: A Hexagonal Hierarchical Geospatial Indexing System

test-linux test-macos test-windows test-website Coverage Status License

H3 is a geospatial indexing system using a hexagonal grid that can be (approximately) subdivided into finer and finer hexagonal grids, combining the benefits of a hexagonal grid with S2's hierarchical subdivisions.

Documentation is available at https://h3geo.org/. Developer documentation in Markdown format is available under the dev-docs directory.

Installing

We recommend using prebuilt bindings if they are available for your programming language. Bindings for Java, JavaScript, Python, and others are available.

On macOS, you can install H3 using brew:

brew install h3

Otherwise, to build H3 from source, please see the following instructions.

Building from source

Still here? To build the H3 C library, you'll need a C compiler (tested with gcc and clang), CMake, and Make. If you intend to contribute to H3, you must have clang-format installed and we recommend installing ccmake and LCOV to configure the cmake arguments to build and run the tests and generate the code coverage report. We also recommend using gcc for the code coverage as some versions of clang generate annotations that aren't compatible with lcov. Doxygen is needed to build the API documentation.

Install build-time dependencies

  • Alpine
# Installing the bare build requirements
apk add cmake make gcc libtool musl-dev
  • Debian/Ubuntu
# Installing the bare build requirements
sudo apt install cmake make gcc libtool
# Installing useful tools for development
sudo apt install clang-format cmake-curses-gui lcov doxygen
  • macOS (using brew)

First make sure you have the developer tools installed and then

# Installing the bare build requirements
brew install cmake
# Installing useful tools for development
brew install clang-format lcov doxygen
  • Windows (Visual Studio)

You will need to install CMake and Visual Studio, including the Visual C++ compiler. For building on Windows, please follow the Windows build instructions.

  • FreeBSD
# Installing the build requirements
sudo pkg install bash cmake gmake doxygen lcov

Compilation

When checking out the H3 Git repository, by default you will check out the latest development version of H3. When using H3 in an application, you will want to check out the most recently released version:

git checkout v$(<VERSION)

From the repository root, you can compile H3 with:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make

All subsequent make commands should be run from within the build directory.

Note: There are several ways to build H3 with CMake; the method above is just one example that restricts all build artifacts to the build directory.

You can install system-wide with:

sudo make install

If using the method above, from the repository root, you can clean all build artifacts with:

rm -rf build

Testing

After making the project, you can test with make test. You can run a faster test suite that excludes the most expensive tests with make test-fast.

Coverage

You can generate a code coverage report if lcov is installed, and if the project was built with the CMAKE_BUILD_TYPE=Debug and ENABLE_COVERAGE=ON options. For example, from a clean repository, you could run:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Debug -DENABLE_COVERAGE=ON ..
make
make coverage

You can then view a detailed HTML coverage report by opening coverage/index.html in your browser.

Benchmarks

You can run timing benchmarks by building with the CMAKE_BUILD_TYPE=Release, and running make benchmarks:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make
make benchmarks

Documentation

You can build developer documentation with make docs if Doxygen was installed when CMake was run. Index of the documentation will be dev-docs/_build/html/index.html.

After making the project, you can build KML files to visualize the hexagon grid with make kml. The files will be placed in KML.

To build the documentation website, see the website/ directory.

Usage

From the command line

To get the H3 index for some location:

./bin/latLngToCell --resolution 10 --latitude 40.689167 --longitude -74.044444

10 is the H3 resolution, between 0 (coarsest) and 15 (finest). The coordinates entered are the latitude and longitude, in degrees, you want the index for (these coordinates are the Statue of Liberty). You should get an H3 index as output, like 8a2a1072b59ffff.

You can then take this index and get some information about it, for example:

./bin/cellToBoundary --index 8a2a1072b59ffff

This will produce the vertices of the hexagon at this location:

8a2a1072b59ffff
{
   40.690058601 -74.044151762
   40.689907695 -74.045061792
   40.689270936 -74.045341418
   40.688785091 -74.044711031
   40.688935993 -74.043801021
   40.689572744 -74.043521377
}

You can get the center coordinate of the hexagon like so:

./bin/cellToLatLng --index 8a2a1072b59ffff

This will produce some coordinate:

40.6894218437 -74.0444313999

From C

The above features of H3 can also be used from C. For example, you can compile and run examples/index.c like so:

cc -lh3 examples/index.c -o example
./example

You should get output like:

The index is: 8a2a1072b59ffff
Boundary vertex #0: 40.690059, -74.044152
Boundary vertex #1: 40.689908, -74.045062
Boundary vertex #2: 40.689271, -74.045341
Boundary vertex #3: 40.688785, -74.044711
Boundary vertex #4: 40.688936, -74.043801
Boundary vertex #5: 40.689573, -74.043521
Center coordinates: 40.689422, -74.044431

Contributing

Pull requests and Github issues are welcome. Please see our contributing guide for more information.

Before we can merge your changes, you must agree to the Uber Contributor License Agreement.

Legal and Licensing

H3 is licensed under the Apache 2.0 License.

DGGRID Copyright (c) 2015 Southern Oregon University

h3's People

Contributors

ajfriend avatar alexey-milovidov avatar alien2150 avatar arnaudswail avatar dcj avatar dependabot[bot] avatar dfellis avatar gordonsmith avatar heshpdx avatar isaacbrodsky avatar isaachier avatar jatorre avatar jogly avatar neatlife avatar nmandery avatar nrabinowitz avatar realprimoh avatar richardvasquez avatar robsalasco avatar rpitonak avatar rustyconover avatar saprykin avatar seanhandley avatar sebisteiner avatar spaceim avatar temporalparts avatar travisbrady avatar wewei avatar wingyplus avatar zachasme avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

h3's Issues

Relation to DGGRID

In the README, I see:

DGGRID Copyright (c) 2015 Southern Oregon University

What is the relationship between H3 and DGGRID?

Segfault on h3SetToLinkedGeo for certain res 8 hexes

To repro:

LinkedGeoPolygon* polygon = calloc(1, sizeof(LinkedGeoPolygon));
H3Index set[] = {0x88ad36c547fffffl, 0x88ad36c467fffffl};
H3_EXPORT(h3SetToLinkedGeo)(set, 2, polygon);

No issues running h3ToGeoBoundary, both return 6 vertices.

The unidirectional edge getOrigin / getDestination functions should check validity

At present, the functions getOriginH3IndexFromUnidirectionalEdge and getDestinationH3IndexFromUnidirectionalEdge assume a valid edge. This leads to some weird behavior when non-edges are passed in:

getOriginH3IndexFromUnidirectionalEdge('891ea6d6533ffff'); // '891ea6d6533ffff'
getOriginH3IndexFromUnidirectionalEdge(0); // '800000000000000'

I don't think we need to call h3UnidirectionalEdgeIsValid, since it might(?) have more performance implications, but perhaps adding a bit check like

if (H3_GET_MODE(edge) != H3_UNIEDGE_MODE) {
  return H3_INVALID_INDEX;
}

would catch some common bad cases?

Distance calculation

Is it possible to calculate the distance in kilometers between the centers of two arbitrary hexagons using h3?

Projected coordinate system

For those functions related to latitude and longitude, is the projected coordinate system used as WGS84 or something?

Make fails

I'm trying to install the core libraries but make fails with the following:

Scanning dependencies of target h3ToGeoHier
[ 30%] Building C object CMakeFiles/h3ToGeoHier.dir/src/apps/miscapps/h3ToGeoHier.c.o
/home/cw/Code/h3/h3-master/src/apps/miscapps/h3ToGeoHier.c: In function โ€˜mainโ€™:
/home/cw/Code/h3/h3-master/src/apps/miscapps/h3ToGeoHier.c:133:37: error: โ€˜%sโ€™ directive writing up to 255 bytes into a region of size 251 [-Werror=format-overflow=]
                 sprintf(name, "Cell %s Res %d", index,
                                     ^~          ~~~~~
/home/cw/Code/h3/h3-master/src/apps/miscapps/h3ToGeoHier.c:133:17: note: โ€˜sprintfโ€™ output between 12 and 277 bytes into a destination of size 256
                 sprintf(name, "Cell %s Res %d", index,
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                         ((res <= rootRes) ? rootRes : res));
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cc1: all warnings being treated as errors
make[2]: *** [CMakeFiles/h3ToGeoHier.dir/build.make:63: CMakeFiles/h3ToGeoHier.dir/src/apps/miscapps/h3ToGeoHier.c.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:1512: CMakeFiles/h3ToGeoHier.dir/all] Error 2
make: *** [Makefile:141: all] Error 2

make shapefiles available

One idea that might help spread the use of h3 would be to make the shapefiles available on the github repo.

Apparent geoToH3 or H3ToGeo bug on master

I used geoToH3 to encode the coordinates for NYC and then ran the H3 hex string through H3toGeo and got a confusing result.
This is with a fresh clone of master built per readme instructions and running on a Mac.

$ ./bin/geoToH3 12
40.7128 -74.0060
8c2a107289061ff

Then

$ ./bin/h3ToGeo
8c2a107289061ff
40.7127470097 285.9940373051

Unless I misunderstand the purpose of these tools, 285.9940373051 is obviously an illegal value and far from the expected -74.0060.

$ uname -a
Darwin HA002727 16.7.0 Darwin Kernel Version 16.7.0: Thu Jun 15 17:36:27 PDT 2017; root:xnu-3789.70.16~2/RELEASE_X86_64 x86_64

How do I group hexagons with the same color?

Let's say I wanna create something similar to movements.uber (pic).

I.e. the task is to return a group of points for every connected polygon (connected means 'hexagons have the same color').

Originally I use polyfill to extract list hexagonId and then extract create
Hexagon { long hexagonId, Color color, List<Vector2D> vertices } -> List<Hexagon> hexagons

My current solution is to group these hexagons by color and then we kinda want to create a convex hull for a whole group of hexagons but the problem is that we can have multiple connected components. Is there a better option (some builtin methods) than to run bfs-like algorithms using a kring(distance=1) to separate these components?

Seeking geofence st_contains query alternative

using geofence polygon to judge one event is too complicated and slow in Hive by directly ESRI st_contains function, which means no index.

In that, I am seeking a better solution, for example, using H3 maxPolyfillSize function.

However, I can not find any example about using maxPolyfillSize function to be a st_contains alternative solution, need help.

By default, maxPolyfillSize will return multiple h3index resolutions and that means SQL need to join many times with resolution levels. Does any better solution exist?

Bindings to other languages

Thanks for supporting this work, and open sourcing it!

Do you have a timeframe for releasing bindings to other languages? My top 2 would be Python and Swift, and if those aren't high on the list for Uber, I'd probably get started working on them myself in the near future.

area/edge length functions appear to be incorrect

The area/edge length functions don't appear to be correct when compared with results from k-ring functions. Here is a sample program demonstrating the inconsistency:

int main(){
    GeoCoord sf; //san francisco
    sf.lat = 37.783333;
    sf.lon = -122.416667;

    GeoCoord mv; //mountain view
    mv.lat = 37.389444l;
    mv.lon = -122.081944;
    
    printf("distance = %g km\n",haversineDistance(degsToRads(sf.lat),degsToRads(sf.lon),degsToRads(mv.lat),degsToRads(mv.lon)));
    
    int res = 3;
    printf ("res = %d\n",res);
    printf("area at res = %g km^2\n",hexAreaKm2(res));
    printf("edge length at res = %g km\n",edgeLengthKm(res));
    
    H3Index h = geoToH3(&sf,res);
    H3Index t = geoToH3(&mv,res);
    
    //keep expanding k until we find t
    int k;
    for(k=0;k<100;k++){
        int max = maxKringSize(k);
        H3Index* out = (H3Index*) calloc(max,sizeof(H3Index));
        kRing(h,k,out);
        int n;
        for(n=0;n<max;n++){
            if(out[n]==t){
                printf("Found! k = %d\n",k);
                return 0;
            }
        }
        free(out);
    }
}

The output is:

distance = 52.8034 km
res = 3
area at res = 12392.3 km^2
edge length at res = 59.8109 km
Found! k = 32

This appears incorrect because at resolution = 3, if each hexagon has an edge length of ~60 km, it shouldn't take k = 32 to find a hexagon only ~53 km away.

Also, it is unclear how the area is calculated. A hexagon with side length 60 km should have an area of ~9353 km^2, according to Google. So where is the 12,392 km^2 coming from?

So it appears that the area/edge functions are incorrect.

Move GeoJSON normalization logic into core C lib

At present, the h3SetToLinkedGeo function produces a single polygon with multiple outer loops, without a guaranteed order. The correct GeoJSON output should only have one outer loop per polygon, and the order of loops within each polygon should be outer, hole, hole, ....

The logic for this is included in the (as yet unpublished) JS and Python bindings, but should be moved into the core C lib. The API of h3SetToLinkedGeo would not change, so this might not require a new API function, but its correctness guarantees would improve.

Logo design

Hi,
I have read your work so I decided to creat a logo for you. I hope you like it and you want to use it. I can give you all the formats of the design free. If you want to make changes please specify.

I used the colours of your website.

Greetings
h3

h3ToGeoBoundary returns duplicate points for some hexagons

Certain hexagons (including at least some on the edge of the icosahedron face) have duplicate points generated by h3ToGeoBoundary:

$ ./bin/h3ToGeoBoundary
894cc536537ffff
894cc536537ffff
{
   18.043333154 293.721634765
   18.042238363 293.720709372
   18.040818259 293.721458061
   18.040492975 293.723132133
   18.041040385 293.723594817
   18.041757122 293.724032885
   18.043007860 293.723308818
   18.043007860 293.723308818
}

The last two vertices here are duplicates. The repeated vertex causes problems in the generation of GeoJSON boundaries.

Will update this issue when I find more details on which hexagons are causing the problem.

Edge direction in getH3UnidirectionalEdgeBoundary is inconsistent

This may not be a big deal for most consumers, but the algorithm used for getH3UnidirectionalEdgeBoundary produces 5 edges that follow the direction of the origin's geo boundary output, and one edge that goes in the opposite direction (from the origin's vertex 5 to vertex 0).

Given that we might rewrite that algorithm to something more efficient in any case, it would be a useful requirement for the output that all edges follow consistent directionality.

Add vertex index modes

The proposal is to add two new index modes (set in the mode bits): H3_VERTEX_MODE and H3_ICOSAEDGE_VERTEX_MODE, to represent a shared vertex with an H3 index. The intent is that each vertex shared by 3 cells (or two in the case of edge distortion vertexes) would be represented by a single index.

The advantages of this approach:

  • Shared vertices can be compared between hexagons with a strict equality check
  • Vertices can be represented and stored without the trig calls required to produce a lat/lon point
  • Vertex to lat/lon can be guaranteed to return the same result across different cells that share the vertex

At a minimum, this should open up significant performance and accuracy gains in h3SetToLinkedGeo and getH3UnidirectionalEdgeBoundary, and there are likely other uses as well.

The format of the index would be:

  • The H3 index of the "owner" cell. The owner would be one of the cells that share the vertex, determined by rules TBD that would identify the same owner regardless of which of the neighbors was being queried. The main work here is determining which cell owns a given vertex, particularly across cell and icosahedron edges.
  • The mode set to H3_VERTEX_MODE (for corner vertices shared by 3 cells) or H3_ICOSAEDGE_VERTEX_MODE (for edge distortion vertices shared by 2 cells)
  • The reserved bits used to identify the index of the vertex on the owner cell, using the index order used by h3ToGeoBoundary (we only have 3 reserved bits, which is why we need two different vertex modes)

We'd want a small suite of functions for dealing with the vertices, including:

  • void getH3Vertex(H3Index h3, H3Vertex *vertices)
  • H3Vertex getH3Vertex(H3Index h3, int vertIndex)
  • GeoCoord h3VertexToGeoCoord(H3Vertex vertex)

GeoToH3 filter not picking up correct argument on Mac OS cli

Followed the instructions to build H3 from source on Mac OS, including sudo make install for global install.

Tried testing it with the example call:

geoToH3 10 40.689167 -74.044444

got back

usage: geoToH3 resolution

Looking at https://github.com/uber/h3/blob/master/src/apps/filters/geoToH3.c
lines 43 to 46:

seems like its printing the error message and then exiting if there are not 2 command line arguments... but aren't there meant to be 4?

Also, after adjusting that it started hanging in the while loop starting on line 60.

I'm not familiar with C, so debugging is slow going but will resume tomorrow.

However it does feel like some sort of weird compiler incompatibly.

Planned changes for 4.0.0

This is a tracking issue for any breaking changes that we plan to include in the next major version.

  • Rename kRing and remove hexRange, hexRanges, and maybe hexRing. (#42)
  • Change all functions that allocate blocks of memory or that could receive invalid input to return a success/error code (uber/h3-java#10, uber/h3-java#21)
    ** Error codes should have meaning, e.g. invalid was not a valid H3 index, etc. uber/h3-java#22
  • Consider accepting an allocator/free function for functions that must allocate memory (#100)

Alpine C Binding

hey guys,

I tried to compile h3 in a dockerized alpine environment. I added the requirements and run cmake but only getting this error message:

cmake .
-- The C compiler identification is GNU 6.4.0
-- The CXX compiler identification is Clang 5.0.1
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- broken
CMake Error at /usr/share/cmake/Modules/CMakeTestCCompiler.cmake:52 (message):
  The C compiler

    "/usr/bin/cc"

  is not able to compile a simple test program.

  It fails with the following output:

    Change Dir: /h3-master/CMakeFiles/CMakeTmp

    Run Build Command:"/usr/bin/make" "cmTC_8e320/fast"
    /usr/bin/make -f CMakeFiles/cmTC_8e320.dir/build.make CMakeFiles/cmTC_8e320.dir/build
    make[1]: Entering directory '/h3-master/CMakeFiles/CMakeTmp'
    Building C object CMakeFiles/cmTC_8e320.dir/testCCompiler.c.o
    /usr/bin/cc   -fPIE   -std=gnu11 -o CMakeFiles/cmTC_8e320.dir/testCCompiler.c.o   -c /h3-master/CMakeFiles/CMakeTmp/testCCompiler.c
    Linking C executable cmTC_8e320
    /usr/bin/cmake -E cmake_link_script CMakeFiles/cmTC_8e320.dir/link.txt --verbose=1
    /usr/bin/cc      -rdynamic CMakeFiles/cmTC_8e320.dir/testCCompiler.c.o  -o cmTC_8e320
    /usr/lib/gcc/x86_64-alpine-linux-musl/6.4.0/../../../../x86_64-alpine-linux-musl/bin/ld: cannot find Scrt1.o: No such file or directory
    /usr/lib/gcc/x86_64-alpine-linux-musl/6.4.0/../../../../x86_64-alpine-linux-musl/bin/ld: cannot find crti.o: No such file or directory
    /usr/lib/gcc/x86_64-alpine-linux-musl/6.4.0/../../../../x86_64-alpine-linux-musl/bin/ld: cannot find -lssp_nonshared
    collect2: error: ld returned 1 exit status
    make[1]: *** [CMakeFiles/cmTC_8e320.dir/build.make:87: cmTC_8e320] Error 1
    make[1]: Leaving directory '/h3-master/CMakeFiles/CMakeTmp'
    make: *** [Makefile:126: cmTC_8e320/fast] Error 2




  CMake will not be able to correctly generate this project.
Call Stack (most recent call first):
  CMakeLists.txt:50 (project)


-- Configuring incomplete, errors occurred!
See also "/h3-master/CMakeFiles/CMakeOutput.log".
See also "/h3-master/CMakeFiles/CMakeError.log".

I can paste the outout / error log if it helps.

Regards,
Thomas

Strange behaviour of h3SetToMultiPolygon()

I used this method in Java: public List<List<List<Vector2D>>> h3SetToMultiPolygon(Collection<Long> h3, boolean geoJson)

long hexagonId = core.geoToH3(40.7128, 74.0060, 5);
List<Long> hexagonIds = core.kRing(hexagonId, 2);
hexagonIds.removeAll(core.kRing(hexagonId, 1));
hexagonIds.add(hexagonId);
List<List<List<Vector2D>>> polygons = h3Core.h3SetToMultiPolygon(hexagonIds, true);

So basically I should get 2 polygons (one is a 'core' hexagon w/o holes, the other is a set of hexagons whose distance from 'core' hexagon is 2 with a hole). Here's what (pic) I received instead.

Here you can see the order is strange (I did receive only 1 polygon which has 1 outline and 2 holes, and the outline itself is arr[1] (not arr[0])).

What's wrong with my code or this method?

UPD: I found this in docs: At present, if the set of hexagons is not contiguous, this function will return a single polygon with multiple outer loops. The correct GeoJSON output should only have one outer loop per polygon. It appears that most GeoJSON consumers are fine with the first input format, but it's less correct than the second format. The function may be updated to produce multiple polygons in the future.

Could you specify what you meant by the first input format, but it's less correct than the second format?

Doxygen docs on readthedocs.org

I'm making this an issue because I'm not sure if there's some other mechanism Uber plans to host documentation for OSS projects, but it seems reasonable to me for the h3 docs to be on readthedocs.org

Here's the official getting started page and here's a stackoverflow answer on how to integrate with doxygen

I will also note that readthedocs needs an account set up, so it probably would have to be someone at Uber to do this, but I can help review things if you decide to go with it.

h3ToGeoBoundary sometimes returns octagon

While trying to track down some unexpected behavior from making shapefiles from polyfill objects, I came across an octagon at address '83a350fffffffff'. The error came up while making shapefiles in h3-java, but after finding the same result in h3-python, I compiled today's version of H3 core, and found it there, too.

Hexbin some data

Knowing the complexity of the library, what do you think would be the efficient way to aggregate data from polygons into hexagonal shapes, taking into account the degree of overlapping?

For example, translating:

Zip code Count
10001 10
10002 3
10003 14

into:

Hash Count
8a2a1072b59ffff 3
8a2a1072b59ffee 5
8a2a1072b59ffdd 3
8a2a1072b59ffcc 2
8a2a1072b59ffbb 2

h3ToGeoBoundary could be used, and then classic methods to compute the overlap between each shape. But the complexity looks pretty high for that.

Add Windows and Mac OS X CI Support

A few pull requests (especially those by @isaachier ) have been blocked because the change breaks compiling on Windows, but there's no obvious way to be sure of this right now, since Travis CI doesn't support Windows (but does support OS X).

It appears that it might make sense to use Microsoft's free Visual Studio Team Services Continuous Integration for Windows support. There are instructions for setting up both gcc-based and visual studio-based testing.

Microsoft's CI solution supposedly also supports Linux testing, but not OS X testing, and I also couldn't find anything about code coverage reporting, so I think it would still be required to keep Travis CI (and turn on OS X testing, ideally), but a second testing integration and badge could be added for the runs on Windows.

Again, this is something that I would like to help on, but most likely Uber would want to own the Microsoft CI account.

I think I can do the OS X integration, however, if we want to split this into two tasks.

Include defined constants for current library version in h3Api header

Per discussion in #104:

it would be great to have defines for the version number in the h3api.h header file. For example something like

#define H3_VERSION_MAJOR 4
#define H3_VERSION_MINOR 0
#define H3_VERSION_PATCH 0

would really help projects depending on this library to deal with the API-change.

Ideally this would generated from the VERSION file.

Incorrect results from polyfill

I've been having a conversation with @nrabinowitz on SO about unexpected results from polyfill.

I noticed the issue while working in h3-java, but my results are consistent with h3-py and h3-js. I get similar (looking) results at resolutions 2, 3, and 4.

Using the same GeoJSON input asking for a polyfill, @nrabinowitz gets 282 correct-looking hexes at resolution 3. I get 349 hexes, none of which have the same address as his 282. I posted a .csv with his results vs mine.

I've tried installing later versions of H3Core and bumped the initial Java version from 3.0.2 (when I started) to 3.0.4 but I got the same (incorrect) results.

Aperture 3

Very exciting tool! One question, why is it called h3 if you use aperture 7? Did you originally use aperture 3? Or do you have aperture 3 support in the pipeline? Just curious.

naming "k-ring"

Internally H3 uses an IJK hex coordinate system, where each hex coordinate has a k-component. So it seems confusing to me to use "k-ring" to refer to an unrelated concept. Have you considered changing to a different label for that concept?

I have mostly dealt with the similar concept of the ring of hexagons at exactly the same metric distance from a central cell. I used to call this an "r-ring", for "radius". But r is too convenient for grid resolution, so I switched to "d-ring", for distance. Lately I've been moving towards referring to grid precision, rather than resolution, as I think that more precisely expresses the situation from the standpoint of the data structure. Then p for "precision" leaves r available for "r-ring". But alas I was still on the fence on resolution/precision when I worked on H3, so I used resolution in naming. But I offer up those alternatives for k-ring; I'd synchronize my terminology with H3 going forward if you chose something other than k-ring.

How do I create a GTA-like circle area instead of hexagon area?

I'm using k-ring method and it returns a hexagon area. How can I nicely exclude some hexagons so it'll look like a circle? I'd probably have to .filterevery hexagon based on its distance from a center (and convert lat, lon to km so I'll be able to use a desired radius).

Does this issue rely on #23?

Why C11?

Does this library use any C11 feature? Mostly out of curiosity, but also because people are more likely to get along with a C99 library than a C11 library (especially true on Windows from what I gather).

Add bidirectional edge mode

It occurred to me that it would be trivial to add a bidirectional edge mode (I would have preferred "directed" and "undirected", but we already have "unidirectional"), just by taking the unidirectional edge of the lower H3 index in a given pair of cells. I don't have use cases in mind yet, but it seems like a useful primitive, and it's simple to implement on top of the unidirectional functions.

If we had a more efficient version of getH3UnidirectionalEdgeBoundary this might allow an even simpler optimization for h3SetToLinkedGeo than vertex mode.

polyfill not filling the complete polygon

Hello,

I just stumbled on an issue where the polyfill function is not able to fully fill polygons. The problem affects long, diagonal polygons, like this:

bug-r13

The blue part is the polygon, the green shape are the generated hexagons. Here is a closeup of the lower end of the polygon:

bug-r13-close

The polyfill was done at resolution 13. Interestingly the result at resolution 12 looks much better:

bug-r12-close

The GeoJSON for my test polygon is

{"type":"Polygon","coordinates":[[[5.76910652153309,51.1122595579185],[5.74843667987113,51.0844285870957],[5.74868565718131,51.0841156106137],[5.76939661923247,51.1120877871771],[5.76910652153309,51.1122595579185]]]}

To further investigate this issue I went ahead and removed the line of code which does the removal of heaxgons located outside the polygon in this file:

out[i] = H3_INVALID_INDEX;

I took this approach because I wondered about the clean cut at the end of the filled part and wanted to see in which radius H3 is generating it indexes.

Running polyfill on my test polygon again gave the following results:

Resolution 12:

hack-r12

Resolution 13:

hack-r13

So the filled minK hex radius seems to be a bit too small for this case. I gave it a try and changed the 1.5 multiplicator in

return (int)ceil(bboxRadiusKm / (1.5 * centerHexRadiusKm));

to the - wildly guessed value - 1.35:

return (int)ceil(bboxRadiusKm / (1.35 * centerHexRadiusKm));

This value is certainly not mathematically correct and needs to be validated. It also increases the number of indexes being generated, but gave me a polygon completely covered in indexes:

hack-r13-crude-fix

So I assume the issue is in the bboxHexRadius function in combination with filling shapes with a large number of indexes. This function seems to have some deficits dealing with long, thin, diagonal shapes.
I did not notice any issues when using polyfill with rounder geometries.

`make coverage` segfaults on Linux

Hey @isaacbrodsky :) The testCompact test in code coverage mode currently segfaults in Linux (Kubuntu 17.04) on both gcc and clang.

I'll try to figure it out and fix it if I can, but you'll probably run into the same thing when you're getting coveralls set up, so I thought I'd give you a heads up.

damocles@Talyn:~/oss/h3(master)$ make coverage
[  1%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/algos.c.o
[  1%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/baseCells.c.o
[  1%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/bbox.c.o
[  2%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/coordijk.c.o
[  2%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/faceijk.c.o
[  2%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/geoCoord.c.o
[  3%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/h3Index.c.o
[  3%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/h3IndexFat.c.o
[  3%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/h3UniEdge.c.o
[  5%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/h3api.c.o
[  5%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/linkedGeo.c.o
[  5%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/mathExtensions.c.o
[  6%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/vec2d.c.o
[  6%] Building C object CMakeFiles/h3.1.dir/src/h3lib/lib/vertexGraph.c.o
[  6%] Linking C shared library lib/libh3.1.so
[  6%] Built target h3.1
[  6%] Building C object CMakeFiles/testH3ToGeoBoundary.dir/src/apps/testapps/testH3ToGeoBoundary.c.o
[  7%] Building C object CMakeFiles/testH3ToGeoBoundary.dir/src/apps/applib/lib/kml.c.o
[  7%] Building C object CMakeFiles/testH3ToGeoBoundary.dir/src/apps/applib/lib/test.c.o
[  7%] Building C object CMakeFiles/testH3ToGeoBoundary.dir/src/apps/applib/lib/utility.c.o
[  9%] Linking C executable bin/testH3ToGeoBoundary
[  9%] Built target testH3ToGeoBoundary
[  9%] Zeroing counters
Deleting all .da files in /home/damocles/oss/h3 and subdirectories
Done.
[  9%] Built target clean-coverage
[  9%] Running testH3ToGeoBoundary_coverage47
[  9%] Built target testH3ToGeoBoundary_coverage47
[ 10%] Building C object CMakeFiles/testLinkedGeo.dir/src/apps/testapps/testLinkedGeo.c.o
[ 10%] Building C object CMakeFiles/testLinkedGeo.dir/src/apps/applib/lib/kml.c.o
[ 10%] Building C object CMakeFiles/testLinkedGeo.dir/src/apps/applib/lib/test.c.o
[ 11%] Building C object CMakeFiles/testLinkedGeo.dir/src/apps/applib/lib/utility.c.o
[ 11%] Linking C executable bin/testLinkedGeo
[ 11%] Built target testLinkedGeo
[ 11%] Running testLinkedGeo_coverage92
[ 11%] Built target testLinkedGeo_coverage92
[ 12%] Building C object CMakeFiles/testH3SetToLinkedGeo.dir/src/apps/testapps/testH3SetToLinkedGeo.c.o
[ 12%] Building C object CMakeFiles/testH3SetToLinkedGeo.dir/src/apps/applib/lib/kml.c.o
[ 12%] Building C object CMakeFiles/testH3SetToLinkedGeo.dir/src/apps/applib/lib/test.c.o
[ 14%] Building C object CMakeFiles/testH3SetToLinkedGeo.dir/src/apps/applib/lib/utility.c.o
[ 14%] Linking C executable bin/testH3SetToLinkedGeo
[ 14%] Built target testH3SetToLinkedGeo
[ 14%] Running testH3SetToLinkedGeo_coverage90
[ 14%] Built target testH3SetToLinkedGeo_coverage90
[ 15%] Building C object CMakeFiles/testH3Api.dir/src/apps/testapps/testH3Api.c.o
[ 15%] Building C object CMakeFiles/testH3Api.dir/src/apps/applib/lib/kml.c.o
[ 15%] Building C object CMakeFiles/testH3Api.dir/src/apps/applib/lib/test.c.o
[ 16%] Building C object CMakeFiles/testH3Api.dir/src/apps/applib/lib/utility.c.o
[ 16%] Linking C executable bin/testH3Api
[ 16%] Built target testH3Api
[ 16%] Running testH3Api_coverage89
[ 16%] Built target testH3Api_coverage89
[ 18%] Building C object CMakeFiles/testH3ToParent.dir/src/apps/testapps/testH3ToParent.c.o
[ 18%] Building C object CMakeFiles/testH3ToParent.dir/src/apps/applib/lib/kml.c.o
[ 18%] Building C object CMakeFiles/testH3ToParent.dir/src/apps/applib/lib/test.c.o
[ 19%] Building C object CMakeFiles/testH3ToParent.dir/src/apps/applib/lib/utility.c.o
[ 19%] Linking C executable bin/testH3ToParent
[ 19%] Built target testH3ToParent
[ 19%] Running testH3ToParent_coverage84
[ 19%] Built target testH3ToParent_coverage84
[ 20%] Building C object CMakeFiles/testH3ToChildren.dir/src/apps/testapps/testH3ToChildren.c.o
[ 20%] Building C object CMakeFiles/testH3ToChildren.dir/src/apps/applib/lib/kml.c.o
[ 20%] Building C object CMakeFiles/testH3ToChildren.dir/src/apps/applib/lib/test.c.o
[ 22%] Building C object CMakeFiles/testH3ToChildren.dir/src/apps/applib/lib/utility.c.o
[ 22%] Linking C executable bin/testH3ToChildren
[ 22%] Built target testH3ToChildren
[ 22%] Running testH3ToChildren_coverage85
[ 22%] Built target testH3ToChildren_coverage85
[ 23%] Building C object CMakeFiles/testHexRanges.dir/src/apps/testapps/testHexRanges.c.o
[ 23%] Building C object CMakeFiles/testHexRanges.dir/src/apps/applib/lib/kml.c.o
[ 23%] Building C object CMakeFiles/testHexRanges.dir/src/apps/applib/lib/test.c.o
[ 24%] Building C object CMakeFiles/testHexRanges.dir/src/apps/applib/lib/utility.c.o
[ 24%] Linking C executable bin/testHexRanges
[ 24%] Built target testHexRanges
[ 24%] Running testHexRanges_coverage83
[ 24%] Built target testHexRanges_coverage83
[ 25%] Building C object CMakeFiles/testHexRing.dir/src/apps/testapps/testHexRing.c.o
[ 25%] Building C object CMakeFiles/testHexRing.dir/src/apps/applib/lib/kml.c.o
[ 25%] Building C object CMakeFiles/testHexRing.dir/src/apps/applib/lib/test.c.o
[ 27%] Building C object CMakeFiles/testHexRing.dir/src/apps/applib/lib/utility.c.o
[ 27%] Linking C executable bin/testHexRing
[ 27%] Built target testHexRing
[ 27%] Running testHexRing_coverage82
[ 27%] Built target testHexRing_coverage82
[ 28%] Building C object CMakeFiles/testKRing.dir/src/apps/testapps/testKRing.c.o
[ 28%] Building C object CMakeFiles/testKRing.dir/src/apps/applib/lib/kml.c.o
[ 28%] Building C object CMakeFiles/testKRing.dir/src/apps/applib/lib/test.c.o
[ 29%] Building C object CMakeFiles/testKRing.dir/src/apps/applib/lib/utility.c.o
[ 29%] Linking C executable bin/testKRing
[ 29%] Built target testKRing
[ 29%] Running testKRing_coverage81
[ 29%] Built target testKRing_coverage81
[ 29%] Running testH3ToGeoBoundary_coverage78
[ 29%] Built target testH3ToGeoBoundary_coverage78
[ 29%] Running testH3ToGeoBoundary_coverage77
[ 29%] Built target testH3ToGeoBoundary_coverage77
[ 31%] Running testH3ToGeoBoundary_coverage76
[ 31%] Built target testH3ToGeoBoundary_coverage76
[ 31%] Running testH3ToGeoBoundary_coverage74
[ 31%] Built target testH3ToGeoBoundary_coverage74
[ 31%] Running testH3ToGeoBoundary_coverage69
[ 31%] Built target testH3ToGeoBoundary_coverage69
[ 31%] Running testH3ToGeoBoundary_coverage68
[ 31%] Built target testH3ToGeoBoundary_coverage68
[ 31%] Running testH3ToGeoBoundary_coverage75
[ 31%] Built target testH3ToGeoBoundary_coverage75
[ 32%] Running testH3ToGeoBoundary_coverage67
[ 32%] Built target testH3ToGeoBoundary_coverage67
[ 32%] Running testH3ToGeoBoundary_coverage65
[ 32%] Built target testH3ToGeoBoundary_coverage65
[ 32%] Running testH3ToGeoBoundary_coverage63
[ 32%] Built target testH3ToGeoBoundary_coverage63
[ 32%] Running testH3ToGeoBoundary_coverage62
[ 32%] Built target testH3ToGeoBoundary_coverage62
[ 32%] Running testH3ToGeoBoundary_coverage60
[ 32%] Built target testH3ToGeoBoundary_coverage60
[ 32%] Building C object CMakeFiles/testCompact.dir/src/apps/testapps/testCompact.c.o
[ 33%] Building C object CMakeFiles/testCompact.dir/src/apps/applib/lib/kml.c.o
[ 33%] Building C object CMakeFiles/testCompact.dir/src/apps/applib/lib/test.c.o
[ 33%] Building C object CMakeFiles/testCompact.dir/src/apps/applib/lib/utility.c.o
[ 35%] Linking C executable bin/testCompact
[ 35%] Built target testCompact
[ 35%] Running testCompact_coverage80
Segmentation fault
CMakeFiles/testCompact_coverage80.dir/build.make:57: recipe for target 'CMakeFiles/testCompact_coverage80' failed
make[3]: *** [CMakeFiles/testCompact_coverage80] Error 139
CMakeFiles/Makefile2:1232: recipe for target 'CMakeFiles/testCompact_coverage80.dir/all' failed
make[2]: *** [CMakeFiles/testCompact_coverage80.dir/all] Error 2
CMakeFiles/Makefile2:1835: recipe for target 'CMakeFiles/coverage.dir/rule' failed
make[1]: *** [CMakeFiles/coverage.dir/rule] Error 2
Makefile:812: recipe for target 'coverage' failed
make: *** [coverage] Error 2
damocles@Talyn:~/oss/h3(master)$

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.