8000 Add h3Distance, and internal h3ToIjk and ijkDistance by isaacbrodsky · Pull Request #83 · uber/h3 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Add h3Distance, and internal h3ToIjk and ijkDistance #83

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 8 commits into from
Jul 25, 2018
Merged

Add h3Distance, and internal h3ToIjk and ijkDistance #83

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
8 commits
Select commit Hold shift + click to select a range
58ee5c3
Add h3ToIjk, along with ijkDistance and h3Distance
Jun 22, 2018
e9eaec6
Make h3ToIjk and ijkDistance internal
Jul 2, 2018
b8fd4e8
Stack alloc in testH3ToIjk
Jul 2, 2018
b245905
Add some coverage of invalid mode, resolution cases
Jul 2, 2018
53ccd77
Change another case of calloc to stack alloc in tests
Jul 2, 2018
5924008
Refactor _getBaseCellDirection to its own function
Jul 11, 2018
d1deaa9
`_imax` is now a macro `MAX`
Jul 18, 2018
6b7299f
Add h3ToIjk filter application to changelog
Jul 19, 2018
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
5 changes: 5 additions & 0 deletions CHANGELOG.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -6,6 +6,11 @@ The public API of this library consists of the functions declared in file
[h3api.h](./src/h3lib/include/h3api.h).

## [Unreleased]
### Added
- `h3Distance` function for determining the grid distance between H3 indexes (#83)
- Internal `h3ToIjk` function for getting IJK+ coordinates from an index (#83)
- Internal `ijkDistance` function for determining the grid distance between IJK+ coordinates (#83)
- `h3ToIjk` filter application for experimenting with `h3ToIjk` (#83)

## [3.0.8] - 2018-07-18
### Added
Expand Down
4 changes: 4 additions & 0 deletions CMakeLists.txt
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -127,6 +127,7 @@ set(EXAMPLE_SOURCE_FILES
examples/edge.c)
set(OTHER_SOURCE_FILES
src/apps/filters/h3ToGeo.c
src/apps/filters/h3ToIjk.c
src/apps/filters/h3ToComponents.c
src/apps/filters/geoToH3.c
src/apps/filters/h3ToGeoBoundary.c
Expand Down Expand Up @@ -157,6 +158,7 @@ set(OTHER_SOURCE_FILES
src/apps/testapps/mkRandGeo.c
src/apps/testapps/testH3Api.c
src/apps/testapps/testH3SetToLinkedGeo.c
src/apps/testapps/testH3ToIjk.c
src/apps/miscapps/h3ToGeoBoundaryHier.c
src/apps/miscapps/h3ToGeoHier.c
src/apps/miscapps/generateBaseCellNeighbors.c
Expand Down Expand Up @@ -279,6 +281,7 @@ endmacro()
add_h3_executable(geoToH3 src/apps/filters/geoToH3.c ${APP_SOURCE_FILES})
add_h3_executable(h3ToComponents src/apps/filters/h3ToComponents.c ${APP_SOURCE_FILES})
add_h3_executable(h3ToGeo src/apps/filters/h3ToGeo.c ${APP_SOURCE_FILES})
add_h3_executable(h3ToIjk src/apps/filters/h3ToIjk.c ${APP_SOURCE_FILES})
add_h3_executable(h3ToGeoBoundary src/apps/filters/h3ToGeoBoundary.c ${APP_SOURCE_FILES})
add_h3_executable(hexRange src/apps/filters/hexRange.c ${APP_SOURCE_FILES})
add_h3_executable(kRing src/apps/filters/kRing.c ${APP_SOURCE_FILES})
Expand Down Expand Up @@ -454,6 +457,7 @@ if(BUILD_TESTING)
add_h3_test(testBBox src/apps/testapps/testBBox.c)
add_h3_test(testVec2d src/apps/testapps/testVec2d.c)
add_h3_test(testVec3d src/apps/testapps/testVec3d.c)
add_h3_test(testH3ToIjk src/apps/testapps/testH3ToIjk.c)

add_h3_test_with_arg(testH3NeighborRotations src/apps/testapps/testH3NeighborRotations.c 0)
add_h3_test_with_arg(testH3NeighborRotations src/apps/testapps/testH3NeighborRotations.c 1)
Expand Down
6 changes: 5 additions & 1 deletion src/apps/applib/include/utility.h
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
/*
* Copyright 2016-2017 Uber Technologies, Inc.
* Copyright 2016-2018 Uber Technologies, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
Expand Down Expand Up @@ -42,4 +42,8 @@ void geoBoundaryPrint(const GeoBoundary* b);
void geoBoundaryPrintln(const GeoBoundary* b);
int readBoundary(FILE* f, GeoBoundary* b);

void iterateAllIndexesAtRes(int res, void (*callback)(H3Index));
void iterateAllIndexesAtResPartial(int res, void (*callback)(H3Index),
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Again, C users would probably prefer macros here and you'll get better performance because C compiler can see what is going on in a macro, but function pointers are opaque. Side note: this is why using the C qsort in C++ is slower than std::sort from C++ STL, due to function pointers being worse off than templates.

Anyway, here's how I'd do it based on Jansson:

#define H3_FOR_EACH_INDEX_RES(argName, res) H3_FOR_EACH_INDEX_PARTIAL((res), NUM_BASE_CELLS)
#define H3_FOR_EACH_INDEX_PARTIAL(argName, res, baseCells) \
    assert((baseCells) <= NUM_BASE_CELLS); \
     for (int i = 0; i < baseCells; i++) { \
         H3Index bc; \
         setH3Index(&bc, 0, i, 0); \
         int childrenSz = H3_EXPORT(maxUncompactSize)(&bc, 1, (res)); \
         STACK_ARRAY_CALLOC(H3Index, children, childrenSz); \
         H3_EXPORT(uncompact)(&bc, 1, children, childrenSz, (res)); \
         for (int j = 0; j < childrenSz; j++) { \
             if (children[j] == 0) { \
                 continue; \
             } \
             H3Index argName = children[j];

Then users can do this:

H3_FOR_EACH_INDEX_AT_RES(1, myIndex) {
    printf("%lld\n", myIndex);
}

Which expands to:

for (...) {
    ...
    H3Index myIndex = children[j];
    printf("%lld\n", myIndex);
}

Copy link
Collaborator Author
@isaacbrodsky isaacbrodsky Jul 18, 2018 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'll change this, but I am not a huge fan of macros. Since this is a test, I don't think performance is that big a concern.

edit: also, this does not permit reusing the code for more than one resolution. That still needs to be a function call or another macro.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ya everyone hates macros until they program in C for a while and realize it's the only way to avoid seriously ugly code. Also, underrated technique: X macro.

Meanwhile, rethinking this API too so that the blocks have matching parentheses.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

OK seeing as this is a test I don't really think it's worth the effort. Thought this might lead to a convenience API in general. Never mind my suggestion.

int maxBaseCell);

#endif
36 changes: 35 additions & 1 deletion src/apps/applib/lib/utility.c
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
/*
* Copyright 2016-2017 Uber Technologies, Inc.
* Copyright 2016-2018 Uber Technologies, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
Expand All @@ -18,10 +18,13 @@
*/

#include "utility.h"
#include <assert.h>
#include <inttypes.h>
#include <stackAlloc.h>
#include <stdio.h>
#include <stdlib.h>
#include "geoCoord.h"
#include "h3Index.h"
#include "h3api.h"

void error(const char* msg) {
Expand Down Expand Up @@ -163,3 +166,34 @@ int readBoundary(FILE* f, GeoBoundary* b) {

return 0;
}

/**
* Call the callback for every index at the given resolution.
*/
void iterateAllIndexesAtRes(int res, void (*callback)(H3Index)) {
iterateAllIndexesAtResPartial(res, callback, NUM_BASE_CELLS);
}

/**
* Call the callback for every index at the given resolution in base
* cell 0 up to the given base cell number.
*/
void iterateAllIndexesAtResPartial(int res, void (*callback)(H3Index),
int baseCells) {
assert(baseCells <= NUM_BASE_CELLS);
for (int i = 0; i < baseCells; i++) {
H3Index bc;
setH3Index(&bc, 0, i, 0);
int childrenSz = H3_EXPORT(maxUncompactSize)(&bc, 1, res);
STACK_ARRAY_CALLOC(H3Index, children, childrenSz);
H3_EXPORT(uncompact)(&bc, 1, children, childrenSz, res);

for (int j = 0; j < childrenSz; j++) {
if (children[j] == 0) {
continue;
}

(*callback)(children[j]);
}
}
}
76 changes: 76 additions & 0 deletions src/apps/filters/h3ToIjk.c
View file
Open in desktop
C87E
Original file line number Diff line number Diff line change
@@ -0,0 +1,76 @@
/*
* Copyright 2018 Uber Technologies, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/** @file
* @brief stdin/stdout filter that converts from H3 indexes to relative IJK
* coordinates. This is experimental.
*
* usage: `h3ToIjk [origin]`
*
* The program reads H3 indexes from stdin and outputs the corresponding
* IJK coordinates to stdout, until EOF is encountered. The H3 indexes
* should be in integer form. `-1 -1 -1` is printed if the IJK coordinates
* could not be obtained.
*
* `origin` indicates the origin (or anchoring) index for the IJK coordinate
* space.
*/

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include "coordijk.h"
#include "h3Index.h"
#include "h3api.h"
#include "utility.h"

void doCell(H3Index h, H3Index origin) {
CoordIJK ijk;
if (h3ToIjk(origin, h, &ijk)) {
printf("-1 -1 -1\n");
} else {
printf("%d %d %d\n", ijk.i, ijk.j, ijk.k);
}
}

int main(int argc, char *argv[]) {
// check command line args
if (argc != 2) {
fprintf(stderr, "usage: %s [origin]\n", argv[0]);
exit(1);
}

H3Index origin;

if (!sscanf(argv[1], "%" PRIx64, &origin))
error("origin could not be read");

if (!H3_EXPORT(h3IsValid)(origin)) error("origin is invalid");

// process the indexes on stdin
char buff[BUFF_SIZE];
while (1) {
// get an index from stdin
if (!fgets(buff, BUFF_SIZE, stdin)) {
if (feof(stdin))
break;
else
error("reading H3 index from stdin");
}

H3Index h3 = H3_EXPORT(stringToH3)(buff);
doCell(h3, origin);
}
}
Loading
0