Summer School Inverse Problems and PDEs

Schnelle Berechnung von Ersatzelementen bei großen Messpunktmengen

Arbeitsgruppe	AG TechnomathematikAG Numerik PDE
Leitung:	Prof. Dr. Peter Maaß ((0421) 218-63801, E-Mail: pmaass@math.uni-bremen.de) Prof. Dr. Alfred Schmidt ((0421) 218-63851, E-Mail: schmidt@math.uni-bremen.de)
Bearbeiter:
Projektpartner:	Mahr GmbH (Göttingen)
Laufzeit:	01.08.2001 - 30.04.2002

Erstes Ziel dieser Kooperation zwischen der Mahr GmbH, einem weltweit operierenden, mittelständischen Unternehmen, das unter anderem hochwertige Messgeräte zum Prüfen von Werkstückgeometrien produziert, und dem Zentrum für Technomathematik ist die Entwicklung neuer, effizienter Methoden zur schnellen Berechnung von 2D- und 3D-Standardformelementen aus großen Messpunktmengen. Insbesondere sollen Verfahren zur Bestimmung von Pferch-, Hüll- und doppelwandigen Zylindern untersucht werden: Zum Beispiel bei der Untersuchung von Bohrlöchern müssen aus einer Menge von Messpunkten erstens der größte Zylinder, in dessen Inneren kein Messpunkt liegt (der Pferchzylinder), und zweitens der kleinste Zylinder, in dem alle Messpunkte liegen (der Hüllzylinder), bestimmt werden. Je weniger sich diese voneinander unterscheiden, desto höher ist die Qualität der Bohrung. Da die Verfahren online eingesetzt werden sollen, sind Algorithmen nötig, deren Komplexität höchstens O(n log n) beträgt (wenn n die Anzahl der Messpunkte ist). Bisher wurden neue Verfahren zur Bestimmung von Pferch- und Hüll-Kreisen für zweidimensionale Daten entwickelt und implementiert, und für dreidimensionale Messdaten eine Projektionsmethode auf diesen 2D-Fall entworfen. Eine Klasse von Algorithmen beruht auf der Delaunay-Triangulierung für Punktemengen, die vor allem im Rahmen der algorithmischen Geometrie untersucht wird, aber auch auch bei der Gittergenerierung für FEM-Berechnungen eingesetzt wird. Zum anderen wurde eine geometrische Basismethode, die auf elementaren Überlegungen beruht, implementiert. Zur Beschleunigung der Verfahren werden die Datensätze vor der Berechnung der Pferch- und Hüllkreise durch Methoden reduziert, die auf der Bestimmung der konvexen Hülle der Messpunkte und einer geeigneten Transformation, die z.B. den Hüllkreis auf eine konvexe - aber nicht kreisförmige - Kurve abbildet, basieren. Damit können typischerweise mehr als 95% aller Messpunkte vorab eliminiert werden. Der Test der neuen Algorithmen anhand realer Messwerte, die an Messgeräten der Mahr GmbH aufgenommen worden sind, und der Vergleich mit bisher verwendeten Verfahren hat ihr großes Potenzial bewiesen. Die Algorithmen sind deshalb in das von derMahr GmbH entwickelte Programmpaket MarShell integriert worden und werden jetzt im realen Einsatz getestet.

©2009-2012 Zentrum für Technomathematik