Packing circles and spheres on surfaces

Abstract

In dieser Diplomarbeit wird ein Verfahren vorgestellt, mit dem Kreispackungen und eng verwandte Kugelkonfigurationen auf Freiformflächen gefunden werden können. Kreispackungen sind Konfigurationen disjunkter Kreise mit vorgegebenen gegenseitigen Tangentialitäten. Die etablierte Theorie der Kreispackungen ist auf einige wenige spezielle geometrische Umgebungen beschränkt und es kann gezeigt werden, dass exakte Kreispackungen im euklidischen Raum nur auf ebenen und kugelförmigen Flächen existieren können. Die Eigenschaft der gegenseitigen Tangentialität wird daher als Ziel eines approximativen Ansatzes verwendet und es werden lokale und globale Fehlermaße eingeführt, um den Unterschied zwischen einer vorliegenden Approximation und einer echten Kreispackung quantifizieren zu können und die Qualität einer Approximation bewerten zu können. Nachdem die kombinatorische Struktur einer Kreispackung äquivalent der eines Dreiecksnetzes ist und Dreiecksnetze eine der gängigsten Darstellungsformen von Flächen darstellen ist es naheliegend, Dreiecksnetze als strukturelle Grundlage für die Approximation von Kreispackungen zu verwenden. Zu diesem Zweck wird eine Bedingung, welche die Existenz einer Kreispackung auf einem ebenen Dreiecksnetz garantiert, modifiziert so dass sie auch auf allgemeinere Netze angewendet werden kann. In der Folge wird begründet, warum Netze welche die erwähnte verallgemeinerte Bedingung erfüllen als Grundlage für eine Approximation von Kreispackungen gut geeignet erscheinen. Für solche Netze wird die Bezeichnung Kreispackungsnetze eingeführt. Es werden zwei verschiedene Möglichkeiten vorgestellt, auf Kreispackungsnetzen approximierte Kreispackungen zu konstruieren. Beide führen zu einem Ausgleichsproblem, bei dem Kreise an eine dreidimensionale Punktmenge angepasst werden müssen. Unterschiedliche Zugänge zu diesen Problemen werden gezeigt und evaluiert. Weiters wird bewiesen, dass Kreispackungsnetze eine Konfiguration von disjunkten Kugeln garantieren, deren Mittelpunkte die Netzknoten sind und von denen benachbarte Kugeln jeweils gegenseitig tangential liegen. In der Folge wird die definierende Bedingung für Kreispackungsnetze als Zielfunktion für numerische Optimierungsmethoden formuliert und zusammen mit zusätzlichen Optimierungstermen, welche die Entfernung des optmierten Netzes vom Ausgangsnetz minimieren, in einer Software implementiert.<br />Schlussendlich werden die Möglichkeiten und Grenzen der vorgestellten Methoden an Beispielen aus der Architektur demonstriert.<br />

This thesis proposes a method for finding circle packings and similar sphere configurations on free-form surfaces. Circle packings are patterns of disjoint circles with prescribed tangencies. The well-established theory of circle packing is restricted to a small number of classical geometric environments and it can be shown that precise circle packings in euclidean space can only exist on planar and spherical surfaces. The property of mutual tangency is therefore used as the target of an approximative approach, and local as well as global error measures are introduced to quantify the difference between the current approximation and a proper circle packing. As the combinatorial structure of a circle packing is equivalent to that of a triangular mesh and those meshes are one of the most common forms of surface representation, the idea of utilizing triangular meshes as a structural basis for circle packing approximation is self-evident. To this end, a condition providing for the existence of circle packings on planar meshes is modified to be applicable to more general meshes and it is motivated that meshes fulfilling that general condition, then defined as circle packing meshes, constitute a suitable basis for circle packing approximation. Two different ways of constructing circle packings based on circle packing meshes are presented, each of which leads to the problem of fitting circles to sets of points in euclidean three-space.<br />Different approaches to these problems are discussed and evaluated. It is further established that circle packing meshes provide a configuration of mutually tangent spheres, the vertices of the mesh being the sphere centers. The condition defining circle packing meshes is then formulated as a target function for numeric optimization methods and implemented in a software together with additional optimization terms responsible for minimizing the distance between the original and optimized meshes. Finally, examples from architecture are used for demonstrating the capabilities and limitations of the proposed techniques.