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

Question

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

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

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

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

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

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

Answer 1

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

Answer 2

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

Производительность будет обеспечиваться за счет большего количества хэш-коллизий.

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

Answer 3

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

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

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

Answer 4

Ознакомьтесь с этой статьей

Ламдан и Вольфсон.Геометрическое хеширование:Общая и эффективная схема распознавания, основанная на модели.Компьютерное зрение.(1988)

Answer 5

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

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

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

Answer 6

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

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

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

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

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

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);
}

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