我有一个由"signed int" 2D坐标组成、顶点按顺时针方向排序的光栅多边形。
我想以一种更加“空间友好”的方式存储这个多边形，即只存储int x、y坐标序列。如果我使用rar压缩文件，得到的文件大小约为未压缩大小的3.5倍。
有没有比仅存储x、y序列更好的表示方式？
压缩应无损。
整数坐标的多边形压缩
3
- Martin Perry
2
这个多边形是凸多边形吗？还是可能是非凸多边形？ - kutschkem
@kutschkem 它不一定是凸多边形，但它是一个简单的多边形：它不会自相交。 - AlexWien
2个回答
7
如果你的多边形是 (x1, y1), (x2, y2) ... (xn, yn)，你可以将其写为：
x1，x2-x1，x3-x2，xn-xn-1，y1，y2-y1...，yn-yn-1
通常相邻 x、y 值之间的差异会比绝对值小，所以你可以将这些差存储为可变长度整数。通过这样做，每个 x、y 对通常只需占用 2 或 4 个字节，而不是 8 个字节。
x1，x2-x1，x3-x2，xn-xn-1，y1，y2-y1...，yn-yn-1
通常相邻 x、y 值之间的差异会比绝对值小，所以你可以将这些差存储为可变长度整数。通过这样做，每个 x、y 对通常只需占用 2 或 4 个字节，而不是 8 个字节。
- sbridges
5
我两年前就已经这样实现了，但是没有使用var ints，而是尽可能使用short，否则使用int。还有一种更好的解决方案，其中变量ints不仅像Google protobuf中那样仅限于整个字节：我读过一篇文章，他们可以使用12位、13位等ints来完美适配多边形deltaX，y所需的大小。这种压缩类型的Java源代码会很有趣。 - AlexWien
1哪个白痴踩了这个非常好的答案？到目前为止，它是唯一正确的答案。 - AlexWien
相对于顺序：x1，y1，dx2，dy2，dx3，dy3，..，dxn，dyn，您认为您提出的顺序x1，dx2，dx3，.. dxn，y1，dy2，dy2，dyn有什么优势？ - AlexWien
它们可能是等价的。 - sbridges
对于特殊应用程序，如果仅需要 x 坐标，例如通过 x 平面扫描搜索，则您提出的顺序可能会稍微有所优势。那将需要传递给这种方法一半的内存。 - AlexWien
1
很难给出明确的答案，因为结果取决于许多因素。我使用GZIPOutputStream进行了一个快速测试，以压缩单个多边形，结果在很大程度上取决于多边形的点数，但也取决于其面积。
基本上，我创建了一个预定义区域内随机分布的顶点数量逐渐增加的多边形。然后，我按顺时针顺序排序顶点，并使用GZIP压缩差异。
对于适合标准屏幕（1440x900）的多边形：
我不确定如何获得比原来小3.5倍的尺寸，但我认为您将一堆多边形压缩在一起了。将多个多边形压缩在一起显然会增加压缩比。
当然，这对于程序来说并不是可用的方法，因为它必须不断解压缩多边形以将它们绘制到屏幕上，这将需要更多的内存和CPU，从而打乱整个目的。我只是想获取一些数字...
基本上，我创建了一个预定义区域内随机分布的顶点数量逐渐增加的多边形。然后，我按顺时针顺序排序顶点，并使用GZIP压缩差异。
对于适合标准屏幕（1440x900）的多边形：
D Npoints: 3 Uncompressed: 24 Compressed: 41 Ratio: 0.58536583
D Npoints: 4 Uncompressed: 32 Compressed: 49 Ratio: 0.6530612
D Npoints: 5 Uncompressed: 40 Compressed: 58 Ratio: 0.6896552
D Npoints: 6 Uncompressed: 48 Compressed: 61 Ratio: 0.78688526
D Npoints: 7 Uncompressed: 56 Compressed: 66 Ratio: 0.8484849
D Npoints: 8 Uncompressed: 64 Compressed: 72 Ratio: 0.8888889
D Npoints: 9 Uncompressed: 72 Compressed: 80 Ratio: 0.9
D Npoints: 10 Uncompressed: 80 Compressed: 84 Ratio: 0.95238096
D Npoints: 11 Uncompressed: 88 Compressed: 89 Ratio: 0.98876405
D Npoints: 12 Uncompressed: 96 Compressed: 94 Ratio: 1.0212766
D Npoints: 13 Uncompressed: 104 Compressed: 96 Ratio: 1.0833334
D Npoints: 14 Uncompressed: 112 Compressed: 102 Ratio: 1.0980393
D Npoints: 15 Uncompressed: 120 Compressed: 108 Ratio: 1.1111112
. . .
D Npoints: 99 Uncompressed: 792 Compressed: 457 Ratio: 1.7330415
随着面积的增大（1440*4x900*4），压缩比降低：
D Npoints: 3 Uncompressed: 24 Compressed: 45 Ratio: 0.53333336
D Npoints: 4 Uncompressed: 32 Compressed: 55 Ratio: 0.58181816
D Npoints: 5 Uncompressed: 40 Compressed: 60 Ratio: 0.6666667
D Npoints: 6 Uncompressed: 48 Compressed: 67 Ratio: 0.7164179
D Npoints: 7 Uncompressed: 56 Compressed: 70 Ratio: 0.8
D Npoints: 8 Uncompressed: 64 Compressed: 79 Ratio: 0.8101266
D Npoints: 9 Uncompressed: 72 Compressed: 87 Ratio: 0.82758623
D Npoints: 10 Uncompressed: 80 Compressed: 93 Ratio: 0.86021507
D Npoints: 11 Uncompressed: 88 Compressed: 102 Ratio: 0.8627451
D Npoints: 12 Uncompressed: 96 Compressed: 109 Ratio: 0.88073397
D Npoints: 13 Uncompressed: 104 Compressed: 113 Ratio: 0.920354
D Npoints: 14 Uncompressed: 112 Compressed: 119 Ratio: 0.9411765
D Npoints: 15 Uncompressed: 120 Compressed: 125 Ratio: 0.96
D Npoints: 16 Uncompressed: 128 Compressed: 135 Ratio: 0.94814813
D Npoints: 17 Uncompressed: 136 Compressed: 137 Ratio: 0.99270076
D Npoints: 18 Uncompressed: 144 Compressed: 137 Ratio: 1.0510949
D Npoints: 19 Uncompressed: 152 Compressed: 148 Ratio: 1.027027
D Npoints: 20 Uncompressed: 160 Compressed: 148 Ratio: 1.081081
D Npoints: 21 Uncompressed: 168 Compressed: 154 Ratio: 1.0909091
D Npoints: 22 Uncompressed: 176 Compressed: 160 Ratio: 1.1
. . .
D Npoints: 99 Uncompressed: 792 Compressed: 520 Ratio: 1.5230769
我不确定如何获得比原来小3.5倍的尺寸，但我认为您将一堆多边形压缩在一起了。将多个多边形压缩在一起显然会增加压缩比。
当然，这对于程序来说并不是可用的方法，因为它必须不断解压缩多边形以将它们绘制到屏幕上，这将需要更多的内存和CPU，从而打乱整个目的。我只是想获取一些数字...
- Jorge Cardoso
2
有些系统会像导航系统一样，将地图的一部分（多边形）压缩起来，以便在该部分不被使用时节省空间。 - AlexWien
@AlexWien 没有考虑过那种情况。在那种情况下是有道理的，因为您不会重复绘制多边形。我不知道为什么，但我的第一反应是原始意图是为屏幕上的多边形保持较小的内存占用。 - Jorge Cardoso
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接