3

我在带有“signed int”二维坐标的栅格中有多边形。多边形的顶点按顺时针方向排列。

我想以更“空间友好”的方式存储这个多边形，只存储 int x, y 坐标的序列。如果我用 rar 压缩这个文件，我得到的大小比未压缩的要小 3.5 倍。有没有比简单地将 x,y 存储在一个序列中更好的表示？

压缩应该是无损的。

4

2 回答 2

7

如果你的多边形是 (x1, y1), (x2, y2) ... (xn, yn)，你可以写成，

x1, x2-x1, x3-x2, xn-xn-1, y1, y2-y1 ..., yn-yn-1

通常，相邻 x,y 值之间的差异将小于绝对值，因此您可以将增量存储为可变长度 ints。通过这样做，每个 x,y 对通常可以存储在 2 或 4 个字节而不是 8 个字节中。

于 2013-03-29T03:21:14.460 回答
1

很难给出一个明确的答案，因为结果取决于很多因素。我使用 GZIPOutputStream 进行了快速测试来压缩单个多边形，结果很大程度上取决于多边形的点数，也取决于它的面积。

基本上，我创建了具有越来越多的顶点随机分布在预定义区域中的多边形。然后我顺时针对顶点进行排序并用 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 超出了整个目的。我只是想得到一些数字...

于 2013-03-29T21:27:00.407 回答