Hey alle zusammen, folgendes Problem: Ich habe 4 Punkte gegeben, die auf jedenfall ein Viereck bilden. Allerdings ist mir die Reihenfolge der Punkte nicht bekannt. Wie kann ich ermitteln, ob sich, wenn ich Punkt1 mit Punkt2, Punkt2 mit Punkt3 usw. verbinde, zwei Linien kreuzen oder nicht? Das war jetzt vermutlich nicht wirklich verständlich. Deshalb ein Beispiel: P1(0, 0) P2(1, 1) P3(1, 0) P4(0, 1) Aus diesen Punkten kann man jetzt zwar ein Viereck bilden, allerdings darf man dann sie dazu nicht der Reihe nach verbinden. Frage: Wie kann ich ermitteln, ob die Punkte, der Reihe nach verbunden ein Viereck bilden oder nicht? Ich habe schon verschieden Methoden mit Vergleich von Seitenlängen, Steigungen, Diagonalen, Umfang, ... probiert, bisher leider nichts funktionierendes gefunden. Grüße Sam
Ich würde aus jeweils zwei Punkten Geraden bilden und den Schnittpunkt berechnen. Liegt dieser zwischen den jeweiligen Punkten, schneiden sich die Linien.
Laufe die Punkte entlang und summiere die Winkel, d.h. die WInkeländerung die an einem Punkt genommen wird. Addiere das, und es muss 360° oder -360° (bzw 2pi oder -2pi) rauskommen. Die Orientierung der Winkel muss beachtet werden, d.h. immer mathematisch positiv oder negativ orientiert rechnen.
Zwei gute Vorschläge, leider muss ich mit Ganzzahlen auskommen, was leider beides ausschließt.
be stucki schrieb: > Ich würde aus jeweils zwei Punkten Geraden bilden und den Schnittpunkt > berechnen. Liegt dieser zwischen den jeweiligen Punkten, schneiden sich > die Linien. Wird blöd bei nem Deltoid und evtl auch bei entarteten Vierecken.
Ist doch einfach, und gilt für beliebige Vielecke unter der Bedingung, dass alle Ecken einen Innenwinkel kleiner 180° haben. Du wählts zuerst einen bliebigen Punkte als Startpunkt. zB. P3 Jetzt tust Du zu allen andern Punkten Strecken bilden. (P3P1, P3P2, P3P4, ...) Nun vergleichst Du die Winkel zwichen den Strecken. Die beiden Strecken, die den größten Winkel bilden (der logischerweise kleiner 180° ist) sind zwei der gesuchten Strecken. Hier wären es P3P4 und P3P2. Nun wählst Du eine dieser Strecken (zB P3P2) gehst Du zum Endpunkt (also P2). Von dort bildest Du wieder alle Strecken (bereits verwendete Strecken lässt Du natürlich aus), Also P2P1 P2P4, und suchst die Strecke von beiden raus, die den größten Winkel mit der Strecke hat, die Du genommen hast um zu diesem Punkt (P2) zu kommen, also mit P3P2. Das sollte jetzt P2P4 sein. Nun gehst Du zu deren Endpunkt (P4) und suchst wieder die Strecke mit dem größten Winkel... bis alle Punkte abgearbeitet sind. Ich haben fertig.
Folgender Ansatz kommt mit Additionen, Subtraktionen, Multiplikationen und Vergleichen aus und ist deswegen auch für Ganzzahlarithmetik geeignet: Wende die hier beschriebene Funktion ccw http://en.wikipedia.org/wiki/Graham_scan#Pseudocode nacheinander auf P1, P2, P3 P2, P3, P4 P3, P4, P1 P4, P1, P2 an und zähle, wie oft das Ergebnis positiv ist. Diese Anzahl n charakterisiert das Viereck wie folgt:
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
Das sollte zumindest dann funktionieren, wenn keine 3 der 4 Punkte auf einer Linie liegen. Falls 3 der 4 Punkte auf einer Linien liegen können (entartetes Viereck), musst du die Ergebnisse von ccw nicht nur auf positiv, sondern auch auf null prüfen. Die weitere Auswertung hängt dann davon ab, welche der entarteten Vierecke du als Viereck akzeptierst und welche nicht.
Ok, vielen Dank. Das mit ccw hat mir sehr geholfen :)
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.