Georg Nührenberg

Algorithmen für das Containment Problem in 2 und 3 Dimensionen

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 05.08.2014

Kurzbeschreibung

In dieser Arbeit wird das Problem untersucht, ob ein Polygon in ein anderes hineinpasst, bzw. ein Polyeder in einen anderen Polyeder. Das Ziel ist dieses “Containment Problem” mit linearer Programmierung zu lösen. Dabei werden verschiedene Varianten des Problems betrachtet und Lösungen vorgestellt. Zu Beginn ist nur eine Translation erlaubt, um das eine Objekt in das andere hinein zu verschieben. Später kann dafür zusätzlich zur Translation auch eine Rotation verwendet werden. Um den Drehwinkel der Rotation mit linearer Programmierung zu betrachten werden zwei Lösungsansätze untersucht. Als erster Ansatz wird eine bestimmte Anzahl von Winkeln diskretisiert. Für zwei Dimensionen wird zusätzlich der zweite Lösungsansatz verwendet, bei dem eine Bedingung für den Drehwinkel linearisiert wird.

Ein weiterer wesentlicher Bestandteil dieser Arbeit war die Implementierung der herausgearbeiteten Algorithmen. Bedienung und Funktionsweise des geschaffenen Programmes werden als Teil der Arbeit erläutert.