• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

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

VPS Starter Arubacloud
0 głosów
247 wizyt
pytanie zadane 20 marca 2017 w C# przez Adam Olesiak Gaduła (3,290 p.)

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ę

komentarz 20 marca 2017 przez vector Dyskutant (9,200 p.)

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

komentarz 20 marca 2017 przez adrian17 Ekspert (344,100 p.)
(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...)

1 odpowiedź

0 głosów
odpowiedź 20 marca 2017 przez Adam Olesiak Gaduła (3,290 p.)

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!

 

komentarz 20 marca 2017 przez adrian17 Ekspert (344,100 p.)
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.

Podobne pytania

+2 głosów
2 odpowiedzi 887 wizyt
0 głosów
3 odpowiedzi 332 wizyt
pytanie zadane 20 maja 2019 w Matematyka, fizyka, logika przez belkowski656 Nowicjusz (220 p.)
0 głosów
0 odpowiedzi 267 wizyt
pytanie zadane 8 stycznia 2017 w C i C++ przez Akdx Początkujący (310 p.)

92,452 zapytań

141,262 odpowiedzi

319,083 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...