Das deutsche Python-Forum

Noch eine Verständnisfrage:
Was macht die methode.sort() denn genau? Sortiert die nach dem ersten Eintrag im Tupel oder irgendwie nach beiden?

HWK hat geschrieben:Interessant wäre ja mal eine Lösung für beliebige Polygone.

Grübel!

DasIch hat geschrieben:
Hyperion hat geschrieben:Ähem ... ja ok. Und? Inwiefern soll das das Problem lösen?
Der Punkt bei dem Y den höchsten Wert hat muss natürlich am höchsten sein. Das sollte nur dass prinzip verdeutlichen.

Das hilft ja aber nicht bei dem von HWK iniziierten problem weiter

@numerix: Bei Deinem Beispiel klappt doch alles. Der Punkt D liegt unterhalb von AB und deshalb tauscht man B und D!

Ich habe diesen interessanten Artikel gefunden. Damit habe ich eine Lösung geschrieben, die hoffentlich auch für beliebige Polygone funktioniert. Sie liefert zumindest bei Dreiecken dieselbe Lösung wie die erste Methode.

Code: Alles auswählen

from itertools import izip
from random import randint

def get_pos(points):
    '''< 0  - im Uhrzeigersinn
       > 0  - gegen den Uhrzeigersinn
       == 0 - kein Dreieck
    '''
    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 get_area(points):
    a = 0
    for (x1, y1), (x2, y2) in izip(points, points[1:] + [points[0]]):
        a += x1 * y2 - x2 * y1
    return cmp(a, 0)

for i in xrange(20):
    points = [(randint(-10, 10), randint(-10, 10)) for _ in xrange(3)]
    pos = get_pos(points)
    area = get_area(points)
    print pos, area
    if pos < 0:
        print points[0], points[2], points[1]
    elif pos > 0:
        print points[0], points[1], points[2]
    else:
        print 'Kein Dreieck'

for i in xrange(20):
    points = [(randint(-10, 10), randint(-10, 10))
              for _ in xrange(randint(3, 6))]
    area = get_area(points)
    if area < 0:
        points.reverse()
    print points
    if area == 0:
        print 'Kein Umlaufsinn'

MfG
HWK

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.

Naja, den Umlaufsinn in 4 Zeilen so wie in der obigen Lösung (Funktion get_area) zu bestimmen, dürfte wohl schwierig werden.

Das Kreuzprodukt hilft bei Orientierungsproblemen.

Wenn ich nicht vollkommen auf dem falschen Gleis bin:

Code: Alles auswählen

#! /usr/bin/env python

####

def center(u, v, w):
  '''berechnet das Zentrum des Dreiecks
  '''
  u1, u2 = u
  v1, v2 = v
  w1, w2 = w

  return (u1+v1+w1) / 3.0, (u2+v2+w2) / 3.0

####

def cross2(v, w):
  ''' 2-dimensionales Kreuzprodukt degeneriert zum Skalar
  '''
  v1, v2 = v
  w1, w2 = w

  return v2*w1 - v1*w2

####

def sub_vec(v, w):
  ''' Vektor Subtraktion (2-dim.)
  '''
  v1, v2 = v
  w1, w2 = w

  return v1 - w1, v2 - w2

####

def is_clockwise(u, v, w):
  ''' Da es nur ein Dreieck ist, braucht man nur
      2 beliebige, aufeinanderfolgnde Punkte eines
      Dreiecks mit Zentrum im Ursprung zu betrachten.
  '''
  c = center(u, v, w)
  return cross2(sub_vec(u, c), sub_vec(v, c)) > 0

###

def test_triangles():

  p1 = (10, 10)
  p2 = (30, 0)
  p3 = (20, -10)

  clockwise = ((p1, p2, p3), (p2, p3, p1), (p3, p1, p2))
  anti_clockwise = ((p3, p2, p1), (p2, p1, p3), (p1, p3, p2))
  
  print [is_clockwise(*p) for p in clockwise]
  print [is_clockwise(*p) for p in anti_clockwise]

####

if __name__ == '__main__':

  test_triangles()

###

Ist 'is_clockwise()' falsch für ein zu untersuchendes Tripel,
vertauscht man einfach 2 Punkte (wie bei HWK).

yipyip

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.

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.

Das Prinzip ist ja dasselbe wie bei der vorzeichenbehafteten Fläche, nämlich das Kreuzprodukt, nur unnötig kompliziert. Mein letzter Vorschlag mit einem Test für 20 Polygone mit 3 bis 6 Ecken auf das wesentliche beschränkt:

Code: Alles auswählen

from itertools import izip
from random import randint
import Tkinter as tk

def get_area(points):
    '''< 0  - im Uhrzeigersinn
       > 0  - gegen den Uhrzeigersinn
       == 0 - kein Dreieck
    '''
    a = 0
    for (x1, y1), (x2, y2) in izip(points, points[1:] + [points[0]]):
        a += x1 * y2 - x2 * y1
    return cmp(a, 0)

def main():
    for i in xrange(20):
        points = [(randint(-10, 10), randint(-10, 10))
                  for _ in xrange(randint(3, 6))]
        root = tk.Tk()
        root.title('Umlaufsinn von Polygonen')
        canvas = tk.Canvas(root, width=200, height=200, bg='white')
        canvas.pack(expand=tk.YES, fill=tk.BOTH)
        canvas.create_line(fill='black', arrow='last',
                           *((100 + 10 * x, 100 - 10 * y)
                             for x, y in points + [points[0]]))
        area = get_area(points)
        if area < 0:
            points.reverse()
        print (('Uhrzeigersinn', 'Kein Umlaufsinn', 'Gegenuhrzeigersinn')
               [area + 1])
        print points
        root.mainloop()

if __name__ == '__main__':
    main()

MfG
HWK

Edit: Mit graphischer Kontrolle

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.

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

#!/usr/bin/env python

import math

points = [(1.,3.),(0.,0.),(7.,-1.)]

def quadmod(point):
        if point[0] < 0:
                return 180
        else:
                if point[1] < 0:
                        return 360
                else:
                        return 0

def achsentest(point):
        if point[0] == 0:
                if point[1] < 0:
                        return 270
                else:
                        return 90
        if point[1] == 0:
                if point[0] < 0:
                        return 180
                else:
                        return 0

winkel = list()

for i in points:
        if i[0] == 0 and i[1] == 0:
                winkel.append(0) #Punkt im Koordinatenursprung
        elif i[0] == 0 or i[1] == 0: #Punkt auf irgendeiner Achse
                winkel.append(achsentest(i))
        else:
                winkel.append( math.degrees(math.atan(i[1]/i[0])) + quadmod(i) )

winkelsort = list()

for i in winkel:
        winkelsort.append(i)

winkelsort.sort()

for i in range(0,len(points)):
        print points[winkel.index(winkelsort[i])]

Naja, so schön ist das auch wieder nicht

. Funktionieren sollts aber.

edit: Ich seh grad, der Ursprung macht Probleme. Wenn ich einen Punkt einfüge für den der Winkel wirklich 0 ist, z.B. (1,0), dann wird am Schluß zweimal der Ursprung ausgegeben.

Man könnte (0,0) einen negativen Winkel zuordnen, dann kommt er vor allen anderen, oder einen von 360 oder darüber, dann kommt er nach allen anderen. Vielleicht kann man den Punkt überhaupt ausschliessen.
Ausserdem kann man sicher auch intelligenter sortieren so dass das Problem nicht auftaucht.

edit edit: Es gibt überhaupt ein Problem wenn zwei Winkel gleich sind, dann wird der erste passende Werte doppelt ausgegeben. Beim Sortieren kenn ich mich nicht übermässig aus.

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.

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

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.

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.

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.

@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.

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.

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

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 ...

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.

MfG
HWK

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.

Das deutsche Python-Forum

Sortieren von Punkten gegen den Uhrzeigersinn

Frage

Tests