Jak obliczyć, czy 2 linie są skierowane w kierunku do lub z dala?


10

Biorąc pod uwagę 4 punkty opisujące 2 segmenty linii, jak obliczyć, czy linia A jest w kierunku do linii B czy od niej?

Dwie linie mają stałą długość i można je zmierzyć jako odległość od x1 / y1 do x2 / y2.

wprowadź opis zdjęcia tutaj


Czym różni się obudowa z krzywą Beziera od obudowy z liniami prostymi? Czy masz krzywą, która może całkowicie zamknąć drugą linię (tak, aby każdy kierunek wskazywał „w kierunku”)?
bummzack,

1
Prawdopodobnie musisz wyjaśnić warunki. W geometrii „linia” rozciąga się nieskończenie w obu kierunkach, w przeciwieństwie do pół linii lub segmentu, więc 2 linie zawsze przecinają się, chyba że są równoległe. O który pytasz? Narysowałeś strzałkę, która wskazuje kierunek, który dla mnie oznacza segment lub co najwyżej pół-linię. A jaka jest twoja definicja „w kierunku” i „z dala”?
Hackworth,

Krzywa Beziera może być trudniejsza do przedstawienia w równości wymaganej do rozwiązania testu przecięcia linii promienia. Nawiasem mówiąc, zmienię słowo reprezentujące twoją strzałkę na „promień”. Możesz uzyskać szybszą odpowiedź. Odpowiem na to pytanie, jeśli będę miał czas podczas lunchu, jeśli nikt inny tego nie zrobi. Jeśli nie, jest to niezwykle częste zadanie w grach. Google „Test przecięcia segmentu linii Ray”. Podejrzewam, że test krzywej Beziera jest podobny, ale nigdy go nie próbowałem.
brandon,

3
Powinieneś podzielić swoje pytanie na dwie części. Część z segmentami linii jest bardzo łatwa. Część z krzywymi Beziera jest niezwykle złożona i ma jedynie przybliżone rozwiązanie numeryczne.
sam hocevar,

Na żądanie podzieliłem moje pytanie na 2. Druga część jest tutaj: gamedev.stackexchange.com/questions/21463/…
Robinicks

Odpowiedzi:


11

Niech Ai Bdwa punkty na czarnej linii. Pozwól Ci Dbądź twoim niebieskim segmentem. Znak zwspółrzędnej krzyżowego iloczynu AB^ACinformuje, czy C„lewa”, czy „prawa” czarnej linii. Podobnie, krzyżowy produkt AB^CDinformuje, czy CDsteruje „w lewo” czy „w prawo” czarnej linii.

Naprawdę nie chcemy wiedzieć, czy jest w lewo, czy w prawo; wszystko, czego chcemy, to upewnić się, że są w tym samym kierunku lub w przeciwnym kierunku, dlatego mnożymy te dwie wartości.

Dlatego powinien działać następujący pseudokod:

z1 = (xB-xA)*(yC-yA) - (yB-yA)*(xC-xA);
z2 = (xB-xA)*(yD-yC) - (yB-yA)*(xD-xC);
z3 = z1 * z2;

if (z3 < 0)
    ; /* Pointing towards (BUT maybe even crossing) */
else if (z3 > 0 || z2 != 0)
    ; /* Pointing away */
else
    ; /* Parallel */

Obawiam się, że potrzebuję trochę czasu, aby napisać właściwe rozwiązanie dla krzywej Beziera. Czy następująca sytuacja jest w kierunku, czy nie?

Problem?


W przypadku krzywej uważam, że można znaleźć styczną krzywej w punkcie najbliższym segmentowi linii i użyć tego w taki sam sposób, jak podczas testowania pozostałych segmentów linii. Prawdopodobnie nieco trudniejsze niż się wydaje :)
notlesh,

@stephelton: Spójrz ponownie na drugie zdjęcie dla krzywych Beziera, wskazując na krzywą, która się zakręca. Lub rozważ krzywą ze styczną równoległą do potencjalnie przecinającego się odcinka, ale która zakrzywia się w kierunku odcinka i przecina się.
Cascabel,

+1 za trollface i dobrą matematykę :). Jednak twój diagram „w kierunku” nadal ma „odejście” - wystarczy przesunąć punkt początkowy powyżej linii.
Jonathan Dickinson,

@JonathanDickinson dzięki, zaktualizowałem obraz, aby nieco jaśniej określić moje przesłuchanie!
sam hocevar,

2

Zakładając, że punktem początkowym jest zielone kółko, a punktem końcowym jest czerwona strzałka

Oblicz odległość między punktem początkowym jako DS i czarnym segmentem i zrób to samo dla punktu końcowego (czerwona strzałka) jak DE. Jeśli DS> DE, segment wskazuje w kierunku. jeśli DE> DS, to wskazuje. Jeśli oba są równe, oba są równoległe.

Można znaleźć w jaki sposób obliczyć odległość od punktu do segmentu tutaj oraz kwadratowej Krzywa Beziera tutaj . Jednak w zależności od kształtu krzywej Beziera może ona zwracać dziwne wyniki (krzywa może się przecinać)


DS> DE gwarantuje działanie tylko dla linii prostych. Może to zawieść dla Beziers. Nie znasz też jego definicji „w kierunku”. Jeśli przedłużenie strzałki przekroczyłoby linię określoną przez 2 punkty, ale nie odcinek zdefiniowany przez te same punkty, to czy nadal jest „w kierunku”?
Hackworth,

Mówię o dwóch segmentach, a nie liniach, więc nie ma „przedłużenia strzałki”. Nie ma też znaczenia, gdzie wskazuje strzałka, ponieważ mówimy tutaj o odległościach. Najbliższym punktem na czarnej linii może być punkt początkowy / końcowy czarnej linii, to nie ma znaczenia. Te dwa segmenty mogą być współliniowe, ta metoda nadal działałaby zgodnie z przeznaczeniem. W przypadku krzywych Beziera wspomniałem, że dałoby to dziwne wyniki w zależności od kształtu krzywej.
Ravachol,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.