Algoritmos e estruturas de dados para visualização de polígonos em aplicações de tempo real

Abstract

Este trabalho apresenta um estudo de algumas estruturas de da- dos e técnicas para processamento de janelas. Estudamos maneiras de estruturar objetos geométricos de tal forma que consultas geométricas são respondidas com eficiência. Neste texto vamos apresentar duas estruturas de dados que estudamos as Árvores de Alcance, e as Árvores de Segmentos. Vamos utilizá-las para consultar objetos no plano portanto este trabalho preparou as estruturas de dados para recuperar objetos no plano. As estru- turas de dados e algoritmos de construção e consulta foram implementados. Por fim, utilizamos nossas implementações em uma aplicação que processa pontos e segmentos no plano. Demonstramos que são estruturas eficientes para consultas espaciais de pontos em aplicações com restrições temporais.

This work presents a study of some data structures and techni- ques to process windows. We study ways to structure geometric objects in such a way that queries in windows are quickly answered. The data structures that we study were KD Tree, Range Tree, Interval Tree and Segment Tree. This work used all the data structures on the plan. The data structures and the algorithms of construction and query were im- plemented. Finally, we used our implementation in an application that processes points and segments on the plan. We showed that the structures are efficient for query spatial points for time constraint applications.