Comments (5)
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.
from h3.
from h3.
@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?
from h3.
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".
from h3.
#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!! :)
from h3.
Related Issues (20)
- illegal instruction on ppc64 big endian server HOT 2
- h3.exact_edge_length execution error HOT 4
- PloygonAlgos - Throws error when used wrapper library in swift HOT 2
- About RFC: Polyfill modes release plan HOT 1
- replace `sprintf` with `snprintf` HOT 1
- Add additional modes for polygonToCells HOT 12
- Hex (cell) ID validation HOT 3
- Fuzzer timeout on fuzzerIj: gridPathCells
- Broken Link to website docs in contributing.md
- Broken link to website in contributing docs
- Uber CLA Contact HOT 1
- Has cell_to_vertex been implemented? HOT 2
- Replace empty function parameters with `void` HOT 1
- cell_to_child_pos() version 4 of the Python API client HOT 3
- polygonToCells: validity of polygons HOT 3
- Missing library stubs MYPY HOT 2
- polygonToCells not returning all H3Cells for the bounding box containing both USA and Russia HOT 1
- Confirmation of grid algorithm HOT 3
- cellToChildren error HOT 2
- Add function for returning the H3 indices of each endpoint of a directed edge HOT 5
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
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.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from h3.