Schnittpunkt 2er Geraden

Hallo!

Ich muss den Schnittpunkt von 2 Geraden(im 2d Raum) ausrechnen(besser gesagt, ich muss es einem Javaprogramm beibringen).

Eigentlich sind es Strecken, ich muss also zum Schluss noch prüfen ob der Schnittpunkt innerhalb des gewünschten Intervalls liegt.

Gegeben sind jeweils 2 Punktpaare.
1. Frage: Wenn ich nun eine klassische Geradengleichung aufstelle, kann es sein dass die Steigung k sehr groß wird, und das ist natürlich problematisch da irgendwann der double Bereich überstiegen wird. (ich müsste dann bei Winkeln unter 45Grad die y Form, bei Winkeln über 45 die x Form berechnen - das macht das Programm auch nicht gerade leichter...)
Wenn ich mit Vektoren arbeite, umgehe ich dieses Problem, oder!?

2. Frage: Also hätte ich dann folgende Schreibweise für eine Gerade: (P1.x, P1.y) + s * (P2.x-P1.x, P2.y-P1.y)
Was ist der beste Algorithmus um den Schnittpunkt von 2 solchen Geraden auszurechnen!? Spontan fällt mir da nur Gauss ein. Ist das vernünftig oder wisst ihr da was besseres? Da ich sehr sehr sehr viele solcher Schnittpunktberechnungen machen muss, wäre ein schneller Algorithmus schon gut.
Nur so nebenbei: Ich weiß im Vorhinein schon das Interval in dem sich der Schnittpunkt, wenn es ihn gibt, befinden muss.

Grüße, Harri

Mit Vektorrechnung liegst du schon richtig, aber das Gaußverfahren zur Lösung ist hier überdimensioniert, da Anzahl der Gleichungen und Variablen bekannt sind... Schreibe dir die Gleichungen einfach mal auf Papier auf und stelle sie nach dem Parameter s (und t für die zweite Strecke) um. Die Berechnung kannst du dann mit entsprechendem Code durchführen.

in Vektorschreibweise steht im Ansatz in etwa sowas da:

P11 + s * (P12 - P11) = P21 + t * (P22 - P21)

(P11 = Punkt 1 der Strecke 1, P12 = Punkt 2 der Strecke 2 usw.)

das nun in Komponenten aufteilen und wahlweise s oder t in Abhängigkeit der Koordinatenwerte ausdrücken

DerAltenburger

Ich habe dafür zwei Funktiomem.

Die 1. rechnet "theoretischen Schnitt aus, die 2. testet auch, ob Schnitt auf einer oder beiden Linien liegt.

PRealPoint ist nur ne Klasse mit x,y als doble und ein wenig "Punktlogik":
Die Rückgabe- Varianten sind aus nem enum.

Boolean __fastcall Intersect(PRealPoint P0,PRealPoint P1, PRealPoint P2, PRealPoint P3, TRealPoint &SP, double MaxKoord)
{ double Xz,Xn;
  double Yz,Yn;
  try
  {
    Xz=(P1->Y - P3->Y) * (P1->X - P0->X) * (P3->X - P2->X) +
       (P3->Y - P2->Y) * (P1->X - P0->X) * P3->X -
       (P1->Y - P0->Y) * (P3->X - P2->X) * P1->X;
    Xn=((P3->Y - P2->Y) * (P1->X - P0->X) - (P1->Y - P0->Y) * (P3->X - P2->X));
    Yz=(P1->X - P3->X) * (P1->Y - P0->Y) * (P3->Y - P2->Y) +
       (P3->X - P2->X) * (P1->Y - P0->Y) * P3->Y -
       (P1->X - P0->X) * (P3->Y - P2->Y) * P1->Y;
    Yn=((P3->X - P2->X) * (P1->Y - P0->Y) - (P1->X - P0->X) * (P3->Y - P2->Y));
    if ((Xn!=0) && (Yn!=0))
    { SP.X=(Xz / Xn);
      SP.Y=(Yz / Yn);
      //Exeption, wenn parallel !!!
      if (MaxKoord!=0)
      { if ((fabs(SP.X)>MaxKoord) || (fabs(SP.Y)>MaxKoord))
        { return false;
        }
        return true;
      }
      else
      { return true;
      }
    }
    else
    { return false;
    }
  }
  catch(...)
  { return false;
  }
//  return true;
}
//---------------------------------------------------------------------------
TIntersectTyp __fastcall IntersectPhys(PRealPoint P0,PRealPoint P1, PRealPoint P2, PRealPoint P3)
{
  double X0,Y0;
  double X1,Y1,X2,Y2,X3,Y3;
  double A1_01,A2_01,SA_01,DA_01;
  double A1_12,A2_12,SA_12,DA_12;
  X0=0;
  Y0=0;
  X1=P1->X - P0->X;
  Y1=P1->Y - P0->Y;
  X2=P2->X - P0->X;
  Y2=P2->Y - P0->Y;
  X3=P3->X - P0->X;
  Y3=P3->Y - P0->Y;
  A1_01=X1 * Y2 - X2 * Y1;// / 2.0
  A2_01=X1 * Y3 - X3 * Y1;// / 2.0
  SA_01=fabs(A1_01 + A2_01);
  DA_01=fabs(A1_01 - A2_01);
  X0=P0->X - P2->X;
  Y0=P0->Y - P2->Y;
  X1=P1->X - P2->X;
  Y1=P1->Y - P2->Y;
  X2=0;
  Y2=0;
  X3=P3->X - P2->X;
  Y3=P3->Y - P2->Y;
  A1_12=X3 * Y0 - X0 * Y3;// / 2.0
  A2_12=X3 * Y1 - X1 * Y3;// / 2.0
  SA_12=fabs(A1_12 + A2_12);
  DA_12=fabs(A1_12 - A2_12);
  if (DA_01==0)
  { if (SA_01==0)
    { return istInLine;
    }
    else
    { return istParallel;
    }
  }
  else
  {
    if (SA_01>DA_01)
    { return istNotInLine;
    }
    else
    {
      if (SA_01==DA_01)
      {
/*      //Oldversion
        return itTouched;
*/      //OldVersion Ende
        //Newversion
        if (DA_12==0)
        { if (SA_12==0)
          { return istInLine;
          }
          else
          { return istParallel;
          }
        }
        else
        {
          if (SA_12>DA_12)
          { return istNotInLine;
          }
          else
          { if (SA_12==DA_12)
            { return istEdged;
            }
            else
            { return istTouched;
            }
          }
        //Newversion Ende
        }
      }
      else
      {
        if (DA_12==0)
        { if (SA_12==0)
          { return istInLine;
          }
          else
          { return istParallel;
          }
        }
        else
        {
          if (SA_12>DA_12)
          { return istNotInLine;
          }
          else
          { if (SA_12==DA_12)
            { return istTouched;
            }
            else
            { return istIntersect;
            }
          }
        }
      }
    }
  }
//  return itParallel;
}