Winkel zwischen allen Kanten für jeden Knoten in einem Netzwerk berechnen

[mcl33]

Hallo liebe Community,

ich habe folgendes Problem, das ich an einem Beispiel vereinfacht habe:

Es gibt ein Netzwerk mit 7 Knoten mit Koordinaten sowie Kanten zwischen den Knoten, dargestellt durch eine Liste mit Tuples der Knoten und x-, y-Koordinate sowie ein Dictionary mit den Verbindungen von jedem Knoten ausgehend:

Code: Alles auswählen

nodes = [(1, 1, 2), (2, 7, 2), (3, 7, 1), (4, 9, 6), (5, 3, 4), (6, 2, 6), (7, 6, 7)]
connections_from_nodes = {1: [6, 5, 2], 2: [1, 5, 4, 3], 3: [2, 4], 4: [7, 5, 2, 3], 5: [1, 2, 4, 7, 6], 6: [1, 5, 7], 7: [5, 6, 4]}

Ich möchte für jeden Knoten alle umliegenden Winkel ausrechnen, d.h. den Winkel zwischen nebeneinanderleigenden Kanten die vom Knoten ausgehen. Die Summe der Winkel um einen Knoten muss dementsprechend 360° betragen.

Ich habe das ganze mal noch grafisch veranschaulicht. An Knoten 6 sieht man z.B., dass drei Winkel berechnet werden müssten, bei Knoten 5 wären es aber ganze fünf:



Die Winkelberechnung vom Knoten a (origin_a) zu zwei anderen Punkten b und c lässt sich leicht über den Kosinussatz berechnen:

Code: Alles auswählen

def get_angle(origin_a, point_b, point_c, nodes):
    a = math.sqrt((nodes[point_b][1] - nodes[point_c][1])**2 + (nodes[point_b][2] - nodes[point_c][2])**2)
    b = math.sqrt((nodes[origin_a][1] - nodes[point_c][1])**2 + (nodes[origin_a][2] - nodes[point_c][2])**2)
    c = math.sqrt((nodes[origin_a][1] - nodes[point_b][1])**2 + (nodes[origin_a][2] - nodes[point_b][2])**2)
    
    cos_alpha = (b**2 + c**2 - a**2) / (2*b*c)
    alpha = math.degrees(math.acos(cos_alpha))
    return alpha

Klar ist, dass über jeden Knoten im connections_from_nodes Dictionary iteriert werden muss um die Winkel für jeden Knoten zu erhalten.
Die Winkel sollten wiederum in einem Dictionary nach gleichem Schema mit {Knoten1: [Winkel1, Winkel2, ...], Knoten2: ...} gespeichert werden.

Jetzt brauche ich nur noch einen Algorithmus, der mir auch wirklich nur die gesuchten Winkel zurückgibt und das für Knoten mit beliebig vielen angrenzenden Kanten.
Bisher habe ich es nur geschafft die Winkel von jeder Kante zu jeder anderen Kante von einem Knoten zu berechnen. Das Problem ist, dass ich nicht weiß, in welcher Reihenfolge die Kanten um einen Punkt auftreten. Z.B. bei Knoten 6, sehe ich, dass ich die Winkel Zwischen 7 und 5, 5 und 1 sowie 1 und 7 berechnen muss, aber wie finde ich das für jeden Knoten algorithmisch heraus?
Problematisch ist auch, dass die Winkelfunktion oben immer einen Winkel < 180° zurückgibt, sodass man bei einigen Winkeln diese noch von 360° abziehen müsste.

Vielleicht hat ja jemand eine Idee...

Danke euch schon mal,
Michael

[/me]

Bisher habe ich es nur geschafft die Winkel von jeder Kante zu jeder anderen Kante von einem Knoten zu berechnen. Das Problem ist, dass ich nicht weiß, in welcher Reihenfolge die Kanten um einen Punkt auftreten. Z.B. bei Knoten 6, sehe ich, dass ich die Winkel Zwischen 7 und 5, 5 und 1 sowie 1 und 7 berechnen muss, aber wie finde ich das für jeden Knoten algorithmisch heraus?

Das sieht grundsätzlich nach Delauney-Triangulierung aus.

Code kann ich dir dafür leider nicht liefern, aber vielleicht kommst du mit dem Begriff ja schon mal weiter.

[mcl33]

Das sieht grundsätzlich nach Delauney-Triangulierung aus.

Danke für den Denkanstoß.
Ich bin mir aber nicht ganz sicher, ob es sich tatsächlich darum dreht. Das Netz habe ich allerdings schon, die Flächen sind mir bekannt. Ich suche nur die Winkel. Zudem können im Netzwerk auch Vierecke, Fünfecke, usw. vorkommen. Vielleicht habe ich das Beispiel unglückliche gewählt, weil dort nur Dreiecke vorkommen. Ich entferne mal noch die Kante [5,4] im ursprünglichen Post, dann sollte es deutlich werden, was ich meine.

Der Algorithmus müsste (in meinen Augen) die Winkel von den Knoten aus berechnen und nicht die Flächen zwischen den Kanten als Grundlage nehmen.

Edit (nach Änderung des Netzwerkes durch Entfernen der Kante [4,5]):

Code: Alles auswählen

nodes = [(1, 1, 2), (2, 7, 2), (3, 7, 1), (4, 9, 6), (5, 3, 4), (6, 2, 6), (7, 6, 7)]
connections_from_nodes = {1: [6, 5, 2], 2: [1, 5, 4, 3], 3: [2, 4], 4: [7, 2, 3], 5: [1, 2, 7, 6], 6: [1, 5, 7], 7: [5, 6, 4]}

Der Algorithmus sollte aber weiterhin auch für Knoten mit mehr als 4 kanten funktionieren!

[BlackJack]

@mcl33: So ganz grob ein mögliches Vorgehen: Du müsstest die Punkte am anderen Ende nach ihrem Winkel zum betrachteten Punkt (als Mittelpunkt) sortieren. Dann kannst Du die Winkel zwischen den sortierten Punktpaaren berechnen. Das scheint mir zumindest verwandt mit der Delauny-Triangulation. Da muss man das sortieren IIRC mit allen Punkten machen, hier halt nur mit denen die schon verbunden sind.

[miracle173]

(...)
Das sieht grundsätzlich nach Delauney-Triangulierung aus.
(...)

Hallo
Mit dem Viereck 2-4-7-5 sieht mir das eigentlich nicht nach einer Triangulierung aus.

[/me]

Mit dem Viereck 2-4-7-5 sieht mir das eigentlich nicht nach einer Triangulierung aus.

Ursprünglich waren es nur Dreiecke. Das Beispiel wurde geändert wie mcl33 schrieb.

[miracle173]

(...)

Code: Alles auswählen

nodes = [(1, 1, 2), (2, 7, 2), (3, 7, 1), (4, 9, 6), (5, 3, 4), (6, 2, 6), (7, 6, 7)]
connections_from_nodes = {1: [6, 5, 2], 2: [1, 5, 4, 3], 3: [2, 4], 4: [7, 5, 2, 3], 5: [1, 2, 4, 7, 6], 6: [1, 5, 7], 7: [5, 6, 4]}

(...)

Hallo
Was mich irritiert ist, dass du den Namen (die Nummer des Knoten) und die Koordinaten in ein Tupel verpackst. Da scheint mir

Code: Alles auswählen

nodes = {1: (1,2), 2: (7,2),...}

klarer, da du aber die Knoten einfach nur durchnummerierts, könne man auch einfach nur

Code: Alles auswählen

nodes = [(1, 2), (7, 2),...]

nehmen und bei der Connection-Liste dann berücksichteigen, dass bei obiger Liste die Nummerierung mit 0 beginnt.


Das berechnen der Winkel ist kein großes Problem, du hast ja schon alles gegeben. Den Winkel berechnest du nicht mit dem Kosinussatz sondern mit Hilfe der Arcustangens-Funktion. Diese gibt dir den Anstieg des Vekors, also den Winkel zwischen x-Achse und Vektor. Du berechnest das am besten mit math.atan2(y,x). Willst du nicht Radianten sondern Grad, dann musst du noch umrechnen mit math.degrees(x), also math.degrees(math.atan2(y,x)). x und y sind da Tatsächlich die Koordinaten des Vektors. Das gibt einen Wert zwischen -180° und 180°. Willst du Werte zwischen 0° und 360°, dann zählst du zu den negativen Werten einfach 360° dazu. Ist aber für die weitere Rechnung nicht notwendig

Das folgende Programm gibt die Winkel von Nummer 5 mit seinen Nachbarn aus:

Code: Alles auswählen

import math
nodes = {1:(1, 2), 2:( 7, 2), 3:( 7, 1), 4:( 9, 6), 5:( 3, 4), 6:( 2, 6), 7:( 6, 7)}
connections_from_nodes = {1: [2, 5,6], 2: [1, 3, 4,5], 3: [2, 4], 4: [2, 3, 5, 7], 5: [1, 2, 4, 6,7], 6: [1, 5, 7], 7: [4, 5, 6]}
base_node=5
for k in sorted([[math.degrees(math.atan2(nodes[i][1]-nodes[base_node][1],nodes[i][0]-nodes[base_node][1])),i] for i in connections_from_nodes[base_node]]):
    print(k[1],k[0])
 

man erhält

Code: Alles auswählen

1 -146.30993247402023
2 -33.690067525979785
4 21.80140948635181
7 56.309932474020215
6 135.0

die Knoten wurden sortiert und man kann also den Winkel zweier benachbarten Knoten berechnen:
Der Winkel 1-5-2 ist -33.690067525979785-(-146.30993247402023), also 112.61986494804044, der Winkel 6-5-1 ist -146.30993247402023 - 135.0, also -281.30993247402023. Da gibt mman noch 360, dazu, das sind also dann 78.69006752597977

[miracle173]

Bei der vorigen Version hat sich ein kleiner Fehler isn Programm eingeschlichen. Hier die korrigierte Version:

(...)

Code: Alles auswählen

nodes = [(1, 1, 2), (2, 7, 2), (3, 7, 1), (4, 9, 6), (5, 3, 4), (6, 2, 6), (7, 6, 7)]
connections_from_nodes = {1: [6, 5, 2], 2: [1, 5, 4, 3], 3: [2, 4], 4: [7, 5, 2, 3], 5: [1, 2, 4, 7, 6], 6: [1, 5, 7], 7: [5, 6, 4]}

(...)

Hallo
Was mich irritiert ist, dass du den Namen (die Nummer des Knoten) und die Koordinaten in ein Tupel verpackst. Da scheint mir

Code: Alles auswählen

nodes = {1: (1,2), 2: (7,2),...}

klarer, da du aber die Knoten einfach nur durchnummerierts, könne man auch einfach nur

Code: Alles auswählen

nodes = [(1, 2), (7, 2),...]

nehmen und bei der Connection-Liste dann berücksichteigen, dass bei obiger Liste die Nummerierung mit 0 beginnt.


Das berechnen der Winkel ist kein großes Problem, du hast ja schon alles gegeben. Den Winkel berechnest du nicht mit dem Kosinussatz sondern mit Hilfe der Arcustangens-Funktion. Diese gibt dir den Anstieg des Vekors, also den Winkel zwischen x-Achse und Vektor. Du berechnest das am besten mit math.atan2(y,x). Willst du nicht Radianten sondern Grad, dann musst du noch umrechnen mit math.degrees(x), also math.degrees(math.atan2(y,x)). x und y sind da Tatsächlich die Koordinaten des Vektors. Das gibt einen Wert zwischen -180° und 180°. Willst du Werte zwischen 0° und 360°, dann zählst du zu den negativen Werten einfach 360° dazu. Ist aber für die weitere Rechnung nicht notwendig

Das folgende Programm gibt die Winkel von Nummer 5 mit seinen Nachbarn aus:

Code: Alles auswählen

import math
nodes = {1:(1, 2), 2:( 7, 2), 3:( 7, 1), 4:( 9, 6), 5:( 3, 4), 6:( 2, 6), 7:( 6, 7)}
connections_from_nodes = {1: [2, 5,6], 2: [1, 3, 4,5], 3: [2, 4], 4: [2, 3, 5, 7], 5: [1, 2, 4, 6,7], 6: [1, 5, 7], 7: [4, 5, 6]}
base_node=5
for k in sorted([[math.degrees(math.atan2(nodes[i][1]-nodes[base_node][1],nodes[i][0]-nodes[base_node][0])),i] for i in connections_from_nodes[base_node]]):
    print(k[1],k[0])

man erhält

Code: Alles auswählen

1 -135.0
2 -26.56505117707799
4 18.43494882292201
7 45.0
6 116.56505117707799

die Knoten wurden sortiert und man kann also den Winkel zweier benachbarten Knoten berechnen:
Der Winkel 1-5-2 ist -26.56505117707799-(-135.0), also 108.43494882292201, der Winkel 6-5-1 ist -135.0 - 116.56505117707799, also -251.56505117707798. Da gibt mman noch 360, dazu, das sind also dann 108.43494882292202