Wyznaczanie punktów przecięcia dwóch okręgów

Stronę tą wyświetlono już: 11083 razy

Dane są dwa okręgi o promieniach r i R, których środki znajdują się w punktach VC1 oraz VC2. Punkty przecięcia tych okręgów można obliczyć korzystając z konstrukcji geometrycznej opisanej na rysunku 1 pod warunkiem, że nie są spełnione następujące warunki:

Równanie [1] [1]

Zapis wyrażenia w formacie TeX-a:

\left|\vec{V}_{C1}-\vec{V}_{C2}\right|&lr;\left|R-r\right|

Równanie [2] [2]

Zapis wyrażenia w formacie TeX-a:

\left|\vec{V}_{C1}-\vec{V}_{C2}\right|>R+r

Gdy warunek [1] jest spełniony okrąg o mniejszym promieni znajduje się w środku okręgu o większym promieniu i okręgi nie mają wspólnych punktów przecięcia, natomiast w przypadku gdy spełniony jest warunek [2], okręgi znajdują się na tyle daleko od siebie, że nie ma możliwości aby miały one punkty przecięcia. Istnieje przypadek, w którym dwa okręgi mają nieskończoną ilość punktów wspólnych, ten przypadek występuje wówczas, gdy spełnione są następujące równości: VC1.x = VC2.x oraz VC1.y = VC2.y oraz R = r.

Interpretacja graficzna konstrukcji do wyznaczania punktów przecięcia dwóch okręgów.
Rys. 1
Interpretacja graficzna konstrukcji do wyznaczania punktów przecięcia dwóch okręgów.

Obliczenia należy zacząć od wyznaczenia kosinusa kąta A zaznaczonego na rysunku 1 wykorzystując do tego niecnego celu twierdzenie kosinusów znane już z szkoły średniej. Wzór twierdzenia tego dla rozpatrywanego przypadku przyjmuje następującą postać:

Równanie [3] [3]

Zapis wyrażenia w formacie TeX-a:

r^2=\left|\vec{V}_{C1}-\vec{V}_{C2}\right|^2+R^2-2\cdot\left| \vec{V}_{C1}-\vec{V}_{C2}\right|\cdot R\cdot cos(A)

Oczywiście wzór [3] wymaga odpowiedniego przekształcenia:

Równanie [4] [4]

Zapis wyrażenia w formacie TeX-a:

cos(A)=\frac{\left|\vec{V}_{C1}-\vec{V}_{C2}\right|^2+r^2-R^2}{2\cdot\left|\vec{V}_{C1}-\vec{V}_{C2}\right|\cdot r}

Potrzebna będzie jeszcze wartość sinusa kąta A więc zastosować należy jedynkę trygonometryczną do jego wyznaczenia w następujący sposób:

Równanie [5] [5]

Zapis wyrażenia w formacie TeX-a:

sin(A)=\sqrt{1-cos^2(A)}

Teraz można przystąpić do wyznaczenia wektora pomocniczego Vp, poprzez przypisanie mu wektora VC1-VC2 przeskalowanego do długości promienia r w następujący sposób:

Równanie [6] [6]

Zapis wyrażenia w formacie TeX-a:

\vec{V}_p=\frac{\vec{V}_{C2}-\vec{V}_{C1}}{\left|\vec{V}_{C1}-\vec{V}_{C2}\right|}\cdot r

Punkty przecięcia V1, V2 okręgów zostaną wyznaczone poprzez obrócenie wektora Vp o kąt A w jedną i drugą stronę z wykorzystaniem wzoru na obrót wektora o dowolny kąt a następnie dodanie wektora VC1. Tak więc poszczególne współrzędne punktów przecięcia zostaną obliczone w następujący sposób:

Równanie [7] [7]

Zapis wyrażenia w formacie TeX-a:

V_1.x=V_p.x\cdot cos(A)-V_p.y\cdot sin(A)+V_{C1}.x

Równanie [8] [8]

Zapis wyrażenia w formacie TeX-a:

V_1.y=V_p.x\cdot sin(A)+V_p.y\cdot cos(A)+V_{C1}.y

Równanie [9] [9]

Zapis wyrażenia w formacie TeX-a:

V_2.x=V_p.x\cdot cos(A)+V_p.y\cdot sin(A)+V_{C1}.x

Równanie [10] [10]

Zapis wyrażenia w formacie TeX-a:

V_2.y= V_p.y\cdot cos(A)-V_p.x\cdot sin(A)+V_{C1}.y

Propozycje książek
tytuł: Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie autor: Ryan T. White, Archana Tikayat Ray

Tytuł:

Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie

Autor:

Ryan T. White, Archana Tikayat Ray

tytuł: Algorytmy kryptograficzne w Pythonie. Wprowadzenie autor: Shannon W. Bray

Tytuł:

Algorytmy kryptograficzne w Pythonie. Wprowadzenie

Autor:

Shannon W. Bray

tytuł: Algorytmy sztucznej inteligencji. Ilustrowany przewodnik autor: Rishal Hurbans

Tytuł:

Algorytmy sztucznej inteligencji. Ilustrowany przewodnik

Autor:

Rishal Hurbans

tytuł: Algorytmy bez tajemnic autor: Thomas H. Cormen

Tytuł:

Algorytmy bez tajemnic

Autor:

Thomas H. Cormen

tytuł: Algorytmy dla bystrzaków autor: John Paul Mueller, Luca Massaron

Tytuł:

Algorytmy dla bystrzaków

Autor:

John Paul Mueller, Luca Massaron

tytuł: Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II autor: David Natingga

Tytuł:

Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II

Autor:

David Natingga

tytuł: Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji autor: Giuseppe Bonaccorso

Tytuł:

Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji

Autor:

Giuseppe Bonaccorso

tytuł: Struktury danych i algorytmy w języku Java. Przewodnik dla początkujących autor: James Cutajar

Tytuł:

Struktury danych i algorytmy w języku Java. Przewodnik dla początkujących

Autor:

James Cutajar

tytuł: C++. Struktury danych i algorytmy autor: Wisnu Anggoro

Tytuł:

C++. Struktury danych i algorytmy

Autor:

Wisnu Anggoro

tytuł: Struktury danych i algorytmy w języku C#. Projektowanie efektywnych aplikacji autor: Marcin Jamro

Tytuł:

Struktury danych i algorytmy w języku C#. Projektowanie efektywnych aplikacji

Autor:

Marcin Jamro

Komentarze

Administrator

Data: 23-01-2018 06:25:36

Powinno być tak: 
            double r = 3;
            double R = 7;
            double x1 = 1;
            double y1 = 1;
            double x2 = 8;
            double y2 = 1;

            double dl = Math.Sqrt(Math.Pow(x2 - x1, 2) + Math.Pow(y2 - y1, 2));
            Console.WriteLine(dl);
            double cosA = (dl * dl + r * r - R * R) / (2 * dl * r);
            double sinA = Math.Sqrt(1 - Math.Pow(cosA, 2));
            double vpx = (x2 - x1) * r / dl; // tutaj odwrotnie trzeba odejmować (nie x1 -x2 a x2 - x1)
            double vpy = (y2 - y1) * r / dl;
            //
            double V1x = vpx * cosA - vpy * sinA + x1;
            double V1y = vpx * sinA + vpy * cosA + y1;
            Console.WriteLine("V1x {0}:", V1x);
            Console.WriteLine("V1y {0}:", V1y);
            Console.WriteLine("sprawdzam:");
            Console.WriteLine("r {0}:", Math.Sqrt(Math.Pow(V1x - x1, 2) + Math.Pow(V1y - y1, 2))); // tutaj zamiast użyć V1x i V1y używałeś vpx i vpy
            Console.WriteLine("R {0}:", Math.Sqrt(Math.Pow(x2 - V1x, 2) + Math.Pow(y2 - V1y, 2))); // i tu to samo co powyżej

            Console.ReadKey();

Programista

Data: 22-01-2018 22:50:30

Witam, prosze pomoc cos podaje nie tak, dla x=0 y=0 jest ok ale dla innych danych nie zgadza sie weryfikacja. Dziekuje i pozdrawiam 
  double r =  3;
            double R =  7;
            double x1 = 1;
            double y1 = 1;
            double x2 = 8;
            double y2 = 1;

            double dl = Math.Sqrt(Math.Pow(x2 - x1, 2) + Math.Pow(y2 - y1, 2));
            Console.WriteLine(dl);
            double cosA = (dl*dl+r*r-R*R) / (2*dl*r);
            double sinA = Math.Sqrt(1 - Math.Pow(cosA,2));
            double vpx = (x1 - x2)*r/dl;
            double vpy = (y1 - y2)*r/dl;
            //
            double V1x = vpx * cosA - vpy * sinA + x1;
            double V1y = vpx * sinA + vpy * cosA + y1;
            Console.WriteLine("V1x {0}:", V1x);
            Console.WriteLine("V1y {0}:", V1y);
            Console.WriteLine("sprawdzam:");
            Console.WriteLine("r {0}:", Math.Sqrt(Math.Pow(vpx-x1,2) + Math.Pow(vpy-y1,2)));
            Console.WriteLine("R {0}:", Math.Sqrt(Math.Pow(x2-vpx,2) + Math.Pow(y2-vpy,2)));

            Console.ReadKey();

Administrator

Data: 15-05-2016 15:47:05

@rado4ever Rzeczywiście, pomyliłem się pisząc wzory, prawdopodobnie nie spojrzałem na rysunek, gdy je pisałem. Już poprawione.

rado4ever

Data: 15-05-2016 12:54:44

Od początku w tym artykule jest błąd. W twierdzeniu kosinusów jest inny kąt niż na rysunku. Zastosowałem ten algorytm w swoim programie i przecinało mi poprawnie tylko okręgi o jednakowej średnicy, ponieważ konsekwencją pomylenia kąta jest niejako zamiana Rr. Gdy promienie są jednakowe to nie ma to znaczenia.
Zastosowałem też pewną modyfikację ( uproszczenie ). Zamiast liczyć sin(A) i Vp od razu konstruuję wektory ( jako liczbę zespoloną biblioteka ) o kacie arg(Vc2-Vc1) +- acos(cos(A)) o długości r i dodaję je do Vc1 ( konstrukcja funkcją polar(r,alfa) z )