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

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

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

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

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

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

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

Посмотрите эту статью

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

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

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

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

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

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

1. Найти набор крайних левых точек (точки с минимальным x из точек с минимальным y), это начальные точки.
2. Для каждой начальной точки и каждого направления итеративно добавляйте связанные точки в заданном направлении и удаляйте все, что не указано ' t крайний левый верхний в текущей итерации. Остановка, когда осталась только одна начальная точка, пара направлений или когда завершено 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();
}

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

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

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

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

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