Diplom-/Masterarbeit : Suchstrukturen für Formen

Jonas Echterhoff

Betreuer: Prof. Dr. Helmut Alt

In dieser Arbeit geht es um effiziente Datenstrukturen zum Verwalten von Formen.

Wie genau der Begriff Formen definiert wird, ist dabei nicht einheitlich - viele der vorgestellten Systemen beschreiben eine Form über eine Bitmap der Umrisse, oder direkt als ein Pixelbild, wärend andere die Umrisse als Polygon betrachten. Der von mir vorgestellte Ansatz beschränkt sich dabei auf offene Kurven beziehungsweise Polygonzüge als Formen.

Nun interessieren wir uns für Datenstrukturen, in denen viele solche Formen verwaltet werden können, und die eine effiziente Suche nach Formen anhand von einer anderen Form als Suchschlüssel erlauben. Zuerst wollen wir einige vorhandene Systeme und deren Funktionsweise betrachten, dann werde ich einen neuen Ansatz vorstellen und analysieren.

Bei meinem Ansatz versuche ich, den Verlauf der Wendefunktion eines Polygonzuges durch eine Einordung in eine Baumstruktur zu repräsentieren. Zwei gleiche oder ähnliche Formen sollten dann möglichst in dem selben Blatt des Baumes gefunden Werden. Ich werde versuchen einige mathematische Eigenschaften dieses Systems zu beweisen, und dann werde ich das System implementieren und die Qualität der Suchergebnisse durch praktische Tests analyiseren.