Algorithmen zur Optimierung von geometrischen Packungsproblemen

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.