algorithm - 多边形的压缩表示

Question

我有很多(数百万)来自 openstreetmap-data 的多边形，其中大部分(超过 99%)刚好有四个坐标代表房屋。

示例

我目前将每个房屋的四个坐标显式保存为浮点元组(纬度和经度)，因此占用 32 字节的内存。

有没有办法以压缩方式(少于 32 字节)存储此信息，因为四个坐标在最后的小数点上仅相差很小？

Answer 1

如果您的 map block 不是太大，您可以存储相对于某个基点(例如，左下角)的坐标。获取这些差异，像这样按 map 大小对它们进行规范化:

   uint16_diff  = (uint16) 65535 * (lat - latbottom) / (lattop - latbottom)

这种方法允许存储 16 位整数值。

对于矩形(您可以将它们存储在单独的列表中)，有一种方法可以存储 5 个 16 位值而不是 8 个值 - 左上角坐标、宽度、高度和旋转角度(可能有另一组数据，例如，包括第二个角)

结合这两种方法，一个人可能会得到高达 3.2 倍的数据大小损失