WInkelberechnung / Koordinatenumgang in Phyton

[Pythonnoob02]

Hallo, habe im Internet eine Interessante Textaufgabe gefunden zum Thema Winkelberechnung und Koordinaten gefunden. Habe selber etwas probiert komme leider nicht weiter könnte mir jemand helfen? Aufgabe folgt...

Ein Anteil von Antons Arbeit ist das Abfliegen aller Außenstellen in Australien. Auf seiner
Tour muss er vorgegebene Orte besuchen, kann sich aber aussuchen, in welcher Reihenfolge
dies geschieht.
Anton möchte dies schnell erledigen. Deshalb hat er sich für seine Tour die folgende Route mit
möglichst kurzer Flugstrecke überlegt. Sie ist 2649 Kilometer lang. Bei dieser Route muss er
an manchen Orten sehr scharf abbiegen. Für diese Orte hat er die Abbiegewinkel in seine Karte
eingetragen:
In Zukunft möchte er alle Abbiegewinkel von mehr als 90 Grad vermeiden. Kannst du ihm
helfen und eine neue Route für ihn berechnen? Diese neue Route muss natürlich weiterhin alle
Außenstellen enthalten. Sie kann an beliebigen Orten beginnen und enden. Desweiteren muss
der Flug von einer Außenstelle zur nächsten geradlinig verlaufen, und Anton muss an keinem
Ort mit einem Winkel von mehr als 90 Grad abbiegen.

Aufgabe
Schreibe ein Programm, das Koordinaten einlesen kann und eine entsprechende Route berech-
net. Kann das Programm immer eine solche finden? Versuche die Flugstrecke möglichst kurz
zu machen, aber es ist nicht verlangt, die allerbeste Route zu finden.

[__deets__]

"Im Internet gefunden" ist wohl das neue "Ich habe Hausaufgaben"

Und Hausaufgabenhilfe gibt es hier nur in Form von konkreter Hilfestellung anhand der eigenen Versuche. Nicht blanko. Du sagst ja selbst, du hast schon etwas probiert. Zeig, was du probiert hast. Und dabei die Code-Tags bitte nicht vergessen, damit der Code lesbar ist.

[grubenfox]

Man könnte ein wenig über das Problem des Handlungsreisenden philosophieren. Die Aufgabe scheint ja eine Variante davon zu sein...

[__deets__]

Wobei ja keine optimale Route gefragt ist. Aber klar, das ist eine verwandte Problemklasse. Wenn man dafuer eine Loesung hat, muss man nur die potentiellen Kandidaten filtern nach denen, die mit einem stumpfen Winkel erreichbar sind.

@Pythonnoob2: die Frage, ob das Programm immer eine solche Route finden kann, solltest du auch mal durchdenken. Dazu hilft es, sich ein Gegenbeispiel auszudenken. Spoiler Alert: es geht nicht immer.

[ThomasL]

Hast du denn schon ChatGPT befragt? Das kann doch angeblich alle Probleme dieser Welt lösen. LOL

[ThomasL]

Spoiler Alert: es geht nicht immer.

Einfachstes Beispiel: 3 Orte die verbunden ein gleichseitiges Dreieck ergeben.

[grubenfox]

https://bwinf.de/bundeswettbewerb/41/2/

[Pythonnoob02]

"Im Internet gefunden" ist wohl das neue "Ich habe Hausaufgaben"

Und Hausaufgabenhilfe gibt es hier nur in Form von konkreter Hilfestellung anhand der eigenen Versuche. Nicht blanko. Du sagst ja selbst, du hast schon etwas probiert. Zeig, was du probiert hast. Und dabei die Code-Tags bitte nicht vergessen, damit der Code lesbar ist.

import math

# Open the file for reading
with open("wenigerkrumm1.txt", "r") as file:
# Read the first line of the file
line = file.readline()

# Initialize lists to store the x and y coordinates
x_coords = []
y_coords = []

# Loop through the lines in the file
while line:
# Split the line into a list of coordinates
coords = line.split()

# Convert the strings into floating point numbers
x = float(coords[0])
y = float(coords[1])

# Add the x and y coordinates to the lists
x_coords.append(x)
y_coords.append(y)

# Read the next line
line = file.readline()

# Find the minimum and maximum x and y values
min_x = min(x_coords)
max_x = max(x_coords)
min_y = min(y_coords)
max_y = max(y_coords)

# Initialize the coordinate system
coord_system = []
for i in range(int(min_y), int(max_y)+1):
row = []
for j in range(int(min_x), int(max_x)+1):
row.append(".")
coord_system.append(row)

# Add the points to the coordinate system
for i in range(len(x_coords)):
x = int(x_coords - min_x)
y = int(max_y - y_coords)
coord_system[y][x] = "*"

# Display the coordinate system
for row in coord_system:
for item in row:
print(item, end=" ")
print("")

# Calculate the turning angle for each set of x and y values
turning_angles = []
for i in range(1, len(x_coords)):
x1 = x_coords[i-1]
y1 = y_coords[i-1]
x2 = x_coords
y2 = y_coords
dx = x2 - x1
dy = y2 - y1
angle = math.degrees(math.atan2(dy, dx))
turning_angles.append(angle)

# Display the turning angles
print("Turning Angles:")
for angle in turning_angles:
print(angle)

Das ist mein bisheriges Skript, passen tut es aber nicht ...

[grubenfox]

Gehören zu einem Abbiegewinkel in diesem Fall nicht immer drei Punkte? Da wo er her kommt, da wo er dreht und da wo er nach dem drehen hin will...

[Pythonnoob02]

Gehören zu einem Abbiegewinkel in diesem Fall nicht immer drei Punkte? Da wo er her kommt, da wo er dreht und da wo er nach dem drehen hin will...

Ich verstehe die Aufgabe so, dass von dem Punkt wo er sich befindet der Winkel nicht größer sein darf als 90 Grad. Daher 2 Punkte der aktuelle Punkt un der nächst gesuchte

[grubenfox]

Welcher Winkel wohin/wogegen? Zwischen zwei Punkten ist die kürzeste Verbindung eine Gerade, da ist kein Winkel...

[__deets__]

Zwischen dem letzten Teilstück und dem geplantem Teilstück.

@Pyhtonnoon02: das mit den Code Tags war schon ernstgemeint. So ist es schwer entzifferbar, was du da fabriziert hast. Weil die Einrückungen fehlen.

[Pythonnoob02]

import math

# Open the file for reading
with open("wenigerkrumm1.txt", "r") as file:
# Read the first line of the file
line = file.readline()

# Initialize lists to store the x and y coordinates
x_coords = []
y_coords = []

# Loop through the lines in the file
while line:
# Split the line into a list of coordinates
coords = line.split()

# Convert the strings into floating point numbers
x = float(coords[0])
y = float(coords[1])

# Add the x and y coordinates to the lists
x_coords.append(x)
y_coords.append(y)

# Read the next line
line = file.readline()

# Find the minimum and maximum x and y values
min_x = min(x_coords)
max_x = max(x_coords)
min_y = min(y_coords)
max_y = max(y_coords)

# Initialize the coordinate system
coord_system = []
for i in range(int(min_y), int(max_y)+1):
row = []
for j in range(int(min_x), int(max_x)+1):
row.append(".")
coord_system.append(row)

# Add the points to the coordinate system
for i in range(len(x_coords)):
x = int(x_coords - min_x)
y = int(max_y - y_coords)
coord_system[y][x] = "*"

# Display the coordinate system
for row in coord_system:
for item in row:
print(item, end=" ")
print("")

# Calculate the turning angle for each set of x and y values
turning_angles = []
for i in range(1, len(x_coords)):
x1 = x_coords[i-1]
y1 = y_coords[i-1]
x2 = x_coords
y2 = y_coords
dx = x2 - x1
dy = y2 - y1
angle = math.degrees(math.atan2(dy, dx))
turning_angles.append(angle)

# Display the turning angles
print("Turning Angles:")
for angle in turning_angles:
print(angle)

So sieht es bei mir in Python aus.

[Pythonnoob02]

Welcher Winkel wohin/wogegen? Zwischen zwei Punkten ist die kürzeste Verbindung eine Gerade, da ist kein Winkel...

Du hast recht würde ansonsten keinen Sinn ergeben.

[__deets__]

Da sind immer noch keine Code-Tags. Das ist der </>-Knopf im vollstaendigen Editor.

[__deets__]

Ein paar Anmerkungen zum Code: so wie du das gerade angehst, ist das quatsch. Es bringt dir ueberhaupt nichts, die Koordinaten in zwei getrennten Listen zu speichern. Das macht alles nur unnoetig kompliziert. Stattdessen nimmt man eine Liste von Tupeln von (x, y).

Die erste Aufgabe besteht darin, ueberhaupt einen Rundweg zu bauen. Noch ohne die Randbedingung. Dazu solltest du einen simplen greedy TSP-Algorithmus schreiben. Von deiner aktuellen Position aus suche den noch nicht besuchten Ort mit dem geringsten euklidischen Abstand. Der wird als neuer Wegpunkt festgelegt, und dann geht es so lange weiter, bis es keine Ziele mehr gibt.

Dazu muss man sich mit weiteren Datenstrukturen wie Listen, Mengen und Woerterbuechern auseinandersetzen.

Wenn dieser TSP steht, muss man die Auswhal des naechsten Ortes einfach um die Randbedingung erweitern: nur Orte, auf denen man sich nicht um mehr als 90 Grad dreht, sind Kandidaten. Dank des schon gespeicherten Weges ist das dann trivial. Ich wuerde da auch nicht mit dem atan2 arbeiten, weil der dann die relativen Winkel schwieriger macht. Sondern einfach mit dem acos des normalisierten Skalarproduktes zwischen den Vektoren zum Herkunftsort und zum Wunschort.

[Pythonnoob02]

Ein paar Anmerkungen zum Code: so wie du das gerade angehst, ist das quatsch. Es bringt dir ueberhaupt nichts, die Koordinaten in zwei getrennten Listen zu speichern. Das macht alles nur unnoetig kompliziert. Stattdessen nimmt man eine Liste von Tupeln von (x, y).

Die erste Aufgabe besteht darin, ueberhaupt einen Rundweg zu bauen. Noch ohne die Randbedingung. Dazu solltest du einen simplen greedy TSP-Algorithmus schreiben. Von deiner aktuellen Position aus suche den noch nicht besuchten Ort mit dem geringsten euklidischen Abstand. Der wird als neuer Wegpunkt festgelegt, und dann geht es so lange weiter, bis es keine Ziele mehr gibt.

Dazu muss man sich mit weiteren Datenstrukturen wie Listen, Mengen und Woerterbuechern auseinandersetzen.

Wenn dieser TSP steht, muss man die Auswhal des naechsten Ortes einfach um die Randbedingung erweitern: nur Orte, auf denen man sich nicht um mehr als 90 Grad dreht, sind Kandidaten. Dank des schon gespeicherten Weges ist das dann trivial. Ich wuerde da auch nicht mit dem atan2 arbeiten, weil der dann die relativen Winkel schwieriger macht. Sondern einfach mit dem acos des normalisierten Skalarproduktes zwischen den Vektoren zum Herkunftsort und zum Wunschort.

Vielen Dank dir, werde mich morgen nocheinmal dran setzen.

[grubenfox]

Die erste Aufgabe besteht darin, ueberhaupt einen Rundweg zu bauen.

kurze Ergänzung: es ist in der Aufgabenstellung kein Rundweg gefordert. Die Route kann an beliebigen Orten beginnen und an beliebigen Orten enden. Auch bei dem Bild der gewählten Route von 2649 Kilometern sind Start und Ziel unterschiedliche Orte.

Das passt jetzt nicht so gut zur gewählten Beschreibung (in den meisten Fällen würde ich auch dorthin zurück wollen wo ich hergekommen bin), aber das liegt wohl an der gewählten Aufgabenbeschreibung.
Ist programmtechnisch jetzt kein relevanter Unterschied, aber ich vermute bei der mehr oder weniger gewünschten Optimierung auf eine kürzere Streckenlänge könnte der fehlende Rückweg vom Ziel zum Start schon einen wichtigen Unterschied machen.

[Sirius3]

Eingerückt wird immer mit 4 Leerzeichen pro Ebene, nicht zwei.
Die while-Schleife zum Lesen der Datei ist umständlich. Dateiobjekte sind Iteratoren, die man mit einer for-Schleife benutzt.

Code: Alles auswählen

with open("wenigerkrumm1.txt", "r") as lines:
    coords = []
    for line in lines:
        x, y = map(float, line.split())
        coords.append((x, y))

[__blackjack__]

Oder als „list comprehension“:

Code: Alles auswählen

    with open("wenigerkrumm1.txt", "r", encoding="ascii") as lines:
        coords = [tuple(map(float, line.split())) for line in lines]