Schnittpunktberechnung zweier "Strecken"

[~Mathe]

Kennt hier jemand Mathe Units/Komponenten die mir bei folgender Aufgabe helfen?

Ich habe 2 Strecken (keine Geraden!) und möchte wissen, ob es einen Schnittpunkt gibt und diesen ausgeben. Ich habe also 4 Punkte, wovon 2 Punkte(x,y) zu einer Strecke gehören.

Strecke 1: PunktA(x,y) und PunktB(x,y)

Strecke 2: PunktC(x,y) und PunktD(x,y)

Für Geraden habe ich eine Lösung gefunden, aber für Strecken hänge ich leider fest. Kann hier jemand weiterhelfen?

[DerAltenburger]

Definiere "Strecke"

- Polygonzug (einfache Lösung)
- Splines, Nurbs... (da wird's schon komplex ...)

Gruss
Frank

[~Math]

Ich habe einfach in einem 2D Koordinatensystem zwei gerade Linien und jede Linie ist durch ihre zwei X,Y Koordinaten definiert. Ich möchte dann gern wissen, wo sich diese zwei Linien schneiden. Aber nur, wenn sich der Schnittpunkt innerhalb der definierten "Strecke" befindet. Also zwischen den zwei bekannten Punkten P1(x,y) und P2(x,y) einer Linie.

Ich finde massenweise "lines segment intersection" funktionen, aber keine die mir den Schnittpunkt auch angibt. Alle sagen nur ob es einen Schnittpunkt gibt.

http://www.smipple.net/snippet/sparkon/[C%2B%2B] 2D lines segment intersection

http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

http://ptspts.blogspot.de/2010/06/how-to-determine-if-two-line-segments.html

http://www.onemoresoftwareblog.com/2011/11/two-line-segment-intersection-algorithm.html

[~Math]

Ich glaube ich habe was gefunden: http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
    float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
    float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
    s10_x = p1_x - p0_x;
    s10_y = p1_y - p0_y;
    s32_x = p3_x - p2_x;
    s32_y = p3_y - p2_y;

    denom = s10_x * s32_y - s32_x * s10_y;
    if (denom == 0)
        return 0; // Collinear
    bool denomPositive = denom > 0;

    s02_x = p0_x - p2_x;
    s02_y = p0_y - p2_y;
    s_numer = s10_x * s02_y - s10_y * s02_x;
    if ((s_numer < 0) == denomPositive)
        return 0; // No collision

    t_numer = s32_x * s02_y - s32_y * s02_x;
    if ((t_numer < 0) == denomPositive)
        return 0; // No collision

    if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
        return 0; // No collision
    // Collision detected
    t = t_numer / denom;
    if (i_x != NULL)
        *i_x = p0_x + (t * s10_x);
    if (i_y != NULL)
        *i_y = p0_y + (t * s10_y);

    return 1;
}

[DerAltenburger]

~Math schrieb:

Ich habe einfach in einem 2D Koordinatensystem zwei gerade Linien und jede Linie ist durch ihre zwei X,Y Koordinaten definiert. Ich möchte dann gern wissen, wo sich diese zwei Linien schneiden. Aber nur, wenn sich der Schnittpunkt innerhalb der definierten "Strecke" befindet. Also zwischen den zwei bekannten Punkten P1(x,y) und P2(x,y) einer Linie.

Ich finde massenweise "lines segment intersection" funktionen, aber keine die mir den Schnittpunkt auch angibt. Alle sagen nur ob es einen Schnittpunkt gibt.

http://www.smipple.net/snippet/sparkon/[C%2B%2B] 2D lines segment intersection

http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

http://ptspts.blogspot.de/2010/06/how-to-determine-if-two-line-segments.html

http://www.onemoresoftwareblog.com/2011/11/two-line-segment-intersection-algorithm.html

Mich hatte irritiert:

~Math schrieb:

Für Geraden habe ich eine Lösung gefunden, aber für Strecken hänge ich leider fest. Kann hier jemand weiterhelfen?

Eine Strecke/ Linie definiert ja mit den Enden eine Richtung und damit eine Gerade. ..

Nun gut, Du hast ja ne Lösung gefunden.

Gruss
Frank

Gruss
Frank

[audacia]

DerAltenburger schrieb:

Mich hatte irritiert:

~Math schrieb:

Für Geraden habe ich eine Lösung gefunden, aber für Strecken hänge ich leider fest. Kann hier jemand weiterhelfen?

Eine Strecke/ Linie definiert ja mit den Enden eine Richtung und damit eine Gerade. ..

Klar, und den Schnittpunkt zwischen zwei Geraden zu bestimmen ist trivial. Das Komplexe daran sind ja gerade die Begrenzungen, wie du an den Fallunterscheidungen in der Lösung siehst.

[DerAltenburger]

audacia schrieb:

DerAltenburger schrieb:

Mich hatte irritiert:

~Math schrieb:

Für Geraden habe ich eine Lösung gefunden, aber für Strecken hänge ich leider fest. Kann hier jemand weiterhelfen?

Eine Strecke/ Linie definiert ja mit den Enden eine Richtung und damit eine Gerade. ..

Klar, und den Schnittpunkt zwischen zwei Geraden zu bestimmen ist trivial. Das Komplexe daran sind ja gerade die Begrenzungen, wie du an den Fallunterscheidungen in der Lösung siehst.

Also wenn Du den SP hast teste einfach:

Xsp zwischen Xstart und Xend oder
Ysp zwischen Ystart und Yend,
je nachdem welche Differenz grösser ist...

Gruss
Frank