Jak wykryć zderzenie linii 2D z linią?


13

Jestem programistą gier flashowych, który jest trochę zacofany w matematyce, choć uważam, że fizyka jest zarówno interesująca, jak i fajna.

Dla porównania jest to gra podobna do tej, którą tworzę : gra flashowa Untangled

Sprawiłem, że ta nieplątana gra jest prawie pełna logiki. Ale kiedy przecinają się dwie linie, potrzebuję tych przeciętych lub „splątanych” linii, aby pokazać inny kolor; czerwony.

Byłoby naprawdę miło z twojej strony, gdybyś mógł zasugerować algorytm do wykrywania kolizji segmentów linii . Jestem w zasadzie osobą, która lubi myśleć „wizualnie” niż „arytmetycznie” :)

Edycja: Chciałbym dodać kilka diagramów, aby wyraźniej przekazać pomysł

bez skrzyżowania bez skrzyżowania skrzyżowanie bez skrzyżowania

PS Próbuję zrobić funkcję jako

private function isIntersecting(A:Point, B:Point, C:Point, D:Point):Boolean

Z góry dziękuję.


6
Jest to rozczarowujące, nie-wizualne wyjaśnienie problemu, ale jest to algorytm i ma sens, jeśli możesz zmusić się do przeczytania ich matematyki: local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d Może to bądź ciężki, jeśli matematyka wektorowa jest słaba. Rozumiem - wolę też wyjaśnienia wizualne. Postaram się później znaleźć czas, aby to narysować, ale jeśli ktoś w ogóle artystycznie skłonny zobaczy ten link i będzie miał czas, zanim to zrobię, przejdź do niego!
Anko

Odpowiedzi:


18

Korzystam z następującej metody, która jest właściwie tylko implementacją tego algorytmu . Jest w C #, ale przetłumaczenie go na ActionScript powinno być trywialne.

bool IsIntersecting(Point a, Point b, Point c, Point d)
{
    float denominator = ((b.X - a.X) * (d.Y - c.Y)) - ((b.Y - a.Y) * (d.X - c.X));
    float numerator1 = ((a.Y - c.Y) * (d.X - c.X)) - ((a.X - c.X) * (d.Y - c.Y));
    float numerator2 = ((a.Y - c.Y) * (b.X - a.X)) - ((a.X - c.X) * (b.Y - a.Y));

    // Detect coincident lines (has a problem, read below)
    if (denominator == 0) return numerator1 == 0 && numerator2 == 0;

    float r = numerator1 / denominator;
    float s = numerator2 / denominator;

    return (r >= 0 && r <= 1) && (s >= 0 && s <= 1);
}

Jest jednak subtelny problem z algorytmem, w którym dwie linie są zbieżne, ale nie nakładają się. W takim przypadku algorytm nadal zwraca przecięcie. Jeśli zależy ci na tej sprawie, uważam, że ta odpowiedź na stackoverflow ma bardziej złożoną wersję, która rozwiązuje ten problem.

Edytować

Przepraszam, nie otrzymałem wyniku z tego algorytmu!

To dziwne, przetestowałem to i działa dla mnie, z wyjątkiem tego jednego przypadku, który opisałem powyżej. Używając dokładnie tej samej wersji, którą zamieściłem powyżej, otrzymałem te wyniki, gdy wziąłem to na jazdę testową:

wprowadź opis zdjęcia tutaj


Przepraszam, nie otrzymałem wyniku z tego algorytmu!
Wisznu

4
@Vish Jaki miałeś problem? Przetestowałem dokładnie tę kopię algorytmu przed opublikowaniem i działała bezbłędnie, z wyjątkiem opisanego pojedynczego przypadku.
David Gouveia

Pozwólcie, że spróbuję jeszcze raz, być może pomieszałem w tym matematykę. Powiadomię cię wkrótce. Dzięki tonie, zawsze :)
Wisznu

1
Algorytm uzyskałem pożądany wynik, dzięki @DavidGouveia.
Wisznu

1
No ale teraz mam kolejny problem :)! Muszę zrobić przecięte linie z kolorem czerwonym i zielonym. Skrzyżowanie działa dobrze. Ale jak teraz rozumiem (choć nie matematycznie), że proste „jeśli” nie zadziała, jak do umieszczania czerwonych i zielonych linii dla linii przecinających się i nie przecinających. Węzeł, który przeciągam, ma zarówno lewą, jak i prawą linię. Więc coś poszło nie tak, zmieniając kolor nie przecinających się linii z powrotem na zielony. Chyba potrzebuję też innego warunku. Hmmm, w każdym razie dzięki tonie, zaznaczam to jako poprawną odpowiedź.
Wisznu

4

Bez podziałów! Więc nie ma problemu z precyzją ani dzieleniem przez zero.

Segment linii 1 to A do B Segment linii 2 to C do D

Linia jest niekończącą się linią, segment linii jest zdefiniowaną częścią tej linii.

Sprawdź, czy dwie ramki ograniczające się przecinają: jeśli nie ma przecięcia -> Bez krzyża! (obliczenia wykonane, zwróć false)

Sprawdź, czy linia seg 1 rozciąga się na linii seg 2 i czy linia seg 2 rozciąga się na linii seg 1 (tj. Linia Segment 1 znajduje się po obu stronach linii zdefiniowanej przez linię Segment 2).

Można tego dokonać, tłumacząc wszystkie punkty przez -A (tzn. Przesuwasz 2 linie, aby A było na początku (0,0))

Następnie sprawdzasz, czy punkty C i D znajdują się po różnych stronach linii określonej przez 0,0 do B

//Cross Product (hope I got it right here)
float fC= (B.x*C.y) - (B.y*C.x); //<0 == to the left, >0 == to the right
float fD= (B.x*D.y) - (B.y*D.x);

if( (fc<0) && (fd<0)) //both to the left  -> No Cross!
if( (fc>0) && (fd>0)) //both to the right -> No Cross!

Jeśli nie masz jeszcze „No Cross”, kontynuuj używanie nie A, B w porównaniu z C, D, ale C, D w porównaniu z A, B (te same cielęta, po prostu zamień A i C, B i D), jeśli nie ma „Bez krzyża!” wtedy masz skrzyżowanie!

Szukałem dokładnych obliczeń dla produktu krzyżowego i znalazłem ten post na blogu, który wyjaśnia również tę metodę.


1
Przykro mi, ale nie jestem całkiem dobry w matematyce wektorowej, zaimplementowałem ten algorytm jako taki, ale nie mam rezultatu, przepraszamy!
Wisznu

1
Powinno to działać, więc może jeśli możesz nam pokazać swój kod, możemy Ci pomóc?
Valmond

Ładny! jednak link jest zerwany
clabe45

Czy można coś do tego dodać, aby uzyskać punkt przecięcia?
SeanRamey

1

Chcę tylko powiedzieć, że potrzebowałem go do mojej gry Gamemaker Studio i działa dobrze:

///scr_line_collision(x1,y1,x2,y2,x3,y3,x4,y4)

var denominator= ((argument2 - argument0) * (argument7 - argument5)) - ((argument3 - argument1) * (argument6 - argument4));
var numerator1 = ((argument1 - argument5) * (argument6 - argument4)) - ((argument0 - argument4) * (argument7 - argument5));
var numerator2 = ((argument1 - argument5) * (argument2 - argument0)) - ((argument0 - argument4) * (argument3 - argument1));

// Detect coincident lines
if (denominator == 0) {return (numerator1 == 0 && numerator2 == 0)}

var r = numerator1 / denominator;
var s = numerator2 / denominator;

return ((r >= 0 && r <= 1) && (s >= 0 && s <= 1));

Myślę, że ta odpowiedź mogłaby się poprawić, jeśli wyjaśnisz, co robi kod.
TomTsagk,

1

Przyjęta odpowiedź dała złą odpowiedź w tym przypadku:

x1 = 0;
y1 = 0;
x2 = 10;
y2 = 10;

x3 = 10.1;
y3 = 10.1;
x4 = 15;
y4 = 15;

Te linie oczywiście się nie przecinają, ale zgodnie z funkcją w „poprawnej odpowiedzi” linie się przecinają.

Oto, czego używam:

function do_lines_intersect(px1,py1,px2,py2,px3,py3,px4,py4) {
  var ua = 0.0;
  var ub = 0.0;
  var ud = (py4 - py3) * (px2 - px1) - (px4 - px3) * (py2 - py1);


  if (ud != 0) {
    ua = ((px4 - px3) * (py1 - py3) - (py4 - py3) * (px1 - px3)) / ud;
    ub = ((px2 - px1) * (py1 - py3) - (py2 - py1) * (px1 - px3)) / ud;
        if (ua < 0.0 || ua > 1.0 || ub < 0.0 || ub > 1.0) ua = 0.0;
  }

  return ua;
}

zwraca 0 = linie nie przecinają się

zwraca> 0 = linie przecinają się


Zaktualizuj, aby odpowiedzieć na pytanie:

Sam nie stworzyłem tego kodu. Ma ponad 5 lat i nie wiem, jakie jest oryginalne źródło. Ale..

Myślę, że wartością zwracaną jest względna pozycja pierwszego wiersza, w którym przecinają się (aby źle to wytłumaczyć). Aby obliczyć punkt przecięcia, prawdopodobnie możesz użyć Lerp w następujący sposób:

l = do_lines_intersect(...)
if (l > 0) {
    intersect_pos_x = l * (px2-px1);
    intersect_pos_y = l * (py2-py1);
} else {
    // lines do not cross
}

(NIE TESTOWAŁEM TEGO)


Czy istnieje wersja tego, która zwraca punkt przecięcia?
SeanRamey
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.