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
Sortieren von Punkten gegen den Uhrzeigersinn
Lösungsvorschlag:MfG
HWK
Edit: float ergänzt
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'
HWK
Edit: float ergänzt
Zuletzt geändert von HWK am Freitag 31. Oktober 2008, 19:04, insgesamt 1-mal geändert.
-
- User
- Beiträge: 23
- Registriert: Freitag 31. Oktober 2008, 15:41
Cool HWK, ich werde es gleich mal ausprobieren!!!
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]
-
- User
- Beiträge: 23
- Registriert: Freitag 31. Oktober 2008, 15:41
Noch eine Verständnisfrage:
Was macht die methode.sort() denn genau? Sortiert die nach dem ersten Eintrag im Tupel oder irgendwie nach beiden?
Was macht die methode.sort() denn genau? Sortiert die nach dem ersten Eintrag im Tupel oder irgendwie nach beiden?
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
Das hilft ja aber nicht bei dem von HWK iniziierten problem weiterDasIch hat geschrieben:Der Punkt bei dem Y den höchsten Wert hat muss natürlich am höchsten sein. Das sollte nur dass prinzip verdeutlichen.Hyperion hat geschrieben:Ähem ... ja ok. Und? Inwiefern soll das das Problem lösen?
@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.MfG
HWK
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'
HWK
-
- User
- Beiträge: 120
- Registriert: Montag 4. Juni 2007, 19:19
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 würd einfach atan(y/x), für jeden quadranten modifiziert, in eine neue liste schreiben und die abarbeiten.
Das Kreuzprodukt hilft bei Orientierungsproblemen.
Wenn ich nicht vollkommen auf dem falschen Gleis bin:
Ist 'is_clockwise()' falsch für ein zu untersuchendes Tripel,
vertauscht man einfach 2 Punkte (wie bei HWK).
yipyip
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()
###
vertauscht man einfach 2 Punkte (wie bei HWK).
yipyip
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.
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:MfG
HWK
Edit: Mit graphischer Kontrolle
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()
HWK
Edit: Mit graphischer Kontrolle
-
- User
- Beiträge: 120
- Registriert: Montag 4. Juni 2007, 19:19
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
#!/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])]
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.
-
- User
- Beiträge: 120
- Registriert: Montag 4. Juni 2007, 19:19
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.
Dann ist mein Programm natürlich sinnlos. Man könnt den Ursprung zwischen die drei Punkte verschieben, dann gehts, wird aber zu mühsam.
-
- 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.