Jaki jest optymalny sposób obliczania skrótu dla zestawu punktów?

Question

Poszukuję optymalnego sposobu obliczania kodu skrótu dla zestawu punktów dwuwymiarowych (aby móc przechowywać wielokąty w tablicy hashtable).

Istnieje kilka oczywistych sposobów, aby to zrobić, na przykład łączenie wszystkich współrzędnych punktów w łańcuchu i jego kodu kreskowego, ale byłoby to bardzo powolne.

Na drugim końcu spektrum prędkości/kolizji, mogę również na przykład podsumować wszystkie współrzędne, co skutkowałoby bardzo szybkim kodem, ale również spowodowałoby wiele kolizji.

Jaki jest optymalny sposób obliczenia kodu skrótu dla zestawu punktów?

Czy optymalne rozwiązanie jest inne, jeśli współrzędne są liczbą całkowitą (w stosunku do rzeczywistych współrzędnych)?

Edytuj: Używam .net, więc hashcode powinien mieć długość 32 bitów.

Answer 1

Nie ma optymalnego sposobu dla tego zadania. Wszystko zależy od tego, na jak dużą skalę możesz sobie pozwolić. Musisz dokonać wymiany między szybkością a dyfuzją. Pamiętaj, że nie ma czegoś takiego jak optymalne rozwiązanie (jeśli nie wiesz dokładnie, co masz zamiar mieszać) W niektórych przypadkach xor może być wystarczająco dobry.

Weźmy na przykład ten kod

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 */ 

Mówiłeś, że agregating punkty razem jest powolny. Jeśli naprawisz górny kod, to nie potrzebujesz żadnego rodzaju agregacji po prostu przekazuj trought (niewiele różni się to sumami) A jeśli używasz integerów i floats prawdopodobnie naprawisz zmiany (< < i >> są operacjami shift, które razem działają jak bitowe obrót), aby dopasować swój typ danych.

Sprawdź inne funkcje hash tutaj: http://www.partow.net/programming/hashfunctions/

Answer 2

Optymalny jest zależny od twoich wymagań od obliczeń haszowania.

Wyniki będą występować kosztem większej liczby kolizji mieszania.

Czy masz jedno twarde ograniczenie? Sprowadzi się to do analizy matematycznej tego, ile procent kolizji hashowych będzie cię kosztowało pod względem wydajności.

Answer 3

Jeśli zestaw danych jest przypadkiem jednym z wielokątów, które mogą mieć wspólne krawędzie, ale nie pokrywają się inaczej, trzeba tylko hash na trzy punkty w każdym wielokąt unikaj kolizji.

Edytuj: Ponownie rozważając to, wyobrażając sobie możliwe kolizje z wklęsłymi/wypukłymi granicami, równie dobrze pokrywają się wielokąty. - Westchnienie

Niestety: kiedy wypukłe i wklęsłe spotykają się, zawsze wpadają mi w kłopoty. :-P

Answer 4

Sprawdź ten papier

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

Answer 5

Alternatywnie, można po prostu XOR mieszań poszczególnych punktach.

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

W zależności od tego, jakie będą wartości. Prawdopodobnie mógł po prostu je dodać.

Answer 6

Jeśli chcesz wielokątów, które są zdefiniowane zgodnie z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara, ale poza tym równe, aby być równe, musisz utworzyć funkcję kanonizacji. Funkcja, która dała punkty wielokątów zaczynając od dowolnego punktu i w dowolnej kolejności, zwróci punkty w równej kolejności.

Jeden algorytm, który mogę myśleć jest znalezienie minimum wszystkich możliwych sekwencji punktów:

1. Znajdź zestaw lewej górnej punktów (punktów minimalnych X punktów z minimum Y) to są punkty wyjścia.
2. Dla każdego punktu początkowego i każdego kierunku, iteracyjnie dodaj połączone punkty w określonym kierunku i wyeliminuj wszystkie, które nie znajdują się najwyżej z lewej strony w bieżącej iteracji. Zatrzymanie, gdy tylko jeden punkt początkowy, para kierunków jest pozostawiony lub po zakończeniu iteracji n-1. Jeśli pozostało więcej niż jeden punkt początkowy i kierunek, wybierz dowolny - wszystkie są izomorficzne.
3. Zmienić kolejność punktów począwszy od znalezionego punktu w znalezionym kierunku.

To jest najgorszy przypadek O (n^2) dla w pełni zdegenerowanych wielokątów, ale jeśli twoje wielokąty nie mają nachodzących na siebie punktów, jest to O (n), z całkiem małym stałym współczynnikiem.

Za pomocą kanonicznej kolejności można łatwo porównać dwa wielokąty dla równości, po prostu iteracyjnie porównać punkty dla równości. Wyliczanie hasztoków jest również trywialne, należy użyć dowolnej rozsądnej metody mieszania hash. Na przykład:

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

Answer 7

na bardzo szybki (do obliczenia) hash o pożądanych właściwościach w kierunku ruchu wskazówek zegara/przeciwnie do ruchu wskazówek zegara niezależności nie chciałby być uzależnione od znalezienia dobrze zdefiniowaną kolejność punktów.

To ogranicza łączenie operacji mieszania do tych, które dojeżdżają do pracy. Dlatego chcemy zachować wszystkie dane niezależne od orientacji podczas operacji łączenia.

Oto proste rozwiązanie:

Zakładając int function połączyć -> int -> int który jest łączne którykolwiek z poniższych zrobi zacząć:

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

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

Wtedy możemy zrobić co następuje:

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

Powołując się na to, aby powyższy kod łatwego

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

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

To nie będzie najlepsza mieszanka pod względem unikania kolizji, ale powinna być bardzo szybka do obliczenia i może okazać się wystarczająca dla twoich potrzeb.