Métodos de indexação alternativos para operações de conjunto de pontos

É comum usar um índice espacial de caixa delimitadora para melhorar o desempenho ao trabalhar com um grande número de recursos. Onde as operações são executadas em geometrias individuais com um grande número de vértices, existem estratégias de otimização semelhantes?

Por exemplo, existem estruturas de dados que podem acelerar o ponto nas operações de polígono ou união?

OK apenas para Ponto no polígono:

Penso que o problema se baseia na "natureza fractal" dos objetos 2D e na distribuição incerta e desequilibrada da informação espacial. Se você possui uma grade regular, é fácil calcular uma posição ou relação de uma célula. Mas um isoline de um modelo de terreno pode ter partes descomplicadas do lado e peças matematicamente complicadas do outro lado (partes morfologicamente ativas, como cumes, vales ...).

A indexação tenta lidar com duas coisas:

1. Uma rotina rápida que fornece a você um conjunto de buckets nos quais você coleta objetos que você pode distinguir espacialmente (os buckets!). E BBoxes são fáceis de calcular e manipular.

2. Um conjunto de relações (sobreposição, toque) para distinguir ou relacionar as coisas espaciais (os objetos).

Infelizmente, os BBoxes não dão idéia, quantos pontos existem em cada BBox, como os objetos são modelados (buracos, convexos, ...) e como as informações são distribuídas localmente (90% dos pontos no canto superior esquerdo do BBox). Portanto, você pode encontrar membros de operação rápida no nível do objeto e perder muito tempo na construção da relação do teste.

Para usar uma abordagem mais irregular, a triangulação da IMO em combinação com e quadtrees é uma das estratégias, nas quais você pode aproximar o bucket e a construção de relações de um índice (bucket == construção de relações).

Para o exemplo do Point-in-Polygon-Test, é possível criar um cache irregular usando:

1. ! triangulação restrita delaunay da sua capa poli, com pontos de malha de borda adicionais para detecção fora da capa
2. coloque isso no esquema de indexação quadtree com não mais de N triângulos por caixa (cubos fractais)
3. encontre o conjunto triangular ao qual o ponto pertence - a folha na quadtree
4. encontre o triângulo no qual o ponto se encontra (a parte do teste sobre o máximo de N triângulos)
5. e solicite os IDs dos polígonos dos vértices do triângulo
6. se o ID for único, o ponto pertence ao polígono; caso contrário, está fora

O custo para construir o estanho e os quadríceps é muito alto e difícil de calcular e o quadtree precisa equilibrar triângulos grandes e pequenos (triângulos que não cabem em caixas menores de subárvore).

Algumas ferramentas e links:

Triângulo - triangulação de polígonos de restrição

Quadtrees - com exemplos de fontes

Stony Brook Repository - Estruturas de dados e geometria de diskrete