Przecinanie się dwóch lini?

Obiekty i przekształcenia geometryczne, opisane za pomocą układu (nie zawsze prostokątnego) współrzędnych.
TobiPL
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 30 cze 2019, o 07:38
Płeć: Mężczyzna
Lokalizacja: Warszawa

Przecinanie się dwóch lini?

Post autor: TobiPL »

Dzień dobry :x...

To mój pierwszy post tutaj przepraszam jeśli w złym miejscu, szukałem miejsca gdzie mógłbym napisać ale nie za bardzo ogarniam te tematy co są tu napisane xD sorry :x...


No ok... to ja mam takiego problema że potrzebuję określić na podstawie matekatyki czy dwie linie się przecinają czy nie...

Wiadomo jak się narysuje i popatrzy to od razu widać czy się przecinają xD
Mam dwie linie i kordy gdzie one są tzn. \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) ich dwóch końców

np.
Linia \(\displaystyle{ A}\) z końcami na np. \(\displaystyle{ X = 13}\) i \(\displaystyle{ Y = 6}\).
Linia \(\displaystyle{ B}\) z końcami na np. \(\displaystyle{ X = 37}\) i \(\displaystyle{ Y = 111}\).

i na podstawie tych cyferek miałbym stwierdzić czy linie się przetną czy nie :x...


Ktoś jakieś pomysły? :c...
Ostatnio zmieniony 1 lip 2019, o 01:48 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Przecinanie się dwóch lini?

Post autor: Bran »

Przepraszam, ale niewiele da się zrozumieć z tego co napisałeś.

Przede wszystkim, gdy mówisz linia masz na myśli prostą (nieograniczona) czy odcinek (ma "dwa końce")?

Domyślam się, że chodzi Ci o odcinek, jednak \(\displaystyle{ X = 13 \text{ i } Y = 6}\), to nie są dwa końce. Końcem odcinka jest punkt, a punkt zadany jest dwoma współrzędnymi, chyba, że rozpatrujemy w jednym wymiarze, na jednej osi, ale domyślam się, że chodzi Ci jednak o płaszczyznę.

Powiedz innymi słowami na czym polega problem. Może powiedz skąd masz do zadanie, albo do czego Ci potrzebne takie rozwiązanie (praca, jakiś własny pomysł...), możliwe że wtedy łatwiej będzie nam się połapać czego dokładnie potrzebujesz. Bo narazie nawet się nie domyślam jaki masz problem i szczerze wątpię, aby ktoś mógł Ci pomóc przy takim opisie.
Możesz też zamieścić rysunek. Spróbuj nam ułatwić pomoc.
TobiPL
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 30 cze 2019, o 07:38
Płeć: Mężczyzna
Lokalizacja: Warszawa

Przecinanie się dwóch lini?

Post autor: TobiPL »

Ok, nie jestem za bardzo zaznajomiony z Matematyką więc ciężko mi opisać matematycznie czego potrzebuję, nie rozumiem za bardzo różnicy między prostą czy odcinkiem.

W pierwszym moim poście widzę że źle napisałem przykład - przepraszam.


Postaram się pokazać na obrazku:


Mając tylko te "Wierzchołki" z tych lini jak odpowiedzieć używając matematyki czy przecinają się te linie czy nie?

Bo jak się po prostu popatrzy na obrazek to wiadomo że się przecinają ale muszę matematycznie to wykazać xD


Jeszcze raz przepraszam za błędny przykład w pierwszym poście

//Edit:
Tam na obrazku oczywiście mamy dwie osie X oraz Y
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Przecinanie się dwóch lini?

Post autor: Bran »

Oki.

No to mamy dwie pary wierzchołków, dajmy na to: \(\displaystyle{ A_1 = (x_A,y_A), A_2 = (x_{A_2},y_{A_2})}\) i \(\displaystyle{ B_1 = (x_B, y_B), B_2 = (x_{B_2}, y_{B_2})}\).

\(\displaystyle{ A_1, A_2}\) to końce jednego odcinka.
\(\displaystyle{ B_1, B_2}\) to końce drugiego odcinka.

No to chyba najbardziej pospolite rozwiązanie, to rozwiązanie trzech układów równań:

\(\displaystyle{ \begin{cases} y_A = ax_A+b \\ y_{A_2} = ax_{A_2}+b \end{cases}}\)

\(\displaystyle{ \begin{cases} y_B = cx_B+d \\ y_{B_2} = cx_{B_2}+d \end{cases}}\)

dzięki temu będziesz miał równania dwóch prostych:

\(\displaystyle{ y = ax + b}\)

\(\displaystyle{ y = cx + d}\)

I sprawdzasz, czy taki układ równań:

\(\displaystyle{ \begin{cases} y = ax + b \\ y = cx + d \end{cases}}\)

ma rozwiązania. Jeżeli tak, to się przecinają, jeżeli nie, to nie.


To rozwiązanie ma jeden mankament, odcinki nie mogą być równoległe do osi \(\displaystyle{ OY}\), jeżeli są, to rozwiązanie jest analogiczne, tylko równania wyglądają trochę inaczej, bo trzeba z kierunkowej przejść na ogólną.
Jan Kraszewski
Administrator
Administrator
Posty: 34128
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Przecinanie się dwóch lini?

Post autor: Jan Kraszewski »

Bran pisze:I sprawdzasz, czy taki układ równań:

\(\displaystyle{ \begin{cases} y = ax + b \\ y = cx + d \end{cases}}\)

ma rozwiązania. Jeżeli tak, to się przecinają, jeżeli nie, to nie.
No niezupełnie. To, że przecinają się wyznaczone proste nie oznacza jeszcze, że przecinają się odcinki.

JK
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: Przecinanie się dwóch lini?

Post autor: Bran »

Jan Kraszewski, bardzo słuszna uwaga! Dziękuję!

Oczywiście trzeba jeszcze sprawdzić, czy punkt przecięcia, dajmy na to \(\displaystyle{ P = (x_p, y_p)}\) leży na odcinkach.

Można by ograniczyć trochę naszą płaszczyznę. Dla uproszczenia zapisu przyjmijmy, że wśród \(\displaystyle{ x_A,y_Ax_{A_2},y_{A_2}, x_B, y_B, B_2, x_{B_2}, y_{B_2}}\) najmniejsza współrzędna \(\displaystyle{ x}\)-owa to \(\displaystyle{ x}\), a największa to \(\displaystyle{ X}\) i analogicznie współrzędna \(\displaystyle{ y}\)-owa.

Niech \(\displaystyle{ A = \left[ x, X\right]}\) a \(\displaystyle{ B = \left[ y, Y\right]}\)
Jak \(\displaystyle{ P \in A \times B}\), to mamy odpowiedź.

A wykazać, że punkt należy lub nie - już jest prosto. Trzeba się pobawić trochę z nierównościami, ale to dosyć intuicyjne, chyba, ze jest jakiś ciekawszy sposób od mojego. Bo w tej chwili się trochę rozrósł.
kry145
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 21 cze 2019, o 19:34
Płeć: Mężczyzna
Lokalizacja: Wadowice

Re: Przecinanie się dwóch lini?

Post autor: kry145 »

Takie zadanie można też rozpatrzeć w następujący sposób.
Dane są odcinki \(\displaystyle{ AB}\) i \(\displaystyle{ CD}\) końcach:
\(\displaystyle{ A=\left( x_A,y_A\right) \\
B=\left( x_B,y_B\right) \\
C=\left( x_C,y_C\right) \\
D=\left( x_D,y_D\right)}\)


Przyjmę następujące oznaczenia przedziałów:
\(\displaystyle{ X_{AB}=\left[ \min \left( x_A,x_B\right) ,\max \left( x_A,x_B\right) \right] \\
Y_{AB}=\left[ \min \left( y_A,y_B\right) ,\max \left( y_A,y_B\right) \right] \\
X_{CD}=\left[ \min \left( x_C,x_D\right),\max \left( x_C,x_D\right) \right] \\
Y_{CD}=\left[ \min \left( y_C,y_D\right),\max \left( y_C,y_D\right) \right]}\)


Przed rozpatrywaniem przypadków należy sprawdzić warunek konieczny na to aby odcinki miały punkt wspólny:
\(\displaystyle{ X_{AB} \cap X_{CD} \neq \varnothing \wedge Y_{AB} \cap Y_{CD} \neq \varnothing}\)
Jeżeli warunek konieczny jest spełniony, to możemy przejść do rozpatrywania przypadków:
1. Odcinki są równoległe do osi \(\displaystyle{ OY}\), co oznacza że:
\(\displaystyle{ x_A=x_B \wedge x_C=x_D}\)
a) Odcinki się przecinają.

2. Tylko odcinek \(\displaystyle{ AB}\) jest równoległy do osi \(\displaystyle{ OY}\), co oznacza że:
\(\displaystyle{ x_A=x_B \wedge x_C \neq x_D}\)
Tu rozpoczniemy od zapisania równania prostej \(\displaystyle{ CD}\) w postaci kierunkowej, skorzystamy z gotowego wzoru na prostą przechodzącą przez dwa punkty:
\(\displaystyle{ CD: y=\frac{y_C-y_D}{x_C-x_D}x + \frac{x_Cy_D-x_Dy_C}{x_C-x_D}}\)
Punkt przecięcia prostych \(\displaystyle{ CD}\) i \(\displaystyle{ AB}\) oznaczamy jako \(\displaystyle{ P}\).
\(\displaystyle{ P=\left( x_P,y_P\right) =\left( x_A,\frac{y_C-y_D}{x_C-x_D} \cdot x_A + \frac{x_Cy_D-x_Dy_C}{x_C-x_D}\right)}\)
a) Jeżeli \(\displaystyle{ P \in \left[ X_{AB} \cap X_{CD}\right] \times \left[ Y_{AB} \cap Y_{CD}\right]}\) to odcinki się przecinają,
b) Jeżeli \(\displaystyle{ P \notin \left[ X_{AB} \cap X_{CD}\right] \times \left[ Y_{AB} \cap Y_{CD}\right]}\) to odcinki się nie przecinają.

3. Tylko odcinek \(\displaystyle{ CD}\) jest równoległy do osi \(\displaystyle{ OY}\), co oznacza że:
\(\displaystyle{ x_A\neq x_B \wedge x_C = x_D}\)
Rozpatrujemy tak jak w przypadku 2.

4.żaden odcinek nie jest równoległy do osi \(\displaystyle{ OY}\), co oznacza że:
\(\displaystyle{ x_A\neq x_B \wedge x_C \neq x_D}\)
Rozpoczniemy od zapisania równań prostych \(\displaystyle{ AB}\) i \(\displaystyle{ CD}\) :
\(\displaystyle{ AB: y=\frac{y_A-y_B}{x_A-x_B}x + \frac{x_Ay_B-x_By_A}{x_A-x_B}}\)
\(\displaystyle{ CD: y=\frac{y_C-y_D}{x_C-x_D}x + \frac{x_Cy_D-x_Dy_C}{x_C-x_D}}\)
Jeżeli \(\displaystyle{ \frac{y_A-y_B}{x_A-x_B} \neq \frac{y_C-y_D}{x_C-x_D}}\), to z poniższego układu równań obliczamy punkt przecięcia prostych \(\displaystyle{ AB}\) i \(\displaystyle{ CD}\), który oznaczamy jako \(\displaystyle{ P=(x_P,y_P)}\)
\(\displaystyle{ \begin{cases}
y_P=\frac{y_A-y_B}{x_A-x_B}x_P + \frac{x_Ay_B-x_By_A}{x_A-x_B}\\
y_P=\frac{y_C-y_D}{x_C-x_D}x_P + \frac{x_Cy_D-x_Dy_C}{x_C-x_D}
\end{cases}}\)
a) Jeżeli \(\displaystyle{ \frac{y_A-y_B}{x_A-x_B}=\frac{y_C-y_D}{x_C-x_D} \wedge \frac{x_Ay_B-x_By_A}{x_A-x_B} \neq \frac{x_Cy_D-x_Dy_C}{x_C-x_D}}\) to odcinki się nie przecinają,
b) Jeżeli \(\displaystyle{ \frac{y_A-y_B}{x_A-x_B}=\frac{y_C-y_D}{x_C-x_D} \wedge \frac{x_Ay_B-x_By_A}{x_A-x_B} = \frac{x_Cy_D-x_Dy_C}{x_C-x_D}}\) to odcinki się przecinają,
c) Jeżeli \(\displaystyle{ \frac{y_A-y_B}{x_A-x_B} \neq \frac{y_C-y_D}{x_C-x_D} \wedge P \in \left[ X_{AB} \cap X_{CD}\right] \times \left[ Y_{AB} \cap Y_{CD}\right]}\) to odcinki się przecinają,
d) Jeżeli \(\displaystyle{ \frac{y_A-y_B}{x_A-x_B} \neq \frac{y_C-y_D}{x_C-x_D} \wedge P \notin \left[ X_{AB} \cap X_{CD}\right] \times \left[ Y_{AB} \cap Y_{CD}\right]}\) to odcinki się nie przecinają.
Ostatnio zmieniony 3 lip 2019, o 18:35 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
ODPOWIEDZ