Qual é a maneira mais rápida para saber a distância cartesiano mais curta entre dois polígonos

StackOverflow https://stackoverflow.com/questions/84034

Pergunta

Eu tenho 1 polígono vermelho dizer e 50 polígono azuis colocadas aleatoriamente - eles estão situados em geográfica espaço 2D . O que é o mais rápido algorithim / mais rápida para saber a distância a mais curta entre um polígono vermelho e seu polígono azul mais próximo?

Tenha em mente que não é um caso simples de tomar os pontos que compõem os vértices do polígono como valores de teste para a distância que eles podem não ser necessariamente os pontos mais próximos.

Assim, no final -. A resposta deve devolver o polígono azul mais próximo ao vermelho singular

Isso é mais difícil do que parece!

Foi útil?

Solução

Duvido que haja uma solução melhor do que calcular a distância entre o vermelho e cada um azul e classificar estes por comprimento.

Com relação a classificação, geralmente QuickSort é difícil de bater no desempenho (um um otimizado, que corta a recursividade se o tamanho vai abaixo de 7 itens e muda para algo como insertion sort, talvez Shell Sort).

Assim, eu acho que a questão é como calcular rapidamente a distância entre dois polígonos, depois de tudo que você precisa para fazer esse cálculo 50 vezes.

A seguinte abordagem irá funcionar para 3D também, mas provavelmente não é o mais rápido:

Mínimo Polígono Distância no espaço 2D

A questão é: você está disposto a negociar precisão para a velocidade? Por exemplo. você pode embalar todos os polígonos em caixas delimitadoras, onde os lados das caixas são paralelos aos eixos de coordenadas do sistema. jogos 3D usar essa abordagem bastante freqüência. Porém você precisa encontrar os valores máximos e mínimos para cada coordenada (x, y, z) para construir a caixa delimitadora virtual. Cálculo das distâncias destas caixas delimitadoras é então uma tarefa trivial bonita.

Aqui está uma imagem exemplo de caixas delimitadoras mais avançados, que não são paralelos aos eixos de coordenadas do sistema:

Oriented Bounding Boxes - OBB

No entanto, isso faz com que o cálculo da distância de menos trivial. É usado para a detecção de colisão, que você não precisa saber a distância para isso, você só precisa saber se uma borda de uma delimitadora mentiras caixa dentro de outra caixa delimitadora.

A caixa delimitadora seguinte imagem mostra uma eixos alinhados:

Eixos Alinhados caixa delimitadora - AABB

OOBs são mais precisos, AABBs são mais rápidos. Talvez você gostaria de ler este artigo:

avançada detecção de colisão

Este é sempre supondo que você está disposto a negociar precisão para a velocidade. Se a precisão é mais importante do que a velocidade, você pode precisar de uma técnica mais avançada.

Outras dicas

Você pode ser capaz de reduzir o problema, e em seguida, fazer uma busca intensiva em um pequeno conjunto.

Processo cada polígono primeiro pela constatação:

  • Centro de polígono
  • raio máximo de polígono (isto é, o ponto no limite de superfície / / vértice do polígono mais afastadas do centro definido)

Agora você pode coletar, digamos, os 5-10 polígonos mais próximos para o vermelho (encontrar o centro de distância do centro, subtrair o raio, classificar a lista e tomar o top 5) e, em seguida, fazer uma rotina muito mais exaustiva.

Para formas poligonais com um número razoável de pontos de fronteira, como em um aplicativo GIS ou jogos que poderia ser mais rápido mais fácil de fazer uma série de testes.

Para cada vértice no compute polígono vermelho a distância a cada vértice no polígono azuis e encontrar o mais próximo (dica, distância comparar ^ 2, assim você não precisa do sqrt ()) Encontre o mais próximo, em seguida, verificar o vértice de cada lado do vértice encontrados vermelho e azul para decidir quais segmentos de linha são os mais próximos e, em seguida, encontrar o maior aproximação entre dois segmentos de linha.

Consulte http://local.wasp.uwa.edu. au / ~ pbourke / geometria / lineline3d / (é fácil simplesmente para o caso 2d)

Esta técnica de triagem se destina a reduzir o número de cálculos de distância você precisa executar no caso médio, sem comprometer a precisão do resultado. Ele funciona em côncavas e convexas polígonos.

Localizar a distância mínima entre cada par de vértices de tal modo que um é um vértice vermelho e um é um azul. Chamá-lo de r . A distância entre os polígonos é, no máximo, r . Construir uma nova região do polígono vermelho, onde cada segmento de linha é deslocado para fora por r e se une aos seus vizinhos por um arco de raio r é centrado no vértice. Encontre a distância de cada vértice dentro desta região para cada segmento de linha da cor oposta que cruza a região.

Claro que você pode adicionar um método aproximado, como caixas delimitadoras para determinar rapidamente quais dos polígonos azuis não pode possivelmente se cruzam com a região vermelha.

Eu sei que você disse que "a distância mais curta", mas você realmente significava a melhor solução ou uma solução de "bom / muito bom" é bom para o seu problema?

Porque se você precisa encontrar a solução ideal, você tem que calcular a distância entre toda a sua fonte e limites destino Polígon (não só vértices). Se você estiver no espaço 3D, em seguida, cada um ligado é um avião. Isso pode ser um grande problema (O (n ^ 2)), dependendo de quantos vértices que você tem.

Então, se você tem vértice contagem que faz que os quadrados para um número scarry e uma "boa / muito boa" solução é bom para você, ir para uma solução heurística ou aproximação.

Você pode querer olhar para Voronoi Culling. Papel e vídeo aqui:

http://www.cs.unc.edu/~geom/DVD/

Gostaria de começar por delimitadora todos os polígonos por um círculo de delimitação e, em seguida, encontrar um limite superior da distância mínima. Então eu iria simplesmente verificar as bordas de todos os polígonos azuis cujo limite inferior de distância é menor do que o limite superior da distância mínima contra todas as arestas do polígono vermelho.

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

Mas tudo depende de seus dados. Se os polígonos azuis são relativamente pequenos em comparação com as distâncias entre eles e o polígono vermelho, então esta abordagem deve funcionar muito bem, mas se eles são muito próximos, você não vai salvar nada (muitos deles vai estar perto o suficiente). E outra coisa -. Se esses polígonos não tem muitos vértices (como se a maioria deles eram triângulos), então ele pode ser quase tão rápido para apenas verificar cada borda vermelha contra cada borda azul

Espero que ajude

Como já foi mencionado usando delimitadora áreas (caixas, círculos) pode permitir que você descartar algumas interações polígono polígonos. Existem várias estratégias para isso, por exemplo.

  1. Escolha qualquer polígono azul e encontrar a distância do vermelho. Agora escolha qualquer outro polígono. Se a distância mínima entre as áreas delimitadas é maior do que a distância já encontrou você pode ignorar este polígono. Continue para todos os polígonos.
  2. Encontre a distância distância mínima / centroid entre o polígono vermelho e todos os polígonos azuis. Organizar os distâncias e considerar a menor distância em primeiro lugar. Calcule a distância mínima real e continuar através da lista ordenada até a distância máxima entre os polígonos é maior do que a distância mínima encontrado até agora.

Sua escolha de círculos / caixas alinhadas de modo axial, ou caixas orientadas pode ter um grande efeito sobre o desempenho do algoritmo, depende da disposição real dos polígonos de entrada.

Para o cálculo da distância mínima real que você poderia usar de Yang et al ' Um novo algoritmo rápido para calcular a distância entre dois polígonos disjuntos convexos com base no diagrama de Voronoi ' que é o (N log N + log m).

Gotta correr para um funeral em um segundo, mas se você quebrar seus polígonos para baixo em subpolies convexas, existem algumas otimizações que você pode fazer. Você pode fazer uma busca binária em cada poli para encontrar o vértice mais próximo, e então eu acreditam o ponto mais próximo deve ser tanto que vértice, ou uma ponta adjacente. Isto significa que você deve ser capaz de fazê-lo em log(log m * n) onde m é o número médio de vértices em um poli, e n é o número de Polies. Este é tipo de hastey, para que ele pudesse estar errado. Vai dar mais detalhes mais tarde, se quisesse.

Você poderia começar comparando a distância entre as caixas delimitadoras. Testando a distância entre retângulos é mais fácil do que testar a distância entre polígonos, e você pode eliminar imediatamente quaisquer polígonos que são mais de nearest_rect + afastado its_diagonal (possivelmente você pode refinar que mesmo mais). Em seguida, você pode testar os polígonos restantes para encontrar o polígono mais próximo.

Existem algoritmos para encontrar polígono proximidade - Tenho certeza de que a Wikipedia tem uma boa revisão deles. Se bem me lembro, aqueles que só permitem polígonos convexos são substancialmente mais rápido.

Eu acredito que o que você está procurando é o algoritmo A *, a sua utilização no pathfinding.

A abordagem ingênua é encontrar a distância entre o vermelho e 50 objetos azuis - então você está olhando para 50 3d cálculos Pitágoras + triagem para encontrar a resposta. Isso só é realmente trabalho para encontrar a distância entre pontos centrais embora.

Se você quiser polígonos arbitrários, talvez o seu melhor melhor é uma solução raytracing que emite raios a partir da superfície do polígono vermelho em relação ao normal, e relatórios quando outro polígono é hit.

Um trabalho força híbrida - poderíamos encontrar a distância entre os pontos centrais, assumindo que tinha alguma noção do tamanho relativo dos polígonos azuis, poderíamos abater o conjunto de resultados para o mais próximo entre as pessoas, em seguida, usar raytracing para estreitar baixo o polígono realmente mais próximo (s).

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top