Dada uma malha de polígonos, e um ponto sobre esta malha, em qual dos polígonos está o ponto ?

Isto se aplica, por exemplo a casos de indicação de cidades, estados ou países em mapas.

A solução tradicional é aplicar o algoritmo de inclusão de pontos em polígono.

Problema:

E se o número de polígonos ou arestas for muito grande, como num mapa ? A aplicação do algoritmo tradicional demandaria muito tempo !!!

Algoritmo das Faixas

Tomemos este diagrama, onde cada polígono pode representar o estado de um país.

Cria-se um conjunto de faixas horizontais sobre os polígonos. Os limites das faixas são os vértices dos polígonos. Na verdade, basta criar uma linha horizontal sobre cada vértice.

Em cada uma das faixas, cria-se uma lista com os nomes dos polígonos que cruzam a faixa, bem como os valores de Y no início e no fim de cada faixa.

Na figura a seguir, as faixas estão definidas sobre a figura.

A lista a seguir apresenta os dados da figura anterior.

 Para saber dentro de que polígono está o um certo ponto (Xp,Yp)deve-se:

•  Descobrir a que faixa pertence o ponto:

usando o Yp do ponto e as colunas YI e YF, a busca pode ser feita de forma extremamente rápida pois os valores de YI e YF estão ordenados, permitindo o uso de um algoritmo de binária.

• Depois de descobrir a faixa, aplicar o algoritmo tradicional de inclusão de ponto em polígono, somente naqueles polígonos que fazem parte da faixa.

No exemplo acima o único caso em que será necessário usar o algoritmo tradicional em todos os polígonos é na faixa 3. Nas demais o número de polígonos é reduzido com o uso deste algoritmo.

Este algoritmo é de fato vantajoso quando o número de polígonos (e/ou de arestas destes) for grande.

A montagem das faixas pode demorar um pouco, mas como em um mapa os componentes não mudam com freqüência, não é preciso gerá-lá várias vezes. A tabela com as faixas pode ser gerada 1 vez e usada várias, podendo inclusive ser guardada junto com o mapa.