algorytm.org

Wyznaczanie punktu przecięcia dwóch prostych



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Wyznaczanie punktu przecięcia dwóch prostych
Ocena użytkowników:***** / 15
SłabyŚwietny 
Wpisany przez Krzysztof Zajączkowski, 02 lutego 2009 19:13

Niech istnieją dwie linie L1 oraz L2 opisane wektorami V1 i V2 dla linii L1 i V3 i V4 dla linii L2. Konieczne jest następujące założenie: linia L1 nie jest równoległa do linii L2. Istnieje możliwość obliczenia wektora V5 będącego przecięciem dwóch linii L1 oraz L2 poprzez wykorzystanie rzutowania prostopadłego wektorów, podobieństw trójkątów oraz skalowania wektorów. Więcej o rzutowaniu prostopadłym punktu na prostą znajdziesz w artykule "Rzutowanie punktu prostopadle na prostą".

W celu wyznaczenia wektora V5 znajdującego się na przecięciu linii L1 z linią L2 należy obliczyć wektor V6 jak na rysunku poniżej a następnie zrzutować ten wektor oraz wektor V4 prostopadle na linię L1.

Punkt przecięcia dwóch prostych


Otrzymane w ten sposób wektory wyznaczają dwa trójkąty prostokątne: pierwszy zbudowany jest na wektorach V1 V6 V7 a drugi na wektorach V5 V4 V8. Nie trudno zauważyć, że trójkąty te są trójkątami podobnymi dzięki czemu w prosty sposób określę odległość dzielącą wektor V4 od wektora V5. Ponieważ trójkąty podobne charakteryzuje pewna ważna dla nich cecha, otóż stosunek długości dwóch boków w jednym trójkącie jest równy stosunkowi odpowiednich dwóch boków trójkąta drugiego. Tak więc można ułożyć następujące równanie:
\frac{|V_6 - V_1|}{|V_6 - V_7|} = \frac{|V_4 - V_5|}{|V_8 - V_4|}
po odpowiednim przekształceniu otrzymuję wzór na szukaną odległość dzielącą wektor V4 od wektora V5:
|V_4 - V_5| = \frac{|V_6 - V_1| * |V_8 - V_4|}{|V_6 - V_7|}
Potrzebny jest jeszcze jeden wektor uwzględniający kierunek i zwrot wektora V5 - V4, w tym celu należy zrzutować wektor V8 na linię L2 otrzymując w ten sposób wektor V9. Znając długość | V4 - V5 można tak przeskalować wektor V9 - V4 aby otrzymać wektor V5 - V4. Oczywiście operacja skalowania wektora wygląda następująco:
V_5 - V_4 = \frac{V_9 - V_4 * |V_4 - V_5|}{|V_9 - V_4|}
Do uzyskanego wektora V5 - V4 należy jeszcze dodać wektor V4 aby otrzymać wektor V5.

W ten sposób programy typu CAD mogą wyznaczać punkty przecięcia się prostych oraz odcinków. Istnieje również możliwość wyznaczenia położenia punktu przecięcia za pomocą układu równań dwóch funkcji liniowych ale to już historia na oddzielny artykuł.
W załączonym programie wyświetlane są dwie linie, których końce można przemieszczać poprzez najechanie myszką w pobliże końca linii wciśnięcie lewego przycisku myszy oraz przemieszczenie myszki w celu zmiany położenia punktu.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Krzysztof ZajączkowskiC/C++MS Visual Studio .net
.cpp
.cpp
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 sierpnia 2012 21:00
Komentarze
photo
+1 # Archeerie 2009-12-10 02:01
Wydaje mi się, że ta metoda jest mocno przekombinowana (sic!)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Kryszał 2010-05-05 04:02
Odnośnie tego algorytmu to należy tutaj jeszcze uwzględnić bardzo ważną kwestię.
Aby dostać punkt przecięcia zawsze gdy takowy istnieje, to nie można dopuścić do tego, aby punkty V4 i V8 się pokryły. Sytuacja ta miałaby miejsce gdyby koniec drugiego odcinka (V4) był współliniowy z krańcami pierwszego odcinka (V1 i V2).
Dlatego przed właściwym wyliczeniem należy dodać pewien warunek w rodzaju:
Kod:<br />if (Geometry.CrossProduct(s1.Beginning, s1.End, s2.End) == 0)<br /> {<br /> double newX = s2.End.X + Math.Abs(s2.Beginning.X - s2.End.X) / 2;<br /> double newY = s2.End.Y + Math.Abs(s2.Beginning.Y - s2.End.Y) / 2;<br /> Point newEnd = new Point(newX, newY);<br /> s2 = new Segment(s2.Beginning, newEnd);<br /> }<br />
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz