Jak określić, czy można narysować okrąg wokół zestawu punktów, tak aby punkty z drugiego zestawu nie znajdowały się w nim?

Question

Zastanawiam się nad algorytmem, który zwraca prawdę lub fałsz, informując mnie, czy możliwe jest narysowanie okręgu wokół zbioru punktów A, tak aby żaden punkt z zestawu punktów B nie znajdował się w środku lub na odwrót. (możliwe narysować koło wokół zbioru punktów B tak, że żaden punkt z zestawu punktów A nie znajduje się w środku).

Zasadniczo, jako dane wprowadzane są 2 zestawy punktów, i trzeba określić, czy możliwe jest narysowanie okręgu wokół jednego, tak aby żaden punkt z drugiego nie znajdował się wewnątrz niego.

Spojrzałem na Megiddo's linear time algorithm dla smallest enclosing circle problem, ale problem polega na tym, że rysuje tylko najmniejsze kółko, co oznacza, że ​​nie działa w przypadku, gdy potrzebujesz dużego koła.

Oto pic co mam na myśli:

W tym obrazie jest możliwe, aby narysować bardzo duży krąg wokół zestawu czerwonych punktów, tak że każdy z zielone punkty nie są w środku, dlatego algorytm Megiddo nie zadziała.

Answer 1

W niniejszej pracy zmniejszają wykrywania, czy dwa zestawy punktów płaszczyzny mogą być oddzielone przez koło, liniowego rozłączności punktów 3D:

O'Rourke'a Józef, S Rao Kosaraju i Nimrod Megiddo. "Obliczanie separacji kołowej." Dyskretna & Geometria obliczeniowa, .1 (1986): 105-113. (PDF download.)

Answer 2

Jeśli chcesz przetestować wiele potencjalnych punktów środkowych (na przykład na siatce), to dla każdego punktu największa odległość do dowolnego punktu czerwonego musi być mniejsza niż najmniejsza odległość do dowolnego punktu zielonego, aby mieć okrąg, który zawiera tylko czerwone punkty i nie ma zielonego punktu.

Domyślam się, że zaczynając od rzadkiej siatki i monitorując "największą odległość do dowolnego punktu czerwonego", "najmniejszą odległość do dowolnego punktu zielonego", możesz sprawić, że niektóre obiecujące obszary staną się lepsze i delikatniejsze (sprytne cięcie), aby w końcu złapać punkt lub obszar o pożądanej właściwości.

Możliwe jest nawet użycie niektórych pochodnych, np. Przejście w kierunku, w którym stosunek "największej odległości do dowolnego punktu czerwonego" do "najmniejszej odległości do dowolnego punktu zielonego" zmniejsza się najszybciej. Z drugiej strony problem może nie być wypukły, a konwergencja może nie być zagwarantowana.

Answer 3

Spróbuj tego: użyj stereographic projection, aby wyświetlić swoje punkty na kuli. Następnie musisz znaleźć płaszczyznę przechodzącą przez kulę, która tnie kulę tak, że wszystkie punkty w pierwszym zestawie znajdują się po jednej stronie płaszczyzny, a wszystkie punkty w drugim zestawie znajdują się po drugiej stronie płaszczyzny. Przecięcie płaszczyzny i kuli jest kołem, które odwzorowuje z powrotem na okrąg (lub w rzadkich okolicznościach na linię) na pierwotnej płaszczyźnie. Powstały okrąg na oryginalnej płaszczyźnie ma pożądane właściwości.

Zmiana problemu z jednego na okręgi na płaszczyźnie na jeden dotyczący płaszczyzn w trzech wymiarach (obiekty liniowe) oznacza, że ​​można użyć pomysłów z programowania liniowego i wypukłych zestawów, aby pomóc. Jednym ze sposobów jest użycie hyperplane separation theorem, aby pokazać, że można znaleźć płaszczyznę, która oddziela obrazy rodzin punktów wtedy i tylko wtedy, gdy wypukłe kadłuby obrazów punktów w A i B nie przecinają się.

Istnieje wiele szybkich metod sprzętowych i programowych do określania, czy dwa ciała wypukłe się przecinają: jest to problem wykrywania kolizji, ważny np. W grach wideo. Wykonano wiele pracy nad tym problemem (patrz np. https://www.medien.ifi.lmu.de/lehre/ss10/ps/Ausarbeitung_Beispiel.pdf, który twierdzi, że algorytm działa w czasie O (n)) i na pewno jest swobodnie dostępny.

Podsumowując: mapowane punkty (x, y) na sferze jednostkowej (x, y, z) poprzez stereograficznego określone wzorem

(x,y,z) = (2*X/(R^2+1), 2*Y/(R^2+1), (R^2-1)/(R^2+1)), R^2 = X^2+Y^2 

Następnie za pomocą algorytmu Gilbert-Johnsona Keerthi lub inny algorytm wykrywania kolizji w celu ustalenia, czy wypukły kadłub obrazów punktów w jednym zestawie jest rozłączny z wypukłego kadłuba obrazów punktów w drugim zbiorze. Odpowiada to na pytanie, czy koło istnieje. Aby rzeczywiście znaleźć okrąg, potrzebujesz płaszczyzny podziału między dwoma wypukłymi ciałami, które następnie przecinają się ze sferą, aby uzyskać okrąg na kuli, który odwzorowujesz z powrotem do płaszczyzny przez odwrotność stereograficznej projekcji.

Jeśli dobrze rozumiem, powyższe można osiągnąć w O (n) czasie.

Answer 4

tylko pomysł: wziąć wszystkie pary czerwonych i zielonych kropek.

Dla każdej pary obliczyć ortogonalną linię środkową.

Te punkty na linii to punkty, w których odległość do zielonej i czerwonej kropki jest równa, więc kółko z tym środkiem nie ma sensu.

Ale obszar po tej samej stronie linii, gdzie czerwony punkt to także obszar, w którym leży potencjalny punkt środkowy.

Dla każdej pary {czerwony, zielony} otrzymasz linię i obszar, w którym znajduje się środkowy punkt koła.

Jeśli przecinasz wszystkie obszary wszystkich par, otrzymasz wszystkie potencjalne punkty środkowe dla wszystkich okręgów.

W twoim przykładzie weź dwie zielone i czerwoną kropkę między nimi. Otrzymasz dwie linie w 1/2 odległości lewej i prawej od osi pionowej.

Weź lewą zieloną kropkę i wszystkie czerwone, otrzymasz linie od lewej górnej do prawej dolnej, a środek okręgu będzie nad nimi.

Prawa zielona kropka z czerwonymi zrobi mniej więcej to samo. Tak więc w tym przypadku otrzymujesz obszar wyniku (wielokąta), który nie jest zbyt oddalony od osi pionowej i co najmniej pewną odległość powyżej osi poziomej i rozciąga się do nieskończoności.

Dla innego zbioru punktów przecięcia może doprowadzić do zbioru pustego, co oznacza, że ​​nie można wyciągnąć takiego kręgu wokół czerwonych bez podejmowania niektórych zielone w.

To zawsze obliczy prawidłowy wynik , ale nie mam pojęcia, jak dobry jest ten performance w porównaniu do algorytmu Josepha. Może on może rzucić okiem?