Algorytm sprawdzający, czy Okrąg jest całkowicie zawarty w obszarze innych okręgów.

Question

Jaki byłby algorytm, który sprawdzi, czy krąg taki jak niebieski poniżej jest CAŁKOWICIE zawarty w obszarze innych kręgów (kółka while). Chcę PRAWDA dla niebieskiego koła i FALSE dla czerwonego koła. Dane wejściowe dla wszystkich okręgów są ich współrzędnymi i ich promieniem.

Answer 1

To wydaje się proste (EDIT: ale nie jest): jeśli każdy punkt każdego łuku danym okręgu jest zawarta w co najmniej jednym z innych środowisk, a następnie cały krąg jest zawarta. Następnie musisz znaleźć wszystkie skrzyżowania (algorithm to detect if a Circles intersect with any other circle in the same plane) i sprawdzić wszystkie łuki określone przez te skrzyżowania. Jeżeli jakikolwiek "wewnętrzny" punkt łuku A1-A2 okręgu A dla danych dwóch przecięć z okręgiem B (łuk B1-B2, gdzie punkty A1 = B1 i A2 = B2) jest zawarty w kole B, to cały łuk jest zawarte w kółku B i na odwrót. Proszę, popraw mnie jeśli się mylę.

EDYCJA: Ok Już wiem, że się myliłem, tak jak pokazałem maksym 1000. To jest bardziej skomplikowane, niż myślałem. Myślę o dodaniu czegoś do mojej odpowiedzi, ale nie jestem pewien, czy to jest rozwiązanie. Mam nadzieję, że to pomoże. Mianowicie: Myślę o wyznaczeniu całkowitego obszaru przecięć między naszym okręgiem a wszystkimi innymi. Znajdujemy wszystkie oddzielone przecięcia w naszym kręgu - wszystkie części, które zawierają te same punkty, które są rozdzielone wszystkimi przecinającymi się łukami - i znajdź ich obszary. Wu je podsumowuje. Jeśli jest równy obszarowi naszego koła, to nasz krąg jest zawarty w innych kręgach. Określenie tego obszaru może stanowić problem sam w sobie, ale, jak powiedziałem, może prowadzić we właściwym kierunku. Niech pomyślę zbyt ..

EDIT: Po chwili myślenia. Określanie wszystkich obszarów w (wielu) przecinających się okręgach jest tylko kwestią dodawania lub odejmowania trójkątów lub ... hmmm ... jak je nazwać? ... żółte elementy, takie jak tutaj na obrazek :)

Answer 2

nie sądzę istnieje proste rozwiązanie.

Chciałbym rozwiązać ten problem, biorąc po kolei każde koło i wykonując odejmowanie boolowskie wszystkich innych okręgów. (Krążki, które są wystarczająco daleko - R0 + R1 < D12 - nie będą się wtrącać).

Po zjedzeniu kawałków, okrąg staje się krzywoliniowym wielokątem utworzonym z okrągłych łuków lub zestawem takich wielokątów, ponieważ koneksja może być zepsuty. Wielokąt może być reprezentowany przez listę okręgów, które tworzą łuk jego obrysu, a punkty końcowe łuków są definiowane przez wspólny punkt przecięcia dwóch kolejnych sąsiadów lub okręgu docelowego i sąsiada. Zauważ, że ten sam sąsiad może pojawić się kilka razy.

Aby rzeczy były trochę bardziej krwawe, wielokąty mogą mieć dziury, które również musisz reprezentować.

Następnie istotną operacją jest odjęcie koła od krzywoliniowego wielokąta. Musisz wykryć łuki, które są całkowicie wewnątrz nowego kręgu i te, które przekraczają go. Po zdobyciu pozostałych części łuku, musisz zmienić rozmieszczenie pozostałych łuków i nowych łuków.

Domyślam się, że wszystkie te operacje można zbudować z pojedynczego elementu podstawowego, który znajduje część łuku (zdefiniowaną przez trzy okręgi) znajdującą się na dysku.

Answer 3

Oto surowy rozwiązanie:

• Take wszystkie koła i odnaleźć wszystkie punkty przecięcia które albo na lub wewnątrz koło T. Test Splitu odpowiednie krawędzie i budować wykres krawędziowy:

Dla każdej krawędzi należy śledzić okrąg, który ją utworzył.

• znaleźć wszystkie nie pokrywających regionów wewnątrz okręgu, przy użyciu minimalnej cyklu algorytm (Find all non-overlapping polygons in a list of edges/vertices).

• Dla każdej ograniczającej krawędzi E każdego obszaru R znajdują, się z koła C, że e-a. Jeśli C jest nie T (czerwony) - czyli E jest niebieski, sprawdź czy punkty na pozostałych krawędziach R są wewnątrz C:

  • jeśli są one następnie C obejmuje R. kontynuować na następnej regionu .
  • Jeśli nie są one, wówczas R nie jest pokryty przez C. pętli w stosunku do innych krawędzi ograniczających niebieskie R.
  • jeśli na koniec R jest jeszcze nie pokryte, to T nie jest całkowicie pokryte - zwraca fałsz .

w powyższym schemacie C zawiera B, to R jest pokryte; ale C nie zawiera, więc nie obejmuje S

• Jeśli nie powrócił jeszcze na tym etapie, a następnie powrót prawda.

---

przypadki uboczne:

• Jeśli pewien krąg zawiera T, a następnie go zignorować.
• Jeśli T zawiera , to, następnie odroczyć test przecięcia, przechowując go na liście. Na koniec powtórz test i podziel jego krawędzie.

Algorytm ten jest wysoce nieefektywne, a ja nie jestem w 100% pewien, czy są jakieś bardziej zdegenerowane przypadki; jeśli ktokolwiek ma jakieś sugestie, daj mi znać.