java - 整数座標のポリゴン圧縮

Question

「signed int」2D座標を持つラスターにポリゴンがあります。ポリゴンの頂点は、時計回りに並べられています。

このポリゴンを、int x、y 座標のシーケンスを格納するだけの、より「スペースにやさしい」方法で格納したいと考えています。このファイルを rar で圧縮すると、非圧縮の約 3.5 倍のサイズになります。単純に x,y をシーケンスに格納するよりも優れた表現はありますか?

圧縮は無損失でなければなりません。

Answer 1

ポリゴンが (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 ペアは通常、8 バイトではなく 2 バイトまたは 4 バイトで格納できます。

Answer 2

結果は多くの要因に依存するため、明確な答えを提供することは困難です。個々のポリゴンを圧縮するために 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 が目的全体を打ち負かすからです。フィギュアが欲しかっただけなのに…