/src/h3/src/h3lib/lib/latLng.c

Source
/*
 * Copyright 2016-2023 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 latLng.c
 * @brief   Functions for working with lat/lng coordinates.
 */

#include "latLng.h"

#include <math.h>
#include <stdbool.h>

#include "constants.h"
#include "h3Assert.h"
#include "h3api.h"
#include "mathExtensions.h"

/**
 * Normalizes radians to a value between 0.0 and two PI.
 *
 * @param rads The input radians value.
 * @return The normalized radians value.
 */
double _posAngleRads(double rads) {
    double tmp = ((rads < 0.0) ? rads + M_2PI : rads);
    if (rads >= M_2PI) tmp -= M_2PI;
    return tmp;
}

/**
 * Determines if the components of two spherical coordinates are within some
 * threshold distance of each other.
 *
 * @param p1 The first spherical coordinates.
 * @param p2 The second spherical coordinates.
 * @param threshold The threshold distance.
 * @return Whether or not the two coordinates are within the threshold distance
 *         of each other.
 */
bool geoAlmostEqualThreshold(const LatLng *p1, const LatLng *p2,
                             double threshold) {
    return fabs(p1->lat - p2->lat) < threshold &&
           fabs(p1->lng - p2->lng) < threshold;
}

/**
 * Determines if the components of two spherical coordinates are within our
 * standard epsilon distance of each other.
 *
 * @param p1 The first spherical coordinates.
 * @param p2 The second spherical coordinates.
 * @return Whether or not the two coordinates are within the epsilon distance
 *         of each other.
 */
bool geoAlmostEqual(const LatLng *p1, const LatLng *p2) {
    return geoAlmostEqualThreshold(p1, p2, EPSILON_RAD);
}

/**
 * Set the components of spherical coordinates in decimal degrees.
 *
 * @param p The spherical coordinates.
 * @param latDegs The desired latitude in decimal degrees.
 * @param lngDegs The desired longitude in decimal degrees.
 */
void setGeoDegs(LatLng *p, double latDegs, double lngDegs) {
    _setGeoRads(p, H3_EXPORT(degsToRads)(latDegs),
                H3_EXPORT(degsToRads)(lngDegs));
}

/**
 * Set the components of spherical coordinates in radians.
 *
 * @param p The spherical coordinates.
 * @param latRads The desired latitude in decimal radians.
 * @param lngRads The desired longitude in decimal radians.
 */
void _setGeoRads(LatLng *p, double latRads, double lngRads) {
    p->lat = latRads;
    p->lng = lngRads;
}

/**
 * Convert from decimal degrees to radians.
 *
 * @param degrees The decimal degrees.
 * @return The corresponding radians.
 */
double H3_EXPORT(degsToRads)(double degrees) { return degrees * M_PI_180; }

/**
 * Convert from radians to decimal degrees.
 *
 * @param radians The radians.
 * @return The corresponding decimal degrees.
 */
double H3_EXPORT(radsToDegs)(double radians) { return radians * M_180_PI; }

/**
 * constrainLat makes sure latitudes are in the proper bounds
 *
 * @param lat The original lat value
 * @return The corrected lat value
 */
double constrainLat(double lat) {
    while (lat > M_PI_2) {
        lat = lat - M_PI;
    }
    return lat;
}

/**
 * constrainLng makes sure longitudes are in the proper bounds
 *
 * @param lng The origin lng value
 * @return The corrected lng value
 */
double constrainLng(double lng) {
    while (lng > M_PI) {
        lng = lng - (2 * M_PI);
    }
    while (lng < -M_PI) {
        lng = lng + (2 * M_PI);
    }
    return lng;
}

/**
 * Normalize an input longitude according to the specified normalization
 * @param  lng           Input longitude
 * @param  normalization Longitude normalization strategy
 * @return               Normalized longitude
 */
double normalizeLng(const double lng,
                    const LongitudeNormalization normalization) {
    switch (normalization) {
        case NORMALIZE_EAST:
            return lng < 0 ? lng + (double)M_2PI : lng;
        case NORMALIZE_WEST:
            return lng > 0 ? lng - (double)M_2PI : lng;
        default:
            return lng;
    }
}

/**
 * The great circle distance in radians between two spherical coordinates.
 *
 * This function uses the Haversine formula.
 * For math details, see:
 *     https://en.wikipedia.org/wiki/Haversine_formula
 *     https://www.movable-type.co.uk/scripts/latlong.html
 *
 * @param  a  the first lat/lng pair (in radians)
 * @param  b  the second lat/lng pair (in radians)
 *
 * @return    the great circle distance in radians between a and b
 */
double H3_EXPORT(greatCircleDistanceRads)(const LatLng *a, const LatLng *b) {
    double sinLat = sin((b->lat - a->lat) * 0.5);
    double sinLng = sin((b->lng - a->lng) * 0.5);

    double A = sinLat * sinLat + cos(a->lat) * cos(b->lat) * sinLng * sinLng;

    return 2 * atan2(sqrt(A), sqrt(1 - A));
}

/**
 * The great circle distance in kilometers between two spherical coordinates.
 *
 * @param  a  the first lat/lng pair (in radians)
 * @param  b  the second lat/lng pair (in radians)
 *
 * @return    the great circle distance in kilometers between a and b
 */
double H3_EXPORT(greatCircleDistanceKm)(const LatLng *a, const LatLng *b) {
    return H3_EXPORT(greatCircleDistanceRads)(a, b) * EARTH_RADIUS_KM;
}

/**
 * The great circle distance in meters between two spherical coordinates.
 *
 * @param  a  the first lat/lng pair (in radians)
 * @param  b  the second lat/lng pair (in radians)
 *
 * @return    the great circle distance in meters between a and b
 */
double H3_EXPORT(greatCircleDistanceM)(const LatLng *a, const LatLng *b) {
    return H3_EXPORT(greatCircleDistanceKm)(a, b) * 1000;
}

/**
 * Determines the azimuth to p2 from p1 in radians.
 *
 * @param p1 The first spherical coordinates.
 * @param p2 The second spherical coordinates.
 * @return The azimuth in radians from p1 to p2.
 */
double _geoAzimuthRads(const LatLng *p1, const LatLng *p2) {
    return atan2(cos(p2->lat) * sin(p2->lng - p1->lng),
                 cos(p1->lat) * sin(p2->lat) -
                     sin(p1->lat) * cos(p2->lat) * cos(p2->lng - p1->lng));
}

/**
 * Computes the point on the sphere a specified azimuth and distance from
 * another point.
 *
 * @param p1 The first spherical coordinates.
 * @param az The desired azimuth from p1.
 * @param distance The desired distance from p1, must be non-negative.
 * @param p2 The spherical coordinates at the desired azimuth and distance from
 * p1.
 */
void _geoAzDistanceRads(const LatLng *p1, double az, double distance,
                        LatLng *p2) {
    if (distance < EPSILON) {
        *p2 = *p1;
        return;
    }

    double sinlat, sinlng, coslng;

    az = _posAngleRads(az);

    // check for due north/south azimuth
    if (az < EPSILON || fabs(az - M_PI) < EPSILON) {
        if (az < EPSILON)  // due north
            p2->lat = p1->lat + distance;
        else  // due south
            p2->lat = p1->lat - distance;

        if (fabs(p2->lat - M_PI_2) < EPSILON)  // north pole
        {
            p2->lat = M_PI_2;
            p2->lng = 0.0;
        } else if (fabs(p2->lat + M_PI_2) < EPSILON)  // south pole
        {
            p2->lat = -M_PI_2;
            p2->lng = 0.0;
        } else
            p2->lng = constrainLng(p1->lng);
    } else  // not due north or south
    {
        sinlat = sin(p1->lat) * cos(distance) +
                 cos(p1->lat) * sin(distance) * cos(az);
        if (sinlat > 1.0) sinlat = 1.0;
        if (sinlat < -1.0) sinlat = -1.0;
        p2->lat = asin(sinlat);
        if (fabs(p2->lat - M_PI_2) < EPSILON)  // north pole
        {
            p2->lat = M_PI_2;
            p2->lng = 0.0;
        } else if (fabs(p2->lat + M_PI_2) < EPSILON)  // south pole
        {
            p2->lat = -M_PI_2;
            p2->lng = 0.0;
        } else {
            double invcosp2lat = 1.0 / cos(p2->lat);
            sinlng = sin(az) * sin(distance) * invcosp2lat;
            coslng = (cos(distance) - sin(p1->lat) * sin(p2->lat)) /
                     cos(p1->lat) * invcosp2lat;
            if (sinlng > 1.0) sinlng = 1.0;
            if (sinlng < -1.0) sinlng = -1.0;
            if (coslng > 1.0) coslng = 1.0;
            if (coslng < -1.0) coslng = -1.0;
            p2->lng = constrainLng(p1->lng + atan2(sinlng, coslng));
        }
    }
}

/*
 * The following functions provide meta information about the H3 hexagons at
 * each zoom level. Since there are only 16 total levels, these are current
 * handled with hardwired static values, but it may be worthwhile to put these
 * static values into another file that can be autogenerated by source code in
 * the future.
 */

H3Error H3_EXPORT(getHexagonAreaAvgKm2)(int res, double *out) {
    static const double areas[] = {
        4.357449416078383e+06, 6.097884417941332e+05, 8.680178039899720e+04,
        1.239343465508816e+04, 1.770347654491307e+03, 2.529038581819449e+02,
        3.612906216441245e+01, 5.161293359717191e+00, 7.373275975944177e-01,
        1.053325134272067e-01, 1.504750190766435e-02, 2.149643129451879e-03,
        3.070918756316060e-04, 4.387026794728296e-05, 6.267181135324313e-06,
        8.953115907605790e-07};
    if (res < 0 || res > MAX_H3_RES) {
        return E_RES_DOMAIN;
    }
    *out = areas[res];
    return E_SUCCESS;
}

H3Error H3_EXPORT(getHexagonAreaAvgM2)(int res, double *out) {
    static const double areas[] = {
        4.357449416078390e+12, 6.097884417941339e+11, 8.680178039899731e+10,
        1.239343465508818e+10, 1.770347654491309e+09, 2.529038581819452e+08,
        3.612906216441250e+07, 5.161293359717198e+06, 7.373275975944188e+05,
        1.053325134272069e+05, 1.504750190766437e+04, 2.149643129451882e+03,
        3.070918756316063e+02, 4.387026794728301e+01, 6.267181135324322e+00,
        8.953115907605802e-01};
    if (res < 0 || res > MAX_H3_RES) {
        return E_RES_DOMAIN;
    }
    *out = areas[res];
    return E_SUCCESS;
}

H3Error H3_EXPORT(getHexagonEdgeLengthAvgKm)(int res, double *out) {
    static const double lens[] = {
        1281.256011, 483.0568391, 182.5129565, 68.97922179,
        26.07175968, 9.854090990, 3.724532667, 1.406475763,
        0.531414010, 0.200786148, 0.075863783, 0.028663897,
        0.010830188, 0.004092010, 0.001546100, 0.000584169};
    if (res < 0 || res > MAX_H3_RES) {
        return E_RES_DOMAIN;
    }
    *out = lens[res];
    return E_SUCCESS;
}

H3Error H3_EXPORT(getHexagonEdgeLengthAvgM)(int res, double *out) {
    static const double lens[] = {
        1281256.011, 483056.8391, 182512.9565, 68979.22179,
        26071.75968, 9854.090990, 3724.532667, 1406.475763,
        531.4140101, 200.7861476, 75.86378287, 28.66389748,
        10.83018784, 4.092010473, 1.546099657, 0.584168630};
    if (res < 0 || res > MAX_H3_RES) {
        return E_RES_DOMAIN;
    }
    *out = lens[res];
    return E_SUCCESS;
}

H3Error H3_EXPORT(getNumCells)(int res, int64_t *out) {
    if (res < 0 || res > MAX_H3_RES) {
        return E_RES_DOMAIN;
    }
    *out = 2 + 120 * _ipow(7, res);
    return E_SUCCESS;
}

/**
 * Surface area in radians^2 of spherical triangle on unit sphere.
 *
 * For the math, see:
 * https://en.wikipedia.org/wiki/Spherical_trigonometry#Area_and_spherical_excess
 *
 * @param   a  length of triangle side A in radians
 * @param   b  length of triangle side B in radians
 * @param   c  length of triangle side C in radians
 *
 * @return     area in radians^2 of triangle on unit sphere
 */
double triangleEdgeLengthsToArea(double a, double b, double c) {
    double s = (a + b + c) * 0.5;

    a = (s - a) * 0.5;
    b = (s - b) * 0.5;
    c = (s - c) * 0.5;
    s = s * 0.5;

    return 4 * atan(sqrt(tan(s) * tan(a) * tan(b) * tan(c)));
}

/**
 * Compute area in radians^2 of a spherical triangle, given its vertices.
 *
 * @param   a  vertex lat/lng in radians
 * @param   b  vertex lat/lng in radians
 * @param   c  vertex lat/lng in radians
 *
 * @return     area of triangle on unit sphere, in radians^2
 */
double triangleArea(const LatLng *a, const LatLng *b, const LatLng *c) {
    return triangleEdgeLengthsToArea(H3_EXPORT(greatCircleDistanceRads)(a, b),
                                     H3_EXPORT(greatCircleDistanceRads)(b, c),
                                     H3_EXPORT(greatCircleDistanceRads)(c, a));
}

/**
 * Area of H3 cell in radians^2.
 *
 * The area is calculated by breaking the cell into spherical triangles and
 * summing up their areas. Note that some H3 cells (hexagons and pentagons)
 * are irregular, and have more than 6 or 5 sides.
 *
 * todo: optimize the computation by re-using the edges shared between triangles
 *
 * @param   cell  H3 cell
 * @param    out  cell area in radians^2
 * @return        E_SUCCESS on success, or an error code otherwise
 */
H3Error H3_EXPORT(cellAreaRads2)(H3Index cell, double *out) {
    LatLng c;
    CellBoundary cb;
    H3Error err = H3_EXPORT(cellToLatLng)(cell, &c);
    if (err) {
        return err;
    }
    err = H3_EXPORT(cellToBoundary)(cell, &cb);
    if (NEVER(err)) {
        // Uncoverable because cellToLatLng will have returned an error already
        return err;
    }

    double area = 0.0;
    for (int i = 0; i < cb.numVerts; i++) {
        int j = (i + 1) % cb.numVerts;
        area += triangleArea(&cb.verts[i], &cb.verts[j], &c);
    }

    *out = area;
    return E_SUCCESS;
}

/**
 * Area of H3 cell in kilometers^2.
 *
 * @param   cell  H3 cell
 * @param    out  cell area in kilometers^2
 * @return        E_SUCCESS on success, or an error code otherwise
 */
H3Error H3_EXPORT(cellAreaKm2)(H3Index cell, double *out) {
    H3Error err = H3_EXPORT(cellAreaRads2)(cell, out);
    if (!err) {
        *out = *out * EARTH_RADIUS_KM * EARTH_RADIUS_KM;
    }
    return err;
}

/**
 * Area of H3 cell in meters^2.
 *
 * @param   cell  H3 cell
 * @param    out  cell area in meters^2
 * @return        E_SUCCESS on success, or an error code otherwise
 */
H3Error H3_EXPORT(cellAreaM2)(H3Index cell, double *out) {
    H3Error err = H3_EXPORT(cellAreaKm2)(cell, out);
    if (!err) {
        *out = *out * 1000 * 1000;
    }
    return err;
}

/**
 * Length of a directed edge in radians.
 *
 * @param   edge  H3 directed edge
 * @param    length  length in radians
 * @return        E_SUCCESS on success, or an error code otherwise
 */
H3Error H3_EXPORT(edgeLengthRads)(H3Index edge, double *length) {
    CellBoundary cb;

    H3Error err = H3_EXPORT(directedEdgeToBoundary)(edge, &cb);
    if (err) {
        return err;
    }

    *length = 0.0;
    for (int i = 0; i < cb.numVerts - 1; i++) {
        *length +=
            H3_EXPORT(greatCircleDistanceRads)(&cb.verts[i], &cb.verts[i + 1]);
    }

    return E_SUCCESS;
}

/**
 * Length of a directed edge in kilometers.
 *
 * @param   edge  H3 directed edge
 * @param    length  length in kilometers
 * @return        E_SUCCESS on success, or an error code otherwise
 */
H3Error H3_EXPORT(edgeLengthKm)(H3Index edge, double *length) {
    H3Error err = H3_EXPORT(edgeLengthRads)(edge, length);
    *length = *length * EARTH_RADIUS_KM;
    return err;
}

/**
 * Length of a directed edge in meters.
 *
 * @param   edge  H3 directed edge
 * @param    length  length in meters
 * @return        E_SUCCESS on success, or an error code otherwise
 */
H3Error H3_EXPORT(edgeLengthM)(H3Index edge, double *length) {
    H3Error err = H3_EXPORT(edgeLengthKm)(edge, length);
    *length = *length * 1000;
    return err;
}

Coverage Report

Created: 2025-10-10 06:39

Line	Count	Source
1		/*
2		* Copyright 2016-2023 Uber Technologies, Inc.
3		*
4		* Licensed under the Apache License, Version 2.0 (the "License");
5		* you may not use this file except in compliance with the License.
6		* You may obtain a copy of the License at
7		*
8		* http://www.apache.org/licenses/LICENSE-2.0
9		*
10		* Unless required by applicable law or agreed to in writing, software
11		* distributed under the License is distributed on an "AS IS" BASIS,
12		* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13		* See the License for the specific language governing permissions and
14		* limitations under the License.
15		*/
16		/** @file latLng.c
17		* @brief Functions for working with lat/lng coordinates.
18		*/
19
20		#include "latLng.h"
21
22		#include <math.h>
23		#include <stdbool.h>
24
25		#include "constants.h"
26		#include "h3Assert.h"
27		#include "h3api.h"
28		#include "mathExtensions.h"
29
30		/**
31		* Normalizes radians to a value between 0.0 and two PI.
32		*
33		* @param rads The input radians value.
34		* @return The normalized radians value.
35		*/
36	0	double _posAngleRads(double rads) {
37	0	double tmp = ((rads < 0.0) ? rads + M_2PI : rads);
38	0	if (rads >= M_2PI) tmp -= M_2PI;
39	0	return tmp;
40	0	}
41
42		/**
43		* Determines if the components of two spherical coordinates are within some
44		* threshold distance of each other.
45		*
46		* @param p1 The first spherical coordinates.
47		* @param p2 The second spherical coordinates.
48		* @param threshold The threshold distance.
49		* @return Whether or not the two coordinates are within the threshold distance
50		* of each other.
51		*/
52		bool geoAlmostEqualThreshold(const LatLng p1, const LatLng p2,
53	0	double threshold) {
54	0	return fabs(p1->lat - p2->lat) < threshold &&
55	0	fabs(p1->lng - p2->lng) < threshold;
56	0	}
57
58		/**
59		* Determines if the components of two spherical coordinates are within our
60		* standard epsilon distance of each other.
61		*
62		* @param p1 The first spherical coordinates.
63		* @param p2 The second spherical coordinates.
64		* @return Whether or not the two coordinates are within the epsilon distance
65		* of each other.
66		*/
67	0	bool geoAlmostEqual(const LatLng p1, const LatLng p2) {
68	0	return geoAlmostEqualThreshold(p1, p2, EPSILON_RAD);
69	0	}
70
71		/**
72		* Set the components of spherical coordinates in decimal degrees.
73		*
74		* @param p The spherical coordinates.
75		* @param latDegs The desired latitude in decimal degrees.
76		* @param lngDegs The desired longitude in decimal degrees.
77		*/
78	0	void setGeoDegs(LatLng *p, double latDegs, double lngDegs) {
79	0	_setGeoRads(p, H3_EXPORT(degsToRads)(latDegs),
80	0	H3_EXPORT(degsToRads)(lngDegs));
81	0	}
82
83		/**
84		* Set the components of spherical coordinates in radians.
85		*
86		* @param p The spherical coordinates.
87		* @param latRads The desired latitude in decimal radians.
88		* @param lngRads The desired longitude in decimal radians.
89		*/
90	0	void _setGeoRads(LatLng *p, double latRads, double lngRads) {
91	0	p->lat = latRads;
92	0	p->lng = lngRads;
93	0	}
94
95		/**
96		* Convert from decimal degrees to radians.
97		*
98		* @param degrees The decimal degrees.
99		* @return The corresponding radians.
100		*/
101	0	double H3_EXPORT(degsToRads)(double degrees) { return degrees * M_PI_180; }
102
103		/**
104		* Convert from radians to decimal degrees.
105		*
106		* @param radians The radians.
107		* @return The corresponding decimal degrees.
108		*/
109	0	double H3_EXPORT(radsToDegs)(double radians) { return radians * M_180_PI; }
110
111		/**
112		* constrainLat makes sure latitudes are in the proper bounds
113		*
114		* @param lat The original lat value
115		* @return The corrected lat value
116		*/
117	0	double constrainLat(double lat) {
118	0	while (lat > M_PI_2) {
119	0	lat = lat - M_PI;
120	0	}
121	0	return lat;
122	0	}
123
124		/**
125		* constrainLng makes sure longitudes are in the proper bounds
126		*
127		* @param lng The origin lng value
128		* @return The corrected lng value
129		*/
130	0	double constrainLng(double lng) {
131	0	while (lng > M_PI) {
132	0	lng = lng - (2 * M_PI);
133	0	}
134	0	while (lng < -M_PI) {
135	0	lng = lng + (2 * M_PI);
136	0	}
137	0	return lng;
138	0	}
139
140		/**
141		* Normalize an input longitude according to the specified normalization
142		* @param lng Input longitude
143		* @param normalization Longitude normalization strategy
144		* @return Normalized longitude
145		*/
146		double normalizeLng(const double lng,
147	0	const LongitudeNormalization normalization) {
148	0	switch (normalization) {
149	0	case NORMALIZE_EAST:
150	0	return lng < 0 ? lng + (double)M_2PI : lng;
151	0	case NORMALIZE_WEST:
152	0	return lng > 0 ? lng - (double)M_2PI : lng;
153	0	default:
154	0	return lng;
155	0	}
156	0	}
157
158		/**
159		* The great circle distance in radians between two spherical coordinates.
160		*
161		* This function uses the Haversine formula.
162		* For math details, see:
163		* https://en.wikipedia.org/wiki/Haversine_formula
164		* https://www.movable-type.co.uk/scripts/latlong.html
165		*
166		* @param a the first lat/lng pair (in radians)
167		* @param b the second lat/lng pair (in radians)
168		*
169		* @return the great circle distance in radians between a and b
170		*/
171	0	double H3_EXPORT(greatCircleDistanceRads)(const LatLng a, const LatLng b) {
172	0	double sinLat = sin((b->lat - a->lat) * 0.5);
173	0	double sinLng = sin((b->lng - a->lng) * 0.5);
174
175	0	double A = sinLat * sinLat + cos(a->lat) * cos(b->lat) * sinLng * sinLng;
176
177	0	return 2 * atan2(sqrt(A), sqrt(1 - A));
178	0	}
179
180		/**
181		* The great circle distance in kilometers between two spherical coordinates.
182		*
183		* @param a the first lat/lng pair (in radians)
184		* @param b the second lat/lng pair (in radians)
185		*
186		* @return the great circle distance in kilometers between a and b
187		*/
188	0	double H3_EXPORT(greatCircleDistanceKm)(const LatLng a, const LatLng b) {
189	0	return H3_EXPORT(greatCircleDistanceRads)(a, b) * EARTH_RADIUS_KM;
190	0	}
191
192		/**
193		* The great circle distance in meters between two spherical coordinates.
194		*
195		* @param a the first lat/lng pair (in radians)
196		* @param b the second lat/lng pair (in radians)
197		*
198		* @return the great circle distance in meters between a and b
199		*/
200	0	double H3_EXPORT(greatCircleDistanceM)(const LatLng a, const LatLng b) {
201	0	return H3_EXPORT(greatCircleDistanceKm)(a, b) * 1000;
202	0	}
203
204		/**
205		* Determines the azimuth to p2 from p1 in radians.
206		*
207		* @param p1 The first spherical coordinates.
208		* @param p2 The second spherical coordinates.
209		* @return The azimuth in radians from p1 to p2.
210		*/
211	0	double _geoAzimuthRads(const LatLng p1, const LatLng p2) {
212	0	return atan2(cos(p2->lat) * sin(p2->lng - p1->lng),
213	0	cos(p1->lat) * sin(p2->lat) -
214	0	sin(p1->lat) * cos(p2->lat) * cos(p2->lng - p1->lng));
215	0	}
216
217		/**
218		* Computes the point on the sphere a specified azimuth and distance from
219		* another point.
220		*
221		* @param p1 The first spherical coordinates.
222		* @param az The desired azimuth from p1.
223		* @param distance The desired distance from p1, must be non-negative.
224		* @param p2 The spherical coordinates at the desired azimuth and distance from
225		* p1.
226		*/
227		void _geoAzDistanceRads(const LatLng *p1, double az, double distance,
228	0	LatLng *p2) {
229	0	if (distance < EPSILON) {
230	0	p2 = p1;
231	0	return;
232	0	}
233
234	0	double sinlat, sinlng, coslng;
235
236	0	az = _posAngleRads(az);
237
238		// check for due north/south azimuth
239	0	if (az < EPSILON \|\| fabs(az - M_PI) < EPSILON) {
240	0	if (az < EPSILON) // due north
241	0	p2->lat = p1->lat + distance;
242	0	else // due south
243	0	p2->lat = p1->lat - distance;
244
245	0	if (fabs(p2->lat - M_PI_2) < EPSILON) // north pole
246	0	{
247	0	p2->lat = M_PI_2;
248	0	p2->lng = 0.0;
249	0	} else if (fabs(p2->lat + M_PI_2) < EPSILON) // south pole
250	0	{
251	0	p2->lat = -M_PI_2;
252	0	p2->lng = 0.0;
253	0	} else
254	0	p2->lng = constrainLng(p1->lng);
255	0	} else // not due north or south
256	0	{
257	0	sinlat = sin(p1->lat) * cos(distance) +
258	0	cos(p1->lat) * sin(distance) * cos(az);
259	0	if (sinlat > 1.0) sinlat = 1.0;
260	0	if (sinlat < -1.0) sinlat = -1.0;
261	0	p2->lat = asin(sinlat);
262	0	if (fabs(p2->lat - M_PI_2) < EPSILON) // north pole
263	0	{
264	0	p2->lat = M_PI_2;
265	0	p2->lng = 0.0;
266	0	} else if (fabs(p2->lat + M_PI_2) < EPSILON) // south pole
267	0	{
268	0	p2->lat = -M_PI_2;
269	0	p2->lng = 0.0;
270	0	} else {
271	0	double invcosp2lat = 1.0 / cos(p2->lat);
272	0	sinlng = sin(az) * sin(distance) * invcosp2lat;
273	0	coslng = (cos(distance) - sin(p1->lat) * sin(p2->lat)) /
274	0	cos(p1->lat) * invcosp2lat;
275	0	if (sinlng > 1.0) sinlng = 1.0;
276	0	if (sinlng < -1.0) sinlng = -1.0;
277	0	if (coslng > 1.0) coslng = 1.0;
278	0	if (coslng < -1.0) coslng = -1.0;
279	0	p2->lng = constrainLng(p1->lng + atan2(sinlng, coslng));
280	0	}
281	0	}
282	0	}
283
284		/*
285		* The following functions provide meta information about the H3 hexagons at
286		* each zoom level. Since there are only 16 total levels, these are current
287		* handled with hardwired static values, but it may be worthwhile to put these
288		* static values into another file that can be autogenerated by source code in
289		* the future.
290		*/
291
292	0	H3Error H3_EXPORT(getHexagonAreaAvgKm2)(int res, double *out) {
293	0	static const double areas[] = {
294	0	4.357449416078383e+06, 6.097884417941332e+05, 8.680178039899720e+04,
295	0	1.239343465508816e+04, 1.770347654491307e+03, 2.529038581819449e+02,
296	0	3.612906216441245e+01, 5.161293359717191e+00, 7.373275975944177e-01,
297	0	1.053325134272067e-01, 1.504750190766435e-02, 2.149643129451879e-03,
298	0	3.070918756316060e-04, 4.387026794728296e-05, 6.267181135324313e-06,
299	0	8.953115907605790e-07};
300	0	if (res < 0 \|\| res > MAX_H3_RES) {
301	0	return E_RES_DOMAIN;
302	0	}
303	0	*out = areas[res];
304	0	return E_SUCCESS;
305	0	}
306
307	0	H3Error H3_EXPORT(getHexagonAreaAvgM2)(int res, double *out) {
308	0	static const double areas[] = {
309	0	4.357449416078390e+12, 6.097884417941339e+11, 8.680178039899731e+10,
310	0	1.239343465508818e+10, 1.770347654491309e+09, 2.529038581819452e+08,
311	0	3.612906216441250e+07, 5.161293359717198e+06, 7.373275975944188e+05,
312	0	1.053325134272069e+05, 1.504750190766437e+04, 2.149643129451882e+03,
313	0	3.070918756316063e+02, 4.387026794728301e+01, 6.267181135324322e+00,
314	0	8.953115907605802e-01};
315	0	if (res < 0 \|\| res > MAX_H3_RES) {
316	0	return E_RES_DOMAIN;
317	0	}
318	0	*out = areas[res];
319	0	return E_SUCCESS;
320	0	}
321
322	0	H3Error H3_EXPORT(getHexagonEdgeLengthAvgKm)(int res, double *out) {
323	0	static const double lens[] = {
324	0	1281.256011, 483.0568391, 182.5129565, 68.97922179,
325	0	26.07175968, 9.854090990, 3.724532667, 1.406475763,
326	0	0.531414010, 0.200786148, 0.075863783, 0.028663897,
327	0	0.010830188, 0.004092010, 0.001546100, 0.000584169};
328	0	if (res < 0 \|\| res > MAX_H3_RES) {
329	0	return E_RES_DOMAIN;
330	0	}
331	0	*out = lens[res];
332	0	return E_SUCCESS;
333	0	}
334
335	0	H3Error H3_EXPORT(getHexagonEdgeLengthAvgM)(int res, double *out) {
336	0	static const double lens[] = {
337	0	1281256.011, 483056.8391, 182512.9565, 68979.22179,
338	0	26071.75968, 9854.090990, 3724.532667, 1406.475763,
339	0	531.4140101, 200.7861476, 75.86378287, 28.66389748,
340	0	10.83018784, 4.092010473, 1.546099657, 0.584168630};
341	0	if (res < 0 \|\| res > MAX_H3_RES) {
342	0	return E_RES_DOMAIN;
343	0	}
344	0	*out = lens[res];
345	0	return E_SUCCESS;
346	0	}
347
348	0	H3Error H3_EXPORT(getNumCells)(int res, int64_t *out) {
349	0	if (res < 0 \|\| res > MAX_H3_RES) {
350	0	return E_RES_DOMAIN;
351	0	}
352	0	out = 2 + 120 _ipow(7, res);
353	0	return E_SUCCESS;
354	0	}
355
356		/**
357		* Surface area in radians^2 of spherical triangle on unit sphere.
358		*
359		* For the math, see:
360		* https://en.wikipedia.org/wiki/Spherical_trigonometry#Area_and_spherical_excess
361		*
362		* @param a length of triangle side A in radians
363		* @param b length of triangle side B in radians
364		* @param c length of triangle side C in radians
365		*
366		* @return area in radians^2 of triangle on unit sphere
367		*/
368	0	double triangleEdgeLengthsToArea(double a, double b, double c) {
369	0	double s = (a + b + c) * 0.5;
370
371	0	a = (s - a) * 0.5;
372	0	b = (s - b) * 0.5;
373	0	c = (s - c) * 0.5;
374	0	s = s * 0.5;
375
376	0	return 4 * atan(sqrt(tan(s) * tan(a) * tan(b) * tan(c)));
377	0	}
378
379		/**
380		* Compute area in radians^2 of a spherical triangle, given its vertices.
381		*
382		* @param a vertex lat/lng in radians
383		* @param b vertex lat/lng in radians
384		* @param c vertex lat/lng in radians
385		*
386		* @return area of triangle on unit sphere, in radians^2
387		*/
388	0	double triangleArea(const LatLng a, const LatLng b, const LatLng *c) {
389	0	return triangleEdgeLengthsToArea(H3_EXPORT(greatCircleDistanceRads)(a, b),
390	0	H3_EXPORT(greatCircleDistanceRads)(b, c),
391	0	H3_EXPORT(greatCircleDistanceRads)(c, a));
392	0	}
393
394		/**
395		* Area of H3 cell in radians^2.
396		*
397		* The area is calculated by breaking the cell into spherical triangles and
398		* summing up their areas. Note that some H3 cells (hexagons and pentagons)
399		* are irregular, and have more than 6 or 5 sides.
400		*
401		* todo: optimize the computation by re-using the edges shared between triangles
402		*
403		* @param cell H3 cell
404		* @param out cell area in radians^2
405		* @return E_SUCCESS on success, or an error code otherwise
406		*/
407	0	H3Error H3_EXPORT(cellAreaRads2)(H3Index cell, double *out) {
408	0	LatLng c;
409	0	CellBoundary cb;
410	0	H3Error err = H3_EXPORT(cellToLatLng)(cell, &c);
411	0	if (err) {
412	0	return err;
413	0	}
414	0	err = H3_EXPORT(cellToBoundary)(cell, &cb);
415	0	if (NEVER(err)) {
416		// Uncoverable because cellToLatLng will have returned an error already
417	0	return err;
418	0	}
419
420	0	double area = 0.0;
421	0	for (int i = 0; i < cb.numVerts; i++) {
422	0	int j = (i + 1) % cb.numVerts;
423	0	area += triangleArea(&cb.verts[i], &cb.verts[j], &c);
424	0	}
425
426	0	*out = area;
427	0	return E_SUCCESS;
428	0	}
429
430		/**
431		* Area of H3 cell in kilometers^2.
432		*
433		* @param cell H3 cell
434		* @param out cell area in kilometers^2
435		* @return E_SUCCESS on success, or an error code otherwise
436		*/
437	0	H3Error H3_EXPORT(cellAreaKm2)(H3Index cell, double *out) {
438	0	H3Error err = H3_EXPORT(cellAreaRads2)(cell, out);
439	0	if (!err) {
440	0	out = out * EARTH_RADIUS_KM * EARTH_RADIUS_KM;
441	0	}
442	0	return err;
443	0	}
444
445		/**
446		* Area of H3 cell in meters^2.
447		*
448		* @param cell H3 cell
449		* @param out cell area in meters^2
450		* @return E_SUCCESS on success, or an error code otherwise
451		*/
452	0	H3Error H3_EXPORT(cellAreaM2)(H3Index cell, double *out) {
453	0	H3Error err = H3_EXPORT(cellAreaKm2)(cell, out);
454	0	if (!err) {
455	0	out = out * 1000 * 1000;
456	0	}
457	0	return err;
458	0	}
459
460		/**
461		* Length of a directed edge in radians.
462		*
463		* @param edge H3 directed edge
464		* @param length length in radians
465		* @return E_SUCCESS on success, or an error code otherwise
466		*/
467	0	H3Error H3_EXPORT(edgeLengthRads)(H3Index edge, double *length) {
468	0	CellBoundary cb;
469
470	0	H3Error err = H3_EXPORT(directedEdgeToBoundary)(edge, &cb);
471	0	if (err) {
472	0	return err;
473	0	}
474
475	0	*length = 0.0;
476	0	for (int i = 0; i < cb.numVerts - 1; i++) {
477	0	*length +=
478	0	H3_EXPORT(greatCircleDistanceRads)(&cb.verts[i], &cb.verts[i + 1]);
479	0	}
480
481	0	return E_SUCCESS;
482	0	}
483
484		/**
485		* Length of a directed edge in kilometers.
486		*
487		* @param edge H3 directed edge
488		* @param length length in kilometers
489		* @return E_SUCCESS on success, or an error code otherwise
490		*/
491	0	H3Error H3_EXPORT(edgeLengthKm)(H3Index edge, double *length) {
492	0	H3Error err = H3_EXPORT(edgeLengthRads)(edge, length);
493	0	length = length * EARTH_RADIUS_KM;
494	0	return err;
495	0	}
496
497		/**
498		* Length of a directed edge in meters.
499		*
500		* @param edge H3 directed edge
501		* @param length length in meters
502		* @return E_SUCCESS on success, or an error code otherwise
503		*/
504	0	H3Error H3_EXPORT(edgeLengthM)(H3Index edge, double *length) {
505	0	H3Error err = H3_EXPORT(edgeLengthKm)(edge, length);
506	0	length = length * 1000;
507	0	return err;
508	0	}