Distancia de un punto a un polígono

Question

Estoy tratando de determinar la distancia de un punto a un polígono en el espacio 2D. El punto puede estar dentro o fuera del polígono; El polígono puede ser convexo o cóncavo.

Si el punto está dentro del polígono o fuera del polígono con una distancia menor que una constante definida por el usuario d, el procedimiento debe devolver True; False de lo contrario.

He encontrado una pregunta similar: Distance from a point to a polyhedron or to a polygon. Sin embargo, el espacio es 2D en mi caso y el polígono puede ser cóncavo, por lo que es de alguna manera diferente de ese.

Supongo que debe haber un método más simple que compensar el polígono por d y determinar si está dentro o fuera del polígono.

Algún algoritmo, código o indirectas para mí para googlear sería apreciado.

Answer 1

Su mejor opción es recorrer todas las líneas y encontrar la distancia mínima de un punto a un segmento de línea.

para encontrar la distancia de un punto a un segmento de línea, primero se encuentre la distancia de un punto a una línea seleccionando puntos arbitrarios P1 y P2 en la línea (que podría ser una buena idea usar sus puntos finales). A continuación, tome el vector de P1 a su punto P0 y encuentre (P2-P1) . (P0 - P1) donde . es el producto escalar. Divida este valor por ||P0-P1||^2 y obtenga un valor r.

Ahora bien, si usted escogió P1 y P2 como sus puntos, sólo tiene que comprobar si r es entre 0 y 1. Si r es mayor que 1, entonces P2 es el punto más cercano, por lo que su distancia es ||P0-P2||. Si r es menor que 0, entonces P1 es el punto más cercano, por lo que su distancia es ||P0-P1||.

Si 0<r<1, a continuación, su distancia es sqrt(||P0-P1||^2 - r * ||P2-P1||^2)

El pseudocódigo es el siguiente:

for p1, p2 in vertices: 

    var r = dotProduct(vector(p2 - p1), vector(x - p1)) 
    //x is the point you're looking for 

    r /= magnitude(vector(x - p1)) 

    if r < 0: 
    var dist = magnitude(vector(x - p1)) 
    else if r > 1: 
    dist = magnitude(vector(p2 - x)) 
    else: 
    dist = sqrt(magnitude(vector(x - p1))^2 - r * magnitude(vector(p2-p1))^2) 

    minDist = min(dist,minDist) 

Answer 2

Si tiene una función de distancia de segmento punto a línea, puede usarla para calcular la distancia desde el punto a cada uno de los bordes del polígono. Por supuesto, debes verificar si el punto está dentro del polígono primero.

Answer 3

¿Necesita rápida o sencilla?
¿Tiene que ser siempre absolutamente correcto en las cajas de borde o lo suficientemente bueno la mayoría de las veces está bien?

La solución típica es encontrar la distancia a cada vértice y encontrar el par con los valores más pequeños (tenga en cuenta que para un punto fuera de un polígono convexo estos pueden no ser adyacentes) y luego controlar las intersecciones de punto a línea para cada segmento.

Para formas complejas grandes también puede almacenar cajas de polígono delimitadoras (rectangulares o hexágonos) y encontrar el lado más cercano antes de consultar más detalles.

Es posible que también necesite un código para manejar el caso especial de exactamente en una línea.

Answer 4

Te puedo ayudar con esto punteros:

• La distancia puede ser calculada usando Wikipedia entry, incluso con una cortada con tijeras sin probar de código.
• El interior/borde exterior puede ser resuelto con este Stack Post and links

y algunas observaciones:

• debe comprobar sólo los puntos más próximos, como Martin Beckett salidas puntuales respuesta, ya que otro segmento se puede "proyectar" muy cerca, pero en realidad no se está cerca de la necesidad.

Answer 5

puede hacer su programa de correr un poco más rápido mediante el uso de la trigonometría y la sentencia pecado