Geometricks: Um framework de estruturas de dados geométricas em C++

Abstract

Objetos geométricos, tais como pontos, retas, polígonos e cubos, não possuem uma ordem intrínseca para estruturas de dados clássicas, devido as suas diversas dimensões serem independentes. Uma possível solução para o armazenamento de dados multidimensionais seria a multi-indexação dos dados por cada uma de suas dimensões. Porém, buscas que, ou utilizem características geométricas dos dados, ou usem mais de uma das diversas dimensões ao mesmo tempo, ainda têm seu desempenho degradada, junto da necessidade de manter diversas cópias atualizadas. Dito isto, como solução para armazenamento e otimização de algoritmos que utilizem estes objetos, estruturas de dados geométricas, tais como rtree, quadtree, kdtree e octree, que particionam o espaço geométrico de busca são utilizadas. Este trabalho visa a implementação, na linguagem C++, de uma biblioteca para as estruturas quadtree e kdtree, com foco na alta personalização dos dados e documentação das técnicas de implementação utilizadas de forma didática, com o intuito de ajudar outras pessoas a implementar estruturas similares de maneira eficiente e genérica.