Znajdź najbliższe najlepsze dopasowanie do koła

12

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.

wprowadź opis zdjęcia tutaj

Botaniczny
źródło
1
jakie jest znaczenie czarnego koła? czy umieścisz nad nim niebieskie kółko?
Ewan
2
Czyli żeby było jasne, czy chcesz, aby miejsce, w którym możesz umieścić niebieskie kółko w taki sposób, aby było to możliwie najkrótsza odległość od białego punktu bez nakładania się na inne kółka?
Robert Harvey
3
Powiązane: Circle Packing
Robert Harvey
2
Czy wszystkie kręgi zawsze będą dotykać jakiegoś innego koła w co najmniej jednym miejscu?
Robert Harvey
3
Powiązane: stackoverflow.com/questions/10666116 i stackoverflow.com/questions/5509151 . Możliwe również znaczenie: stackoverflow.com/a/19375601
Robert Harvey

Odpowiedzi:

4

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 dwa niebieskie kółka kandydują na parę czerwonych kółek

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

Mandryl
źródło
nie działa, gdy jest tylko jedno koło
Ewan
lub dwa okręgi, ale z punktem docelowym poza oboma z nich
Ewan
Problem w tym, że nie możesz mieć pewności, że masz wszystkie skrzynie
Ewan
również. istnieją unikalne rozwiązania dla tych przypadków
Ewan
Musisz zapisać wszystkie założenia, na podstawie których rozwiązanie jest poprawne, lub przynajmniej wskazać wszystkie przypadki graniczne. Niektóre z nich mogą być oczywiste, ale niektóre nie. Na przykład to nie zadziała, jeśli można narysować linię oddzielającą białą kropkę od wszystkich czerwonych kół, a biała kropka znajduje się w odległości mniejszej niż R od najbliższego koła.
Vlad
2

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

możliwe punkty środkowe

musisz sprawdzić całą zieloną linię, a nie tylko skrzyżowania, aby pokryć te przypadki krawędzi.

etui z pojedynczym kołem

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

Ewan
źródło
2
To, że musi przetoczyć krawędź niebieskiego koła na zewnątrz pozostałych kół, jest najłatwiejszym rozwiązaniem. Trudną częścią jest znalezienie równań / obliczeń, aby to zrobić.
Robert Harvey
1
naprawdę? jego po prostu (x-x1) ^ 2 + (r-y1) ^ 2 = (r + r1) ^ 2
Ewan
2
A potem musisz to wszystko powtórzyć, gdy spróbujesz przejść do następnego punktu. Wiem, że OP powiedział, że wydajność nie jest problemem, ale musi się ona zakończyć przed śmiercią wszechświata.
Robert Harvey
2
Jedynym sposobem, aby dowiedzieć się, czy dostaniesz dziesięć głosów pozytywnych, jest opublikowanie kodu C # i sprawdzenie, co się stanie.
Robert Harvey
2
myślę, że tak się stanie, że OP zakoduje to jako odpowiedź na zadanie domowe i nigdy więcej się od niego nie odezwie
Ewan
1

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

Nisko latający pelikan
źródło
Czy ktoś może wyjaśnić, co jest nie tak z tym podejściem?
Low Flying Pelican
Trudno to przeczytać. Używaj dobrych nazwisk i abstrakcji. Czy zabiłoby cię dodanie diagramu?
candied_orange
O ile widzę, to podejście próbuje znaleźć tylko prawidłowe miejsca dla niebieskiego koła, ale nie najbliższą możliwą lokalizację. Można to naprawić, jednak podejście zakłada również (najprawdopodobniej nieprawidłowe) założenie, że istnieje tylko skończona liczba współrzędnych wartości całkowitych.
Doc Brown
Zaczyna się od współrzędnej białej kropki i okrąża ją, rozszerzając siatkę wyszukiwania. Z tego powodu nie napotka żadnej sytuacji, w której będzie miał nieskończoną liczbę współrzędnych. W końcu znajdzie pasującą współrzędną.
Low Flying Pelican
1
... aby uzyskać poprawne rozwiązanie we współrzędnych całkowitych, musisz użyć zwiększającego się promienia i spraw, aby twoja przestrzeń wyszukiwania była okręgiem tego promienia wokół białego punktu. I chociaż OP napisał, że wydajność nie jest jego zmartwieniem, niemniej jednak dobrym pomysłem byłoby nie testować każdej już przetestowanej pary współrzędnych w każdej pętli.
Doc Brown
0
  • 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ń

Harald Scheirich
źródło
0

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

Vlad
źródło