Geraden-Schnitt anhand Punktkoordinaten detektieren |
23.11.2015, 15:52 | Heino | Auf diesen Beitrag antworten » |
Geraden-Schnitt anhand Punktkoordinaten detektieren 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. |
||
23.11.2015, 16:31 | kgV | Auf diesen Beitrag antworten » |
RE: Geraden-Schnitt anhand Punktkoordinaten detektieren Dieser Ansatz ist für die Tonne, tut mir leid [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 |
||
23.11.2015, 17:13 | 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 Vielleicht nicht effektiv, aber einfacher gehts dann wohl nicht...^^ |
||
23.11.2015, 17:32 | kgV | Auf diesen Beitrag antworten » |
Du brauchst nur einen Schnitt, nicht zwei (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 |
||
23.11.2015, 17:39 | 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. 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... |
||
23.11.2015, 17:42 | 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 |
||
Anzeige | ||
|
||
23.11.2015, 18:00 | 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 |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|