Sortieren von Punkten gegen den Uhrzeigersinn

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
ichbinsisyphos
User
Beiträge: 120
Registriert: Montag 4. Juni 2007, 19:19

Samstag 1. November 2008, 02:03

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.
ichbinsisyphos
User
Beiträge: 120
Registriert: Montag 4. Juni 2007, 19:19

Samstag 1. November 2008, 02:38

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
bords0
User
Beiträge: 172
Registriert: Mittwoch 4. Juli 2007, 20:40

Samstag 1. November 2008, 14:37

numerix hat geschrieben:
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.
Zeig doch mal. :wink:

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.
Hab grad mal ausprobiert:

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)]
Verbindet man die Punkte in dieser Reihenfolge, müsste man ein Polygon erhalten, das sternförmig bzgl. des Schwerpunkts der gegeben Punkte ist.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Samstag 1. November 2008, 15:37

Wenn du mit Vektoren arbeiten willst, kannst du doch eine Vektor Klasse definieren. Ist sicher besser als das Integer Geschmeisse. Wenn du willst, könnte ich meine eigene Vektorklasse, die ich aktuell benutze, posten.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Samstag 1. November 2008, 15:41

@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.
spinneratz
User
Beiträge: 23
Registriert: Freitag 31. Oktober 2008, 15:41

Montag 3. November 2008, 10:12

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.
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Montag 3. November 2008, 11:19

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:

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
Hier das Ergebnis:

Code: Alles auswählen

0.00023215241043205088
0.00023159368020236903
0.00023271114066172917
0.00022880002905396814
0.00023047621974300913
@numerix: Übrigens muss in

Code: Alles auswählen

w1 = atan((b[1]-a[1])/float((b[0]-a[0])))
auch noch der ZeroDivisionError abgefangen werden.
MfG
HWK
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Montag 3. November 2008, 11:32

HWK hat geschrieben:@numerix: Übrigens muss in

Code: Alles auswählen

w1 = atan((b[1]-a[1])/float((b[0]-a[0])))
auch noch der ZeroDivisionError abgefangen werden.
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 ... :wink:
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Montag 3. November 2008, 11:40

Das leuchtet ein. :)
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'
einfügen. :wink:
MfG
HWK
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Montag 3. November 2008, 15:31

Das hatte ich mir noch aufgehoben für den Fall, dass der Aspekt "Gibt es überhaupt ein solches Dreieck ..." noch thematisiert würde. Aber das hast du ja jetzt erledigt. :)
bords0
User
Beiträge: 172
Registriert: Mittwoch 4. Juli 2007, 20:40

Dienstag 4. November 2008, 21:14

HWK hat geschrieben:Das täuscht. Zum einen habe ich fünf unterschiedliche Methoden gefunden, zum anderen bewegen sich deren Geschwindigkeitsunterschiede im Bereich von Mikrosekunden.
Eine Messung mit auskommentierter Berechnung (Zeile 70) scheint mir wenig aussagekräftig :?
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Mittwoch 5. November 2008, 11:26

Stimmt! :oops:
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
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
Antworten