Poniżej znajduje się przykładowy obraz, jeśli mam punkt białej kropki na środku i chcę znaleźć najbliższą możliwą lokalizację dla niebieskiego koła (która jest oczywiście w miejscu, w którym go umieściłem), jeśli wszystkie czerwone koła już istnieją . Jak mogę znaleźć tę lokalizację?
Wydajność nie jest dla mnie głównym problemem tej aplikacji.
design
design-patterns
algorithms
performance
geometry
Botaniczny
źródło
źródło
Odpowiedzi:
Nie jest to ogólne rozwiązanie, ponieważ istnieje kilka sytuacji, w których nie zapewni pozycji niebieskiego koła w najkrótszej odległości od białej kropki. Na przykład, jeśli masz 100 zgrupowanych czerwonych kulek, a biała kropka jest daleko od tej grupy czerwonych kulek, to żadna z czerwonych kulek nie będzie miała wpływu na pozycję niebieskiego koła, którą można wyśrodkować na białej kropce . Nie pokaże też wszystkich szczegółów obliczeń. W każdym razie, dla podzbioru konfiguracji, w których rozwiązanie (niebieskie koło) jest styczne do dwóch czerwonych kół, powinny działać:
1) niech R będzie promieniem niebieskiego koła
2) zrób pętlę nad wszystkimi parami czerwonych kół, tak Wiem, że to O (n2).
3) dla każdej pary kół i, j o środkach w (xi, yi) i (xj, yj) o odpowiednich promieniach ri i rj, oblicz kwadrat kwadratu odległości między parą kół
4) umieść wszystkie pary kół, które
do listy.
5) przejrzyj listę, znajdując 2 rozwiązania okręgów o promieniu R stycznym do obu okręgów i i j. Aby to zrobić, użyj tych równań razem z tym obrazem
z powyższymi informacjami można znaleźć (X1ij, Y1ij) i (X2ij, Y2ij) środki dwóch okręgów stycznych do okręgów i i j. Dla każdego kandydata niebieskie kółko zapętlić nad wszystkimi innymi czerwonymi kółkami i sprawdzić, czy się nie nakładają. Jeśli to zrobią, odrzuć to, jeśli nie, sprawdź odległość do białego koła. Jeśli trzymasz ten z mniejszą odległością, myślę, że będziesz miał rozwiązanie, gdy skończysz przemierzanie listy par kół. Algorytm wygląda jak O (n3).
źródło
Najbliższe umiejscowienie do punktu będzie albo na punkcie, albo na okręgu.
dlatego najpierw sprawdź punkt, a następnie przetocz nowy okrąg dookoła krawędzi każdego istniejącego koła, obliczając odległość od punktu i jeśli zachodzi na siebie, idź wzdłuż minimalnego punktu odległości. Zatrzymaj się, gdy przejdziesz przez każdy krąg.
to znaczy. sprawdź wszystkie punkty na zielonych liniach oraz białe kółko. gdzie zielona linia jest okręgiem o promieniu czerwonego plus niebieskiego
musisz sprawdzić całą zieloną linię, a nie tylko skrzyżowania, aby pokryć te przypadki krawędzi.
Oczywiście wielkość kroku twojego przejścia będzie ważna pod względem wydajności. Ale ponieważ stwierdzasz, że wydajność nie stanowi problemu, wybierz wartość odpowiadającą rozdzielczości wartości wyjściowej. tj. pływak, długo?
wyjaśnienie:
moją sugestią jest brutalne użycie siły we wszystkich punktach wokół każdego koła, sprawdzając, czy pokrywają się one ze wszystkimi innymi okręgami w każdym punkcie. bez sprytu.
Jeśli przykładowe zdjęcie wskazuje liczbę kół i rozdzielczość, nie powinno to stanowić problemu dla standardowego komputera
mamy 20 okręgów o średnim promieniu 200, czyli około 20 * 2 π * 200 punktów * 20 testów przecięcia = 4800000 iteracji
Uwaga:
Takie podejścia iteracyjne są wadliwe, ponieważ rozmiar kroku, w tym przypadku rozdzielczość wyniku, może znacznie wpłynąć na wynik.
Powiedzmy, że mam dwa czerwone koła oddalone od siebie o 2 piksele i niebieski okrąg o promieniu 1 piksela, aby się między nimi ścisnąć. Najwyraźniej jeden z dwóch pikseli jako środek niebieskiego koła nachodzi na jeden z czerwonych. ale oczywiście jest miejsce na koło, jeśli środek leży między dwoma pikselami.
Stąd mój komentarz z pytaniem o rozdzielczość wyjścia. co powiedziałeś, że może być cokolwiek.
możesz także rozwiązać równanie równoczesne dla każdej pary kół ze wzrostem promienia o promień niebieskiego koła.
da ci to punkty, w których niebieskie kółko dotknie obu czerwonych kół bardziej dokładnie niż iteracyjnie.
Jednak. istnieje kilka warunków, w których jeśli tylko to zrobisz, otrzymasz błędną odpowiedź lub jej brak. to znaczy.
1 lub brak kręgów
2 lub więcej okręgów, ale z punktem docelowym daleko i poza nimi.
wiele okręgów, ale z punktem docelowym blisko powierzchni
źródło
Ten fragment zawiera działający kod,
Pojęcie
Podane okręgi to C1, C2 .... Cn
a współrzędne okręgu Cn to Cnx, Cny, a promień to Cr
a promień wymaganego okręgu wynosi R
jeśli niebieskie kółko znajduje się w położeniu X, Y i nie koliduje z żadnym innym okręgiem, poniższe równania są prawdziwe
zmiana pierwszego równania,
więc równania mogą zostać zapisane ponownie,
Realizacja
zacznij od współrzędnej białej kropki (Xw, Yw),
pierwszą współrzędną spełniającą wszystkie równania jest lokalizacja niebieskiego koła
źródło
rozszerzony okrąg jest jednym z okręgów o promieniu przedłużonym o r
Istnieje dodatkowa praca, jeśli O nie znajduje się w środku okręgu. Więc teraz załóżmy, że O == C0
Oblicz wszystkie przecięcia wszystkich okręgów za pomocą C0, używając ich odpowiednich promieni plus r , tj. Przecinają rozciągnięte okręgi z rozszerzonym C0. Jeśli nie ma skrzyżowań, punkt, którego szukasz, znajduje się w dowolnym miejscu na C0, jeśli są skrzyżowania, dla każdego skrzyżowania sprawdź, czy znajduje się w innym rozszerzonym okręgu (możesz ograniczyć się do okręgów, które miały skrzyżowania z C0). Weź pierwsze skrzyżowanie, które nie znajduje się w innym rozszerzonym kole, ponieważ P, mogą być inne.
Jeśli nie ma przecięć między rozszerzonymi okręgami i C0, które nie znajdują się w innym rozszerzonym okręgu, obliczyć przecięcia wszystkich rozszerzonych okręgów ze sobą. Następnie sprawdź te skrzyżowania w kolejności od odległości do O, ponownie, czy którekolwiek z skrzyżowań leży w innym rozszerzonym kole, jeśli tak, odrzuć, jeśli nie, to twój wynik.
Jeśli wyobrażasz to sobie, wyobraź sobie rysowanie linii wokół wszystkich okręgów, które wskazują możliwą lokalizację twojego niebieskiego koła, połączenie wszystkich rozszerzonych okręgów wskaże obszar, w którym twoje niebieskie koło nie może być. Punkt, którego szukasz, to najbliższy punkt, którego nie ma w tym związku. Jeśli jest jakikolwiek punkt na C0, który nie znajduje się w tej unii, który jest rozwiązaniem, jeśli C0 jest w pełni pokryte, P musi znajdować się na przecięciu dwóch innych rozszerzonych okręgów i musi znajdować się w obszarze, który nie jest objęty ten związek (to znaczy nie w rozszerzonym kręgu ).
To jest O (n ^ 2), istnieje kilka sposobów, aby to poprawić, można jednak użyć siatki, aby zmniejszyć wysiłek w poszukiwaniu pary, również myślę, że sortowanie kręgów według ich bliskości do O (odległość między dwa okręgi zmniejszane przez radio) pomogłyby ograniczyć przestrzeń wyszukiwania dla zasięgu i wyszukiwania skrzyżowań
źródło
Możliwe rozwiązania odnośnika
Rzeczywiste wyszukiwanie rozwiązań wśród możliwych rozwiązań
Teraz masz zestaw punktów, które są możliwymi rozwiązaniami , iteruj je i sprawdzaj dla każdego z nich.
NB: Nie twierdzę, że implementacja algorytmu powinna być dokładnie opisana. Możesz spróbować poprawić wydajność za pomocą programowania dynamicznego lub pomijając możliwe rozwiązania, w przypadku których oczywiste jest, że nie będą działać.
źródło