Ich nutzte diese Funktion, um den Drehwinkel für Label aus Karten zu berechnen. Beispiel-Karten zeigen Länder oder Wasserflächen.
In den Beispiel-Karten wird das Ergebnis der Berechnung unmittelbar benutzt: auch bei minimaler Asymmetrie der Fläche wird das Label in der berechneten Richtung gedreht; die Karten sehen deshalb unruhig aus. Im praktischen Einsatz wird man bei wenig exzentrischen Flächen wie Frankreich auf das Drehen des Labels verzichten.
Es gibt elegantere Methoden zur Berechnung von Flächen-Labels, ich mag aber Lösungen, die auf einfacher Mathematik beruhen und deren Implementierung eine geringe Rechenzeit verspricht, idealerweise unter Nutzung von SIMD-Befehlen.
Das Trägheitsmoment für ein Polygon wird berechnet als:
⟪ I = sum_(i=0)^(n-1) I_i = 1/12 * sum_(i=0)^(n-1) (x_i-x_(i+1)) * ( y_(i+1)2 + y_i^2 ) * (y_(i+1) + y_i) ⟫
Wir wollen das Trägheitsmoment nach einer linearen Abbildung des Polygons berechnen:
⟪ ( (a, b, c), (d, e, f), (0, 0, 1)) * ((x), (y), (1)) = ((a*x + b*y + c), (d*x + e*y + f), (1)) = ((x'), (y'), (1)) ⟫
In die Gleichung
⟪ I = 1/12 sum_(i=0)^(n-1) I_i = 1/12 sum_(i=0)^(n-1) (x'_i - x'_(i+1)) * ( y'_i^2 + y'_(i+1)^2 ) * ( y'_i + y'_(i+1) ) ⟫
setzen wir ⟪ x' = a*x + b*y + c ⟫ und ⟪ y' = d*x + e*y + f ⟫ ein:
⟪ = 1/12 sum_(i=0)^(n-1) ( ( ( [a*x_i + b*y_i + c] - [a*x_(i+1) + b*y_(i+1) + c] ) ), ( * ), ( ( [d*x_i + e*y_i + f]^2 + [d*x_(i+1) + e*y_(i+1) + f]^2 ) ), ( * ), ( ( [d*x_i + e*y_i + f] + [d*x_(i+1) + e*y_(i+1) + f] ) ) ) ⟫
⟪ = 1/12 sum_(i=0)^(n-1) ( ( ( a*x_i + b*y_i - a*x_(i+1) - b*y_(i+1) ) ), ( * ), ([{: ( d^2 * x_i^2 + e^2 * y_i^2 + f^2 + 2*de*x_i *y_i + 2*df*x_i + 2*ef * y_i + ), ( d^2 * x_(i+1)^2 + e^2 * y_(i+1)^2 + f^2 + 2*de*x_(i+1)*y_(i+1) + 2*df*x_(i+1) + 2*ef * y_(i+1) ) :}]), ( * ), ( ( d*x_i + d*x_(i+1) + e*y_i + e*y_(i+1) + 2f ) ) ) ⟫
Und multiplizieren aus (zur Kontrolle: es entstehen 4 × 12 × 5 = 240 Summanden):
⟪ = 1/12 sum_(i=0)^(n-1) ({: ( ad^3x_i^4 +ad^3x_i^3x_(i+1) +ad^2ex_i^3y_i +ad^2ex_i^3y_(i+1) +2ad^2fx_i^3 ), ( +ade^2x_i^2y_i^2 +ade^2x_ix_(i+1)y_i^2 +ae^3x_iy_i^3 +ae^3x_iy_i^2y_(i+1) +2ae^2fx_iy_i^2 ), ( +adf^2x_i^2 +adf^2x_ix_(i+1) +aef^2x_iy_i +aef^2x_iy_(i+1) +2af^3x_i ), ( +2ad^2ex_i^3y_i +2ad^2ex_i^2x_(i+1)y_i +2ade^2x_i^2y_i^2 +2ade^2x_i^2y_iy_(i+1) +4adefx_i^2y_i ), ( +2ad^2fx_i^3 +2ad^2fx_i^2x_(i+1) +2adefx_i^2y_i +2adefx_i^2y_(i+1) +4adf^2x_i^2 ), ( +2adefx_i^2y_i +2adefx_ix_(i+1)y_i +2ae^2fx_iy_i^2 +2ae^2fx_iy_iy_(i+1) +4aef^2x_iy_i ), ( +ad^3x_i^2x_(i+1)^2 +ad^3x_ix_(i+1)^3 +ad^2ex_ix_(i+1)^2y_i +ad^2ex_ix_(i+1)^2y_(i+1) +2ad^2fx_ix_(i+1)^2 ), ( +ade^2x_i^2y_(i+1)^2 +ade^2x_ix_(i+1)y_(i+1)^2 +ae^3x_iy_iy_(i+1)^2 +ae^3x_iy_(i+1)^3 +2ae^2fx_iy_(i+1)^2 ), ( +adf^2x_i^2 +adf^2x_ix_(i+1) +aef^2x_iy_i +aef^2x_iy_(i+1) +2af^3x_i ), ( +2ad^2ex_i^2x_(i+1)y_(i+1) +2ad^2ex_ix_(i+1)^2y_(i+1) +2ade^2x_ix_(i+1)y_iy_(i+1) +2ade^2x_ix_(i+1)y_(i+1)^2 +4adefx_ix_(i+1)y_(i+1) ), ( +2ad^2fx_i^2x_(i+1) +2ad^2fx_ix_(i+1)^2 +2adefx_ix_(i+1)y_i +2adefx_ix_(i+1)y_(i+1) +4adf^2x_ix_(i+1) ), ( +2adefx_i^2y_(i+1) +2adefx_ix_(i+1)y_(i+1) +2ae^2fx_iy_iy_(i+1) +2ae^2fx_iy_(i+1)^2 +4aef^2x_iy_(i+1) ), ( +bd^3x_i^3y_i +bd^3x_i^2x_(i+1)y_i +bd^2ex_i^2y_i^2 +bd^2ex_i^2y_iy_(i+1) +2bd^2fx_i^2y_i ), ( +bde^2x_iy_i^3 +bde^2x_(i+1)y_i^3 +be^3y_i^4 +be^3y_i^3y_(i+1) +2be^2fy_i^3 ), ( +bdf^2x_iy_i +bdf^2x_(i+1)y_i +bef^2y_i^2 +bef^2y_iy_(i+1) +2bf^3y_i ), ( +2bd^2ex_i^2y_i^2 +2bd^2ex_ix_(i+1)y_i^2 +2bde^2x_iy_i^3 +2bde^2x_iy_i^2y_(i+1) +4bdefx_iy_i^2 ), ( +2bd^2fx_i^2y_i +2bd^2fx_ix_(i+1)y_i +2bdefx_iy_i^2 +2bdefx_iy_iy_(i+1) +4bdf^2x_iy_i ), ( +2bdefx_iy_i^2 +2bdefx_(i+1)y_i^2 +2be^2fy_i^3 +2be^2fy_i^2y_(i+1) +4bef^2y_i^2 ), ( +bd^3x_ix_(i+1)^2y_i +bd^3x_(i+1)^3y_i +bd^2ex_(i+1)^2y_i^2 +bd^2ex_(i+1)^2y_iy_(i+1) +2bd^2fx_(i+1)^2y_i ), ( +bde^2x_iy_iy_(i+1)^2 +bde^2x_(i+1)y_iy_(i+1)^2 +be^3y_i^2y_(i+1)^2 +be^3y_iy_(i+1)^3 +2be^2fy_iy_(i+1)^2 ), ( +bdf^2x_iy_i +bdf^2x_(i+1)y_i +bef^2y_i^2 +bef^2y_iy_(i+1) +2bf^3y_i ), ( +2bd^2ex_ix_(i+1)y_iy_(i+1) +2bd^2ex_(i+1)^2y_iy_(i+1) +2bde^2x_(i+1)y_i^2y_(i+1) +2bde^2x_(i+1)y_iy_(i+1)^2 +4bdefx_(i+1)y_iy_(i+1) ), ( +2bd^2fx_ix_(i+1)y_i +2bd^2fx_(i+1)^2y_i +2bdefx_(i+1)y_i^2 +2bdefx_(i+1)y_iy_(i+1) +4bdf^2x_(i+1)y_i ), ( +2bdefx_iy_iy_(i+1) +2bdefx_(i+1)y_iy_(i+1) +2be^2fy_i^2y_(i+1) +2be^2fy_iy_(i+1)^2 +4bef^2y_iy_(i+1) ), ( -ad^3x_i^3x_(i+1) -ad^3x_i^2x_(i+1)^2 -ad^2ex_i^2x_(i+1)y_i -ad^2ex_i^2x_(i+1)y_(i+1) -2ad^2fx_i^2x_(i+1) ), ( -ade^2x_ix_(i+1)y_i^2 -ade^2x_(i+1)^2y_i^2 -ae^3x_(i+1)y_i^3 -ae^3x_(i+1)y_i^2y_(i+1) -2ae^2fx_(i+1)y_i^2 ), ( -adf^2x_ix_(i+1) -adf^2x_(i+1)^2 -aef^2x_(i+1)y_i -aef^2x_(i+1)y_(i+1) -2af^3x_(i+1) ), ( -2ad^2ex_i^2x_(i+1)y_i -2ad^2ex_ix_(i+1)^2y_i -2ade^2x_ix_(i+1)y_i^2 -2ade^2x_ix_(i+1)y_iy_(i+1) -4adefx_ix_(i+1)y_i ), ( -2ad^2fx_i^2x_(i+1) -2ad^2fx_ix_(i+1)^2 -2adefx_ix_(i+1)y_i -2adefx_ix_(i+1)y_(i+1) -4adf^2x_ix_(i+1) ), ( -2adefx_ix_(i+1)y_i -2adefx_(i+1)^2y_i -2ae^2fx_(i+1)y_i^2 -2ae^2fx_(i+1)y_iy_(i+1) -4aef^2x_(i+1)y_i ), ( -ad^3x_ix_(i+1)^3 -ad^3x_(i+1)^4 -ad^2ex_(i+1)^3y_i -ad^2ex_(i+1)^3y_(i+1) -2ad^2fx_(i+1)^3 ), ( -ade^2x_ix_(i+1)y_(i+1)^2 -ade^2x_(i+1)^2y_(i+1)^2 -ae^3x_(i+1)y_iy_(i+1)^2 -ae^3x_(i+1)y_(i+1)^3 -2ae^2fx_(i+1)y_(i+1)^2 ), ( -adf^2x_ix_(i+1) -adf^2x_(i+1)^2 -aef^2x_(i+1)y_i -aef^2x_(i+1)y_(i+1) -2af^3x_(i+1) ), ( -2ad^2ex_ix_(i+1)^2y_(i+1) -2ad^2ex_(i+1)^3y_(i+1) -2ade^2x_(i+1)^2y_iy_(i+1) -2ade^2x_(i+1)^2y_(i+1)^2 -4adefx_(i+1)^2y_(i+1) ), ( -2ad^2fx_ix_(i+1)^2 -2ad^2fx_(i+1)^3 -2adefx_(i+1)^2y_i -2adefx_(i+1)^2y_(i+1) -4adf^2x_(i+1)^2 ), ( -2adefx_ix_(i+1)y_(i+1) -2adefx_(i+1)^2y_(i+1) -2ae^2fx_(i+1)y_iy_(i+1) -2ae^2fx_(i+1)y_(i+1)^2 -4aef^2x_(i+1)y_(i+1) ), ( -bd^3x_i^3y_(i+1) -bd^3x_i^2x_(i+1)y_(i+1) -bd^2ex_i^2y_iy_(i+1) -bd^2ex_i^2y_(i+1)^2 -2bd^2fx_i^2y_(i+1) ), ( -bde^2x_iy_i^2y_(i+1) -bde^2x_(i+1)y_i^2y_(i+1) -be^3y_i^3y_(i+1) -be^3y_i^2y_(i+1)^2 -2be^2fy_i^2y_(i+1) ), ( -bdf^2x_iy_(i+1) -bdf^2x_(i+1)y_(i+1) -bef^2y_iy_(i+1) -bef^2y_(i+1)^2 -2bf^3y_(i+1) ), ( -2bd^2ex_i^2y_iy_(i+1) -2bd^2ex_ix_(i+1)y_iy_(i+1) -2bde^2x_iy_i^2y_(i+1) -2bde^2x_iy_iy_(i+1)^2 -4bdefx_iy_iy_(i+1) ), ( -2bd^2fx_i^2y_(i+1) -2bd^2fx_ix_(i+1)y_(i+1) -2bdefx_iy_iy_(i+1) -2bdefx_iy_(i+1)^2 -4bdf^2x_iy_(i+1) ), ( -2bdefx_iy_iy_(i+1) -2bdefx_(i+1)y_iy_(i+1) -2be^2fy_i^2y_(i+1) -2be^2fy_iy_(i+1)^2 -4bef^2y_iy_(i+1) ), ( -bd^3x_ix_(i+1)^2y_(i+1) -bd^3x_(i+1)^3y_(i+1) -bd^2ex_(i+1)^2y_iy_(i+1) -bd^2ex_(i+1)^2y_(i+1)^2 -2bd^2fx_(i+1)^2y_(i+1) ), ( -bde^2x_iy_(i+1)^3 -bde^2x_(i+1)y_(i+1)^3 -be^3y_iy_(i+1)^3 -be^3y_(i+1)^4 -2be^2fy_(i+1)^3 ), ( -bdf^2x_iy_(i+1) -bdf^2x_(i+1)y_(i+1) -bef^2y_iy_(i+1) -bef^2y_(i+1)^2 -2bf^3y_(i+1) ), ( -2bd^2ex_ix_(i+1)y_(i+1)^2 -2bd^2ex_(i+1)^2y_(i+1)^2 -2bde^2x_(i+1)y_iy_(i+1)^2 -2bde^2x_(i+1)y_(i+1)^3 -4bdefx_(i+1)y_(i+1)^2 ), ( -2bd^2fx_ix_(i+1)y_(i+1) -2bd^2fx_(i+1)^2y_(i+1) -2bdefx_(i+1)y_iy_(i+1) -2bdefx_(i+1)y_(i+1)^2 -4bdf^2x_(i+1)y_(i+1) ), ( -2bdefx_iy_(i+1)^2 -2bdefx_(i+1)y_(i+1)^2 -2be^2fy_iy_(i+1)^2 -2be^2fy_(i+1)^3 -4bef^2y_(i+1)^2 ) :}) ⟫
Wir fassen gleiche Terme in den Variablen ⟪ x_i ⟫, ⟪ x_(i+1) ⟫, ⟪ y_i ⟫ und ⟪ y_(i+1)⟫ zusammen:
⟪ = 1/12 sum_(i=0)^(n-1) ({: ( , 6 , (aef^2 - bdf^2) , (x_iy_(i+1)-x_(i+1)y_i) ), ( + , 4 , (adef - bd^2f) , (x_iy_(i+1)-x_(i+1)y_i) * (x_i+x_(i+1)) ), ( + , 4 , (ae^2f - bdef ) , (x_iy_(i+1)-x_(i+1)y_i) * (y_i+y_(i+1)) ), ( + , , (ad^2e - bd^3 ) , (x_iy_(i+1)-x_(i+1)y_i) * (x_i^2+x_ix_(i+1)+x_(i+1)^2) ), ( + , , (ae^3 - bde^2) , (x_iy_(i+1)-x_(i+1)y_i) * (y_i^2+y_iy_(i+1)+y_(i+1)^2) ), ( + , , (ade^2 - bd^2e) , (2 y_iy_(i+1) * (x_i^2 - x_(i+1)^2) + 2 x_ix_(i+1) * (y_(i+1)^2 - y_i^2) + x_i^2y_(i+1)^2 - x_(i+1)^2y_i^2) ) :}) ⟫
Und ziehen die Konstanten aus der Summe:
⟪ = ({: ( , (ae-bd) (f^2), * , 1/2 , sum_(i=0)^(n-1) (x_iy_(i+1)-x_(i+1)y_i) ), ( + , (ae-bd) (df) , * , 1/3 , sum_(i=0)^(n-1) (x_iy_(i+1)-x_(i+1)y_i) * (x_i+x_(i+1)) ), ( + , (ae-bd) (ef) , * , 1/3 , sum_(i=0)^(n-1) (x_iy_(i+1)-x_(i+1)y_i) * (y_i+y_(i+1)) ), ( + , (ae-bd) (d^2), * , 1/12 , sum_(i=0)^(n-1) (x_iy_(i+1)-x_(i+1)y_i) * (x_i^2+x_ix_(i+1)+x_(i+1)^2) ), ( + , (ae-bd) (e^2), * , 1/12 , sum_(i=0)^(n-1) (x_iy_(i+1)-x_(i+1)y_i) * (y_i^2+y_iy_(i+1)+y_(i+1)^2) ), ( + , (ae-bd) (de) , * , 1/12 , sum_(i=0)^(n-1) (2 y_iy_(i+1) * (x_i^2 - x_(i+1)^2) + 2 x_ix_(i+1) * (y_(i+1)^2 - y_i^2) + x_i^2y_(i+1)^2 - x_(i+1)^2y_i^2) ) :}) ⟫
Nachdem die sechs Summen einmalig aus den Koordinaten der Polygon-Ecken berechnet wurden, kann das Trägheitsmoment des Polygons nach einer linearen Abbildung unabhängig von der Zahl der Ecken in konstanter Zeit berechnet werden.
⟪ square ⟫
Beobachtung: bei der Identitätsabbildung ( ⟪ a=e=1, b=c=d=f=0 ⟫ ) reduziert sich die Formel auf den fünften Term:
⟪ = 1/12 sum_(i=0)^(n-1) (x_iy_(i+1)-x_(i+1)y_i) * (y_i^2+y_iy_(i+1)+y_(i+1)^2) ⟫
in Übereinstimmung mit der Basisgleichung.