Punkte eines Vierecks ordnen

[Samuel C. (dragonsam)]

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

[B. S. (bestucki)]

Ich würde aus jeweils zwei Punkten Geraden bilden und den Schnittpunkt 
berechnen. Liegt dieser zwischen den jeweiligen Punkten, schneiden sich 
die Linien.

[Johann L. (gjlayde)]

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.

[Samuel C. (dragonsam)]

Zwei gute Vorschläge, leider muss ich mit Ganzzahlen auskommen, was 
leider beides ausschließt.

[Johann L. (gjlayde)]

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.

[Detlef K. (adenin)]

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.

[Yalu X. (yalu) (Moderator)]

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:

 n   Eigenschaft
————————————————————————————————
 0   konvex, negativer Drehsinn
 1   konkav, negativer Drehsinn
 2   verdrillt
 3   konkav, positiver Drehsinn
 4   konvex, positiver Drehsinn
————————————————————————————————

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.

[Samuel C. (dragonsam)]

Ok, vielen Dank. Das mit ccw hat mir sehr geholfen :)