[Back]


Diploma and Master Theses (authored and supervised):

C. Schwab:
"Visibility-Based Obstacle Placing";
Supervisor: G. Raidl; Institut für Computergraphik und Algorithmen, 2016; final examination: 2016-02-11.



English abstract:
In this thesis the problem of placing multiple obstacles in a discrete 2D environment is considered.
An example real life application for this problem is the placing of exhibition objects
in museums. Previous studies by various authors showed that people´s behaviour in space is
linked to the circularity measure - also called compactness - of their field of vision. This measure
describes the shape of the space that can be seen from a specific point. An evolutionary
algorithm (EA) is developed that places the given obstacles at the remaining unblocked space
according to the compactness at the remaining unoccupied space. The EA uses different target
functions to either minimise or maximise the compactness measure globally or locally.
Several test series are executed in order to assess influence of the algorithm´s parameters on
its performance. The solutions of the EA show emerging patterns for different target functions.
From those results a faster constructive heuristic is developed that can provide several
different solutions to simple placing problems within short time. In the EA a version of the
Shadow Casting algorithm is used to calculate the field of vision for a point. The heuristic
extends this algorithm by placing obstacles while iterating through the visible areas. The
objects are placed in a way such that preset points show a high compactness value and that
the architect can be inspired by the presented diverse solutions.

German abstract:
Diese Masterarbeit befasst sich mit dem Problem eine Mehrzahl an Objekten in einem diskreten
2D Raum zu platzieren. Ein Beispiel eines realen Problems dieser Art ist das Platzieren
von Ausstellungsstücken in einem Museum. Vergangene Studien diverser Autoren zeigten,
dass das Verhalten von Menschen in Räumen mit der Zirkularität - auch Kompaktheit - von
ihrem Sichtfeld zusammen hängt. Dieses Maß beschreibt die Form des Raumes der von einem
bestimmten Punkt aus gesehen werden kann. Im Rahmen dieser Arbeit wurde ein evolutionärer
Algorithmus (EA) entwickelt, der definierte Objekte abhängig von der Kompaktheit
des freibleibenden Raumes platziert. Der EA verwendet verschiedene Zielfunktionen um die
Kompaktheit global oder lokal entweder zu minimieren oder zu maximieren. Mehrere Testreihen
wurden ausgeführt um den Einfluss der Parameter des Algorithmus auf seine Effizienz
zu untersuchen. Die Lösungen die der EA produziert zeigen dass sich bestimmte Muster
für unterschiedliche Zielfunktionen entwickeln. Basierend auf diesen Ergebnissen wurde eine
schnellere konstruierende Heuristik entwickelt, die mehrere unterschiedliche Lösungen für
einfache Platzierungsprobleme in kurzer Zeit berechnen kann. Im EA wurde eine Version
des Shadow Casting Algorithmus verwendet um das Sichtfeld für einen Punkt zu berechnen.
Die Heuristik erweitert diesen Algorithmus um das Platzieren von Objekten während dem
Durchlaufen des Sichtfeldes. Die Objekte werden so platziert, dass voreingestellte Punkte eine
hohe Kompaktheit aufweisen und die präsentierten Lösungen dem Architekt als Inspiration
dienen.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/publik_254594.pdf


Created from the Publication Database of the Vienna University of Technology.