Effizienter mathematischer Algorithmus zur Berechnung von Schnittpunkten

Question

Für ein Spiel, das ich entwickle, brauche ich einen Algorithmus, der Schnittpunkte berechnen kann. Ich habe das Problem gelöst, aber die Art und Weise, wie ich es gemacht habe, ist wirklich unschön und ich hoffe, dass jemand hier eine elegantere Lösung hat.

Ein Punktpaar stellt die Endpunkte einer zwischen ihnen gezogenen Linie dar. Schneiden sich die gezeichneten Linien bei zwei Punktpaaren, und wenn ja, in welchem Punkt?

Nennen Sie zum Beispiel die Linien (A.x, A.y)-(B.x, B.y) und (C.x, C.y)-(D.x, D.y)

Fällt jemandem eine Lösung ein? Eine Lösung in einer beliebigen Sprache ist ausreichend.

Bearbeiten: Ein Punkt, den ich deutlicher hätte machen sollen: Der Algorithmus muss false zurückgeben, wenn der Schnittpunkt außerhalb der Längen der Liniensegmente liegt.

Answer 1

Die meisten der hier bereits gegebenen Antworten scheinen dem allgemeinen Gedanken zu folgen, dass:

1. Finden Sie den Schnittpunkt zweier Geraden, die durch die gegebenen Punkte verlaufen.
2. bestimmen, ob der Schnittpunkt zu beiden Liniensegmenten gehört.

Wenn es aber nicht oft zu Überschneidungen kommt, ist es wahrscheinlich besser, diese Schritte umzukehren:

1. drücken die Geraden in Form von y = ax + b (Linie durch A,B) und y = cx + d (Linie über C,D)
2. sehen, ob C und D sind auf derselben Seite von y = ax+b
3. sehen, ob A und B sind auf derselben Seite von y = cx+d
4. wenn die Antwort auf die obigen Fragen beides ist keine dann gibt es ist eine Kreuzung. Ansonsten gibt es keine Kreuzung.
5. den Schnittpunkt zu finden, falls es einen gibt.

Hinweis: Für Schritt 2 genügt es zu prüfen, ob (C.y - a(C.x) - b) und (D.y - a(D.x) - b) das gleiche Vorzeichen haben. Schritt 3 ist ähnlich. Schritt 5 ist nur Standardmathematik aus den beiden Gleichungen.

Wenn Sie außerdem jedes Liniensegment mit (n-1) anderen Liniensegmenten vergleichen müssen, spart die Vorberechnung von Schritt 1 für alle Linien Zeit.

Answer 2

Wenn Sie die Gelegenheit haben, sollten Sie sich unbedingt die Bibel der Kollisionserkennung, "Real Time Collision Detection", ansehen, wenn Sie irgendetwas nicht Triviales vorhaben. Ich bin kein professioneller Spieleprogrammierer, aber ich habe die darin enthaltenen Konzepte verstanden und konnte sie ohne große Probleme anwenden.

Amazon - Kollisionserkennung in Echtzeit

Grundsätzlich ist die Durchführung einer Reihe von Linienkreuzungstests in jedem Fall teuer. Was Sie tun, ist Dinge wie Bounding Boxes (Achse ausgerichtet oder orientiert) über Ihre komplexe Polygone verwenden. Damit können Sie schnell eine O(N^2)-Kollisionsprüfung für den schlimmsten Fall zwischen den einzelnen "Objekten" durchführen. Sie können dann die Dinge noch weiter beschleunigen, indem Sie räumliche Bäume (Binary Partitioning oder QuadTrees) verwenden, indem Sie nur die Schnittpunkte von Objekten in der Nähe von einander überprüfen.

Auf diese Weise können Sie viele, viele Kollisionstests streichen. Die beste Optimierung ist, gar nichts zu tun. Erst wenn eine Kollision zwischen Boundingboxen vorliegt, führen Sie die teuren Linienüberschneidungen durch, um festzustellen, ob sich die Objekte wirklich überschneiden oder nicht. Auf diese Weise können Sie die Anzahl der Objekte erhöhen, ohne die Geschwindigkeit zu beeinträchtigen.

Answer 3

float x12 = x1 - x2;
float x34 = x3 - x4;
float y12 = y1 - y2;
float y34 = y3 - y4;

float c = x12 * y34 - y12 * x34;

if (fabs(c) < 0.01)
{
  // No intersection
  return false;
}
else
{
  // Intersection
  float a = x1 * y2 - y1 * x2;
  float b = x3 * y4 - y3 * x4;

  float x = (a * x34 - b * x12) / c;
  float y = (a * y34 - b * y12) / c;

  return true;
}

Formeln entnommen aus:
Linienkreuzung - Wikipedia

Answer 4

public struct PointD
{
    public double X { get; set; }
    public double Y { get; set; }
}

/// <summary>
/// Find the intersection point between two lines.
/// </summary>
/// <param name="IntersectPoint">The intersection point. A <see cref="Esteem.Geometry.PointD">PointD</see> structure.</param>
/// <param name="L1StartPoint">The starting point of first line. A PointD structure.</param>
/// <param name="L1EndPoint">The end point of first line. A PointD structure.</param>
/// <param name="L2StartPoint">The starting point of second line. A PointD structure.</param>
/// <param name="L2EndPoint">The end point of second line. A PointD structure.</param>
/// <param name="L1IntersectPos">The intersection position at first line.</param>
/// <param name="L2IntersectPos">The intersection position at second line.</param>
/// <returns>Returns a boolean. True if there is intersection, false otherwise.</returns>
/// <remarks>The formula is taken from comp.graphics.algorithms Frequently Asked Questions.</remarks>
public static bool LineIntersect(out PointD IntersectPoint, PointD L1StartPoint, PointD L1EndPoint, PointD L2StartPoint, PointD L2EndPoint, out double L1IntersectPos, out double L2IntersectPos) 
{
    IntersectPoint = new PointD();
    double ay_cy, ax_cx, px, py;
    double dx_cx = L2EndPoint.X - L2StartPoint.X,
        dy_cy = L2EndPoint.Y - L2StartPoint.Y,
        bx_ax = L1EndPoint.X - L1StartPoint.X,
        by_ay = L1EndPoint.Y - L1StartPoint.Y;

    double de = (bx_ax) * (dy_cy) - (by_ay) * (dx_cx);
    //double tor = 1.0E-10;     //tolerance

    L1IntersectPos = 0;      L2IntersectPos = 0;
    if (Math.Abs(de)<0.01)
        return false;
    //if (de > -tor && de < tor) return false; //line is in parallel

    ax_cx = L1StartPoint.X - L2StartPoint.X;
    ay_cy = L1StartPoint.Y - L2StartPoint.Y;
    double r = ((ay_cy) * (dx_cx) - (ax_cx) * (dy_cy)) / de;
    double s = ((ay_cy) * (bx_ax) - (ax_cx) * (by_ay)) / de;
    px = L1StartPoint.X + r * (bx_ax);
    py = L1StartPoint.Y + r * (by_ay);

    IntersectPoint.X = px;  //return the intersection point
    IntersectPoint.Y = py;  //return the intersection position
    L1IntersectPos = r;      L2IntersectPos = s;

    return true; //indicate there is intersection
}

Um zu prüfen, ob der Schnittpunkt nicht über die ursprüngliche Länge der Linie hinausgeht, müssen Sie nur sicherstellen, dass 0<r<1 y 0<s<1

Answer 5

Eine einfache Optimierung, die Ihnen viel Zeit ersparen kann, besteht darin, die achsenausgerichteten Begrenzungsrahmen der Linien zu überprüfen, bevor Sie mit der Schnittpunktberechnung beginnen.
Wenn die Begrenzungsrahmen vollständig disjunkt sind, können Sie sicher sein, dass es keine Überschneidung gibt.
Natürlich hängt dies von den Daten ab, die Sie haben. Wenn ein Schnittpunkt bei jeder Prüfung, die Sie durchführen, sehr wahrscheinlich ist, verschwenden Sie möglicherweise Zeit mit einer Prüfung, die immer wahr ist.