algoritmo para dividir recursivamente um polígono em quadrantes de entrada / saída: como é chamado e onde está o código?

Question

Tenho muitos pontos (centenas de milhares) e quero verificar quais estão dentro de um polígono. Para um polígono relativamente pequeno (ou seja, provavelmente conterá apenas dezenas ou centenas de pontos), posso apenas usar a caixa delimitadora do polígono como uma verificação inicial e, em seguida, fazer uma verificação regular de ponto no polígono para os pontos dentro da caixa . Mas imagine um grande (ou seja, provavelmente conterá milhares de meus pontos), polígono de formato irregular. Muitos pontos passarão na verificação da caixa delimitadora e, além disso, a verificação do ponto no polígono será mais cara porque o polígono maior é composto de muitos mais pontos. Então, eu gostaria de poder filtrar a maioria dos pontos dentro ou fora sem ter que fazer a verificação completa do ponto no polígono.

Então, eu tenho um plano e, principalmente, quero saber se o que estou descrevendo é um algoritmo bem conhecido e, em caso afirmativo, como é chamado e onde posso encontrar o código existente para ele. Não acredito que o que estou descrevendo seja uma árvore quádrupla ou uma árvore r, e não sei como procurá-la. Estou chamando de "árvore retilínea" abaixo.

A ideia é lidar com esses polígonos maiores:

Faça um pré-processo de "árvore reta", em que a profundidade da árvore reta varia de acordo com o tamanho do polígono (ou seja, permita mais profundidade para um polígono maior). A árvore retangular dividiria a caixa delimitadora do polígono em quatro quartos. Ele verificaria se cada quarto de retângulo está totalmente dentro do polígono, totalmente fora do polígono ou nenhum dos dois. No caso de nenhum dos dois, ele dividiria os sub-reitos recursivamente, continuando dessa maneira até que todos os retos estivessem totalmente dentro ou fora, ou a profundidade máxima fosse alcançada. Portanto, a ideia é que (a) o tempo de pré-processamento para fazer esta árvore, embora ela própria faça várias verificações de ponto no polígono, vale a pena porque esse tempo é diminuído pelo número de pontos a serem verificados, e (b) a grande maioria dos pontos pode ser tratada usando verificações simples de caixa delimitadora (geralmente algumas verificações conforme você desce da árvore), e então um número relativamente pequeno teria que fazer a verificação completa do ponto no polígono ( para quando você alcançar um nó folha que ainda não é "nenhum").

Como é chamado esse algoritmo? E onde está o código? Na verdade, não parece tão difícil de escrever, mas pensei em perguntar antes de pular para a codificação.

Answer 1

Na verdade, acabei usando uma abordagem relacionada, mas diferente. Percebi que essencialmente esta estrutura de árvore que eu estava construindo não era mais do que um polígono desenhado em baixa resolução. Por exemplo, se minha árvore caísse a uma profundidade de 8, isso seria exatamente como desenhar meu polígono em um bitmap com resolução 256x256 e, em seguida, fazer testes de acerto de pixel contra esse polígono. Então, estendi essa ideia e usei uma biblioteca gráfica rápida (a biblioteca CImg). Eu desenho o polígono em um bitmap preto e branco de tamanho 4000x4000. Então, apenas verifico os pontos como pixels em relação ao bitmap. A mágica é que desenhar aquele bitmap enorme é muito rápido em comparação com o tempo que levei para construir a árvore. Portanto, obtenho uma resolução muito mais alta do que jamais poderia ter com minha árvore.

Um problema é ser capaz de detectar pontos próximos à borda do polígono, que podem ser incluídos ou excluídos incorretamente devido a problemas de arredondamento / resolução, mesmo no tamanho 4000x4000. Se você precisa saber precisamente se esses pontos estão dentro ou fora, você pode desenhar um traço ao redor do polígono em outra cor e, se seu teste de pixel atingir essa cor, você fará o ponto completo na verificação do polígono. Para meus propósitos, a resolução de 4000x4000 era boa o suficiente (eu poderia tolerar inclusão / exclusão incorreta para alguns dos meus pontos de extremidade).

Portanto, o truque fundamental desta solução é a ideia de que algoritmos de desenho de polígonos são muito rápidos em comparação com outras maneiras de "digitalizar" seu polígono.