Каков оптимальный способ вычисления хэш-кода для набора точек?

Question

Я ищу оптимальный способ вычисления хэш-кода для набора двумерных точек (чтобы я мог хранить многоугольники в хэш-таблице).

Есть некоторые очевидные способы сделать это, например, конкатенировать все координаты точек в строке и ее хэш-код, но это будет очень медленно.

На другом конце спектра скорости/столкновения я могу, например, суммировать все координаты, что приведет к очень быстрому коду, но также создаст много столкновений.

Каков оптимальный способ вычисления хэш-кода для набора точек?

Является ли оптимальное решение отличным, если координаты целые (vs действительные координаты)?

Редактировать: Я использую .net, поэтому хэш-код должен быть длиной 32 бит.

Answer 1

Нет оптимального способа для этой работы. Все зависит от того, какой большой хэш вы можете себе позволить. Вы должны сделать tradoffs между скоростью и диффузией. Имейте в виду, что нет оптимального решения (если вы точно не знаете, что собираетесь делать хэшем). В некоторых случаях 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 */ 

Вы сказали, что agregating очков вместе, чтобы замедлить. Если вы исправляете верхний код, вам не нужен какой-либо агрегат, который просто пропускает обработку (не сильно отличается от суммы). И если вы используете целые числа и поплавки, вы, вероятно, исправите сдвиги (< < и >> - это операции сдвига, которые вместе работают как побитовые вращение), чтобы соответствовать типу данных.

Проверьте другие хэш-функции здесь: http://www.partow.net/programming/hashfunctions/

Answer 2

Оптимальный зависит от ваших требований от вычисления хеша.

Производительность будет зависеть от дополнительных столкновений с хэшем.

Есть ли у вас жесткая граница на любом из них? Приведем математический анализ того, насколько каждый процент столкновений с хешем будет стоить вам с точки зрения производительности.

Answer 3

Если набор данных случайно один из полигонов, которые могут иметь общие ребра, но не перекрываются в противном случае, вам нужно только хэш на трех точках каждого полигона в избегать столкновений.

Редактирование: пересматривая это, представляя возможные столкновения с вогнутыми/выпуклыми границами, это также хорошо перекрывает ваши полигоны. - Sigh

Увы: Когда выпуклое и вогнутое встречается, это всегда вызывает у меня проблемы. :-P

Answer 4

Заканчивать этот документ

Lamdan and Wolfson. Geometric hashing: A general and efficient model-based recognition scheme. Computer Vision. (1988)

Answer 5

В качестве альтернативы, вы можете просто XOR хэши отдельных точек.

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

В зависимости от того, какие значения будут в любом случае. Вероятно, можно просто добавить их.

Answer 6

Если вы хотите, чтобы полигоны, определенные по часовой стрелке и против часовой стрелки, но в остальном равные, были равны, вам необходимо создать функцию канонизации. Функция, задающая точки полигонов, начиная с любой точки и в любом порядке, вернет точки в равном порядке.

Один алгоритм, который я могу думать о том, чтобы найти минимум из всех возможных последовательностей точек:

1. Найти множество топ-левый точек (точки с минимальным х точек с минимальным у), это отправные точки.
2. Для каждой начальной точки и каждого направления итеративно добавьте подключенные точки в заданном направлении и устраните все, что не являются верхними левыми в текущей итерации. Остановка, когда оставлена ​​только одна начальная точка, пара направлений или когда завершены n-1 итерации. Если осталось больше одной стартовой точки и направления, выберите любой - все они изоморфны.
3. Изменить порядок точек, начиная с найденной точки в указанном направлении.

Это O (n^2) наихудший вариант для полностью вырожденных полигонов, но если ваши многоугольники не имеют перекрывающихся точек, это O (n), с довольно небольшим постоянным коэффициентом.

С каноническим порядком вы можете легко сравнить два полигона для равенства, просто итеративно сравнить точки для равенства. Расчет Hashcode также является тривиальным, используйте любой разумно надежный метод хэш-комбинации. Например:

int result = 0; 
foreach (var point in this.points) { 
    result = (result * 31 + point.X.GetHashCode()) * 31 + point.Y.GetHashCode(); 
} 

Answer 7

Для очень быстрого (для расчета) хэша с заданными свойствами по часовой стрелке/против часовой стрелки независимости вы не хотите зависеть от нахождения четко определенного порядка точек.

Это ограничивает ваши операции хеша, объединяющие операции с коммутируемыми. Поэтому мы хотим сохранить любые и все данные, которые не зависят от ориентации, отдельной во время операций объединения.

Вот простое решение:

Предполагая объединить функции 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); 
} 

Это не лучший хэш с точки зрения предотвращения столкновений, но он должен быть очень быстрым для расчета, и вы можете найти его достаточно для своих нужд.