I'm trying to understand uber's H3 geo-indexing system. I understand the _geoToVec3d() function but I am stuck with the _geoToHex2d() function.
Does anyone understand where the equation
cos(r) = 1 - 2 * sin^2(r/2) = 1 - 2 * (sqd / 4) = 1 - sqd/2
in the function _geoToHex2d() in uber's H3 source code comes from? What does it describe?
Or maybe someone understands what the parameter r in the equation stands for?
I understand that sqd is the squared distance from the icosahedron face center to the point to encode. On the next few lines in the code, the 2D hex coordinates of the cell containing the point are set to (0,0) if r is smaller than epsilon. I'm speculating that r must somehow be the distance from the face center but maybe already in the gnomonoic projected plane?
I have to admit that this is the area of the H3 library I am least familiar with, so take the following explanation with a grain of salt:
I believe that in the beginning of this function, r
is the distance in radians from the point being indexed to the center of the nearest icosahedron face. The line
// cos(r) = 1 - 2 * sin^2(r/2) = 1 - 2 * (sqd / 4) = 1 - sqd/2
double r = acos(1 - sqd / 2);
converts the squared 3d distance between the two points on a unit sphere to the distance in radians. The comment uses the double angle identity cos(2𝛼) = 1 − 2sin^2(𝛼)
to formulate cos(r)
in terms of sqd
.
Explanation
In the above diagram, a cross section of the unit sphere, the distance from F->C
is 1
, and the squared distance from C->E
is sqd
. We're trying to find the angle CFE
.
sin^2(r/2)
is the same as sin^2(CFd)
. Since sin(CFd) = C->d / 1 = C->d
, the sin^2(CFd)
is the squared distance C->d
.C->d
is (sqrt(sqd) / 2)^2 = sqd / 4
cos(r) = 1 - 2 * sin^2(r/2)
. Substituting the squared distance C->d
gives us cos(r) = 1 - 2 * (sqd / 4)
, which simplifies to 1 - sqd / 2
.r
as acos(1 - sqd / 2)
Apologies for the slightly tortured explanation, as I'm not a mathematician. As you can see, r
is now the angle CFE
, which is the distance in radians between C
and E
. Later in the function, this is projected using the gnomonic projection into the planar space of the icosahedron face, and then located in the planar hex grid on that face using 2-dimensional hex coordinates.