Znajdź najbliższe najlepsze dopasowanie do koła

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.

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ół

d_ij^2=(xi-xj)^2+(yi-yj)^2  

4) umieść wszystkie pary kół, które

dij^2<R^2

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

a = R+ri  
b = R+rj  
c = dij  
α = arccos((b^2+c^2-a^2)/(2bc)  

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).

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

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

(C1x - X)^2 + (C1y - Y)^2 > (C1r + R)^2
(C2x - X)^2 + (C2y - Y)^2 > (C2r + R)^2
....
(Cnx - X)^2 + (Cny - Y)^2 > (Cnr + R)^2

zmiana pierwszego równania,

C1x^2 - 2C1x*X + X^2 + C1y^2 - 2C1y*Y + Y^2 > C1r^2 + 2C1r*R + R^2
X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2

więc równania mogą zostać zapisane ponownie,

X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2
X^2 + Y^2 - 2C2x*X - 2C2y*Y > C2r^2 + 2C2r*R + R^2 - C2x^2 - C2y^2
....
X^2 + Y^2 - 2Cnx*X - 2Cny*Y > Cnr^2 + 2Cnr*R + R^2 - Cnx^2 - Cny^2

Realizacja

zacznij od współrzędnej białej kropki (Xw, Yw),

    var isValidLocation = function(x,y,r){
       var valid = true;
       for (var i = 0; i< circles.length; i++){
          var circle = circles[i];
          valid = valid && ((x*x + y*y - 2*circle.x*x - 2*circle.y*y) > (circle.radius*circle.radius + 2*circle.radius*r + r*r - circle.x*circle.x - circle.y*circle.y));
       }
       return valid;
      };

      var find = function(Xw,Yw,Rw){
        var radius = 0;
        while(true){
          for (var x=-1 * radius ;x <= radius; x++) {
            for (var y=-1 * radius;y <= radius; y++) {
               if (isValidLocation(Xw + x,Yw + y, Rw)){
                 drawCircle(Xw + x,Yw + y,Rw,"#0000FF");
                 return;
               }
            }   
          } 
          radius++;
        }
     }; 

pierwszą współrzędną spełniającą wszystkie równania jest lokalizacja niebieskiego koła

• O, będąc punktem, do którego próbujesz być blisko
• P jest punktem, którego szukasz (środek niebieskiego koła
• r jest promieniem niebieskiego koła
• C0 .. Cn jest środkiem wszystkich okręgów, które ograniczają umieszczanie niebieskiego na

• 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ń

Możliwe rozwiązania odnośnika

1. Sprawdź, czy biały punkt sam w sobie jest rozwiązaniem. Obejmuje skrzynkę z 0 czerwonymi kółkami i trywialną skrzynkę, gdy czerwone kółka są daleko od białego punktu.
2. Jedno czerwone kółko.
   1. Biały punkt jest środkiem koła. Możliwymi rozwiązaniami jest nieskończona liczba punktów na okręgu, którego środek znajduje się w białym punkcie, a promień jest sumą promienia niebieskich kół i średnicy czerwonego kółka. Nazwijmy to zielonym kółkiem .
   2. Biały punkt jest gdzie indziej. Jest tylko jedno możliwe rozwiązanie na linii, która łączy biały punkt i środek czerwonego koła, jest to promień niebieskiego koła od punktu, w którym czerwone koło przecina linię w kierunku białego punktu.
3. Dwa lub więcej czerwonych kółek.
   1. Weźmy czerwone kółka jeden po drugim i poszukaj możliwego rozwiązania dla każdego z nich osobno, zgodnie z punktem 2 (jedno koło).
   2. Dla każdej pary czerwonych kółek sprawdźmy, czy możesz narysować niebieskie koło dotykając obu czerwonych. To znaczy, jeśli odległość między ich środkami jest równa lub mniejsza niż suma ich promieni plus średnica niebieskiego koła. Jeśli możesz, masz dwa (lub jedno, jeśli czerwone kółka są dokładnie o jedną niebieską średnicę od siebie) możliwe rozwiązania .

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.

1. Jeśli chodzi o rozwiązanie. Żadne czerwone kółko nie powinno mieć środka bliżej niż promień do tego punktu.
2. Jeśli jest bliżej punktu bieli niż rozwiązanie znalezione wcześniej.
3. Jeśli masz zielone kółko (punkt 2.1)
   • Jeśli wśród poszczególnych punktów nie ma rozwiązania, które należy do zielonego koła, to zielone kółko jest odpowiedzią.
   • Jeśli masz indywidualne rozwiązania w zielonym kółku i potrzebujesz tylko dowolnego rozwiązania, wybierz jedno z nich.
   • Jeśli masz indywidualne rozwiązania w zielonym kółku i potrzebujesz wszystkich nieograniczonej liczby rozwiązań, musisz rozwiązać inny problem. Musisz wyciąć z zielonego koła wszystkie łuki zdefiniowane przez parę indywidualnych rozwiązań z każdego czerwonego koła.

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ć.