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 do movimento, e desenho assistido por computador (CAD). Na sua forma mais geral, o problema é que, 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 em um mouse para seguir um link em um navegador web, este problema 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, dado um ponto de consulta, determina de forma rápida qual região contém o ponto de consulta.

Caso no Plano

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

Decomposição em Slab

A mais simples e mais antiga estrutura de dados para atingir O(log n) para tempo de consulta foi descoberto 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 dois períodos consecutivos de linhas verticais é chamado de slab. Observe que cada slab é dividido pela não-interseção de segmentos de linha que atravessa completamente o slab da esquerda para a direita. A região entre dois segmentos consecutivos dentro de um slab corresponde a uma única face de S. Portanto, reduzimos nosso problema de localização do ponto a dois problemas mais simples:

1. Dado uma subdivisão do plano em slabs verticais, determinar qual slab contém um determinado ponto.
2. Dado um slab subdividido em regiões de não-interseção de segmentos que atravessam completamente o slab 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 pesquisa binária. Para ver como, observe que, como os segmentos não se cruzam e atravessam completamente transversalmente o slab, os segmentos podem ser ordenados verticalmente dentro de cada slab. Enquanto este algoritmo permite a localização em tempo logarítmo e é fácil de implementar, o espaço necessário para construir os slabs e as regiões contidas dentro dos slabs podem ser tão grande como O(n²), uma vez que cada slab pode atravessar uma fração significativa da segmentos. Vários autores notaram que os segmentos que se cruzam dois slabs 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 dois slabs adjacentes é armazenado. Sarnak e Tarjan conseguiram usar essa idéia 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 complexo.

Subdivisões Monotone

Uma cadeia (vertical) monotone é um caminho tal que a coordenada y nunca aumenta ao longo do caminho. Um polígono simples é (vertical) monotone se ela é formada por duas cadeias monotone, com os primeiros e últimos vértices em comum. É possível adicionar algumas arestas a uma subdivisão planar, a fim de fazer todos as faces monotone, obtendo o que é chamado de uma subdivisão monotone. 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 monotone, como fazemos nesta seção. A fraqueza da decomposição em slab é 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 monotone . A idéia é usar cadeia vertical monotone, em vez de usar linhas verticais para particionar o subdivisão. Convertendo essa idéia geral para uma estrutura de dados reais eficiênte não é uma tarefa simples. Em primeiro lugar, precisamos ser capazes de calcular uma cadeia monotone que divide a subdivisão em duas metades de tamanhos semelhantes. Segundo, uma vez que algumas arestas podem estar contidas em várias cadeias monotone, precisamos ter cuidado para garantir que o espaço de armazenamento é O(n). E em terceiro, testes verificando um ponto está à esquerda ou à direita de uma subdivisão monotone leva tempo de O(n), se realizada 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 monotone 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 monotone.

Refinamento por 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 idéia 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ído 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. Porque 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 abordagem randômica para este problema e, provavelmente, o mais prático, é baseado em decomposição trapezoidal, ou mapa trapezoidal. A decomposição trapezoidal é obtido por disparar balas verticais indo para cima e para baixo de cada vértice na subdivisão original. As balas param quando batem uma aresta, e formam uma nova aresta na subdivisão. Desta forma, obtemos um subconjunto da decomposição em slab, com apenas O(n) arestas e vértices, uma vez que apenas adiciona duas aretas 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 ao utilizado na decomposição em slab 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, construimos 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. Construimos 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 dados gerais de ponto de localização com estruturas lineares com espaço e tempo de consulta logarítmica 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 idéia 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 idéia seria aumentar o espaço de armazenamento para O(n²). Da mesma forma como na decomposição em slab, 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 de d-dimensional estruturas de dados 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 hierárquica 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 eixo ortogonal. 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 revised 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 

Links Externos

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