Jak ustalić, czy dwie linie przecinają się, a jeśli tak, to w jakim punkcie x, y?
geometry
line-intersection
KingNestor
źródło
źródło
Odpowiedzi:
Jest ładne podejście do tego problemu, w którym wykorzystuje się krzyżowe produkty wektorowe. Zdefiniuj dwuwymiarowy wektorowy krzyżowy iloczyn v × w na v x w y - v y w x .
Załóżmy, że dwa segmenty linii biegną od p do p + r i od q do q + s . Następnie każdy punkt na pierwszej linii się przedstawić jako p + t r (dla skalarnych parametru t ) oraz dowolny punkt na drugiej linii, q + u s (o skalara parametru U ).
Obie linie przecinają się, czy możemy znaleźć T i U takie, że:
Przejdź po obu stronach z s , coraz
A ponieważ s × s = 0, oznacza to
A zatem rozwiązanie dla t :
W ten sam sposób możemy rozwiązać dla ciebie :
Aby zmniejszyć liczbę kroków obliczeniowych, wygodnie jest przepisać to w następujący sposób (pamiętając, że s × r = - r × s ):
Teraz są cztery przypadki:
Jeśli r × s = 0 i ( q - p ) × r = 0, wówczas dwie linie są współliniowe.
W takim przypadku wyraż punkty końcowe drugiego segmentu ( q i q + s ) w kategoriach równania pierwszego segmentu linii ( p + t r ):
Jeżeli odstęp między t 0 i t 1 krzyżuje się z przedziału [0, 1], po czym odcinki są współliniowe i nakładania; w przeciwnym razie są kolinearne i rozłączne.
Należy zauważyć, że jeśli s i R punkt w przeciwnych kierunkach, a y · R <0, a więc w odstępie być sprawdzony [ T 1 , T 0 ] zamiast [ t 0 , T 1 ].
Jeśli r × s = 0 i ( q - p ) × r ≠ 0, wówczas dwie linie są równoległe i nie przecinają się.
Jeśli R x y ≠ 0 i 0 ≤ t ≤ 1 i 0 ≤ U ≤ 1, dwa odcinki spotkać w punkcie p + t r = q + u s .
W przeciwnym razie dwa segmenty linii nie są równoległe, ale się nie przecinają.
Źródło: ta metoda to dwuwymiarowa specjalizacja algorytmu przecięcia linii 3D z artykułu Ronalda Goldmana „Przecięcie dwóch linii w trójprzestrzeni”, opublikowanego w Graphics Gems , strona 304. W trzech wymiarach zwykle występuje to, że linie są pochylone (ani równoległe, ani przecinające się), w którym to przypadku metoda podaje punkty najbliższego zbliżenia dwóch linii.
źródło
/ (r × s)
, ale czy(r × s)
jest to wektor, prawda? Wektor(0, 0, rx * sy - ry * sx)
. A lewa strona jest podobnie wektorem równoległym do osi Z. Więc ... czy po prostu dzielę składnik Z przez inny składnik Z? Czy rzeczywiście wzór na t|(q − p) × s| / |(r × s)|
?FWIW, następująca funkcja (w C) zarówno wykrywa przecięcia linii, jak i określa punkt przecięcia. Opiera się on na algorytmie z „Trików guru programowania gier systemu Andre” Leona LeMotheta . Nie różni się od niektórych algorytmów w innych odpowiedziach (np. Garetha). Następnie LeMothe używa reguły Cramera (nie pytaj mnie), aby rozwiązać same równania.
Mogę zaświadczyć, że działa w moim słabym klonie asteroid i wydaje się, że poprawnie radzi sobie z przypadkowymi przypadkami opisanymi w innych odpowiedziach przez Elementala, Dana i Wodzu. Prawdopodobnie jest także szybszy niż kod opublikowany przez KingNestor, ponieważ to wszystko mnożenie i dzielenie, bez pierwiastków kwadratowych!
Wydaje mi się, że istnieje potencjał podziału przez zero, choć w moim przypadku nie było to problemem. Łatwo je zmodyfikować, aby i tak uniknąć awarii.
BTW, muszę powiedzieć, że w książce LeMothe'a, chociaż najwyraźniej poprawia algorytm, konkretny przykład, w którym pokazuje błędne liczby i błędne obliczenia. Na przykład:
Zdezorientowało mnie to godzinami . :(
źródło
s
it
bezpośrednio, przetestować związek między dwoma licznikami i mianownikiem. Tylko jeśli linie się przecinają, faktycznie musisz obliczyć wartośćt
(ale nies
).Problem sprowadza się do pytania: czy przecinają się dwie linie od A do B i od C do D? Następnie możesz go zadać cztery razy (między linią a każdym z czterech boków prostokąta).
Oto matematyka wektorowa do tego. Zakładam, że linia od A do B jest linią, o której mowa, a linia od C do D jest jedną z linii prostokątnych. Mam na
Ax
myśli, że jest to „współrzędna x A” iCy
„współrzędna y C.” A „*
” oznacza iloczyn skalarny, więc npA*B = Ax*Bx + Ay*By
.Ten
h
numer jest kluczem. Jeślih
jest pomiędzy0
i1
, linie przecinają się, w przeciwnym razie nie. JeśliF*P
wynosi zero, oczywiście nie można wykonać obliczeń, ale w tym przypadku linie są równoległe i dlatego przecinają się tylko w oczywistych przypadkach.Dokładny punkt przecięcia to
C + F*h
.Więcej zabawy:
Jeśli
h
jest dokładnie0
lub1
linie stykają się w punkcie końcowym. Możesz uznać to za „skrzyżowanie” lub nie, jak uważasz za stosowne.W szczególności
h
jest to, ile trzeba pomnożyć długość linii, aby dokładnie dotknąć drugiej linii.Dlatego „If”
h<0
oznacza, że linia prostokąta znajduje się „za” daną linią („kierunek” jest „od A do B”), ah>1
linia prostokąta znajduje się „przed” daną linią.Pochodzenie:
A i C to wektory, które wskazują początek linii; E i F to wektory z końców A i C, które tworzą linię.
Dla dwóch dowolnych nierównoległych linii w płaszczyźnie musi istnieć dokładnie jedna para skalarna
g
ih
takie równanie zawiera:Dlaczego? Ponieważ dwie nierównoległe linie muszą się przecinać, co oznacza, że można przeskalować obie linie o określoną wartość i dotknąć się nawzajem.
( Początkowo to wygląda pojedynczego równania z dwoma niewiadomymi! Ale to nie jest jeśli wziąć pod uwagę, że jest to równanie wektorowe 2D, co oznacza, że jest to naprawdę parę równań
x
ay
).Musimy wyeliminować jedną z tych zmiennych. Prostym sposobem jest uczynienie
E
terminu zerowym. Aby to zrobić, weź iloczyn iloczynu po obu stronach równania, używając wektora, który będzie kropkował zero do E. Ten wektor, który wezwałemP
powyżej, i wykonałem oczywistą transformację E.Teraz masz:
źródło
A + E*g = C + F*h
Dwie linie przecinają się wtedy i tylko wtedy, gdy rozwiązanie tego równania (przy założeniu, że nie są one równoległe) ma oba,g
ih
od 0 do 1 (in lub wykluczające, w zależności od tego, czy liczysz dotyk w punkcie końcowym).Próbowałem zaimplementować algorytm tak elegancko opisany przez Jasona powyżej; niestety podczas pracy z matematyką podczas debugowania znalazłem wiele przypadków, dla których to nie działa.
Rozważmy na przykład punkty A (10,10) B (20,20) C (10,1) D (1,10), które dają h = .5, a jednak z badania wynika, że segmenty te nie znajdują się blisko siebie inny.
Wykreślenie tego pokazuje, że kryteria 0 <h <1 wskazują tylko, że punkt przecięcia leżałby na CD, gdyby istniał, ale nie mówi nic o tym, czy ten punkt leży na AB. Aby upewnić się, że istnieje punkt przecięcia, należy wykonać obliczenia symetryczne dla zmiennej g, a warunkiem przechwytywania jest: 0 <g <1 AND 0 <h <1
źródło
Oto poprawka do odpowiedzi Gavina. Rozwiązanie marcp jest również podobne, ale żadne nie opóźnia podziału.
W rzeczywistości okazuje się to również praktycznym zastosowaniem odpowiedzi Garetha Reesa, ponieważ ekwiwalentem wielu produktów w 2D jest iloczyn perp-kropka, z czego ten kod wykorzystuje trzy. Przełączenie na 3D i użycie produktu krzyżowego, interpolacja zarówno s, jak i t na końcu, daje w wyniku dwa najbliższe punkty między liniami w 3D. W każdym razie rozwiązanie 2D:
Zasadniczo odkłada podział na ostatnią chwilę i przenosi większość testów, aż do wykonania pewnych obliczeń, dodając w ten sposób wczesne wyjścia. Wreszcie, unika się również dzielenia przez przypadek zerowy, który występuje, gdy linie są równoległe.
Możesz również rozważyć użycie testu epsilon zamiast porównania z zerem. Linie, które są bardzo zbliżone do równoległych, mogą dawać nieznacznie niejednoznaczne wyniki. To nie jest błąd, to ograniczenie matematyki zmiennoprzecinkowej.
źródło
s32_y
zamiast czegoś, co opisuje, jak to jestpoint2YDifference
?Pytanie C: Jak wykryć, czy przecinają się dwa segmenty linii?
Szukałem tego samego tematu i nie byłem zadowolony z odpowiedzi. Napisałem więc artykuł, który wyjaśnia bardzo szczegółowo, jak sprawdzić, czy dwa segmenty linii przecinają się z wieloma obrazami. Istnieje kompletny (i przetestowany) kod Java.
Oto artykuł, przycięty do najważniejszych części:
Algorytm, który sprawdza, czy odcinek linii a przecina się z odcinkiem linii b, wygląda następująco:
Co to są obwiednie? Oto dwie ramki ograniczające dwóch segmentów linii:
Jeśli obie ramki ograniczające mają przecięcie, przesuwasz segment linii a, tak aby jeden punkt znajdował się na (0 | 0). Teraz masz linię przechodzącą przez początek zdefiniowany przez. Teraz przesuń segment linii b w ten sam sposób i sprawdź, czy nowe punkty segmentu linii b znajdują się po różnych stronach linii a. W takim przypadku sprawdź to na odwrót. W takim przypadku odcinki linii przecinają się. Jeśli nie, nie przecinają się.
Pytanie A: Gdzie przecinają się dwa segmenty linii?
Wiesz, że dwa odcinki linii aib przecinają się. Jeśli nie wiesz, sprawdź to za pomocą narzędzi, które ci dałem w „Pytaniu C”.
Teraz możesz przejrzeć niektóre przypadki i uzyskać rozwiązanie z matematyki 7 klasy (patrz kod i interaktywny przykład ).
Pytanie B: Jak rozpoznać, czy przecinają się dwie linie?
Załóżmy, że punkt
A = (x1, y1)
, punktB = (x2, y2)
,C = (x_3, y_3)
,D = (x_4, y_4)
. Twój pierwszy wiersz jest zdefiniowany przez AB (z A! = B), a twój drugi przez CD (z C! = D).Pytanie D: Gdzie przecinają się dwie linie?
Sprawdź pytanie B, czy w ogóle się przecinają.
Linie aib są zdefiniowane przez dwa punkty dla każdej linii. Możesz w zasadzie zastosować tę samą logikę, której użyto w pytaniu A.
źródło
Odpowiedź raz zaakceptowana tutaj jest niepoprawna (od tego czasu nie została zaakceptowana, więc brawo!). Nie eliminuje poprawnie wszystkich nieprzecięć. Trywialnie może się wydawać, że działa, ale może się nie powieść, szczególnie w przypadku, gdy 0 i 1 są uważane za prawidłowe dla h.
Rozważ następujący przypadek:
Linie w (4,1) - (5,1) i (0,0) - (0,2)
Są to linie prostopadłe, które wyraźnie się nie nakładają.
A = (4,1)
B = (5,1)
C = (0,0)
D = (0,2)
E = (5,1) - (4,1) = (- 1,0)
F = (0,2) - (0,0) = (0, -2)
P = (0,1)
h = ((4,1) - (0,0)) kropka (0,1) / ((0 , -2) kropka (0,1)) = 0
Zgodnie z powyższą odpowiedzią te dwa segmenty linii spotykają się w punkcie końcowym (wartości 0 i 1). Ten punkt końcowy to:
(0,0) + (0, -2) * 0 = (0,0)
Zatem najwyraźniej dwa segmenty linii spotykają się w punkcie (0,0), który znajduje się na linii CD, ale nie na linii AB. Co się dzieje nie tak? Odpowiedź jest taka, że wartości 0 i 1 są niepoprawne i tylko czasami SZCZĘŚLIWY, aby poprawnie przewidzieć przecięcie punktu końcowego. Gdy przedłużenie jednej linii (ale nie drugiej) byłoby zgodne z segmentem linii, algorytm przewiduje przecięcie segmentów linii, ale nie jest to poprawne. Wyobrażam sobie, że poprzez testowanie zaczynając od AB kontra CD, a następnie także testując CD z AB, problem ten zostałby wyeliminowany. Tylko jeśli oba mieszczą się w przedziale od 0 do 1 włącznie, można powiedzieć, że się przecinają.
Polecam użycie wektorowej metody krzyżowej, jeśli musisz przewidzieć punkty końcowe.
-Dan
źródło
Wersja odpowiedzi iMalc w języku Python:
źródło
denom = float(...)
Znalezienie prawidłowego przecięcia dwóch segmentów linii jest niełatwym zadaniem z dużą liczbą przypadków krawędzi. Oto dobrze udokumentowane, działające i przetestowane rozwiązanie w Javie.
Zasadniczo istnieją trzy rzeczy, które mogą się zdarzyć po znalezieniu przecięcia dwóch segmentów linii:
Segmenty się nie przecinają
Istnieje unikalny punkt przecięcia
Skrzyżowanie to kolejny segment
UWAGA : W kodzie zakładam, że segment linii (x1, y1), (x2, y2) z x1 = x2 i y1 = y2 jest prawidłowym segmentem linii. Z matematycznego punktu widzenia segment linii składa się z odrębnych punktów, ale pozwalam, aby segmenty były punktami w tej implementacji dla kompletności.
Kod pochodzi z mojego repozytorium github
Oto prosty przykład użycia:
źródło
Chciałem tylko wspomnieć, że dobre wyjaśnienie i jednoznaczne rozwiązanie można znaleźć w serii Przepisy numeryczne. Mam wydanie trzecie, a odpowiedź znajduje się na stronie 1117, sekcja 21.4. Inne rozwiązanie z inną nomenklaturą można znaleźć w artykule Marina Gavrilova Reliable Line Intersection Testing . Moim zdaniem jej rozwiązanie jest nieco prostsze.
Moja implementacja jest poniżej:
źródło
Wiele rozwiązań jest dostępnych powyżej, ale myślę, że poniższe rozwiązanie jest dość proste i łatwe do zrozumienia.
Dwa segmenty Vector AB i Vector CD przecinają się wtedy i tylko wtedy, gdy
Mówiąc dokładniej, aib znajdują się po przeciwnej stronie segmentu CD wtedy i tylko wtedy, gdy dokładnie jedna z dwóch trójek a, c, d i b, c, d jest w kolejności przeciwnej do ruchu wskazówek zegara.
W tym przypadku CCW reprezentuje przeciwnie do ruchu wskazówek zegara, co zwraca wartość prawda / fałsz na podstawie orientacji punktów.
Źródło: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf Strona 2
źródło
CCW
zdefiniowany jest test? Ze znakiem produktu zewnętrznego?C i Cel-C
Na podstawie odpowiedzi Garetha Reesa
Wiele funkcji i struktur jest prywatnych, ale powinieneś dość łatwo wiedzieć, co się dzieje. To jest publiczne w tym repozytorium https://github.com/hfossli/AGGeometryKit/
źródło
To działa dobrze dla mnie. Zabrano stąd .
źródło
Próbowałem niektórych z tych odpowiedzi, ale one nie działały dla mnie (przepraszam chłopaki); po kilku kolejnych poszukiwaniach w sieci znalazłem to .
Z niewielką modyfikacją jego kodu mam teraz funkcję, która zwróci punkt przecięcia lub jeśli nie zostanie znalezione żadne przecięcie, zwróci -1, -1.
źródło
Wydaje się, że istnieje pewne zainteresowanie odpowiedzią Gavina, dla której cortijon zaproponował wersję javascript w komentarzach, a iMalc dostarczył wersję z nieco mniejszą liczbą obliczeń . Niektórzy zwracali uwagę na wady różnych propozycji kodu, a inni komentowali efektywność niektórych propozycji kodu.
Algorytm dostarczony przez iMalc za pośrednictwem odpowiedzi Gavina jest tym, którego obecnie używam w projekcie javascript i chciałem tylko tutaj dostarczyć oczyszczoną wersję, jeśli może to komukolwiek pomóc.
źródło
t = dx2 * dy3 - dx3 * dy2;
...t/d
wchodzi.crossProduct = (line1XDifference * line2YDifference) - (line2XDifference * line1YDifference)
iscaledResult = crossProduct / dotProduct
?p1x, p1y
itp. Mają opisywać punkty za pomocą ich wartości x i y, więcp1x
jest to skrótpoint1x
, podobnie jakd1x
, moim zdaniem, skrót od greckiej litery,deltaX
lub można powiedziećdifferenceInX
. (więcej)Myślę, że istnieje znacznie prostsze rozwiązanie tego problemu. Wpadłem dziś na inny pomysł i wydaje się, że działa dobrze (przynajmniej na razie w 2D). Wszystko, co musisz zrobić, to obliczyć przecięcie między dwiema liniami, a następnie sprawdzić, czy obliczony punkt przecięcia znajduje się w polach ograniczających obu segmentów linii. Jeśli tak, odcinki linii przecinają się. Otóż to.
EDYTOWAĆ:
W ten sposób obliczam przecięcie (już nie wiem, gdzie znalazłem ten fragment kodu)
pochodzi z
i to jest moja (uproszczona dla celów odpowiedzi) klasa BoundingBox:
źródło
To rozwiązanie może pomóc
źródło
Przesłałem powyższą odpowiedź Krisa do JavaScript. Po wypróbowaniu wielu różnych odpowiedzi podał poprawne punkty. Myślałem, że wariuję, że nie dostaję potrzebnych punktów.
źródło
Próbowałem na wiele sposobów, a potem postanowiłem napisać własny. Oto on:
Na podstawie tych dwóch formuł: (uprościłem je z równania linii i innych formuł)
źródło
Opiera się to na odpowiedzi Garetha Ree. Zwraca również nakładanie się segmentów linii, jeśli tak się dzieje. Kodowany w C ++, V jest prostą klasą wektorową. Gdzie iloczyn krzyżowy dwóch wektorów w 2D zwraca pojedynczy skalar. Został przetestowany i zdany przez mój system automatycznych testów.
źródło
Oto podstawowa implementacja segmentu linii w języku C # z odpowiednim kodem wykrywania skrzyżowań. Wymaga wywołania struktury wektorowej / punktowej 2D
Vector2f
, choć można ją zastąpić dowolnym innym typem, który ma właściwości X / Y. Można również wymienićfloat
zedouble
jeśli który odpowiada Twoim potrzebom lepiej.Ten kod jest używany w mojej bibliotece fizyki .NET, Boing .
źródło
Program C ++ do sprawdzania, czy przecinają się dwa podane segmenty linii
źródło
Na podstawie odpowiedzi @Gareth Rees, wersja dla Python:
źródło
Jeśli każda strona prostokąta jest segmentem linii, a część narysowana przez użytkownika jest segmentem linii, musisz po prostu sprawdzić segment narysowany przez użytkownika pod kątem przecięcia z czterema segmentami linii bocznej. Powinno to być dość proste ćwiczenie, biorąc pod uwagę punkty początkowe i końcowe każdego segmentu.
źródło
Na podstawie odpowiedzi t3chb0t:
źródło
Algorytm czytam z książki „geometria wielu widoków”
następujący tekst za pomocą
„jako znak transpozycji
* jako produkt kropkowy
x jako produkt krzyżowy, gdy jest używany jako operator
1. definicja linii
punkt x_vec = (x, y) 'leży na linii ax + o + c = 0
oznaczamy L = (a, b, c) ', punkt jako (x, y, 1)' jako współrzędne jednorodne
równanie liniowe można zapisać jako
(x, y, 1) (a, b, c) '= 0 lub x' * L = 0
2. przecięcie linii
mamy dwie linie L1 = (a1, b1, c1) ', L2 = (a2, b2, c2)'
załóżmy, że x jest punktem, wektorem, a x = L1 x L2 (iloczyn L1 L2).
bądź ostrożny, x jest zawsze punktem 2D, przeczytaj jednorodne współrzędne, jeśli się mylisz (L1xL2) to wektor trzech elementów, a x to współrzędne 2D.
według potrójnego produktu wiemy o tym
L1 * (L1 x L2) = 0, a L2 * (L1 x L2) = 0, ze względu na współpłaszczyznę L1, L2
podstawiamy (L1xL2) wektorem x, a następnie mamy L1 * x = 0, L2 * x = 0, co oznacza, że x leży zarówno na L1, jak i L2, x jest punktem przecięcia.
uważaj, tutaj x jest jednorodnymi współrzędnymi, jeśli ostatni element x wynosi zero, oznacza to, że L1 i L2 są równoległe.
źródło
Wiele odpowiedzi zawarło wszystkie obliczenia w jednej funkcji. Jeśli musisz obliczyć nachylenie linii, przecięcia y lub przecięcia x do użycia w innym miejscu w kodzie, będziesz wykonywać te obliczenia nadmiarowo. Wyodrębniłem odpowiednie funkcje, użyłem oczywistych nazw zmiennych i skomentowałem mój kod, aby ułatwić śledzenie. Musiałem wiedzieć, czy linie przecinają się nieskończenie poza ich punktami końcowymi, więc w JavaScript:
http://jsfiddle.net/skibulk/evmqq00u/
źródło