Buscar un algoritmo eficiente encontrar rápidamente la línea más cercana (definida por la distancia perpendicular) a un punto arbitrario

Question

Tengo un gran conjunto de líneas en 2D con un punto de inicio y punto final conocido, y me gustaría encontrar el más cercano (definido por distancia perpendicular) de esos bordes (o la extensión de esos bordes más allá de sus puntos de inicio y final.) a un punto arbitrario.

Lo mejor que he hecho hasta ahora es generar un conjunto de puntos de muestra a lo largo de cada línea y usar un árbol KD para resolver el problema del vecino más cercano para los puntos: I.E. Encuentre el punto de muestra de línea más cercano al punto de consulta.Pero esto es inexacto y necesita una gran cantidad de muestras para líneas largas.

He visto esto: algoritmo para el borde más cercanoDetección con respecto a un punto (en todas las direcciones)

Pero se basó en un método de barrido y un pequeño número de líneas de longitud finita.

Answer 1

Todas sus líneas definen una subdivisión de Planar , donde cada región poligonal está limitada por un número finito de segmentos de línea o rayos. Por lo tanto, al principio necesita encontrar una región (probablemente infinita), que contenga un punto de consulta, y luego podrá seleccionar su línea de límite con una distancia mínima de este punto.

Hay muchas maneras de preprocesar una subdivisión plana para resolver la problema de ubicación de punto Con complejidad de tiempo logarítmica. Una estructura de datos jerárquicos se idea normalmente, que se puede atravesar para cualquier punto de consulta, y está probado, que la longitud de la ruta transversal está limitada por $ O (log (n)) $ , donde $ n $ es el número de regiones. Como @Pseudóndon, se menciona en los comentarios, también puede usar partición de espacio binario (BSP) para construir un Árbol BSP: también es una estructura de datos jerárquicos (árbol binario), que le permitirá encontrar eficientemente una región, que contenga un punto de consulta. Parece que su problema se adapta bien a este enfoque BSP.

Lamento decir, puede obtener regiones con $ o (n) $ segmentos / rayos de límites, donde $ n $ es el número de líneas. Para superar esta dificultad, puede superar aún más a cada región en diagrama de voronoi , generalizado por sus segmentos de límites y Rayos. Es fácil ver que el número total de regiones tan refinadas estará limitada por $ o (n ^ 2) $ , que aún le brinda complejidad de tiempo logarítmico para la línea más cercana buscar. Sin embargo, en promedio, estas regiones con muchos segmentos / rayos de límites conformarán una pequeña fracción de todas las regiones, por lo que, en promedio, aún podrá seleccionar rápidamente el segmento / ray del límite más cercano, simplemente al bucle sobre el límite de la región.

---

Si desea saber más sobre las propiedades generales de la estructura geométrica con la que está trabajando, tiene sentido leer esta página wiki.

Answer 2

Puede que haya malinterpretado su objetivo, ¿asuma que los bordes continúan en ambas direcciones, aunque se definen por 2 puntos específicos a lo largo de ellos?Supongo que sí, porque dice que la distancia se define por distancia perpendicular.En cuánto caso, ¿qué hay de esto -
1. Para cada segmento de línea, calcule el ángulo.
2. Dibuja una línea imaginaria que pase por su punto arbitrario en un ángulo que sea perpendicular al segmento de línea.
3. Encuentre el punto de intersección entre el segmento de línea y la nueva línea imaginaria, encuentre la distancia entre ese punto y su punto arbitrario.Mantenga la distancia más baja.
Si las líneas no son infinitamente largas, cuando comprueba la distancia, marque MIN (distancia al punto de inicio, distancia al punto final).