Schnittpunkt von 2 Geraden

[DanDanger]

Hallo,

ich habe 2 Geraden, durch je 2 Punkte gegeben.
also z.B.

Gerade 1 geht durch die Punkte : (0, 0) , (5, 3)
Gerade 2 geht durch die Punkte : (1, 3) , (0, 1)


Ich suche nun nach einer Möglichkeit, zu Prüfen, ob sich die beiden Geraden schneiden.
Der Schnittpunkt ist mir erstmal egal, ein einfach Test (SCHNEIDET SICH <-> SCHNEIDET SICH NICHT)
würde mir schon reichen.

Hat da jemand ne' Idee ???

PS: Ich hoffe, das Post ist hier nicht Total OT :)

Neugierige Grüsse
DanDanger

[Pingu]

Mathematik Abitur - Grundkurs 2002 - Aufgabenstellung (http://www.sn.schule.de/~matheabi/02/ma02ga.htm) - nur mal so als Hinweis.

Ansonsten, sind die ersten beiden Treffer (http://www.google.com/search?q=funktion+schnittpunkt+geraden&ie=UTF-8&oe=UTF-8) von Google (http://www.google.de) sehr Hilfreich bei der Lösungsfindung der gegeben Aufgabe.

Gruß

Pingu

[wraith]

Da deine Geraden im 2D liegen,gibt es ja nur zwei Möglichkeiten,
schneiden,oder nicht (oder sie sind identisch,ok. drei Möglichkeiten ^^).

Und jetzt ist es doch simpel,sind die Richtungsvektoren linear abhängig schneiden sie sich nicht (oder sind identisch).
Ansonsten schneiden sie sich.



PS: Ich hoffe, das Post ist hier nicht Total OT

Hättest du noch gefragt,wie man das in C/C++ umsetzt,wäre es nicht mehr OT :).

[Berufspenner]

Original geschrieben von DanDanger
Ich hoffe, das Post ist hier nicht Total OT :)Naja, ich lass es erstmal hier und je nach entwicklung werde ich es dann verschieben.

Cu
André

[bischi]

Da es 2d ist und da es sich nicht um Strecken (sondern um Geraden) handelt, gibt es nur die 2 Möglichkeiten:

Schneiden oder Parallel


Ob sie paralell sind, findest du folgendermassen heraus:

Steigung 1. Gerade: dy/dx (d=Unterschied)
=3/5

Steigung 2. Gerade: analog
= 1/2 (-1/-2)


Da die Steigungen nicht gleich sind, können die Geraden nicht Parallel sein, und da es Geraden sind, müssen sie sich schneiden.

MfG Bischi

PS: Im 3D-Raum ist es viiiiel lustiger!

[DanDanger]

Hi,

erstmal : Danke für Eure Antworten.

Nun, das Problem ist leider nicht gaz so trivial, wie ich es hier beschrieben habe :-((

Ich habe mir aus den Geradengleichungen (in Parameterform) und I-Net Recherche folgenden Code zusammengebastelt :


/**************************
Rueckgabewerte :
TRUE , wenn : Linien sind gleich ODER Schnittpunkt Existiert
FALSE, wenn : Linien sind Parallel
Falls Schnittpunkt ex., enthalten <InterX, InterY> den Schnittpunkt
***************************/
bool IntersecPoint(GLfloat Line1XStart, GLfloat Line1YStart, GLfloat Line1XEnd, GLfloat Line1YEnd,
GLfloat Line2XStart, GLfloat Line2YStart, GLfloat Line2XEnd, GLfloat Line2YEnd,
GLfloat *InterX, GLfloat *InterY)
{
GLfloat U1 ;
GLfloat Numerator, Denominator ; // Zaehler, Nenner
GLfloat IntersectX, IntersectY ;


Numerator = (((Line2XEnd - Line2XStart) * (Line1YStart - Line2YStart)) - ((Line2YEnd - Line2YStart) * (Line1XStart - Line2XStart))) ;
Denominator = (((Line2YEnd - Line2YStart) * (Line1XEnd - Line1XStart)) - ((Line2XEnd - Line2XStart) * (Line1YEnd - Line1YStart))) ;

U1 = Numerator / Denominator ;


if((Numerator == 0) && (Denominator == 0))
{
//Linien sind gleich
return true ;
}

if(Denominator == 0)
{
// Linien sind Parallel
return false ;
}

// Fuer Schnittpunkt : U1 muss zwischen 0 und 1 liegen
if(U1 > 0.0f && U1 < 1.0f)
{
// Schnittpunkt Berechnen
IntersectX = Line1XStart + U1 * (Line1XEnd - Line1XStart) ;
IntersectY = Line1YStart + U1 * (Line1YEnd - Line1YStart) ;
}
else
{
// Kein Schnittpunkt
return false ;
}

*InterX = IntersectX ;
*InterY = IntersectY ;

return true ;
}


Diese Fkt. liefert mir den Schnittpunkt der beiden Strecken (falls er ex.).
Das Problem ist nun, das dieser Code auch für folgende Werte einen Schnittpunkt zurückgibt (Strecke 1 Start/Endpunkt, Strecke 2 Start/Endpunkt) :
Strecke 1 : .................................................. ........................Strecke 2 :
(-0.25, 0.25) (0.25, 0.25) // (0.11588, 0.5198) (0.6563, 1.3611)
Wenn man die Werte mal grob Skizziert sieht man, das hier auf keinen Fall ein Schnittpunkt ex. kann.

Meine Frage : Was läuft hier falsch ???
Kennt jemand einen besseren Algorithmus, zur Berechnung ob sich 2 Strecken (KEINE UNENDLICHEN Geraden, Sorry für die Verwirrung) schneiden, und den Schnittpunkt bestimmen.

Neugierige Grüsse
DanDanger

[anda_skoa]

Du solltest auf jeden Fall beachten, dass deine == 0 Abfragen bei float Zahlen ziemlich daneben gehen können.

Außerdem wäre es angebracht, die Division erst zu machen, wenn du überprüft hast, ob der Nenner != 0 ist denn sonst PUFFF

Ciao,
_

[DanDanger]

Hmm,

wie kann ich denn bei floating-Points auf 0 Prüfen ???
Soll ich so eine Art Epsilon (z.B. 0.00001f) definieren, und darauf testen, oder gibt's da noch ne' bessere Methode ????

Neugierige Grüsse
DanDanger

[anda_skoa]

Original geschrieben von DanDanger
Hmm,

wie kann ich denn bei floating-Points auf 0 Prüfen ???
Soll ich so eine Art Epsilon (z.B. 0.00001f) definieren, und darauf testen, oder gibt's da noch ne' bessere Methode ????


Nein, das ist die beste Methode. == 0 geht nur, wenn der Wert zB mit = 0 initialisiert wurde.

Ciao,
_

[BLUESCREEN3D]

kann das programm nicht einfach die beiden geraden-gleichungen aufstellen und diese gleichsetzen und nach x auflösen? das ist wohl die performanteste und genaueste lösung...

[axeljaeger]

anda_skoa hat schon recht, es ist ein bißchen doof, floats miteinander zu vergleichen. Ich hab da gerade selber Ärger mit. Mit einem Epsilon meinst du sicher, du schaust nach, wie groß die Differenz ist und wenn die kleiner als Epsilon ist, tust du so, als wären die beiden Zahlen gleich?

[bischi]

@ Bluescreen: Nur können Computer leider keine Gleichungen lösen, sonst wäre die ganze Mathematik sinnlos...

MfG Bischi

PS: Geradengleichungen sind relativ einfach, die kannst du schon mit erträglichem Aufwand dem Computer beibringen.

[BLUESCREEN3D]

Original geschrieben von bischi
@ Bluescreen: Nur können Computer leider keine Gleichungen lösen, sonst wäre die ganze Mathematik sinnlos...

MfG Bischi

PS: Geradengleichungen sind relativ einfach, die kannst du schon mit erträglichem Aufwand dem Computer beibringen.
schön, wie du dir selbst widersprichst :D

ich stelle mir das so vor:



steigung1=(gerade1.y2-gerade1.y1)/(gerade1.x2-gerade1.x1);
steigung2=(gerade2.y2-gerade2.y1)/(gerade2.x2-gerade2.x1);
verschiebung1=gerade1.y1-gerade1.x1*steigung1;
verschiebung2=gerade2.y1-gerade2.x1*steigung2;

//damit haben wir beide geradengleichungen:
//y=steigung1*x+verschiebung1
//und
//y=steigung2*x+verschiebung2

//sonderfälle:
if (steigung1==steigung2)
{
if (verschiebung1==verschiebung2)
{
cout << "unendlich schnittpunkte" << endl;
}
else
{
cout << "kein schnittpunkt" << endl;
}
}

//zwei geraden schneiden sich, wenn sie an der gleichen x-stelle den gleichen y-wert haben
//also kann man die beiden geraden gleichsetzen und nach x auflösen:
//steigung1*x+verschiebung1=steigung2*x+verschiebung 2
//steigung1*x=steigung2*x+verschiebung2-verschiebung1
//steigung1*x-steigung2*x=verschiebung2-verschiebung1
//(steigung1-steigung2)*x=verschiebung2-verschiebung1
//x=(verschiebung2-verschiebung1)/(steigung1-steigung2)
//also:

x=(verschiebung2-verschiebung1)/(steigung1-steigung2);
y=steigung1*x+verschiebung1;
cout << "Schnittpunkt bei " << x << "/" << y << endl;

[BLUESCREEN3D]

ist das ein bug im forum?

ich schreibe:
/ / s t e i g u n g 1 * x + v e r s c h i e b u n g 1 = s t e i g u n g 2 * x + v e r s c h i e b u n g 2
(ohne die leerzeichen)

und angezeigt wird:
//steigung1*x+verschiebung1=steigung2*x+verschiebung 2

also mit einem leerzeichen hinter dem "//" und der 2 in der nächsten zeile...

[bischi]

@Bluescreen: Ich widerspreche mir überhaupt nicht: Computer können grundsätzlich keine Gleichungen lösen, du kannst die Gleichung aber sonst lösen und dem Computer dann beibringen, was er zu rechnen hat, um die Lösung zu errechnen. :)

MfG Bischi

[peschmae]

so progs wie Mathmatica können schon Gleichungen lösen

keine Ahnung wie

MfG Peschmä

[BLUESCREEN3D]

Original geschrieben von peschmae
so progs wie Mathmatica können schon Gleichungen lösen

keine Ahnung wie

kann das proggie wirklich gleichungen lösen/umformen, oder kann es nur für eine bestimmte gleichung sagen, welche variable welchen wert hat?

wenn es das zweite ist, dann ist das ein annäherungsverfahren - im prinzip ein optimiertes durchprobieren von verschiedenen zahlen