Jak wykryć zderzenie linii 2D z linią?

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ł

PS Próbuję zrobić funkcję jako

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

Z góry dziękuję.

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ą:

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ę.

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));

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)