9

二次元ポイントのセットのハッシュコードを計算する最適な方法を探しています (ポリゴンをハッシュテーブルに格納できるようにするため)。

文字列内のすべてのポイント座標とそのハッシュコードを連結するなど、いくつかの明白な方法がありますが、これは非常に遅くなります。

速度/衝突スペクトルの反対側では、たとえば、すべての座標を合計することもできます。これにより、非常に高速なコードが得られますが、多くの衝突も発生します。

ポイントのセットのハッシュコードを計算する最適な方法は何ですか?

座標が整数の場合 (対実際の座標)、最適解は異なりますか?

編集: 私は .net を使用しているため、ハッシュコードは 32 ビット長にする必要があります。

4

7 に答える 7

13

この仕事に最適な方法はありません。それはすべて、余裕のあるハッシュの大きさに依存します。速度と拡散の間でトレードオフを行う必要があります。最適な解決策などないことに注意してください (何をハッシュするかを正確に把握していない場合)。場合によっては xor で十分です。

たとえば、このコードを見てください

unsigned int JSHash(char* str, unsigned int len)
{
    unsigned int hash = 1315423911;
    unsigned int i    = 0;

    for(i = 0; i < len; str++, i++)
    {
        hash ^= ((hash << 5) + (*str) + (hash >> 2));
    }

    return hash;
}
/* End Of JS Hash Function */

ポイントをまとめるのが遅いとおっしゃいました。上位コードを修正する場合、どのような種類の集計も必要ありません。単にトラウトを渡すだけです (合計と大差ありません)。また、整数と浮動小数点数を使用している場合は、おそらくシフトを修正します (<< と >> は、一緒にビット単位のように機能するシフト演算です)。回転) を使用して、データ型に合わせます。

ここで他のハッシュ関数を確認してください: http://www.partow.net/programming/hashfunctions/

于 2009-08-16T14:06:34.933 に答える
1

最適は、ハッシュ計算の要件によって異なります。

パフォーマンスは、より多くのハッシュ衝突を犠牲にして実現されます。

どちらかにハードバウンドがありますか？ハッシュの衝突の各パーセントがパフォーマンスの観点からどれだけのコストをかけるかについての数学的な分析に行き着きます。

于 2009-08-16T13:51:24.177 に答える
1

万一、データ セットが、共通のエッジを持つ可能性があるがそれ以外はオーバーラップしないポリゴンの 1 つである場合、衝突を避けるために、各ポリゴンの 3 つのポイントでハッシュするだけで済みます。

編集：これを再考し、凹面/凸面の境界との衝突の可能性を描写すると、ポリゴンが重なっています。- ため息

悲しいかな、凸面と凹面が出会うと、いつも困ってしまいます。:-P

于 2009-08-16T14:34:01.193 に答える
0

時計回り/反時計回りの独立性に関する目的のプロパティを備えた非常に高速な（計算する）ハッシュの場合、ポイントの明確に定義された順序を見つけることに依存したくないでしょう。

これにより、ハッシュ結合操作が通勤する操作に制限されます。したがって、結合操作中は、方向に依存しないすべてのデータを分離しておく必要があります。

簡単な解決策は次のとおりです。

結合関数int->int->intが結合法則であると仮定すると、次のいずれかで始まります。

public static int combine(int h, int x)
{
    return h * 31 + x;
} 

public static int combine(int h, int x)
{
    return h ^ x;
}

次に、次のことを実行できます。

public override int GetHashCode()
{
    int x = 0;
    int y = 0;
    uint h = 0;    
    foreach (var point p in polgon)
    {
        x = combine(x, p.X);
        y = combine(y, p.Y);
        h++;
    }
    // simplified, unrolled Murmur2 hash for end stage
    const uint m = 0x5bd1e995;
    const int r = 24;
    uint h = count;
    uint k = ReinterpretInt32ToUInt32(x);
    k *= m;
    k ^= k >> r;
    k *= m;
    h *= m;
    h ^= k;
    k = ReinterpretInt32ToUInt32(y);
    k *= m;
    k ^= k >> r;
    k *= m;
    h *= m;
    h ^= k;
    // avalanche
    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;
    return ReinterpretUInt32ToInt32(h);
}

上記のコードを簡単にするためにこれに依存する

public unsafe uint ReinterpretInt32ToUInt32(int i)
{
    return *((uint*) (void*) &i);
}

public unsafe int ReinterpretUInt32ToInt32(uint u)
{
    return *((int*) (void*) &u);
}

これは、衝突回避の観点からは最良のハッシュではありませんが、計算が非常に高速である必要があり、ニーズに十分に対応できる場合があります。

于 2009-08-20T00:19:35.730 に答える
0

この論文をチェックしてください

ラムダンとウルフソン。幾何学的ハッシュ: 一般的で効率的なモデルベースの認識スキーム。コンピュータビジョン。(1988)

于 2009-08-16T22:58:04.843 に答える
0

または、個々のポイントのハッシュを XOR することもできます。

return p1.GetHashCode() ^ p2.GetHashCode()

とにかく値がどうなるかによって異なります。おそらくそれらを追加することができます。

于 2009-08-16T22:59:57.023 に答える
0

時計回りと反時計回りに定義されているが、それ以外は等しいポリゴンを等しくしたい場合は、正規化関数を作成する必要があります。任意のポイントから始まるポリゴン ポイントを任意の順序で指定する関数は、ポイントを同じ順序で返します。

私が考えることができる 1 つのアルゴリズムは、すべての可能なポイント シーケンスの最小値を見つけることです。

  1. 左上端の点 (y が最小の点のうち x が最小の点) のセットを見つけます。これらが開始点です。
  2. 各開始点と各方向について、指定された方向に接続されたポイントを繰り返し追加し、現在の反復で左上にないすべてのポイントを削除します。開始点と方向のペアが 1 つだけ残ったとき、または n-1 回の反復が完了したときに停止します。複数の開始点と方向が残っている場合は、いずれかを選択します。それらはすべて同形です。
  3. 見つかったポイントから、見つかった方向にポイントを並べ替えます。

これは、完全に縮退したポリゴンの最悪の場合は O(n^2) ですが、ポリゴンに重複するポイントがない場合、これは O(n) であり、かなり小さな定数係数です。

正規化された順序を使用すると、2 つのポリゴンが等しいかどうかを簡単に比較できます。ポイントが等しいかどうかを繰り返し比較するだけです。ハッシュコードの計算も自明です。適度に堅牢なハッシュ結合方法を使用してください。例えば：

int result = 0;
foreach (var point in this.points) {
    result = (result * 31 + point.X.GetHashCode()) * 31 + point.Y.GetHashCode();
}
于 2009-08-17T18:32:21.450 に答える