Geraden-Schnitt anhand Punktkoordinaten detektieren

Neue Frage »

Heino Auf diesen Beitrag antworten »
Geraden-Schnitt anhand Punktkoordinaten detektieren
Moinson!

Ich sitze momentan an einem Programmierprojekt und eine der benötigten Teilaufgaben besteht darin, bei zwei Polygonen zu testen, ob sie sich (teilweise) überlappen.
Die Polygone sind durch ihre Eckpunkte gegeben, wobei jeder Eckpunkt eine x- und eine y-Koordinate besitzt.

Mein (naiver?) Ansatz würde darin bestehen, aus beiden Polygonen jeweils zwei Eckpunkte zu nehmen und zu schauen, ob sich die dazwischenliegenden beiden Geraden schneiden. Das müsste man dann bei allen möglichen Geraden-Kombinationen testen. Schneiden sich mindestens zwei Geraden, überlappen sich die Polygone.
Gibt es eine (leichte) mathematische Methode, anhand der Koordinaten der Start- und Endpunkte rauszufinden, ob sich die dazwischenliegenden Geraden schneiden?
Ich dachte dabei an sowas oder so ähnlich: Wenn xStart1 > xStart2, aber xEnd1 < xEnd2 gilt, muss sich ja irgendwo was gedreht haben -> Schnitt? Wollte mal bei "richtigen" Mathematikern nachfragen, da dieser Part enorm wichtig fürs ganze Projekt ist. Danke im Voraus. Big Laugh
kgV Auf diesen Beitrag antworten »
RE: Geraden-Schnitt anhand Punktkoordinaten detektieren
Dieser Ansatz ist für die Tonne, tut mir leid Augenzwinkern

[attach]39854[/attach]

Die beiden Dreiecke im Bild überlappen offensichtlich nicht, dennoch schneiden sich die beiden eingezeichneten Verbindungsgeraden


Ein funktionierender Ansatz wäre der Folgende:
Zwei Polygone überlappen, wenn sich mindestens zwei der Kanten schneiden (je eine Kante pro Polygon). Du müsstest jetzt jede Kante parametrisieren und dann auf Schnittpunkte prüfen.

Wird ein ziemlicher Aufwand werden, aber etwas leichteres fällt mir grad nicht ein.

Wenn sich Schwierigkeiten mit dem Parametrisieren auftun, dann melde dich einfach noch mal

Lg
kgV
Wink
Heino Auf diesen Beitrag antworten »

Alles klar, dann iteriere ich durch alle Kanten (also bei N und M Eckpunkten wären das N*M Kombinationen) und nebenher läuft ein Zähler, der nach zwei gefundenen Schnitten abbricht smile
Vielleicht nicht effektiv, aber einfacher gehts dann wohl nicht...^^
kgV Auf diesen Beitrag antworten »

Du brauchst nur einen Schnitt, nicht zwei smile (das wäre zum Beispiel der Fall, wenn deine Polygone eine Kante gemeinsam haben, sonst wirst du immer mindestens zwei Schnitte finden)

Die zwei in meinem Beitrag bezog sich auf die Anzahl der Kanten, nicht der Schnittpunkte smile
Heino Auf diesen Beitrag antworten »

Okay, macht Sinn. Schneiden sie sich einmal, ist ja eh von vorneherein klar, dass sie sich auch noch ein zweites Mal schneiden. Big Laugh
Hm. Mir fällt gerade auf, dass ich immer noch nicht weiß, wie ich am besten auf Schnittpunkte prüfe. :/ Ich könnte wahrscheinlich die Strecken als Geradengleichung nehmen, gleichsetzen und schauen ob ne Lösung rauskommt, und danach noch wieder auf die Strecke beschränken. Weiß nur nicht, ob ich das programmiertechnisch effizient genug umsetzen kann...
Steffen Bühler Auf diesen Beitrag antworten »

Ich hab mich mit dem Problem zwar noch nicht beschäftigt, aber Googlen nach "polygon overlap" bringt einige Ergebnisse, die Dir vielleicht weiterhelfen.

Viele Grüße
Steffen
 
 
kgV Auf diesen Beitrag antworten »

Die einzelnen Kanten sind relativ schnell parametrisiert: Wenn zwei Ecken im ersten Polygon sind und zwei Ecken im zweiten, dann ist die entsprechende Kante bzw .

Jetzt gleichsetzen liefert dann im Endeffekt ein Gleichungssystem in den beiden t-Variablen. Wenn das eine Lösung hat, dann gibt es einen Schnittpunkt.

Google hat aber sicher wesentlich effizientere Algorithmen parat, da gebe ich Steffen Recht smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »