Mais

Caixa delimitadora XYZ de um polígono esférico

Caixa delimitadora XYZ de um polígono esférico


Estou procurando um algoritmo para calcular a caixa delimitadora 3d de um polígono esférico - ou seja, o mín. / Máx. X, Y e Z sobre essa parte da superfície de uma esfera unitária.

O objetivo é auxiliar cálculos de sobreposição de área rápidos para um grande número de polígonos esféricos simples (convexos): Ter todas as caixas delimitadoras permitirá que você calcule rapidamente, para um determinado polígono alvo, uma grande maioria dos outros polígonos que definitivamente fazem não cruze-o (porque suas caixas delimitadoras são disjuntas).

Já tenho um cálculo que faz esse tipo de seleção, usando centros poligonais e raios máximos. No entanto, isso levará O (N ^ 2) tempo para calcular (para todos os polígonos de origem; para todos os polígonos de destino). Considerando que, esta abordagem esperançosamente seria executado em tempo O (N.log N), uma vez que a informação XYZ pode ser ordenada e então classificada / pesquisada (por exemplo, usando kdtrees).

Acho que isso é um pouco menos trivial do que parece. Por exemplo, o valor máximo de X em um segmento de limite de polígono (que é um grande círculo) pode obviamente ocorrer em um ponto em algum lugar entre os dois pontos finais. Mas também, de fato, um valor extremo pode ocorrer em algum lugar dentro o polígono afastado do limite - por exemplo, devemos ser capazes de obter um máximo de Z = 1,0 para um polígono desenhado em torno do pólo Norte, embora seu limite esteja inteiramente ao sul do pólo.

Alguém pode ajudar com isso ?


Assista o vídeo: Triángulos esféricos