XNA Liniensegment Schnittpunkt?

Question

Sagen wir, wir haben 4 Vector2 (ja, das ist 2d), also haben wir lineOneStart, lineOneEnd, lineTwoStart und lineTwoEnd.

Wie kann ich erkennen, ob sich die beiden Linien kreuzen? Es ist mir egal, wo sie sich kreuzen, ich möchte nur wissen, ob sie sich schneiden.

Answer 1

Überprüfen Sie diese Formel mit Bourke .

Auch ich musste dieses Problem kürzlich lösen. Eine andere Möglichkeit besteht darin, die Gleichung der Geraden zu verwenden ( y = mx + c ), aber es gibt einige Randfälle, mit denen Sie sich befassen müssen, ebenso wie mit der Überprüfung, ob der Schnittpunkt innerhalb des Liniensegments liegt. Die Formel im obigen Link funktioniert, obwohl ich nicht wirklich kommentieren kann, wie die Gleichung umgestellt wird, ich kann nur sagen, dass es funktioniert ;)

Editer :

Wie von AndiDog erwähnt, habe ich auch diese Website verwendet (das Beispiel ist ebenfalls ausgezeichnet) tutorial . Da es sich um XNA handelt, ist der zweite Link genau das Richtige für Sie.

Bearbeiten (Inhalt von defektem Link) :

Die Gleichungen der Linien lauten Pa = P1 + ua ( P2 - P1 ) y Pb = P3 + ub ( P4 - P3 )

Die Lösung für den Punkt, an dem Pa = Pb ergibt die folgenden zwei Gleichungen mit zwei Unbekannten (ua und ub) x1 + ua (x2 - x1) = x3 + ub (x4 - x3) y y1 + ua (y2 - y1) = y3 + ub (y4 - y3) Die Lösung ergibt die folgenden Ausdrücke für ua und ub

Setzt man eine dieser beiden Gleichungen in die entsprechende Geradengleichung ein, erhält man den Schnittpunkt. Zum Beispiel ist der Schnittpunkt (x,y) x = x1 + ua (x2 - x1) y = y1 + ua (y2 - y1)

Anmerkungen: Die Nenner der Gleichungen für ua und ub sind identisch. Wenn der Nenner der Gleichungen für ua und ub gleich 0 ist, sind die beiden Geraden parallel. Wenn der Nenner und der Zähler der Gleichungen für ua und ub gleich 0 sind, dann fallen die beiden Geraden zusammen. Die Gleichungen gelten für Geraden, wenn der Schnittpunkt von Geradensegmenten benötigt wird, muss nur geprüft werden, ob ua und ub zwischen 0 und 1 liegen. Je nachdem, welches von beiden innerhalb dieses Bereichs liegt, enthält das entsprechende Geradensegment den Schnittpunkt. Liegen beide im Bereich von 0 bis 1, dann liegt der Schnittpunkt in beiden Liniensegmenten.

Answer 2

Es gibt eine tutorial zu diesem Thema (Schnittpunkt von Liniensegmenten).

Answer 3

Der Vollständigkeit halber füge ich im Folgenden den Algorithmus für die Darstellung von Zeilen in (a,b,c) Koordinaten, so dass die Gleichung für die Linie lautet a*x+b*y+c=0 .

• Zwei Zeilen mit Koordinaten (a1,b1,c1) y (a2,b2,c2) sich in einem Punkt schneiden (x,y)

• Ermitteln Sie die homogenen Koordinaten des Punktes als

  u = b1*c2-b2*c1;
  v = a2*c1-a1*c2;
  w = a1*b2-a2*b1;

• Wenn Linien parallel sind, dann w=0 .

• Andernfalls befindet sich der Schnittpunkt bei

  x = u/w;
  y = v/w;

Anhang

• So definieren Sie eine Linie (a,b,c) durch zwei Punkte (x1,y1) y (x2,y2) verwenden.

  a= y1-y2;
  b= x2-x1;
  c= x1*y2-y1*x2;

• So definieren Sie eine Linie (a,b,c) durch einen Punkt (x,y) mit polarer Richtung (cos(),sin())

  a= -sin();
  b=  cos();
  c= x*sin()-y*cos();