Direkt zum Inhalt

Lexikon der Mathematik: Geometrische Datenverarbeitung

Die Geometrische Datenverarbeitung befaßt sich mit der rechnerunterstützten Bearbeitung von geometrischen Daten, was hauptsächlich die Approximation und Interpolation von geometrischen Daten durch Kurven, Flächen, Bewegungsabläufe und andere geometrische Objekte bedeutet. Sie verknüpft Geometrie und Approximationstheorie und ist die mathematischen Grundlage des Computer-Aided Design.

Als einer der Ursprünge der geometrischen Datenverarbeitung werden die Arbeiten von P. de Casteljau und P. Bézier um 1960 gesehen, die das interaktive und rechnerunterstützte Design von Freiformkurven und Freiformflächen im Automobilbau ermöglichten. Dies geschah durch Bézierkurven und Bézierflächen, die durch ihre Kontrollpunkte in einer für den Designer durchsichtigen Weise festgelegt sind, und mit Hilfe des Algorithmus von de Casteljau in effizienter Weise ausgewertet werden können.

Das Modellieren von Freiformkurven und -flächen kann als Approximation von regelmäßig verteilen geometrischen Daten (den Kontrollpunkten) durch Kurven und Flächen interpretiert werden. Neben den polynomialen Bézierkurven und -flächen wurden viele Kurven- und Flächenschemata entwickelt − das prominenteste davon sind wohl die B-Splinekurven und B-Splineflächen. Die meisten entsprechen dem folgenden Muster: Eine Kurve oder Fläche ist durch Knotenvektoren und ein Kontrollpolygon oder -polyeder festgelegt, welches sie approximiert. Sie ist meist stückweise analytisch, global jedoch nur von einer endlichen Differenzierbarkeitsklasse, wobei die Stellen der niedrigsten Differenzierbarkeit durch die Knotenvektoren bestimmt sind. Ist die entstehende Kurve oder Fläche glatter als ihre Parametrisierung, spricht man von einer geometrischen Splinekurve oder geometrischen Splinefläche.

Die für das Entwerfen von Freiformkurven und Freiformflächen geeigneten Kurven- und Flächenschemata haben interessante geometrische Form- und Unterteilungseigenschalten, wie die convex hull property, die variation diminishing property, oder die Eigenschaft, daß Teile von solchen Kurven und Flächen ebenfalls in das gleiche Schema passen. Diese Eigenschaften sind für die formerhaltende Approximation von Datenpunkten und für Schnittalgorithmen für Freiformkurven und -flächen von Bedeutung.

Die Interpolation von regelmäßig verteilten Daten umfaßt die Interpolation mit Splinefunktionen, und von einem geometrischen Standpunkt aus betrachtet gehören dazu das Interpolieren von Punkten der Ebene oder des Raumes durch B-Splinekurven (vgl. chordale Parametrisierung, zentripetale Parametrisierung), oder die Interpolation von Punkten und Kurvennetzen mit Freiformflächen (Flächenverband). Für Anwendungen wichtig ist die formerhaltende Interpolation, die durch die oben erwähnten geometrischen Eigenschaften der verwendeten Kurven- und Flächenschemata möglich wird.

Zur Interpolation von unregelmäßig verteilten Daten gehört das Problem der Konstruktion eines Flächenverbandes, der Punkte und Randkurven interpoliert, und die scattered data Interpolation, wo man beispielweise eine Fläche durch eine großer Menge Datenpunkte legt. Die verwendeten Methoden umfassen etwa radiale Basisfunktionen (Hardysche Multiquadrik) oder Finite Elemente-Methoden zur Triangulierung und lokalen Interpolation von unregelmäßig verteilten Daten.

Als Approximation von unregelmäßig verteilten geometrischen Daten kann die Aufgabe interpretiert werden, ein Polyeder durch eine glatte Fläche anzunähern. Eine Möglichkeit bieten iterative diskrete Unterteilungsalgorithmen, die für viele Anwendungen schon nach wenigen Schritten ein ausreichend glattes Näherungspolyeder erzeugen. Ebenso zu diesem Problemkreis zählt die Approximation einer Punktwolke durch eine Kurve oder Fläche.

Diese Konzepte lassen sich neben der Konstruktion von Kurven und Flächen noch auf andere Probleme anwenden. Ohne eine Aufzählung versuchen zu wollen, sei als Beispiel nur das Planen von Fräsbahnen erwähnt − das sind Scharen von Freiformkurven in einer bestimmten fünfdimensionalen Teilmannigfaltigkeit der euklidischen Bewegungsgruppe.

Die geometrische Datenverarbeitung umfaßt jedoch nicht nur die obenstehende systematische Beschreibung von Problemen der geometrischen Approximationstheorie, sondern befaßt sich auch mit denjenigen Eigenschaften von geometrischen Objekten, die in der Datenverarbeitung im weitesten Sinne von Interesse sind (z. B. im Computer- Aided Design und im computer vision).

Darunter finden sich die Schnittalgorithmen für Flächen − die Unterteilungseigenschaften der B-Splines zusammen mit der convex hull property erlauben schnelle Algorithmen für die meisten Freiformflächen. Ein weiteres Beispiel sind Ausrundungs- und Übergangsflächen zwischen Freiformflächen, die auf Bindefunktionen beruhen oder als Flächenverband angelegt sind.

Zur geometrischen Qualitätskontrolle gehört das Überprüfen des Krümmungsverhaltens von Kurven und Flächen, wozu sich geometrische Objekte eignen, die zu ihrer Konstruktion einer Ableitung bedürfen, wie Reflexionslinien oder Isophoten.

Literatur

[1] Farin, G.: Curves and Surfaces for Computer Aided Geometric Design. Academic Press San Diego, 4th Ed. 1997.

[2] Hoschek, J., Lasser, D.: Grundlagen der geometrischen Datenverarbeitung. Teubner-Verlag Stuttgart, 2. Auflage 1992.

[3] Hoschek, J., Farin, G. (Hrsg.): Computer Aided Geometric Design. Elsevier, erscheint 9 mal jährlich.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos