Koordinaten von Orten und deren Beziehungen

[N3WB]

N'Abend allerseits

Ich bin aktuell dabei ein Problem mit Python zu lösen und muss dazu zunächst mal die Abstände von Häusern zu anderen Häusern berechnen.
Insgesamt habe ich 70 verschiedene Häuser.

Aktuell habe ich die Koordinaten in einer Liste vorliegen, die ungefähr dieser Form entspricht (Allerdings natürlich mit 70 Einträgen).
Die erste Koordinaten von Haus 1 wären Beispielsweise: x=1, y=4.

[ (3,4), (5,6), (13,2), (14,8)]

Ich bin noch nicht so sicher in Python und bin mir ein bisschen unschlüssig, wie ich vorgehen soll. Welchen Datentyp würdet ihr mir empfehlen, um mit den Entfernungsdaten arbeiten zu können?


Aktuell habe ich ein kleines Programmchen, dass meine Häuserliste durchgeht und den Abstand von Haus 1 zu allen anderen Häusern berechnet und die Abstände in einer Liste speichert.
Das Programm habe ich mir so vorgestellt:

- berechne Abstände von Haus 1 zu allen anderen Häusern -> speichere Ergebnis in Liste 1
- berechne Abstände von Haus 2 zu allen anderen Häusern -> speichere Ergebnis in Liste 1
- usw.

Allerdings schaffe ich es nicht Listen automatisch zu erstellen.

Wäre sehr dankbar für ein paar Tipps.

[DeaD_EyE]

Die Funktion math.dist berechnet die Distanz zwischen zwei Punkten (mit beliebig vielen Dimensionen).
Die Eingabe ist schon vorgegeben. Du verwendest eine Liste, in der jedes Element eine Tupel ist und die Koordinaten eines Hauses darstellt.
Wenn man über die Liste iteriert (for-schleife z.B.), bekommt man die Tuple als Elemente zurück.
Da du Distanzen von jedem Haus zu jedem Haus berechnen willst, brauchst du eine verschachtelte Schleife.

Code: Alles auswählen

import math


häuser = [(3,4), (5,6), (13,2), (14,8)]

distanzen = [
    [math.dist(haus, anderes_haus) for anderes_haus in häuser]
    for haus in häuser
]

Wenn du nun die Distanz zwischen Haus 1 und Haus 4 suchst, kannst du mit dem Index darauf zugreifen.
Haus 1 wäre z.B. an Position 0 und Haus 4 wäre bei Position 3. Python fängt beim Index 0 an zu zählen.

Code: Alles auswählen

dist_haus1_haus4 = distanzen[0][3]

Wenn man mit Namen arbeiten will, könnte man das mit einem verschachteltem Dict erreichen.

Code: Alles auswählen

import math


häuser = {"Haus 1": (3,4), "Haus 2": (5,6), "Haus 3": (13,2), "Haus 4": (14,8)}

distanzen = {
    haus_name: {
        anderes_haus_name: math.dist(haus_xy, anderes_haus_xy)
        for anderes_haus_name, anderes_haus_xy
        in häuser.items()
        if anderes_haus_name != haus_name
    }
    for haus_name, haus_xy in häuser.items()
}

Geht bestimmt auch schöner. Die Umlaute habe ich verwendet, damit andere was zum meckern haben.
Die erste Variante filter nichts raus. D.h. du hast auch Abstände von Haus 1 zu Haus 1, die dann 0 sind.
Im dict filtere ich das einfach raus, da ich die Namen habe. Das kann man auch mit der Liste erreichen, aber dann stimmt der Index nicht mehr.

[einfachTobi]

Um das eindeutig zu beantworten, müssest du auch noch erklären, wie du den Abstand zwischen zwei Häusern definierst. Geringster Abstand von zwei Eckpunkten?
Was passiert in so einem Fall:

Code: Alles auswählen

Haus 1
------\
xxxxxx|
xxxxxx|
xxxxxx|
xxxxxx|
xxxxxx|
xxxxxx|      Haus 2
xxxxxx|   /----------
xxxxxx|   |xxxxxxxxx
xxxxxx|   \----------
xxxxxx|
xxxxxx|
xxxxxx|
xxxxxx|
xxxxxx|
xxxxxx|
------/

Dort ist der Abstand von den Eckpunkten von Haus 1 zu Haus 2 groß, aber die Abstand der Wände/Punkte von Haus 2 sind gering. Kommt es dir auf den echten Abstand an oder auf die Relationen?

[DeaD_EyE]

Ich glaube, seine Häuser sind nur Punkte, die über XY-Koordinaten definiert sind.

Für die Eckpunkte müsste er noch die Abmessungen der Häuser haben oder mindestens die Koordinaten zwei diagonal gegenüberliegenden Eckpunkte pro Haus.
Auch eine interessante Aufgabe.

[nezzcarth]

Um alle "Häuser"-Kombinationen zu bestimmen, kannst du itertools.combinations verwenden. Welche Datenstruktur sicher zur Ablage eignet, hängt davon ab, was du anschließend mit den berechneten Distanzen vorhast. Dazu hast du noch nichts gesagt.

[__deets__]

Ich wuerde so nicht vorgehen. Fuer ein solches Problem bieten sich raeumliche Datenstrukturen wie binary space partitioning an, damit man eben nicht stumpf den Abstand des Berliner Doms vom Berghain bestimmt.

[nezzcarth]

@__deets__: Hängt das nicht auch von der Anzahl der Vergleiche ab, wie man vorgeht? Die vorgeschlagenen Varianten kann jemand, der Python halbwegs beherrscht in wenigen Minuten so runterprogrammieren. Bis ein Uneingeweihter zum Beispiel BSP verstanden und (effizient) in Python umgesetzt hat, könnten durchaus Stunden bis Tage vergehen, glaube ich. Daher kann ein Kompromiss je nach Anwendung vielleicht doch praktisch sein?

[__deets__]

Natürlich hängt das von der Anzahl ab. Aber wenn man die nicht kennt, zu einem quadratischen Algorithmus zu raten, ist eben nicht ungefährlich.

Und BSPs gibts auch als Module von der Stange.

[__deets__]

Ich habe nochmal ein bisschen nachgedacht, und ich glaube meine Idee ist Murks. Ein BSP ist eine richtige Lösung, wenn man mit dem erstellten Index oft nachschlagen muss. Doch das passiert hier ja nicht, und ich vermute mal man bekommt eh ein quadratisches Verhalten beim erzeugen des Index. Womit der Ansatz das paarweise zu machen auch ok geht.

[bords0]

Wie kennen ja die Anzahl: 70. Das läuft ja schneller, als man BSP in die Suchmaschine eingetippt hat