Algorytm wyszukujący kwadraty w zbiorze punktów - optymalizacja

Question

Taki projekt: https://youtu.be/Z3eBgXXaToU

Ogólnie mój algorytm działa, ale jest dosyć wolny ze względu na złożoność silniową. Jeśli gracz ma 10 kropek, znalezienie wszystkich kwadratów zajmuje ~1000ms, jak ma 20 kropek - ~20000ms.

Mój algorytm:

1) znajdź wszytskie 4-elementowe kombinacje w zbiorze kropek i zapisz je.

2) dla każdej kombinacji wyznacz 6 dystansów(1-2,2-3,3-4,4-1,1-3,2-4)

3) dla każdej szóstki dystansów wyznacz i zapisz ich wszystkie 6-elementowe wariacje(jest ich 120)

4) dla każdej takiej wariacji: jeśli pierwsze 4 dystanse są sobie równe(boki kwadratu) i ostatnie dwa są sobie równe(przekątne kwadratu), to znalazłeś kwadrat i przerwij pętlę szukającą kwadratu w wariacjach.

 

Wydaje mi się, że może być efektywny sposób połączenia 3 i 4 kroku, w każdym razie ta 6! mocno spowalnia algorytm.

 

Jak ktoś ma jakiś pomysł na usprawnienie algorytmu lub zupełnie inne rozwiązanie, to dajcie znać

 

PS: algorytm jest wywoływany za każdym razem, jak gracz wybierze kropkę - dla kropek gracza, który właśnie wybrał kropkę

Comments

Mając dwa punkty zauważ że kwadrat zawierający je jest dwuznacznie zdefiniowany. Możesz dla każdej pary punktów sprawdzić oba kwadraty w czasie stałym przy użyciu hashmapy. Złożoność tego algorytmu jest O(n^2).

Istnieją lepsze algorytmy lecz są bardziej skomplikowane. Możesz sobie poczytać jak chcesz czegoś szybszego. Finding squares and rectangles in sets of points

---

(drugie źródło, które vector też na pewno widział, a pewnie jest warte zalinkowania: http://stackoverflow.com/questions/3831144/finding-the-squares-in-a-plane-given-n-points )

(nawiasem mówiąc, to pierwszy wynik wyszukiwania w googlu...)

Answer 1

Ok, znalazłem na stacku:

for each pair of points
    for each of 3 possible squares which might be formed from these two points
        test remaining points to see if they coincide with the other two vertices

 

Trochę mi głupio, że nie pogooglowałem tematu zanim napisałem temat, no ale już trudno, może się komuś kiedyś przyda ;)

dzięki chłopaki!

 

Comments

Well, to jedno z gorszych rozwiązań, najwyraźniej O(n^3) lub, z optymalizacjami, O(n^2 * log(n)). Ale jak to Cię zadowala to ok.