Hallo,
bin noch anfänger im Programmieren.
Hoffe mir kann jemand helfen:
Ich habe X und Y Koordinaten von drei Punkten eines Dreieckes.
Nun soll eine Liste der Punkte erstellt werden und zwar so dass sie hintereinander in der Reihenfolge gegen den Uhrzeigersinn aufgelistet werden.
Also folgendes Beispiel:
Dreieck 1 besteht aus Punkt 1 mit X = 2,2 und Y = 5,5
Punkt 2 mit X = 3,2 und Y = 7,3
Punkt 3 mit X = 3,2 und Y = 1,5
Dann sollte die richtige Reihenfolge der Punkte gegen den Uhrzeigersinn sein also z.B.:
3 2 1 oder 2 1 3 oder 1 3 2
Weiß jemand wie man das in Python machen kann? Hab schon irgendwas mit Quicksort überlegt, aber ich komme irgendwie auf keine Lösung.
Bitte helft mir!
Sortieren von Punkten gegen den Uhrzeigersinn
Hi,
als erste Idee würde ich versuchen, heraus zu finden, wie jeweils zwei der Punkte zueinander stehen (Rechts/Links/Oben/Unten), und die dann per Fallunterscheidung danach anordnen.
Du hast ja immer Punkt A als Startpunkt, und dann zum Beispiel folgendes Szenario:
- B ist Linksunten zu A,
- C ist Linksoben zu A,
damit kann man jetzt schon sagen das die Reihenfolge gegen den Uhrzeigersinn A C B seien wird.
Mal dir am besten mal alle Fälle auf.
als erste Idee würde ich versuchen, heraus zu finden, wie jeweils zwei der Punkte zueinander stehen (Rechts/Links/Oben/Unten), und die dann per Fallunterscheidung danach anordnen.
Du hast ja immer Punkt A als Startpunkt, und dann zum Beispiel folgendes Szenario:
- B ist Linksunten zu A,
- C ist Linksoben zu A,
damit kann man jetzt schon sagen das die Reihenfolge gegen den Uhrzeigersinn A C B seien wird.
Mal dir am besten mal alle Fälle auf.
Ich weiß gar nicht, wo hier das Problem ist: Die Reihenfolge der Punkte eines Dreiecks ist allein dadurch festgelegt, dass man das Dreieck in spezieller Weise bezeichnet, und zwar durch Angabe der Eckpunkte, die dann gegen den Uhrzeigersinn durchlaufen werden. Mit der konkreten Lage der Punkte in der Ebene hat das nichts zu tun.
Lösung also z.B.:
Das ist alles.
Lösung also z.B.:
Code: Alles auswählen
eckpunkte = [(2.2,5.5), (3.2,7.3), (3.2, 1.5)]
-
- User
- Beiträge: 23
- Registriert: Freitag 31. Oktober 2008, 15:41
Hallo,
bin ja neu hier und begeistert wie schnell man hier eine Antwort bekommt.
Also die Dreicken haben keine Einschränkung.
Leider bin ich eben ganz neu mit Python und kann ohne Beispiele wenig anfangen. Man müsste sich wohl irgendwie einen Punkt als Startpunkt nehmen und dann die anderen X und Y Koordinaten irgendwie vergleichen.
Aber wie man das umsetzt dazu fehlt mir leider noch die Erfahrung in Python.
Vielen Dank schoneinmal!
bin ja neu hier und begeistert wie schnell man hier eine Antwort bekommt.
Also die Dreicken haben keine Einschränkung.
Leider bin ich eben ganz neu mit Python und kann ohne Beispiele wenig anfangen. Man müsste sich wohl irgendwie einen Punkt als Startpunkt nehmen und dann die anderen X und Y Koordinaten irgendwie vergleichen.
Aber wie man das umsetzt dazu fehlt mir leider noch die Erfahrung in Python.
Vielen Dank schoneinmal!
@numerix:
das verstehe ich jetzt grade nicht. Ich habe drei Punkte gegeben, A=(xa,ya), B=(xb,yb), C=(xc,yc). Wie willst du jetzt ohne die spezielle Lage in der Ebene rausfinden, wie die Anordnung aussieht?
Wobei es natürlich noch wichtig wäre zu wissen ob der Uhrzeiger im Nullpunkt oder im Mittelpunkt des Dreiecks verankert ist.
das verstehe ich jetzt grade nicht. Ich habe drei Punkte gegeben, A=(xa,ya), B=(xb,yb), C=(xc,yc). Wie willst du jetzt ohne die spezielle Lage in der Ebene rausfinden, wie die Anordnung aussieht?
Wobei es natürlich noch wichtig wäre zu wissen ob der Uhrzeiger im Nullpunkt oder im Mittelpunkt des Dreiecks verankert ist.
-
- User
- Beiträge: 23
- Registriert: Freitag 31. Oktober 2008, 15:41
Wenn man einen Punkt als Startpunkt nimmt, kann man ja die anderen Punkte mit ihren X und Y Koordinaten untereinander Vergleichen und bei Richtung gegen den Uhrzeigersinn muss irgendwie das so gehen wie: Wenn Xp1 >= Xp2 und/oder Yp2 <Yp1 ..... dann vertausche Reihenfolge.... genau weiß ich eben auch nicht wei das aussehen muss.
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
Also ich würde mal behaupten es läuft folgendermaßen:
- Suche Dir den Punkt mit der kleinsten x-Koordinate
- gibt es 2 davon, wähle den mit der kleinsten y-Koordinate
- Gehe zunächst zu dem Punkt mit der größten x-Koordinate
- sind diese von den verbleibenden Punkten gleich, wähle den mit der kleineren y-Koordinate
- Gehe von dort aus zum letzten Punkt.
Ich denke je nach Wahl des ersten Kriteriums sind die Regeln dann entsprechend, man kann also auch mit der größten x-Koordinate anfangen und dann bei den folgenden Entscheidungen die Regeln entsprechend umbauen.
Aber so sollte es gehen - zumindest habe ich hier auf dem Papier kein Beispiel konstruieren können, bei dem das nicht geklappt hätte.
- Suche Dir den Punkt mit der kleinsten x-Koordinate
- gibt es 2 davon, wähle den mit der kleinsten y-Koordinate
- Gehe zunächst zu dem Punkt mit der größten x-Koordinate
- sind diese von den verbleibenden Punkten gleich, wähle den mit der kleineren y-Koordinate
- Gehe von dort aus zum letzten Punkt.
Ich denke je nach Wahl des ersten Kriteriums sind die Regeln dann entsprechend, man kann also auch mit der größten x-Koordinate anfangen und dann bei den folgenden Entscheidungen die Regeln entsprechend umbauen.
Aber so sollte es gehen - zumindest habe ich hier auf dem Papier kein Beispiel konstruieren können, bei dem das nicht geklappt hätte.
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
Und was ist oberhalb und was unterhalb? Vergiss nicht sie Spezialfälle, bei denen es um "rechts" und "links" gehen könnte
Also sollte man noch als Bedingung einführen, dass man nur Punkte als "A" und "B" benennt, die sich in beiden Koordinatenwerten unterscheiden, dann tritt das Problem natürlich nicht auf.
Edit: Gibt es denn einen eleganten Weg das "oberhalb" rauszufinden? Mir fiele da spontan nur das Berechnen des Funktionswertes von der x-Koordinate von C durch die aufgestellte Geradengleichung. Kommt mir nur nicht wirklich elegant vor
Also sollte man noch als Bedingung einführen, dass man nur Punkte als "A" und "B" benennt, die sich in beiden Koordinatenwerten unterscheiden, dann tritt das Problem natürlich nicht auf.
Edit: Gibt es denn einen eleganten Weg das "oberhalb" rauszufinden? Mir fiele da spontan nur das Berechnen des Funktionswertes von der x-Koordinate von C durch die aufgestellte Geradengleichung. Kommt mir nur nicht wirklich elegant vor
Hyperion hat geschrieben:Edit: Gibt es denn einen eleganten Weg das "oberhalb" rauszufinden?
Code: Alles auswählen
max([point[1] for point in points])
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
Ähem ... ja ok. Und? Inwiefern soll das das Problem lösen?DasIch hat geschrieben:Hyperion hat geschrieben:Edit: Gibt es denn einen eleganten Weg das "oberhalb" rauszufinden?Code: Alles auswählen
max([point[1] for point in points])
Ich gebe Dir ein Beispiel:
Code: Alles auswählen
# (x, y)
points = ((0, 0), (2, 2), (0, 1))
Ah, okay, ich hatte die Aufgabe wohl missverstanden.
Dann könnte man es so machen:
Annahme: A ist der Punkt mit dem kleinsten x-Wert, B der Punkt mit dem größten x-Wert. Dann berechnet man z.B. mittels arctan() den Winkel zwischen Strecke AB und Strecke AC, wobei arctan(m_AC)-arctan(m_AB) zu rechnen ist. Ist dieser positiv, war die Annahme korrekt und der übrige Punkt ist C. Ist der Winkel negativ, war die Annahme falsch, der übrige Punkt ist B und C ist das frühere B.
Edit: Den Fall, dass eine Strecke dabei parallel zur y-Achse verläuft muss natürlich als Sonderfall behandeln, weil arctan() dann versagt. Ist aber kein Problem an sich.
Dann könnte man es so machen:
Annahme: A ist der Punkt mit dem kleinsten x-Wert, B der Punkt mit dem größten x-Wert. Dann berechnet man z.B. mittels arctan() den Winkel zwischen Strecke AB und Strecke AC, wobei arctan(m_AC)-arctan(m_AB) zu rechnen ist. Ist dieser positiv, war die Annahme korrekt und der übrige Punkt ist C. Ist der Winkel negativ, war die Annahme falsch, der übrige Punkt ist B und C ist das frühere B.
Edit: Den Fall, dass eine Strecke dabei parallel zur y-Achse verläuft muss natürlich als Sonderfall behandeln, weil arctan() dann versagt. Ist aber kein Problem an sich.
Zuletzt geändert von numerix am Freitag 31. Oktober 2008, 18:07, insgesamt 1-mal geändert.
So wie ich das sehe, hilft das Vergleichen von x und y Werten und das Heraussuchen des "Größten" etc. nicht wirklich weiter.
Beispiel: A(0|0), B(4|3), C(2,5|2) und D(3|2)
Dabei ist ABC korrekt orientiert, ABD hingegen nicht.
Beispiel: A(0|0), B(4|3), C(2,5|2) und D(3|2)
Dabei ist ABC korrekt orientiert, ABD hingegen nicht.
-
- User
- Beiträge: 23
- Registriert: Freitag 31. Oktober 2008, 15:41
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
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
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]