Localização de ponto

O problema da localização de ponto é um tema fundamental da geometria computacional. Ele encontra aplicações em áreas que lidam com o processamento de dados geométricos: computação gráfica, sistemas de informação geográfica (GIS), planejamento de movimento, e desenho assistido por computador (CAD).

Na sua forma mais geral, o problema é: dada uma partição do espaço em regiões disjuntas, determinar a região onde se encontra um ponto de consulta. Como um exemplo de aplicação, cada vez que você clicar o mouse para seguir um link em um navegador web, o problema de localização de ponto deve ser resolvido a fim de determinar qual a área da tela do computador está sob o ponteiro do mouse. Um caso especial simples é o problema do ponto no polígono. Neste caso, é preciso determinar se o ponto está dentro, fora, ou no limite de um único polígono.

Em muitas aplicações, é preciso determinar a localização de vários pontos diferentes em relação à mesma partição do espaço. Para resolver este problema de forma eficiente, é útil construir uma estrutura de dados que, recebendo um ponto de consulta, determina de forma rápida qual região contém o ponto de consulta.

Caso no Plano

No caso plano, nos é dada uma subdivisão planar S , formada por vários polígonos chamados faces, e precisamos determinar qual face contém um ponto de consulta. A pesquisa por força bruta de cada face usando o algoritmo ponto-em-polígono é possível, mas geralmente não é viável para subdivisões de alta complexidade. Várias abordagens diferentes conduzem a uma estrutura de dados ótima, com espaço de armazenamento O(n) e tempo de consulta O(log n), onde n é o número total de segmentos em S. Por simplicidade, assumimos que a subdivisão do plano está contida dentro de uma caixa quadrada delimitadora.

Decomposição em fatias

A mais simples e mais antiga estrutura de dados com tempo de consulta O(log n) foi descoberta por Dobkin e Lipton em 1976. Baseia-se em subdividindo S utilizando linhas verticais que passam através de cada vértice em S . A região entre duas linhas verticais consecutivas é chamada de fatia. Observe que cada fatia é dividida pela não-interseção de segmentos de linha que atravessa completamente a fatia da esquerda para a direita. A região entre dois segmentos consecutivos dentro de uma fatia corresponde a uma única face de S. Portanto, reduzimos nosso problema de localização do ponto a dois problemas mais simples:

1. Dada uma subdivisão do plano em fatias verticais, determinar qual fatia contém um determinado ponto.
2. Dada uma fatia subdividida por segmentos que atravessam completamente a fatia da esquerda para a direita, determine qual a região contém um determinado ponto.

O primeiro problema pode ser resolvido por busca binária na coordenada x das linhas verticais em tempo de O(log n). O segundo problema também pode ser resolvido em tempo de O(log n) por busca binária. Para ver como, observe que, como os segmentos não se cruzam e atravessam completamente transversalmente a fatia, os segmentos podem ser ordenados verticalmente dentro de cada fatia.

Enquanto este algoritmo permite a localização em tempo logarítmico e é fácil de implementar, o espaço necessário para construir as fatias e as regiões contidas dentro delas pode ser tão grande como O(n²), uma vez que cada fatia pode atravessar uma fração significativa dos segmentos.

Vários autores notaram que os segmentos que se cruzam duas fatias adjacentes são praticamente os mesmos. Portanto, o tamanho da estrutura de dados poderia ser reduzido através da aplicação de algum tipo de compressão, onde apenas a diferença entre duas fatias adjacentes é armazenado. Sarnak e Tarjan conseguiram usar essa ideia em conjunto com a técnica de persistência para reduzir o espaço de armazenamento para O(n), mantendo a O(log n) em tempo de consulta. Infelizmente, a estrutura de dados torna-se altamente complexa.

Subdivisões monótonas

Uma cadeia (vertical) monótona é um caminho tal que a coordenada y nunca aumenta ao longo do caminho. Um polígono simples é (verticalmente) monótono se ele é formada por duas cadeias monótonas, com os primeiros e últimos vértices em comum. É possível adicionar algumas arestas a uma subdivisão planar, a fim de tornar todas as faces monótonas, obtendo o que é chamado de uma subdivisão monótona. Este processo não acrescenta qualquer vértices para a subdivisão (portanto, o tamanho continua sendo O(n)), e pode ser realizada em tempo de O(n log n) varrendo o plano (também pode ser realizado em tempo linear, utilizando a triangulação de polígonos). Portanto, não há perda de generalidade, se restringimos nossa estrutura de dados para o caso de subdivisões monótonas, como fazemos nesta seção.

A fraqueza da decomposição em fatias é que as linhas verticais criam segmentos adicionais na decomposição, tornando-o difícil de conseguir O(n) de espaço de armazenamento. Edelsbrunner, Guibas, e Stolfi descobriram uma ótima estrutura de dados que utiliza apenas as bordas em uma subdivisão monótona. A ideia é usar cadeias verticais monótonas, em vez de usar linhas verticais para particionar a subdivisão.

Converter essa ideia geral para uma estrutura de dados reais eficiente não é uma tarefa simples. Em primeiro lugar, precisamos ser capazes de calcular uma cadeia monótona que divide a subdivisão em duas metades de tamanhos semelhantes. Segundo, uma vez que algumas arestas podem estar contidas em várias cadeias monótona, precisamos ter cuidado para garantir que o espaço de armazenamento é O(n). E em terceiro, testes verificando se um ponto está à esquerda ou à direita de uma subdivisão monótona levam tempo O(n), se realizados ingenuamente.

Detalhes de como resolver as duas primeiras questões estão fora do escopo deste artigo. Mencionamos brevemente como abordar a terceira questão. Usando busca binária, podemos testar se um ponto está à esquerda ou à direita de uma cadeia monótona em tempo de O(log n). Como precisamos realizar outra pesquisa binária através de O(log n) cadeias para realmente determinar a localização do ponto, o tempo de consulta é O(log² n). Para atingir tempo de consulta de O(log n), precisamos usar em cascata fracionária, mantendo ponteiros entre as bordas de diferentes cadeias monótona.

Refinamento de triangulação

Um polígono com m vértices pode ser particionado em m-2 triângulos. Existem diversos algoritmos para triangular um polígono de forma eficiente, a forma mais rápida tem tempo O(n) no pior caso. Portanto, podemos decompor cada polígono da nossa subdivisão em triângulos, e restringir a nossa estrutura de dados para o caso de subdivisões constituída exclusivamente por triângulos. Kirkpatrick dá uma estrutura de dados para localização do ponto em subdivisões trianguladas com O(n) de espaço de armazenamento e O(log n) de tempo de consulta.

A ideia geral é a construção de uma hierarquia de triângulos. Para executar uma consulta, começamos por encontrar o triângulo de nível superior que contém o ponto de consulta. Como o número de triângulos de nível superior é limitada por uma constante, esta operação pode ser realizada em tempo O(1). Cada triângulo tem ponteiros para os triângulos que ele intercepta no próximo nível da hierarquia, e o número de ponteiros também é limitada por uma constante. Prosseguimos com a consulta encontrando qual triângulo contém o ponto de consulta nível por nível.

A estrutura de dados é construída em ordem inversa, ou seja, de baixo para cima. Começamos com as subdivisões trianguladas, e escolhemos um conjunto independente de vértices a ser removido. Depois de remover os vértices, fazemos uma nova subdivisão por triângulos. Como a subdivisão é formada por triângulos, um algoritmo guloso pode encontrar um conjunto independente que contém uma fração constante dos vértices. Portanto, o número de etapas de remoção é O(log n).

Decomposição trapezoidal

Uma algoritmo probabilístico para este problema e, provavelmente, o mais prático, é baseado na decomposição trapezoidal, ou mapa trapezoidal. A decomposição trapezoidal é obtida disparando balas verticais indo para cima e para baixo de cada vértice na subdivisão original. As balas param quando batem em uma aresta, e formam uma nova aresta na subdivisão. Desta forma, obtemos um subconjunto da decomposição em fatias, com apenas O(n) arestas e vértices, uma vez que apenas adiciona duas arestas e dois vértices para cada vértice na subdivisão original.

Não é fácil ver como usar uma decomposição trapezoidal para localização do ponto, já que a pesquisa binária semelhante a utilizada na decomposição em fatias não pode mais ser realizada. Em vez disso, precisamos responder a consulta da mesma forma como a abordagem de refinamento por triangulação, mas a estrutura de dados é construído de cima para baixo. Inicialmente, construímos uma decomposição trapezoidal contendo apenas a caixa delimitadora, e nenhum vértice interno. Então, adicionamos os segmentos da subdivisão, um por um, em ordem aleatória, refinando a decomposição trapezoidal. Usando uma análise de trás para frente, podemos mostrar que o número esperado de trapézios criados para cada inserção é limitada por uma constante.

Construímos um grafo acíclico dirigido, onde os vértices são os trapézios que existiam em algum momento no refinamento, e as arestas dirigidas conectam os trapézios obtidos pela subdivisão. A profundidade esperada de uma pesquisa neste dígrafo, a partir do vértice correspondente à caixa delimitadora, é O(log n).

Dimensões superiores

Não são conhecidos estruturas de dados gerais para localização de ponto com armazenamento lineare e tempo de consulta logarítmico para dimensões maiores do que 2. Portanto, precisamos de sacrificar o tempo de consulta, ou espaço de armazenamento, ou limitar-se a algum tipo menos geral de subdivisão.

No espaço tridimensional, é possível responder a consultas de localização do ponto em O(log² n) usando O(n log n) de espaço. A ideia geral é manter várias estruturas de dados de localização de ponto no plano, correspondendo à interseção da subdivisão com o n planos paralelos que contêm cada subdivisão. Um uso ingênuo dessa ideia seria aumentar o espaço de armazenamento para O(n²). Da mesma forma como na decomposição em fatias, a semelhança entre as estruturas de dados consecutivas podem ser explorados, a fim de reduzir o espaço de armazenamento para O(n log n), mas o tempo de consulta aumenta para O(log² n).

Em espaço d-dimensional, localização do ponto pode ser resolvido de forma recursiva projetando as faces em um espaço (d-1)-dimensional. Enquanto o tempo de consulta é O(log n), o espaço de armazenamento pode ser tão alta quanto $O(n^{2^{d}})$. A alta complexidade das estruturas de dados d-dimensionais levou ao um estudo de tipos especiais de subdivisão.

Um exemplo importante é o caso dos arranjos de hiperplanos. Um arranjo de n hiperplanos define O(n^d) células, mas a localização dos pontos pode ser realizada em tempo O(log n) com O(n^d) de espaço usando a hierarquia de cortes de Chazelle.

Outro tipo especial de subdivisão é chamado subdivisão retilínea (ou ortogonal). Em uma subdivisão retilínea, todas as arestas são paralelas a um dos d eixos ortogonais. Neste caso, localização do ponto pode ser respondida em tempo O(log^d-1 n) com O (n) de espaço.

Referências

• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). «Chapter 6: Point location». Computational Geometry 2nd revis ed. [S.l.]: Springer-Verlag. pp. 121–146. ISBN 3-540-65620-0 
• Dobkin, David; Lipton, Richard J. (1976). «Multidimensional searching problems». SIAM Journal on Computing. 5 (2): 181–186. doi:10.1137/0205015 
• Snoeyink, Jack (2004). «Chapter 34: "Point Location». In: Goodman, Jacob E.; O'Rourke, Joseph. Handbook of Discrete and Computational Geometry 2nd ed. [S.l.]: Chapman & Hall/CRC. ISBN 1584883014 
• Sarnak, Neil; Tarjan, Robert E. (1986). «Planar point location using persistent search trees». Communications of the ACM. 29 (7): 669–679. doi:10.1145/6138.6151 
• Edelsbrunner, Herbert; Guibas, Leonidas J.; Stolfi, Jorge (1986). «Optimal point location in a monotone subdivision». SIAM Journal on Computing. 15 (2): 317–340. doi:10.1137/0215023 
• Kirkpatrick, David G. (1983). «Optimal search in planar subdivisions». SIAM Journal on Computing. 12 (1): 28–35. doi:10.1137/0212002 
• Este artigo foi inicialmente traduzido, total ou parcialmente, do artigo da Wikipédia em inglês cujo título é «Point location», especificamente desta versão.

Ligações externas

• Point-Location Source Repository at Stony Brook University
• Point-Location Queries in CGAL, the Computational Geometry Algorithms Library