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

Nachfolgend sehen Sie meine Linienkreuzung, wie sie in MathWorld . Für die allgemeine Kollisionserkennung/Kreuzung sollten Sie sich die Satz von der trennenden Achse . Ich fand diese Anleitung auf SAT sehr informativ.

    /// <summary>
    /// Returns the intersection point of the given lines. 
    /// Returns Empty if the lines do not intersect.
    /// Source: http://mathworld.wolfram.com/Line-LineIntersection.html
    /// </summary>
    public static PointF LineIntersection(PointF v1, PointF v2, PointF v3, PointF v4)
    {
        float tolerance = 0.000001f;

        float a = Det2(v1.X - v2.X, v1.Y - v2.Y, v3.X - v4.X, v3.Y - v4.Y);
        if (Math.Abs(a) < float.Epsilon) return PointF.Empty; // Lines are parallel

        float d1 = Det2(v1.X, v1.Y, v2.X, v2.Y);
        float d2 = Det2(v3.X, v3.Y, v4.X, v4.Y);
        float x = Det2(d1, v1.X - v2.X, d2, v3.X - v4.X) / a;
        float y = Det2(d1, v1.Y - v2.Y, d2, v3.Y - v4.Y) / a;

        if (x < Math.Min(v1.X, v2.X) - tolerance || x > Math.Max(v1.X, v2.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v1.Y, v2.Y) - tolerance || y > Math.Max(v1.Y, v2.Y) + tolerance) return PointF.Empty;
        if (x < Math.Min(v3.X, v4.X) - tolerance || x > Math.Max(v3.X, v4.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v3.Y, v4.Y) - tolerance || y > Math.Max(v3.Y, v4.Y) + tolerance) return PointF.Empty;

        return new PointF(x, y);
    }

    /// <summary>
    /// Returns the determinant of the 2x2 matrix defined as
    /// <list>
    /// <item>| x1 x2 |</item>
    /// <item>| y1 y2 |</item>
    /// </list>
    /// </summary>
    public static float Det2(float x1, float x2, float y1, float y2)
    {
        return (x1 * y2 - y1 * x2);
    }

Answer 2

(Ich würde dies als Kommentar hinterlassen, aber ich habe noch nicht herausgefunden, wie man das macht).

Als Alternative/Ergänzung zu einem Bounding-Box-Test könnte man auch prüfen, ob der Abstand zwischen den Mittelpunkten der Linien größer ist als die Hälfte der Gesamtlänge der Linien. Wenn dies der Fall ist, können sich die Linien unmöglich überschneiden.

Stellen Sie sich für jede Linie einen minimal umschließenden Kreis vor und testen Sie dann den Schnittpunkt der Kreise. Dies ermöglicht eine Vorberechnung (zumindest für statische Linien und Linien, die ihre Länge beibehalten) und eine effiziente Möglichkeit, viele potenzielle Schnittpunkte auszuschließen.

Answer 3

Nun, Mathematik und skalare Produkte können hier helfen.
- Angenommen, Sie möchten die Segmente [AB] und [CD] schneiden.
- Angenommen, der Schnittpunkt der Linien ist M

M liegt innerhalb des Segments [ÅB], wenn und nur wenn
Vektor(AB) . Vektor(AM) >= 0
y
Vektor(AB) . Vektor(MB) >= 0

wobei der Punkt "." ein Skalarprodukt bezeichnet: u . v = ux * vx + uy * vy

Ihr Algo ist also :
- M finden
- M befindet sich innerhalb beider Segmente, wenn die folgenden 4 Gleichungen zutreffen
Vektor(AB) . Vektor(AM) >= 0
Vektor(AB) . Vektor(MB) >= 0
Vektor(CD) . Vektor(CM) >= 0
Vektor(CD) . Vektor(MD) >= 0

Ich hoffe, das hilft

Answer 4

private function Loop(e:Event):void
{
    var x12:Number = Ball1.x - Ball2.x;
    var x34:Number = Ball3.x - Ball4.x;
    var y12:Number = Ball1.y - Ball2.y;
    var y34:Number = Ball3.y - Ball4.y;

    // Det
    var c:Number = x12 * y34 - y12 * x34;

    if (Math.abs(c) < 0.01)
    {
        Circle.visible = false;
    }
    else
    {
        var a:Number = Ball1.x * Ball2.y - Ball1.y * Ball2.x;
        var b:Number = Ball3.x * Ball4.y - Ball3.y * Ball4.x;
        var px:Number = (a * x34 - b * x12) / c;
        var py:Number = (a * y34 - b * y12) / c;

        var Btwn12x:Boolean = (px >= Math.min(Ball1.x, Ball2.x)) && (px <= Math.max(Ball1.x, Ball2.x));
        var Btwn12y:Boolean = (py >= Math.min(Ball1.y, Ball2.y)) && (py <= Math.max(Ball1.y, Ball2.y));
        var Btwn34x:Boolean = (px >= Math.min(Ball3.x, Ball4.x)) && (px <= Math.max(Ball3.x, Ball4.x));
        var Btwn34y:Boolean = (py >= Math.min(Ball3.y, Ball4.y)) && (py <= Math.max(Ball3.y, Ball4.y));

        var Btwn12:Boolean = Btwn12x && Btwn12y;
        var Btwn34:Boolean = Btwn34x && Btwn34y;

        if(Btwn12 && Btwn34)
        {
            Circle.visible = true;
            Circle.x = px;
            Circle.y = py;
        }
        else
        {
            Circle.visible = false;
        }
    }
}