add distance utility functions

[jogly]

from discussion in #18, it could be useful to add the following utilities to the core:

• geoDistKm
• geoDistRads
• h3DistKm
• h3DistRads

[dfellis]

I have one more proposed H3 distance function: h3KDistance. And I think I finally have an algorithm for this "grail." :)

Think of this: Two hexagons that are neighbors have a k distance of one. The k distance of any child to any other children is anywhere from 1 to 5 (for both hexes and pentagons, this can just be exhaustively proven on a whiteboard). The precise number depends on the which hexagon you're talking about relative to each center. The k distance between any children of a particular hexagon is 1 to 3.

We can make a log7(n) algorithm to find the k distance between any two hexagons by starting at their base cells, finding the k distance there, and then drilling down, using the traversal directions of the base cells in both directions to narrow down the answer at each level to the correct price on at that level, then splitting it up to the children and repeating where the new estimate is equal to the old k distance calculated k' minus 2 times 3 plus (1..5), and then figure out that last part based on the relative positions of the child hexagons versus the parent neighbor on the k path.

I wish I could draw a diagram to show you guys. :) Maybe another day since it's super late and I just had to write this down before going to bed.

[sahrk]

Note that cpi index subtraction and magnitude operations are basically per-digit table look-ups (plus some integer arithmetic for magnitude). So I think what you are describing is equivalent to subtracting the two cpi indexes to get a cpi "difference vector", and then taking it's magnitude.

On Sat, Feb 3, 2018 at 12:57 AM, David Ellis [email protected] wrote:

I have one more proposed H3 distance function: h3KDistance. And I think I finally have an algorithm for this "grail." :)

Think of this: Two hexagons that are neighbors have a k distance of one. The k distance of any child to any other children is anywhere from 1 to 5 (for both hexes and pentagons, this can just be exhaustively proven on a whiteboard). The precise number depends on the which hexagon you're talking about relative to each center. The k distance between any children of a particular hexagon is 1 to 3.

We can make a log7(n) algorithm to find the k distance between any two hexagons by starting at their base cells, finding the k distance there, and then drilling down, using the traversal directions of the base cells in both directions to narrow down the answer at each level to the correct price on at that level, then splitting it up to the children and repeating where the new estimate is equal to the old k distance calculated k' minus 2 times 3 plus (1..5), and then figure out that last part based on the relative positions of the child hexagons versus the parent neighbor on the k path.

I wish I could draw a diagram to show you guys. :) Maybe another day since it's super late and I just had to write this down before going to bed.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/uber/h3/issues/23#issuecomment-362791741, or mute the thread https://github.com/notifications/unsubscribe-auth/AMcSoOxewDt2jvvPcIxo0PxxSaU9uJ8dks5tRB9tgaJpZM4RxMMw .

[isaacbrodsky]

@dfellis it would definitely be great to discuss this in person with the ability to draw what we're discussing. :)

Doing the large-scale distances at a base cell level makes sense to me. I had previously been thinking about icosahedron unfolding for this kind of purpose, but I realize that has the disadvantages of triangle neighbor traversal, which is more complicated, as well as not being directly done on the indexes. Using base cell k-rings, it should be possible to determine the distance between two base cells and the necessary reorientation.

It seems to me that for pentagon cells, a different set of lookup tables, as mentioned by @sahrk, could be used, to account for the deleted coordinate space. Does this match what you're thinking?

[dfellis]

Hi @sahrk :) To be honest I'm not sure if we're talking about the same thing. I'm referring to the minimum number of hexagons needed to be crossed ("k"rossed?) to get from hex A to hex B. It certainly wouldn't surprise me if there's multiple ways to solve this problem, and it is certainly similar in the sense that I'm trying to traverse the virtual tree (with a bit of special logic at the base cell layer).

Also after thinking about it more, it is still a bit more complex because the number of hops the children need to take can sometimes be two instead of three, and the number of times depends on the angle between the origin and destination cell versus the major edge being crossed.

I have some handwritten notes at home that I'll scan in. Because it's still discrete math, I think it should be possible to make a performant solution, but it'll need to know the actual number of hexagons crossed and use the angle to figure out how many times it crosses "sideways".

[sahrk]

#dfellis, I believe we are both talking about what is usually referred to as "metric distance". I was just pointing out that the H3 indexes (below the base cell) encode a vector (direction and magnitude), and your virtual tree traversal can be expressed as vector operations, which can be defined on H3 indexes using per-digit table lookups. I have the basic operations implemented in Java, and would be glad to port them to C once we get our non-technical difficulties sorted out, which I hope happens quickly. I want to be a Collaborator!! :)