search

ImperialSpaceSociety / LoRaMac-node

Reference implementation and documentation of a LoRa network node.
Other
6 stars 1 forks source link

Use h3 coordinates instead of lat/long degrees #480

Open MedadRufus opened 1 year ago

MedadRufus commented 1 year ago

Problem

H3 coordinates suffers no changes in precision with regards to absolute distance anywhere in the world. In contrast, using lat, long degrees has a precision change depending on longitude - at the equator, 1 degrees longitude is around 100km while its close to 1 cm at the poles.

Benefits of H3

Uber H3 has several levels of precision, as shown in the table below. We currently use 16 bits to represent lat, 16 bits to represent longitude and 16 bits for altitude, giving us 48 bits to define for location. We can rearrange those bits if needed. Lets say we take 3 bits of precision from altitude, we will have 35 bits for long/lat(or h3). With 13 bits, altitude can be represented [0, 16,383] with precision of 2 meters - more than enough. Now max value of 35 bits unsigned is 34,359,738,360 - just over max cells in h3 resolution of 10. At h3 resolution of 10, hexagon edge length is only 65 meters - thats really precise.

image

image

MedadRufus commented 1 year ago

This paper on tiling methods is really interesting - turns out I am not the only one who as encountered this loss of precision issue. https://richard.science/sci/2019_barnes_dgg_published.pdf

MedadRufus commented 1 year ago

The Uber h3 index uses a 64 bit value to store the cell index. source: https://location.foursquare.com/resources/reports-and-insights/ebook/all-about-h3-your-questions-answered/

I am not sure if we can trucate and use only 35 bits to represent cells. For storage and transmission, I think we can truncate to 35 bits, but when converting from cell_to_latlong(), we pad it to make 64 bits.

MedadRufus commented 1 year ago

Apparently the h3 index contains a resolution field, taking up 5 bits. We can truncate that still, by using fixing the resolution to 10 everywhere. ref: https://observablehq.com/@nrabinowitz/h3-index-bit-layout

MedadRufus commented 1 year ago

Google have a rival system called S2: https://s2geometry.io/

MedadRufus commented 1 year ago

There have been questions and a good answer on truncating the h3 index from 64bits to 32bits. See https://github.com/uber/h3/issues/320#issuecomment-599641885