Effizienter mathematischer Algorithmus zur Berechnung von Schnittpunkten

Meisten Antworten bereits hier zu Folgen scheint die Allgemeine Idee, dass:

1. finden, den Schnittpunkt von zwei geraden Vorbeigehen die Punkte gegeben.
2. bestimmen, ob die Kreuzung gehören beide Liniensegmente.

Aber bei Kreuzung nicht oft auftreten, ein besserer Weg ist wohl umkehren diese Schritte:

1. express die geraden Linien in der form von y = ax + b (line passing A,B) und y = cx + d (Linie C übergeben,D)
2. sehen, ob C und D sind auf der gleichen Seite von y = ax+b
3. sehen, ob A und B sind auf der gleichen Seite von y = cx+d
4. wenn die Antwort auf die oben sind beide keinedann gibt es ist eine Kreuzung. ansonsten gibt es keinen Schnittpunkt.
5. finden Sie die Kreuzung und wenn es einer ist.

Hinweis: Schritt 2 überprüfen Sie, ob (C. y - a(C. x) - b) und (D. y - a(D. x) - b) haben das gleiche Vorzeichen. Schritt 3 ist ähnlich. Schritt 5 ist nur standard Mathe aus den beiden Gleichungen.

Darüber hinaus, wenn Sie vergleichen müssen jeder Zeile segment mit (n-1) anderen Liniensegmente, precomputing Schritt 1 für alle Zeilen spart Ihnen Zeit.

InformationsquelleAutor der Antwort PolyThinker

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:

Line-line-intersection - Wikipedia

InformationsquelleAutor der Antwort Tom Wijsman

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
}

Prüfen, ob der Schnittpunkt ist nicht über die ursprüngliche Länge der Linie, so stellen Sie sicher, dass 0<r<1 und 0<s<1

InformationsquelleAutor der Antwort Graviton

Gut, der Mathematik und der skalaren Produkte können helfen.

- Sagen Sie, Sie wollen zu schneiden Segmente [AB] und [CD]

- Nehmen wir an, die Linie Schnittpunkt der Linien ist M

M ist im inneren segment [ÅB], wenn und nur, wenn

Vektor(AB) . Vector(AM) >= 0

und

Vektor(AB) . Vector(MB) >= 0

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

So, Ihr algo :

- finden Sie M

- M ist in beiden segment, wenn und nur wenn die 4 eq-unten sind wahre

Vektor(AB) . Vector(AM) >= 0

Vektor(AB) . Vector(MB) >= 0

Vector(CD) . Vector(CM) >= 0

Vector(CD) . Vector(MD) >= 0

Hoffe, das hilft

InformationsquelleAutor der Antwort Pascal T.

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

InformationsquelleAutor der Antwort Galindo