Bibliography | Geringer, Sergej: Algorithmen zur Optimierung von geometrischen Packungsproblemen. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 90 (2014). 70 pages, german.
|
CR-Schema | F.2.2 (Nonnumerical Algorithms and Problems)
|
Abstract | Geometrische Packungs-Probleme sind in vielen industriellen Prozessen anzutreffen. Dadurch motiviert wird in dieser Arbeit untersucht, wie geometrische Formen möglichst oft in einem rechteckigen Gebiet platziert werden können.
Um zu garantieren, dass Platzierungen von Formen ohne Überschneidungen sind, wird ein rasterbasierter Schnitttest realisiert, der unter Verwendung der OpenGL-API die Erkennung von Schnitten komplett auf der Grafikkarte durchführt. Die Problemstellung wird anhand von einfachen Polygonen modelliert und mithilfe der geometrischen Eigenschaften der Polygone untersucht. Dafür werden mögliche Platzierungen von Polygonen eingeschränkt und mit Hilfe des Schnitttests auf Überschneidungen geprüft. Eine Datenstruktur zur Verwaltung schnittfreier Polygon-Stellungen wird entwickelt; damit zusammenhängend werden Heuristiken vorgestellt, anhand derer solche Polygon-Stellungen bewertet werden können. Weiterhin werden Strategien diskutiert, die die Anzahl betrachteter Polygon-Stellungen, und somit nötiger Schnitttests, erheblich reduzieren. Diese Strategien orientieren sich an den geometrischen Eigenschaften der Polygone, sowie an strukturellen Eigenschaften der verwendeten Datenstruktur. Durch das iterative Aufbauen lokal enger und schnittfreier Polygon-Platzierungen werden globale Lösungen für das rechteckige Gebiet konstruiert.
Anhand einer Software-Implementierung werden die dargelegten Strategien evaluiert und als effizient erachtet.
|
Full text and other links | PDF (1813639 Bytes)
|
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
|
Superviser(s) | Funke, Stefan |
Entry date | April 22, 2014 |
---|