algorithm - sacar - distancia entre puntos

Distancia desde un punto a un polígono.

Question

Estoy tratando de determinar la distancia desde 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 más pequeña que una constante d definida por el usuario, el procedimiento debe devolver True ; False contrario.

He encontrado una pregunta similar: Distancia desde un punto a un poliedro o un polígono . 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 aquel.

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

Se agradecería cualquier algoritmo, código o sugerencias para que busque en Google.

Answer 1

¿Necesitas rápido o simple?
¿Tiene que ser siempre absolutamente correcto en los casos perimetrales o será lo suficientemente bueno la mayor parte del tiempo estará bien?

Las soluciones típicas son 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 podrían no ser adyacentes) y luego verifique las intersecciones de punto a línea para cada segmento.

Para formas complejas grandes, también puede almacenar cuadros de delimitación de polígonos aprox. (Rectangulares o hexágonos) y encontrar el lado más cercano antes de verificar más detalles.

También puede necesitar un código para manejar el caso especial de exactamente en una línea.

Answer 2

Puedo ayudarte con estos consejos:

• La distancia se puede calcular utilizando la entrada de Wikipedia , incluso con un código de código no probado.
• El borde interior / exterior se puede resolver con esta publicación de pila y enlaces

y algunas observaciones:

• debe verificar solo los puntos más cercanos, como señala la respuesta de Martin Beckett, ya que otro segmento puede "proyectarse" muy cerca, pero en realidad no está tan cerca como sea necesario.

Answer 3

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

Answer 4

Corregido según el comentario de @Jcaron.

Su mejor apuesta 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 debe encontrar la distancia de un punto a una línea seleccionando los puntos arbitrarios P1 y P2 en la línea (puede ser conveniente utilizar sus puntos finales). Luego toma el vector de P1 a tu punto P0 y encuentra (P2-P1) . (P0 - P1) (P2-P1) . (P0 - P1) donde . es el producto punto. Divida este valor por ||P2-P1||^2 y obtenga un valor r .

Ahora, si eligió P1 y P2 como sus puntos, simplemente puede verificar si r está 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, entonces su distancia es ||P0-P1|| .

Si 0<r<1 , entonces 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(p2 - 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)