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

Oh je

Beitragvon spinneratz » Freitag 31. Oktober 2008, 18:27

:cry: Uffz das ist ja schwieriger als gedacht. Ehrlich gesagt komme ich bei Euch nicht mehr so ganz mit. Wenn ich das richtig vertehe gibt es jetzt zwei Ansätze:
den mit Arcus und den mit Minimum/Maximum.
Problem: ich verstehe jetzt ungefähr was Ihr meint (das ist ja schon mal gut) aber da ich erst seit zwei Tagen mit python zu tun habe, weiß ich nicht wie ich Eure Algorithem in Python code schreiben kann.
Also mal angenommen ich habe die Punktnummern und Koordinaten als Tupel jeweils in einer Liste. wie könnte ich das dann mit dem Arcus machen? Bzw. wie würde das dann mit Max gehen? Sorry das ich mich so blöd anstelle, aber python ist noch recht chinesisch für mich :roll:
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Beitragvon HWK » Freitag 31. Oktober 2008, 18:32

Lösungsvorschlag:

Code: Alles auswählen

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)

POINTS = [(1, 6), (2, 4), (1, 2)]
pos = get_pos(POINTS)
if pos < 0:
    print POINTS[0], POINTS[2], POINTS[1]
elif pos > 0:
    print POINTS[0], POINTS[1], POINTS[2]
else:
    print 'Kein Dreieck'
MfG
HWK

Edit: float ergänzt
Zuletzt geändert von HWK am Freitag 31. Oktober 2008, 19:04, insgesamt 1-mal geändert.
spinneratz
User
Beiträge: 23
Registriert: Freitag 31. Oktober 2008, 15:41

Hallo HWK

Beitragvon spinneratz » Freitag 31. Oktober 2008, 18:39

:lol: Cool HWK, ich werde es gleich mal ausprobieren!!!
:o
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Beitragvon HWK » Freitag 31. Oktober 2008, 18:46

Interessant wäre ja mal eine Lösung für beliebige Polygone.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 31. Oktober 2008, 18:50

Auch ein Lösungsvorschlag:

Code: Alles auswählen

from math import atan,pi

punkte = [(0,0), (4,3), (2.5,2)]
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]
for n,ch in enumerate("ABC"):
    print ch,punkte[n]
spinneratz
User
Beiträge: 23
Registriert: Freitag 31. Oktober 2008, 15:41

Frage

Beitragvon spinneratz » Freitag 31. Oktober 2008, 18:51

Noch eine Verständnisfrage:
Was macht die methode.sort() denn genau? Sortiert die nach dem ersten Eintrag im Tupel oder irgendwie nach beiden?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 31. Oktober 2008, 18:51

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


Grübel!
Benutzeravatar
Hyperion
Moderator
Beiträge: 7471
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Beitragvon Hyperion » Freitag 31. Oktober 2008, 19:11

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

Beitragvon HWK » Freitag 31. Oktober 2008, 19:22

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

Beitragvon ichbinsisyphos » Freitag 31. Oktober 2008, 22:12

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

Beitragvon HWK » Freitag 31. Oktober 2008, 22:33

Naja, den Umlaufsinn in 4 Zeilen so wie in der obigen Lösung (Funktion get_area) zu bestimmen, dürfte wohl schwierig werden.
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Beitragvon yipyip » Freitag 31. Oktober 2008, 22:42

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

:wink:
yipyip
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Beitragvon numerix » Freitag 31. Oktober 2008, 22:48

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

Beitragvon HWK » Freitag 31. Oktober 2008, 22:54

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

Beitragvon ichbinsisyphos » Freitag 31. Oktober 2008, 23:25

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.

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.

Wer ist online?

Mitglieder in diesem Forum: Yahoo [Bot]