next up previous contents
Nächste Seite: Graphenbasierte Algorithmen Aufwärts: Geometrische Algorithmen Vorherige Seite: Koordinaten-Bisektion   Inhalt


Hauptachsenmethode

Die Hauptachsenmethode (siehe [Farhat und Lesoinne 1993], [Nour-Omid u. a. 1987], [Belkhale und Prithviraj 1990], [Simon 1991], [Chrisochoides u. a. 1994a]) teilt das Gebiet entlang der Hauptachse, die das größere Flächenträgheitsmoment aufweist. Die Achsen können aus den Eigenvektoren der Matrix

\begin{displaymath}
I=\left[
\begin{array}{lll}
I_{xx}&I_{xy}\\
I_{yx}&I_{yy}
\end{array}\right]
\end{displaymath} (6)

bestimmt werden. Die Matrixelemente lassen sich mit Hilfe des Gaußschen Integralsatzes berechnen. Eine Koordinatentransformation in den Schwerpunkt ist notwendig.
Schwerpunktskoordinaten:
\begin{displaymath}
x_s = \frac{\int x dA}{\int dA}
\end{displaymath} (7)


\begin{displaymath}
y_s = \frac{\int y dA}{\int dA}
\end{displaymath} (8)

Die Trägheitsmomente berechnen sich dann wie folgt:
\begin{displaymath}
I_{xx} = \int y^2 dA
\end{displaymath} (9)


\begin{displaymath}
I_{yy} = \int x^2 dA
\end{displaymath} (10)


\begin{displaymath}
I_{xy} = \int x \cdot y dA
\end{displaymath} (11)

Abbildung 2.16: Hauptachsen Bisektion: a) zwei Teilgebiete, b) vier Teilgebiete, c) acht Teilgebiete
\begin{figure}
\centerline {\psfig{figure=parti/hauptachsen.eps}} \end{figure}

Der numerische Aufwand der Partitionierung ist wegen der Berechnung der Integrale wesentlich höher als bei der Koordinaten-Bisektion. Dieser höhere Aufwand rechtfertigt sich durch die wesentlich günstigeren Formen der Teilgebiete, die eine geringere Länge der Außenkante besitzen und daher weniger Kommunikationsaufwand während der nachfolgenden Berechnung bewirken [Lämmer 1997](siehe Abbildung 2.16). Eine Verbesserung der Partitionierung ist mit der Kernighan-Lin-Heuristik [Kernighan und Lin 1970] und dem Algorithmus der Hilfreichen Mengen [Diekmann u. a. 1994] möglich.


next up previous contents
Nächste Seite: Graphenbasierte Algorithmen Aufwärts: Geometrische Algorithmen Vorherige Seite: Koordinaten-Bisektion   Inhalt