Estou tentando encontrar todos os polígonos cruzados por uma única linha (uma pista de GPS). Estou usando a biblioteca OGR (de python) para calcular isso, mas atualmente é um pouco de 'força bruta' (e lenta). Para cada ponto da minha trilha, chamo o método de interseção com todos os polígonos. A otimização óbvia é verificar apenas com polígonos adjacentes. Mas acho que esse é um problema clássico, com uma solução já conhecida (que não consigo encontrar ...).
Gostaria de evitar o uso de um banco de dados dedicado, pois estou tentando escrever um software independente (spatialite é uma opção se o banco de dados for o caminho a percorrer).
(Para sua informação, o código fonte atual está disponível aqui: https://github.com/dkm/airspace-checker )
Em vez de interseção expansiva , você pode executar a pré-seleção de polígonos com base na comparação de caixas delimitadoras. Em outras palavras, encontre todos os polígonos sobrepostos / adjacentes ao MBR dos segmentos da sua faixa. Em seguida, execute um teste detalhado no subconjunto de polígonos.
fonte
As propostas de mloskot e Nicklas para comparar as caixas delimitadoras estão realmente corretas.
Se você estiver usando shapefiles, considere também chamar este módulo saga: http://www.saga-gis.org/saga_modules_doc/shapes_transect/index.html
fonte
O que um banco de dados como o PostGIS faz para acelerar isso é primeiro fazer uma comparação de caixa delimitadora de índice. Primeiro, ele encontra todos os polígonos que possuem caixas delimitadoras que interagem com a caixa delimitadora da linha. O problema no seu caso pode ser que a cadeia de linhas seja longa e tenha uma caixa delimitadora muito grande interceptando muitos polígonos que não são de interesse.
Se as linhas forem muito longas, você provavelmente também precisará trabalhar com funções geodésicas muito mais complexas e lentas que as funções planares.
Pode ser bastante complexo fazer as coisas funcionarem sem problemas.
Por que você não deseja confiar em um banco de dados? Isso não resolverá todos os seus problemas, mas há muitas otimizações incorporadas no PostGIS, por exemplo. Lá você também tem os cálculos geodésicos de interseção, se necessário.
Atualização: li sua pergunta novamente e percebi que você não está usando a cadeia de linhas dos formulários trac, mas cada vértice.
Eu acho que você está no trac errado;)
Tanto porque você está faltando para verificar se a borda entre os pontos de vértice cruza o polígono e porque você está movendo a iteração entre os pontos de vértice para python, em vez de alguma implementação C, que eu acho que é muito mais rápida . Então você tem esse problema com índices. Para tornar as coisas mais rápidas, você precisará criar e manipular algum tipo de índice espacial.
Por outro lado, se você está fazendo muito do trabalho em seu próprio código, por que não faz o teste de interseção também. Esse teste é apenas um ponto no teste de polígono se você estiver lidando com os pontos de vértice. Google para "point in polygon" e você encontrará vários algoritmos.
Mas, eu iria para uma abordagem orientada a banco de dados. Isso lhe dará a possibilidade de usar índices espaciais.
/ Nicklas
fonte