Event

Back to the event list

Ef­fi­z­i­en­te Da­ten­struk­tu­ren und Al­go­rith­­men für die Kol­li­si­on­s­er­­ken­nung im zwei­di­­men­si­o­n­a­len Raum

Location: F2.419
Organizer: Ibrahim Abdul Rahman, Bachelorarbeitsabschlussvortrag, Fischer

Diese Bachelorarbeit untersucht verschiedene Datenstrukturen zur effizienten Kollisionserkennung im zweidimensionalen Raum. Dafür wurden Quadtrees, Bounding Volume Hierarchies, Uniform Grids sowie hybride Varianten in einem eigens entwickelten C++-Testframework implementiert und anhand mehrerer Szenarien hinsichtlich Laufzeit und Speicherverbrauch verglichen. 
Die Ergebnisse zeigen, dass es keine universell beste Datenstruktur gibt. Insgesamt erzielten Uniform Grids in den meisten Tests die besten Laufzeiten, während Quadtrees besonders speichereffizient waren. Hybride Ansätze konnten in einzelnen Fällen Vorteile bieten, verursachten jedoch häufig zusätzlichen Aufwand. Damit hängt die geeignete Wahl der Datenstruktur vor allem vom jeweiligen Anwendungsszenario und den Prioritäten zwischen Geschwindigkeit und Speicherbedarf ab.