Visibility-based obstacle placing : automated obstacle placing based on circularity

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.

In this thesis the problem of placing multiple obstacles in a discrete 2D environment is con-sidered. 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.