Koło wielokątów przecięcia

Question

obliczeniowej Geometria problemów:
Punkt P0 dobiera się losowo na krawędzi (np EB) wielokąta (np BCDE), w celu znalezienia możliwych punktów (tj P1,P2,P3,...) w innych krawędzie oparte na podanej odległości (tj. r). Poniższa demonstracja pokazuje rozwiązanie poprzez znalezienie przecięć między okręgiem wyśrodkowanym na punkcie P0 a krawędziami wielokąta. Tak więc problem można w zasadzie rozwiązać przez analizę skrzyżowań Circle--Line-Segment.

Zastanawiam się, czy istnieje bardziej skuteczna metoda dla tego bardzo prostego problemu pod względem kosztów obliczeniowych? Proces zostanie poddany ocenie kilku million times, więc każda poprawka jest interesująca.

• końcowe rozwiązanie skorzysta z Python mocy;
• obliczenie rdzenia będzie w Fortran w razie potrzeby.

Aktualizacje:
Dzięki za komentarze. Proszę wziąć pod uwagę moje komentarze do komentarzy, które pomogą wyjaśnić pytanie więcej. Nie chce ich tutaj powtarzać, zachęcając do rozważenia wszystkich komentarzy i odpowiedzi;).

Właśnie zaimplementowałem metodę Circle--Line-Segment Intersection na podstawie algorytmu znalezionego [here]. Właściwie to dostosowałem go do pracy z liniowymi segmentami. Wzorcem algorytmu realizowanego w Pythonie jest następująca:


liczba odcinków jest: 100,000 a system jest zwykle na pulpicie. Upłynął czas: 15 seconds. Mam nadzieję, że są one pomocne w wyjaśnieniu kosztów obliczeniowych. Wdrożenie rdzenia w Fortan może znacznie poprawić wydajność.
Tłumaczenie jest jednak ostatnim krokiem.

Answer 1

Na przecięciu line (lub line-segment) i circle (sphere w 3D) jest trochę bardziej wyjaśnienie, szczegóły realizacji oraz Python C itp próbek kodów w [this link]. Możesz spróbować ich dla swojego problemu.
Pomysł jest w zasadzie taki sam jak wcześniej w wersji [here].

Answer 2

Zakładając, że circle--line-intersection jest zoptymalizowany, może być w stanie uzyskać coś od rozróżniania różnych przypadkach:

do punktu A, B:

• Jeśli d (P0, A) < ri d (P0, B) < R: punkt przecięcia nie

• Jeśli d (P0, ą) == r: skrzyżowanie A

• gdy d (P 0, B) == r: skrzyżowanie B
• Jeśli D (P0, ą) < R i D (P0, B)> R 1 przecięcia wykonania circle--line-intersection

• Jeśli D (P0 A)> R i d (P0, B) < R 1 przecięcia wykonania circle--line-intersection

• Jeśli d (P0 a)> r d (P0, B)> R: W oznacza 0, 1 lub 2 przecięcia -> Jeśli minimum distance do linii (A, B)> r: Brak przecięć -> Jeśli minimum distance do linii (A, B) == r: 1 przecięcie -> Jeśli minimum distance do linii (A, B) < r: 2 przecięcie d