Das deutsche Python-Forum

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!

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.

spinneratz hat geschrieben:[...]eines Dreieckes[...]

Es gibt keinerlei Einschränkungen, wie rechtwinkliges Dreieck?

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.

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!

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

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.

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.

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

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

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

Code: Alles auswählen

max([point[1] for point in points])

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

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.

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.

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.

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

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

Cool HWK, ich werde es gleich mal ausprobieren!!!

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

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]

Das deutsche Python-Forum

Sortieren von Punkten gegen den Uhrzeigersinn

Sortieren von Punkten gegen den Uhrzeigersinn

Re: Sortieren von Punkten gegen den Uhrzeigersinn

Danke erteinmal

Vergleichen

Oh je

Hallo HWK