Mostrar código-fonte de Localização de ponto

{{má tradução|ci=s|data=dezembro de 2011|consulte [[:en:Point location|Point location]] (inglês)}}
{{Revisão|ci=s}}
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 [[Grande-O|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 delimitadora mínima|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 [[David Dobkin (professor)|Dobkin]] e [[Richard J. Lipton|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:

#Dada uma subdivisão do plano em fatias verticais, determinar qual fatia contém um determinado ponto.
#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. [[Herbert Edelsbrunner|Edelsbrunner]], [[Leonidas J. Guibas|Guibas]], e [[Jorge Stolfi|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 <math>O(n^{2^d})</math>. 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<sup>d</sup>'') células, mas a localização dos pontos pode ser realizada em tempo O(log ''n'') com O(''n<sup>d</sup>'') 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<sup>''d''-1</sup> ''n'') com O (''n'') de espaço.

{{referências}}
* {{citar livro|primeiro1 =Mark|último1 =de Berg|primeiro2 =Marc|último2 =van Kreveld|primeiro3 =Mark|último3 =Overmars|autorlink3 =Mark Overmars|primeiro4 =Otfried|último4 =Schwarzkopf|ano= 2000 |título= Computational Geometry |publicado= [[Springer-Verlag]] |edição= 2nd revis | isbn = 3-540-65620-0|capítulo= Chapter 6: Point location|páginas=121–146}}
*{{citar periódico
 |autorlink1 = David Dobkin (professor)
 |último1 = Dobkin
 |primeiro1 = David
 |autorlink2 = Richard J. Lipton
 |último2 = Lipton
 |primeiro2 = Richard J.
 |título= Multidimensional searching problems  |periódico= [[SIAM Journal on Computing]]  | volume = 5  |número= 2  |páginas= 181–186  |ano= 1976  | doi = 10.1137/0205015}}
* {{citar livro
  |editor-nome1 = Jacob E.|editor-sobrenome1 = Goodman|editor2-link=Joseph O'Rourke (professor)|editor-nome2 =Joseph|editor-sobrenome2 =O'Rourke
  |título= Handbook of Discrete and Computational Geometry |edição= 2nd   |publicado= Chapman & Hall/CRC   |data= 2004   | isbn = 1584883014|capítulo=Chapter 34: "Point Location|primeiro =Jack|último =Snoeyink}}
* {{citar periódico
  |primeiro1 = Neil|último1 =Sarnak|autorlink2 =Robert Tarjan|primeiro2 =Robert E.|último2 =Tarjan
  |título= Planar point location using persistent search trees   |periódico= [[Communications of the ACM]]   | volume = 29   |número= 7   |páginas= 669–679   |data= 1986   | doi = 10.1145/6138.6151}}
* {{citar periódico
  |autorlink1 = Herbert Edelsbrunner|primeiro1 =Herbert|último1 =Edelsbrunner|autorlink2 =Leonidas J. Guibas|primeiro2 =Leonidas J.|último2 =Guibas|autorlink3 =Jorge Stolfi|primeiro3 =Jorge|último3 =Stolfi
  |título= Optimal point location in a monotone subdivision   |periódico= [[SIAM Journal on Computing]]   | volume = 15   |número= 2   |data= 1986   |páginas= 317–340   | doi = 10.1137/0215023}}
* {{citar periódico
  |primeiro = David G. |último = Kirkpatrick   |autorlink = David G. Kirkpatrick   |título= Optimal search in planar subdivisions   |periódico= [[SIAM Journal on Computing]]   | volume = 12   |ano= 1983   |páginas= 28–35   | doi = 10.1137/0212002   |número= 1}}
{{tradução/ref|en|Point location|oldid=460844169}}

==Ligações externas==
*[http://www.cs.sunysb.edu/~algorith/files/point-location.shtml Point-Location Source Repository] at Stony Brook University
*[http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Arrangement_on_surface_2/Chapter_main.html#Subsection_31.3.1 Point-Location Queries] in [[CGAL]], the Computational Geometry Algorithms Library

{{esboço-informática}}

[[Categoria:Geometria]]
[[Categoria:Computação científica]]