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

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! :?
.robert
User
Beiträge: 274
Registriert: Mittwoch 25. April 2007, 17:59

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.
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

spinneratz hat geschrieben:[...]eines Dreieckes[...]
Es gibt keinerlei Einschränkungen, wie rechtwinkliges Dreieck?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

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

Code: Alles auswählen

eckpunkte = [(2.2,5.5), (3.2,7.3), (3.2, 1.5)] 
Das ist alles.
spinneratz
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!
.robert
User
Beiträge: 274
Registriert: Mittwoch 25. April 2007, 17:59

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

Liegt C oberhalb der Linie durch A und B, ist ABC gegen den Uhrzeigersinn. Liegt C unterhalb der Linie, dann ist ACB gegen den Uhrzeigersinn.
MfG
HWK
Benutzeravatar
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 ;-)
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Hyperion hat geschrieben:Edit: Gibt es denn einen eleganten Weg das "oberhalb" rauszufinden?

Code: Alles auswählen

max([point[1] for point in points])
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

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])
Ähem ... ja ok. Und? Inwiefern soll das das Problem lösen?

Ich gebe Dir ein Beispiel:

Code: Alles auswählen

# (x, y)
points = ((0, 0), (2, 2), (0, 1))
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Ah, okay, ich hatte die Aufgabe wohl missverstanden. :cry:

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.
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

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

: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

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

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

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

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]
Antworten