Para un punto en un polígono irregular, ¿cuál es la forma más eficiente de seleccionar el borde más cercano al punto?

Question

Dado un polígono irregular y un punto dentro de ese polígono, ¿cómo puedo determinar qué borde en el polígono está más cerca del punto?

I probable que tenga que ejecutar este cálculo para un gran conjunto de puntos dentro del polígono (por ejemplo 50-200 puntos).

Answer 1

1. Calcular punto más cercano en la línea que es tangente a cada borde del polígono.
2. Calcular el punto más cercano en cada segmento de línea (borde del polígono) hasta el punto en cuestión.
3. Calcule la distancia desde el punto más cercano en cada segmento de línea hasta el punto en cuestión.
4. Encuentra la distancia mínima. La poligonal correspondiente con la distancia mínima es la respuesta.

Cada paso de este algoritmo es el tiempo lineal (O (n)).

Éstos son las fórmulas básicas para cada uno de los pasos:

Calcular punto más cercano en la línea que es tangente a cada borde del polígono.

• Vamos el punto final de un borde de un polígono sea p1 = {x1, y1}.
• Deje que el otro punto final de un borde de un polígono sea p2 = {x2, y2}.
• Deje que el punto en el polígono que está analizando sea p3 = {x3,y3}.
• Sea u el porcentaje de la distancia entre p1 y p2, que es necesario para encontrar el punto en la línea formada por p1 y p2, tal que p1+u(p2-p1) = el punto en la línea más cercana a p3 (el segmento de línea entre este punto y p3 también pasa a ser perpendicular a la línea que pasa por p1 y p2).
• u = ((x3 - x1)(x2 - x1)+(y3 - y1)(y2 - y1))/((x2 - x1)^2 + (y2 - y1)^2)
• Deje que el punto más cercano a P3 en la línea formada por p1 y p2 ser conocido como pu = {xu, yu}
• xu = x1 + u (x2 - x1)
• yu = y1 + u (y2- y1)
• Y como hemos dicho antes pu = {xu, yu}
• Repita estos cálculos para cada borde del polígono (es decir, sustituir en nuevos p1s y p2s)

Calcule el punto más cercano en cada segmento de línea (borde del polígono) hasta el punto en cuestión.

El punto pu es solo el punto más cercano en el segmento de línea cuando 0 <= u <= 1. De lo contrario, el punto final apropiado del segmento de línea es el punto más cercano al punto en cuestión.Así, para cada pu, p1, p2, and u calculado en la etapa anterior haga lo siguiente:

• Let pc = {xc, yc} se denotará como el punto más cercano en el segmento de línea del borde de polígono para el punto en cuestión.
• IF u<0 THEN pc = p1
• ELSE IF u>1 THEN pc = p2
• ELSE pc = pu

calcular la distancia desde el punto más cercano en cada segmento de línea hasta el punto en cuestión.

• Distancia entre p3 y pc = `sqrt ((x3 - xc)^2 + (y3 - yc)^2)
• Repetir este cálculo para todos los PC

Encuentre la distancia minima. La poligonal correspondiente con la distancia mínima es la respuesta.

• Iterate a través de todas las distancias hasta que encuentres el más pequeño. El borde del polígono correspondiente es la respuesta.

Aquí es un diagrama para ayudarle a entender lo que los puntos y la terminología en este post representan:

....

Answer 2

Se este mensaje el SO para la inspiración distance from point within a polygon to polygon edge o éste Shortest distance between a point and a line segment

Answer 3

La respuesta correcta depende de la grande-cuadro estructura del problema: ¿qué sucede cuando se tienen en cuenta múltiples consultas? Supongo que cada consulta tratará con un punto diferente. Pero, ¿y el polígono? ¿Esperas recibir múltiples consultas para el mismo polígono? ¿O cada vez que el polígono es diferente?

Si cada consulta se aplica a un polígono diferente e impredecible, la única solución que tiene es esencialmente la inspección total de todos los bordes del polígono con una prueba de distancia punto a segmento para cada uno. Se puede optimizar de varias maneras [heurísticas] (para descartar las pruebas innecesarias al principio), pero en el peor de los casos no hay forma de evitar la prueba completa.

Sin embargo, si espera algún tipo de predictibilidad y estabilidad en el lado del polígono del problema (suficientes consultas puntuales al mismo polígono oa un conjunto fijo de polígonos), la situación cambia drásticamente. El mejor enfoque en este caso sería precompilar el diagrama de Voronoi basado en el borde dentro del polígono (s). Luego puede resolver el problema de ubicación de puntos (para el cual existen algoritmos eficientes conocidos) a fin de determinar en qué región de Voronoi cae el punto de consulta. Eso te dirá inmediatamente qué borde es el más cercano.

Este último es incomparablemente más eficiente cuando necesita manejar muchas consultas puntuales al mismo polígono (s), pero requiere un gran esfuerzo para implementarlo. Entonces, todo depende de qué tipo de solución necesites.

P.S. Veo que indicas en tu pregunta que vas a ejecutarlo para un gran conjunto de puntos para un solo polígono. Esto inmediatamente hace que la solución basada en el diagrama de Voronoi sea el camino a seguir.Los matices adicionales del algoritmo pueden depender de si ese gran conjunto de puntos es completamente conocido de antemano o llega punto por punto de manera impredecible.