有谁知道纬度/经度坐标的最有效表示?对于消费类 GPS 设备,精度级别应该足够了。
大多数实现似乎都double
用于每个单元,但我怀疑一个float
或定点格式应该足够了。我很想知道任何尝试压缩和/或存储这些值的大型数组的人的来信。
编辑:
换句话说,代表消费级设备的纬度/经度所需的最低准确度是多少?
有谁知道纬度/经度坐标的最有效表示?对于消费类 GPS 设备,精度级别应该足够了。
大多数实现似乎都double
用于每个单元,但我怀疑一个float
或定点格式应该足够了。我很想知道任何尝试压缩和/或存储这些值的大型数组的人的来信。
编辑:
换句话说,代表消费级设备的纬度/经度所需的最低准确度是多少?
我个人会使用 32 位十进制定点表示,根据埃文的回答和我的评论除以 1,000,000。
但是,如果空间真的很宝贵,这里有一些额外的想法:
您可以在线上使用 26 位定点表示。这将需要将纬度和经度编组和解组为一个大的字节数组,但是在 32 位值表示上为每个位置节省 12 位 - 几乎节省了 19%,所以这可能是值得的。
您可以利用这样一个事实,即当您靠近两极时,经度值需要的精度较低 - 它们在赤道处只需要 26 位。因此,您可以编写一个方案,其中用于编码经度的位数取决于纬度的值。
如果您的数据具有其他可压缩属性 - 例如,所有点通常非常接近 - 您可以利用这些特定优势,例如使用增量编码方案(其中除第一个点之外的每个点都可以编码为最后一个点的增量观点)。
编辑:从评论中添加了一些观点,32 位值应该能够提供足够的精度。
我会使用 32 位定点表示。如果值为:
42.915512
,-99.521654
我会存储values * 100000
in int32_t
(它们可以是负数)。
int32_t lat = 42915512;
int32_t lon = -99521654;
这是简单和准确之间的一个很好的折衷(5
小数点通常足够好,如果需要,您可以随时将其提高到1000000
)6
。
要向用户显示,请执行caf建议的操作:
...显示给用户 - 使用整数除法和模数,例如
printf("Lat = %d.%06d\n", lat / 1000000, abs(lat) % 1000000)
由于将保留相对顺序,因此这些也将以有效的方式进行比较/排序。
编辑:另一个好处是它可以通过网络发送或以可移植的方式以二进制格式存储到磁盘。
地球的周长约为。40.000 公里或 24900 英里。
您需要一米的精度(3 英尺)才能将 gps 精度提高一个数量级。
因此,您需要精确存储 40.000.000 个不同的值。这至少是 26 位信息。32 位浮点数或整数会很好。
浮点数足以存储 GPS 坐标,即使消费级 GPS 设备的精度接近声称的精度。如果您不相信这是真的,请尝试以下两个简单的实验:
多年来,我一直在为支持 GPS 的 PDA 编写应用程序,并且我已经一遍又一遍地为可疑的客户验证了这一点(我什至以这种方式赢得了赌注)。有更高质量的 GPS 设备确实可以实现比这更好的精度,但是使用更昂贵的芯片组可以实现更好的精度,并且这些设备会在一个地方放置数天甚至数周,随着时间的推移平均读数。
四字节浮点数比设备本身准确得多。只要 2X 因素对您来说不是问题,使用双倍当然不会对您造成伤害。
假设地球是一个完美的球体(它不是,但足够近),半径“R”为 3959 英里(或 ×5280 英尺/英里 = 20903520 英尺),周长为 131340690 英尺(使用 2×PI×R) .
360 度经度覆盖 131340690 英尺。180 度的纬度覆盖 65670345 英尺。
如果要将 lat/lng 存储到 3 英尺的精度,则需要能够存储 43780230 (131340690/3) 经度值和 21890115 (65670345/3) 纬度值。43780230 需要 25.38 位 (log(43780230)/log(2)) 来存储,21890115 需要 24.38 位 (log(21890115)/log(2)) 来存储 - 或略低于 50 位(或 6.25 字节)。
那么显而易见的问题就变成了,如果你想在 6 个字节中存储经纬度,那么准确度会是多少?嗯,6 个字节是 48 位。这意味着纬度为 23.5 位,经度为 24.5 位(经度的值是两倍,只有一位,24.5-23.5=1 位)。因此 23.5 位允许您表示从 0 到 11863282 的数字(11863283 个值)。65670345 英尺除以 11863283 值是 5.53 英尺(经度的精度值相同)。
底线:因此,如果您可以接受 5.5 英尺的纬度和经度精度,那么您可以将这两个值打包成 6 个字节。
*旁注:关于纬度和经度对于存储球体周围的位置信息非常糟糕的评论(因为在两极存储的信息较少) - 好吧,这些评论不符合数学!让我们弄清楚。假设我们要设计一个新的完美系统,可以记录并在每平方英尺地球中心的地面上放置一个木桩。地球的表面积(R 为 3959 英里;球体表面积的公式)为 5490965469267303 SQ FT——许多桩需要 52.29 位来表示。现在现有的经纬度系统使用的是矩形系统。矩形的宽度是地球的周长,矩形的高度是周长的 1/2)——即 131340690 * 65670345(见上文),或 8625188424838050 平方英尺——需要 52。94 位来表示(这个系统在电线杆周围的地面上放置了“太多”的木桩)。因此,令人震惊的答案是,新的完美系统和旧的纬度/经度系统都需要 53 个实际位来存储地球上的单个位置,精度低至 1 英尺!
179度经度的23位精度提供10米以下的精度,这是普通GPS设备所能提供的最好的。在赤道:
% gps distance "0.0, 179.0" "0.0, $((179 * (1 + 2**-23)))"
From 0.0, 179.0 to 0.0, 179.00002133846283 is 7.79 feet E
From 0.0, 179.0 to 0.0, 179.00002133846283 is 2.38 meters E
因此,一个 IEEE 754 单精度浮点数(您的 C 编译器称为float
)将足以表示。小心使用浮点数进行扩展计算!舍入误差可能会吃掉你的午餐。咨询数值分析师。
在 Garmin 的 IMG 地图格式中,它们使用浮点数将坐标存储在边界框内以设置框的边缘。框内的坐标是使用可变数量的位来定义的,这些位在最小值和最大值之间是线性的,具体取决于所需的精度。
例如:minlat=49.0, maxlat=50.0, minlon=122.0, maxlon=123.0, number of bits=16
所以值:
32768,32768 将转换为 49.5, 122.5
16384,0 将是 49.25, 122.0
如果需要精度较低,可以使用位数 = 4 生成相同的输出
8,8 将转换为 49.5, 122.5
4,0 将是 49.25, 122.0
如果您要存储这些值的大型数组,则有一些简单的技巧,如果您进行增量压缩并存储增量,则可以大大减少数据流的大小。您可以从“关键点”进行增量
KDDDDDDDDDDKDDDD...
k + d 带你到任何 d 点
增量都引用了前一个 K,因此要重建任何点,您需要一个 K 和一个 D
或者你可以做增量增量
KIIIIIIIIIIK
这可能需要多个总和才能到达所需的位置。但总体数据较小。所以重建
k+i+i+i 到达第 4 点
最后你可以结合两者
KDIIIDIIIDIIIK
这就像带有 IPB 帧的 mpeg-2,但这样一来,任何位置的总和都不会超过 4,并且您可以获得 Delta 和增量压缩的一些好处。
如果您使用递归平铺系统,您可以将纬度和经度值打包在一个32 位整数中,最差的分辨率约为 2.4 米/像素(在赤道处)。每个级别使用两位,您可以在 32 位中存储 16 个级别。查看有关Virtual Earth 平铺系统的这篇文章,您可以了解它是如何工作的。这使用墨卡托,所以它会给你的两极带来问题。您可以改为使用不同的投影,但仍然得到非常相似的结果。
这也可用于粗略过滤器以查找给定父图块内的任何点,因为前 N 位将是相同的(因此搜索变为位掩码)。
因为我需要它,所以这里是 Jerry Jongerius 的答案的 python 代码,它表示 6 字节的纬度/经度值,使用 23.5 和 24.5 位在赤道附近的精度约为 1.7m:
import struct
NBYTES=6
LATVALS=int(2**(NBYTES*4-0.5))
LONVALS=int(2**(NBYTES*4+0.5))
def serialize_gps(latlon):
lat=(int(latlon[0]*LATVALS/180)+LATVALS//2)%LATVALS
lon=(int(latlon[1]*LONVALS/360)+LONVALS//2)%LONVALS
return struct.pack("!Q",lat*LONVALS+lon)[8-NBYTES:]
def deserialize_gps(b):
if len(b)!=NBYTES:
raise Exception("len(b)!=NBYTES")
c=struct.unpack("!Q",(b"\x00"*6+b)[-8:])[0]
lat=(c//LONVALS-LATVALS//2)*180/LATVALS
lon=(c%LONVALS-LONVALS//2)*360/LONVALS
return (lat,lon)
s=serialize_gps((47.55754133918577,10.74961245059967))
print(deserialize_gps(s))
#(47.557526866719776, 10.749611216389258)
我很惊讶没有人发布这样一个事实,即 long/lat 是一种在球体上存储数据的糟糕方式(有人确实提到经度在两极附近需要较低的精度)。
基本上,您可以将数据位置存储为以米为单位的 X 和 Y 坐标。想象一个围绕地球的立方体完全适合(哈哈好吧几乎适合它)。您只需要存储 X 和 Y 位置,而不是所有 3 个坐标,因为第 3 个坐标可以来自地球的半径,r = square root[x^2 + y^2 + z^2] .
因此,将您的纬度/经度转换为以米为单位的 x/y。每个坐标总共只需要 12756200m(这就是地球的直径)。因此,您的总值只需跨越 0 到 25,512,400(其他人声称 40,000,000,因为他们使用的是经度/纬度)即可精确到 +/- 0.5m。
这将导致每个位置只有 25 位。如果我是你,我只会将精度精确到 2m 以内,每个位置使用 24 位,因为这是一个整洁的 3 个字节。
此外,如果您在路径上存储路点信息,您可以将每个路点存储为与上一个路点的偏移量。就像从 24 位 x/y 坐标开始一样。然后有一个 16 位的“更新”,通过添加/减去 x/y 米来调整位置。16 位将允许航点更新超过 400m。因此,如果您知道该设备不适用于飞机并且经常更新,这也可能是可以接受的。