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.
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 ccwhttp://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
n Eigenschaft
2
————————————————————————————————
3
0 konvex, negativer Drehsinn
4
1 konkav, negativer Drehsinn
5
2 verdrillt
6
3 konkav, positiver Drehsinn
7
4 konvex, positiver Drehsinn
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.
Eine eigene Frage?
Dieser Thread ist über 11 Jahre alt.
Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.
