Algorytm pokrywający maksymalną liczbę punktów z jednym okręgiem o zadanym promieniu

To jest "problem częściowego pokrywania dysku" w literaturze -- to powinno dać ci dobre miejsce do rozpoczęcia googlowania. Oto papier zawierający jedno możliwe rozwiązanie, ale jest to trochę intensywne matematycznie: http://www.utdallas.edu/ ~ edsha/papers/bin / ispan04_cover.pdf

W rzeczywistości jest to dziedzina zwana geometrią obliczeniową, która jest fascynująca, ale może być trudna do opanowania. Jest dobry przegląd przez deBerg na temat różnych algorytmów związanych z temat.

Jeśli chcesz czegoś prostego, weź losową pozycję (x,y), oblicz liczbę punktów wewnątrz okręgu i porównaj z poprzednią pozycją. Weź maksimum. Powtórz operację w dowolnym momencie.

Dlaczego do cholery downvote? Słyszałeś kiedyś o metodach Monte Carlo? W rzeczywistości dla ogromnej liczby punktów deterministyczny algorytm może nie zakończyć się w rozsądnym czasie.

Problem powraca do znalezienia globalnego optimum funkcji f :R x R -> N. Wejście dla f jest punktem środkowym okręgu, a wartością jest oczywiście liczba punktów zawartych w zbiorze. Wykres funkcji będzie nieciągły, nieciągły.

Możesz zacząć od sprawdzenia funkcji w każdym punkcie odpowiadającym punktowi w zbiorze, uporządkować punkty przez zmniejszenie wartości f , a następnie zintensyfikować wyszukiwanie wokół tych punktów (np. poruszanie się wzdłuż spirali).

Inną opcją jest rozważenie wszystkich punktów przecięcia segmentów łączących dowolne pary punktów w zbiorze. Twój optymalny punkt będzie na jednym z tych skrzyżowań, ale ich liczba jest prawdopodobnie zbyt duża, aby wziąć pod uwagę.

Można również dokonać hybrydyzacji opcji 1 i 2 oraz rozważyć przecięcia segmentów wygenerowanych z punktów wokół "dobrych punktów zadanych".

Tak czy inaczej, chyba że liczba punktów ustawionych jest niski (pozwala sprawdzić wszystkie skrzyżowania), nie sądzę można zagwarantować, aby znaleźć optymalne (po prostu dobre rozwiązanie).

Na pierwszy rzut oka powiedziałbym, że rozwiązanie quad tree.

Istnieje również metoda wizualizacji informacji / eksploracji danych o nazwie K-means, która tworzy klastry danych. Może być używany z dodatkową funkcjonalnością, aby dopasować się do twojego celu.

Podstawowy algorytm dla K-oznacza:

1. umieść punkty K w przestrzeni reprezentowanej przez elementy które są grupowane-punkty te reprezentują początkowe centroidy grupy
2. przypisanie każdej pozycji danych do grupa, która ma najbliższą centroid
3. Gdy wszystkie elementy zostały przypisane, Przelicz ponownie pozycje centroidów K obliczając średnią pozycję Twoich kropek
4. powtórz kroki 2 i 3, aż centroidy nie będą się już poruszać lub poruszają się bardzo mało

Dodana funkcjonalność będzie wtedy:

1. oblicz liczbę punktów w okręgu umieszczonych w Centroidach K
2. Wybierz ten, który najbardziej Ci odpowiada ;)

Źródła:
K-oznacza algorytm- Linköping University
Quadtree - en.wikipedia.org/wiki/Quadtree

Szybkie przeszukanie Wikipedii i znalezienie kodu źródłowego: en.wikipedia.org/wiki/K-means_clustering

Oto dwie idee: algorytm przybliżenia O(n) i algorytm dokładnego O(N^2 log n):

Szybkie przybliżenie

Użyj hashowania wrażliwego na lokalizację. Zasadniczo, hash każdy punkt do wiadra hash, który zawiera wszystkie pobliskie punkty. Łyżki są tak skonfigurowane, że kolizje zdarzają się tylko między pobliskimi punktami - w przeciwieństwie do podobnie nazwanych tabel skrótów, kolizje są tutaj przydatne. Zachowaj bieżącą liczbę kolizji w wiadrze, a następnie użyj środek wiadra jako środek twojego okręgu.

Przyznaję, że jest to szybkie wyjaśnienie pojęcia, które nie jest zbyt oczywiste, gdy pierwszy raz o nim usłyszysz. Analogią byłoby zapytać grupkę ludzi, jaki jest ich kod pocztowy i użyć najczęstszego kodu pocztowego, aby określić najbardziej zaludniony krąg. To nie jest idealne, ale dobre szybkie heurystyczne.

Jest to w zasadzie czas liniowy pod względem liczby punktów i można aktualizować zestaw danych w locie, aby stopniowo uzyskać nowe odpowiedzi w stałym czasie na punkt(stała w odniesieniu do n = liczba punktów).

Więcej o ogólnie o hashach lub o mojej ulubionej wersji, która by w tym przypadku zadziałała.

Podejście deterministyczne lepsze od brutalnej siły

Idea jest taka: dla każdego punktu umieść krawędź okręgu na tym punkcie i zamiataj okrąg wokół, aby zobaczyć, w którym kierunku znajduje się najwięcej punktów. Zrób to dla wszystkich punktów i my znajdź global max.

Zamiatanie wokół punktu p może być wykonane w czasie n log n przez: (a) znalezienie przedziału kątowego dla innego punktu q takiego, że gdy umieścimy okrąg pod kątem theta, to zawiera on q; oraz (b) sortowanie przedziałów tak, że możemy maszerować/zamiatać wokół p w czasie liniowym.

Więc potrzeba czasu O(N log n), aby znaleźć najlepszy okrąg dotykający ustalonego punktu p, a następnie pomnóż to przez O (n), aby sprawdzić wszystkie punkty. Całkowity czas wynosi O (N^2 log n).

Jeśli prawdą jest, że precyzja nie jest ważna i algorytm może popełniać małe błędy, to myślę, że poniżej.

Niech {[0] } Jest funkcją, która ma maksimum w punkcie (0,0) i jest znacząca tylko w punktach wewnątrz okręgu o promieniu R. na przykład f(x,y) = e^{(x^2 + y^2)/ (2 * R^2)}.

Niech (x_i,y_i) będą punktami i E_i(x,y) = f(x - x_i, y - y_i).

Twoim problemem jest znalezienie maksimum \sum_i E_i(x,y) .

Możesz użyć opadania gradientu rozpoczynającego go od każdego punktu.

Czy mogę zaproponować mapę gęstości? Znajdź granice min i max dla X i Y. podziel zakres granic x i y na pojemniki o szerokości równej średnicy okręgu. Policz liczbę punktów w każdym koszu dla x i y oddzielnie. Teraz znajdź skrzyżowanie na mapie gęstości między najwyżej sklasyfikowanym koszem x i najwyżej sklasyfikowanym koszem Y.

Jest to bardzo szybki algorytm do szybkiego uogólniania dużych zbiorów danych, ale nie zawsze jest dokładny, aby poprawić dokładność może pokroić kosze na mniejsze i mniejsze kawałki lub przesunąć pozycje kosza w lewo lub w prawo n razy i użyć systemu głosowania, aby wybrać odpowiedź, która występuje najczęściej między próbami.

Możesz pikselizować cały obszar, a następnie przejść do każdego punktu i zwiększyć wartość wszystkich pikseli w okręgu promienia wokół tego punktu. Piksele z najwyższą sumą są dobrymi kandydatami.

Oczywiście możesz stracić kilka dobrych obszarów lub "halucynować" dobre obszary z powodu błędów zaokrąglania. Być może mógłbyś najpierw spróbować zrobić rough pixellation, a następnie udoskonalić obiecujące obszary.

Jest to słynny algorytm K-najbliższego punktu. Opisane tutaj: http://www.cs.ucsb.edu/ ~ suri / cs235 / ClosestPair. pdf