Procurando por um algoritmo eficiente encontrar rapidamente a linha mais próxima (definida pela distância perpendicular) para um ponto arbitrário

Question

Eu tenho um grande conjunto de linhas em 2D com um ponto de partida conhecido e ponto final, e gostaria de encontrar o mais próximo (definido pela distância perpendicular) dessas bordas (ou a extensão dessas bordas passam de seus pontos de início e fim) para um ponto arbitrário.

O melhor que fiz até agora é gerar um conjunto de pontos de amostra ao longo de cada linha e usar uma kd-tree para resolver o problema vizinho mais próximo para os pontos - i.E. Encontre o ponto de amostra da linha mais próxima para o ponto de consulta.Mas isso é impreciso e precisa de um grande número de amostras para longas filas.

Eu vi isso: algoritmo para a borda mais próximadetecção em relação a um ponto (em todas as direções)

Mas dependia de um método de varredura e um pequeno número de linhas de comprimento finito.

Answer 1

Todas as suas linhas definem uma subdivisão planária , onde cada região poligonal é delimitada por um número finito de segmentos ou raios de linha. Então, a princípio você precisa encontrar uma região (provavelmente infinita), contendo um ponto de consulta e, em seguida, você poderá selecionar sua linha limite com distância mínima deste ponto.

Há muitas maneiras de pré-processar uma subdivisão planária para resolver o Problema de localização do ponto com complexidade de tempo logarítmico. Alguma estrutura de dados hierárquicos é tipicamente concebida, que pode ser percorrida para qualquer ponto de consulta, e é provado, que o comprimento do caminho Traverse é limitado por $ O (log (n)) $ , onde $ n $ é o número de regiões. Como @pseudônimo mencionado em comentários, você também pode usar Particionamento de espaço binário (BSP) para construir um BSP Tree - também é uma estrutura de dados hierárquica (árvore binária), que permitirá que você encontre eficientemente uma região, contendo um ponto de consulta. Parece que seu problema é adequado para esta abordagem BSP.

desculpe dizer, você pode obter regiões com $ o (n) $ segmentos de limite / raios, onde $ n $ é o número de linhas. Para superar essa dificuldade, você pode subdividir ainda cada região em Diagrama Voronoi , generalizado para seus segmentos de limite e raios. É fácil ver que o número total de tais regiões refinadas será limitado por $ o (n ^ 2) $ , que ainda lhe dá complexidade de tempo logarítmico para a linha mais próxima procurar. No entanto, em média, essas regiões com muitos segmentos / raios de fronteira compõem uma pequena fração de todas as regiões - por isso, em média, você ainda poderá selecionar rapidamente o segmento / raio de limite mais próximo apenas por loop sobre a fronteira da região.

---

.

Se você quiser saber mais sobre propriedades gerais da estrutura geométrica em que você está trabalhando - faz sentido ler Esta página wiki.

Answer 2

Eu posso ter entendido mal seu objetivo - você assume que as bordas continuam em ambas as direções, apesar de serem definidas por 2 pontos específicos ao longo deles?Eu assumo assim porque você diz que a distância é definida pela distância perpendicular.Nesse caso, como sobre isso -
1. Para cada segmento de linha, calcule o ângulo.
2. Desenhe uma linha imaginária que passe pelo seu ponto arbitrário em um ângulo que seja perpendicular ao segmento de linha.
3. Encontre o ponto de interseção entre o segmento de linha e a nova linha imaginária, encontre a distância entre esse ponto e seu ponto arbitrário.Mantenha a menor distância.
Se as linhas não são infinitamente longas, quando você verificar a distância, verifique min (distância ao ponto de partida, distância ao ponto final).