Ahh, der meint wirklich den Umlaufsinn der verbindenden Geraden. Ich hab den thread 4mal lesen müssen ums zu glauben .
Dann ist mein Programm natürlich sinnlos. Man könnt den Ursprung zwischen die drei Punkte verschieben, dann gehts, wird aber zu mühsam.
Sortieren von Punkten gegen den Uhrzeigersinn
-
- User
- Beiträge: 120
- Registriert: Montag 4. Juni 2007, 19:19
Na gut, dann würd ich Differenzenvektoren bilden. Beliebigen Punkt wählen und wenn das Kreuzprodukt der nächsten beiden Differenzvektoren positiv ist, dann nächsten Punkt dazu zur sortierten Liste, sonst der andere zuerst, bei drei Punkten eh ned übermässig kompliziert.
Code: Alles auswählen
#!/usr/bin/env python
points = [(1, 4), (4, 9), (0, 8)]
vec1 = (points[1][0] - points[0][0], points[1][1] - points[0][1])
vec2 = (points[2][0] - points[1][0], points[2][1] - points[1][1])
vec3 = (points[0][0] - points[2][0], points[0][1] - points[2][1])
sorted = list()
sorted.append(points[0])
if vec1[0] * vec2[1] - vec1[1] * vec2[0] > 0:
sorted.append(points[1])
sorted.append(points[2])
else:
sorted.append(points[2])
sorted.append(points[1])
print sorted
Hab grad mal ausprobiert:numerix hat geschrieben:Zeig doch mal.ichbinsisyphos hat geschrieben:winkel zu jedem wertepaar berechnen und danach sortieren ist euch zu wenig elegant?
ich würd einfach atan(y/x), für jeden quadranten modifiziert, in eine neue liste schreiben und die abarbeiten.
Ich habe mir über einen Zugang über Winkel auch Gedanken gemacht und ich sehe noch nicht, dass das auf diese Weise (einfach) lösbar wäre.
Code: Alles auswählen
>>> def counterclockwise(points):
x0 = sum(p[0] for p in points) / float(len(points))
y0 = sum(p[1] for p in points) / float(len(points))
return sorted(points, key = lambda p: atan2(p[1] - y0, p[0] - x0))
>>> counterclockwise([(0, 0), (0, 1), (1, 0), (1, 1)])
[(0, 0), (1, 0), (1, 1), (0, 1)]
@ichbinsisyphos:
Dein Code hilft beim aktuellen Problem nicht weiter und er beschreitet ja auch nicht den Weg, auf den ich angesprochen hatte. Über die Orientierung eines Dreiecks sind wir in diesem Thread schon hinaus und es wurden mindestens zwei funktionierende Lösungen gepostet.
@bords0:
Das nenne ich mal eine geniale Idee!
Ich hatte mich daran festgebissen, jeweils die Winkel zwischen benachbarten Strecken zu berücksichtigen und das scheint mir nach wie vor nicht so einfach lösbar zu sein. Deine Idee mit dem Schwerpunkt ist prima. Das müsste eigentlich für alle konvexen Polygone funktionieren. Für nichtkonvexe leider nicht.
Dein Code hilft beim aktuellen Problem nicht weiter und er beschreitet ja auch nicht den Weg, auf den ich angesprochen hatte. Über die Orientierung eines Dreiecks sind wir in diesem Thread schon hinaus und es wurden mindestens zwei funktionierende Lösungen gepostet.
@bords0:
Das nenne ich mal eine geniale Idee!
Ich hatte mich daran festgebissen, jeweils die Winkel zwischen benachbarten Strecken zu berücksichtigen und das scheint mir nach wie vor nicht so einfach lösbar zu sein. Deine Idee mit dem Schwerpunkt ist prima. Das müsste eigentlich für alle konvexen Polygone funktionieren. Für nichtkonvexe leider nicht.
-
- User
- Beiträge: 23
- Registriert: Freitag 31. Oktober 2008, 15:41
Hallo,
also ersteinmal nochmal Danke für Eure Lösungen.
Ich habe jetzt mit den drei Varianten einmal rumgespielt und die Variante von bords0 ist (nach dem was ich jetzt gesehen habe) auch bei Dreiecken die schnellste.
also ersteinmal nochmal Danke für Eure Lösungen.
Ich habe jetzt mit den drei Varianten einmal rumgespielt und die Variante von bords0 ist (nach dem was ich jetzt gesehen habe) auch bei Dreiecken die schnellste.
Das täuscht. Zum einen habe ich fünf unterschiedliche Methoden gefunden, zum anderen bewegen sich deren Geschwindigkeitsunterschiede im Bereich von Mikrosekunden. Selbst wenn dies signifikant wäre, wäre es praktisch sicher bedeutungslos.
Hier mein Test-Script:Hier das Ergebnis:@numerix: Übrigens muss in
auch noch der ZeroDivisionError abgefangen werden.
MfG
HWK
Hier mein Test-Script:
Code: Alles auswählen
from itertools import izip
from math import atan, atan2, pi
from random import randint
from time import clock
def counterclockwise1(points):
a = 0
for (x1, y1), (x2, y2) in izip(points, points[1:] + [points[0]]):
a += x1 * y2 - x2 * y1
if a < 0:
points.reverse()
return points
def get_pos(points):
points.sort()
p1, p2, p3 = points
if p2[0] == p1[0]:
if p2[1] == p1[1]:
return 0
return cmp(p1[0], p3[0])
m = (p2[1] - p1[1]) / float(p2[0] - p1[0])
b = p1[1] - m * p1[0]
return cmp(p3[1], m * p3[0] + b)
def counterclockwise2(points):
if get_pos(points) < 0:
points.reverse()
return points
def counterclockwise3(punkte):
punkte.sort()
a, c, b = punkte
w1 = atan((b[1] - a[1]) / float((b[0] - a[0])))
try:
w2 = atan((c[1] - a[1]) / float((c[0] - a[0])))
except ZeroDivisionError:
w2 = pi / 2
if w2 - w1 > 0:
punkte[1], punkte[2] = punkte[2], punkte[1]
return punkte
def counterclockwise4(points):
x0 = sum(p[0] for p in points) / float(len(points))
y0 = sum(p[1] for p in points) / float(len(points))
return sorted(points, key = lambda p: atan2(p[1] - y0, p[0] - x0))
def counterclockwise5(points):
vec1 = (points[1][0] - points[0][0], points[1][1] - points[0][1])
vec2 = (points[2][0] - points[1][0], points[2][1] - points[1][1])
vec3 = (points[0][0] - points[2][0], points[0][1] - points[2][1])
sorted = list()
sorted.append(points[0])
if vec1[0] * vec2[1] - vec1[1] * vec2[0] > 0:
sorted.append(points[1])
sorted.append(points[2])
else:
sorted.append(points[2])
sorted.append(points[1])
return sorted
if __name__ == '__main__':
time_list = 5 * [0]
for i in xrange(100):
points = [(randint(-10, 10), randint(-10, 10)) for _ in xrange(3)]
#print points
for i, f in enumerate((counterclockwise1, counterclockwise2,
counterclockwise3, counterclockwise4,
counterclockwise5)):
t0 = clock()
#print f(points),
t1 = clock()
t = t1 - t0
time_list[i] += t
#print t
print time_list
Code: Alles auswählen
0.00023215241043205088
0.00023159368020236903
0.00023271114066172917
0.00022880002905396814
0.00023047621974300913
Code: Alles auswählen
w1 = atan((b[1]-a[1])/float((b[0]-a[0])))
MfG
HWK
Das habe ich absichtlich nicht gemacht, weil in diesem Fall alle drei Punkte auf einer senkrechten Geraden liegen und somit gar kein Dreieck entsteht. Das wollte ich dann mit einer Exception quittieren ...HWK hat geschrieben:@numerix: Übrigens muss inauch noch der ZeroDivisionError abgefangen werden.Code: Alles auswählen
w1 = atan((b[1]-a[1])/float((b[0]-a[0])))
Das leuchtet ein.
Und Du wolltest deshalb bestimmt noch eineinfügen.
MfG
HWK
Und Du wolltest deshalb bestimmt noch ein
Code: Alles auswählen
if abs(w2 - w1) < 0.000001:
raise ValueError, 'not a triangle but a line'
MfG
HWK
Eine Messung mit auskommentierter Berechnung (Zeile 70) scheint mir wenig aussagekräftigHWK hat geschrieben:Das täuscht. Zum einen habe ich fünf unterschiedliche Methoden gefunden, zum anderen bewegen sich deren Geschwindigkeitsunterschiede im Bereich von Mikrosekunden.
Stimmt!
Meine Tests hatte ich zwar ohne Kommentare durchgeführt, habe sie dann aber eingefügt, um die Ausgabe nicht unnötig aufzublähen.
Hier sind jetzt die Ergebnisse mit ausgeführtem f(points):Dabei schneidet die für spinneratz subjektiv am schnellsten erscheinende Lösung leider am schlechtesten ab, wobei wohl selbst die 1 ms nicht ins Gewicht fällt.
MfG
HWK
Meine Tests hatte ich zwar ohne Kommentare durchgeführt, habe sie dann aber eingefügt, um die Ausgabe nicht unnötig aufzublähen.
Hier sind jetzt die Ergebnisse mit ausgeführtem f(points):
Code: Alles auswählen
0.000812
0.000771
0.000798
0.001868
0.000790
MfG
HWK
-
- User
- Beiträge: 1
- Registriert: Samstag 2. März 2019, 09:18
Man braucht hierfür keine Winkelfunktionen, es geht auch einfacher.
Punkt A hat die Koordinaten (x_a, y_a), Punkt B (x_B, y_B) und Punkt C (x_C, y_C).
Dann kann man von A ausgehend die Vektoren AB = B-A und AC = C-A berechnen.
Diese haben die Koordinaten x_AB = x_B - x_A, y_AB = y_B - y_A, x_AC = x_C - x_A und y_AC = y_C - y_A.
Nun bildet man das Vektorprodukt von AB und AC. Da das Dreieck in einer Ebene liegt, hat das Vektorprodukt nur eine z-Komponente.
Diese berechnet sich zu
V_z = x_AB * y_AC - y_AB * x_AC oder ausgeschrieben:
V_z = (x_B - x_A)*(y_C - y_A) - (y_B - y_A)*(x_C - x_A).
"Im Uhrzeigersinn" und "gegen Uhrzeigersinn" kann man nun am Vorzeichen von V_z unterscheiden:
Positives Vorzeichen, V_z > 0: Die Punkte (A, B, C) werden im UZS durchlaufen.
Negatives Vorzeichen, V_z < 0: Die Punkte (A, B, C) werden gegen den Uhrzeigersinn durchlaufen.
V_z = 0: Die Punkte liegen auf einer Linie (oder sind sogar identisch): Richtung nicht eindeutig.
Die Methode kommt mit zwei Multiplikationen und 5 Subtraktionen aus und dürfte im Vergleich am schnellsten sein. Es gibt nur eine Fallunterscheidung ganz am Ende.
Die Rückmeldung kommt etwas spät, habe die Frage heute erst gelesen.
Vielleicht hilft es aber trotzdem noch irgendwo.
Punkt A hat die Koordinaten (x_a, y_a), Punkt B (x_B, y_B) und Punkt C (x_C, y_C).
Dann kann man von A ausgehend die Vektoren AB = B-A und AC = C-A berechnen.
Diese haben die Koordinaten x_AB = x_B - x_A, y_AB = y_B - y_A, x_AC = x_C - x_A und y_AC = y_C - y_A.
Nun bildet man das Vektorprodukt von AB und AC. Da das Dreieck in einer Ebene liegt, hat das Vektorprodukt nur eine z-Komponente.
Diese berechnet sich zu
V_z = x_AB * y_AC - y_AB * x_AC oder ausgeschrieben:
V_z = (x_B - x_A)*(y_C - y_A) - (y_B - y_A)*(x_C - x_A).
"Im Uhrzeigersinn" und "gegen Uhrzeigersinn" kann man nun am Vorzeichen von V_z unterscheiden:
Positives Vorzeichen, V_z > 0: Die Punkte (A, B, C) werden im UZS durchlaufen.
Negatives Vorzeichen, V_z < 0: Die Punkte (A, B, C) werden gegen den Uhrzeigersinn durchlaufen.
V_z = 0: Die Punkte liegen auf einer Linie (oder sind sogar identisch): Richtung nicht eindeutig.
Die Methode kommt mit zwei Multiplikationen und 5 Subtraktionen aus und dürfte im Vergleich am schnellsten sein. Es gibt nur eine Fallunterscheidung ganz am Ende.
Die Rückmeldung kommt etwas spät, habe die Frage heute erst gelesen.
Vielleicht hilft es aber trotzdem noch irgendwo.