¿Cómo puedo encontrar el punto más cercano en un polígono a partir de un punto de

Question

Tengo un punto que puede ser dentro o fuera de un polígono, necesito encontrar el punto más cercano en el polígono límite desde el punto.

El punto(x,y) puede ser dentro o fuera del polígono, la distancia más corta entre el polígono ABCDE y el punto(x,y) es marcado como línea roja, el punto de intersección es el Punto (m,n). Necesito el valor de m y n.

He ABCDE y el Punto(x,y)

Answer 1

Usted puede conseguir con JSTS.

Verificación DistanceOp.js.

Answer 2

Una solución muy simple: resolver un equasion para cada par de poli vértices.

Un algoritmo para un segmento del polígono (gris en la imagen) con los puntos de un y b:

• Un vector es sólo un punto de coordenadas
• vector S(egment) = b - a
• vector N es la normal a S (-ys, xs)
• el vector P es de las coordenadas del punto

Desea comprobar la longitud de la normal desde el punto de Segmento y asegúrese de que el punto de destino está dentro del Segmento.

Aquí está el equasion desea resolver:

En la solución, me debe estar entre 0 y 1. Si es así, entonces la distancia es |en| y el punto es P + en, de lo contrario es el más cercano entre los vértices (a & b). A continuación, usted puede encontrar el punto más cercano entre aquellos para cada borde.

He aquí un código Javascript que busca la distancia más cercana, pero debe ser fácil de modificar para el punto más cercano:

function vlen(vector) {
  return Math.sqrt(vector[0]*vector[0] + vector[1] * vector[1]);
}

function vsub(v1, v2) {
  return [v1[0] - v2[0], v1[1] - v2[1]];
}

function vscale(vector, factor) {
  return [vector[0] * factor, vector[1] * factor];
}

function vnorm(v) {
  return [-v[1], v[0]];
}

function distance_to_poly(point, poly) {
  var dists = $.map(poly, function(p1, i) {
    var prev = (i == 0 ? poly.length : i) - 1,
        p2 = poly[prev],
        line = vsub(p2, p1);

    if (vlen(line) == 0)
      return vlen(vsub(point, p1));

    var norm = vnorm(line),
        x1 = point[0],
        x2 = norm[0],
        x3 = p1[0],
        x4 = line[0],
        y1 = point[1],
        y2 = norm[1],
        y3 = p1[1],
        y4 = line[1],

        j = (x3 - x1 - x2 * y3 / y2 + x2 * y1 / y2) / (x2 * y4 / y2 - x4),
        i;

      if (j < 0 || j > 1)
        return Math.min(
          vlen(vsub(point, p1)),
          vlen(vsub(point, p2)));

      i = (y3 + j * y4 - y1) / y2;

      return vlen(vscale(norm, i));
  });

  return Math.min.apply(null, dists);
}

Answer 3

Encontrar los dos puntos más próximos a su punto; solo hacer esto con pitágoras, pero no sqrt, usted no necesita la distancia, sólo la orden.

Trabajar el gradiente entre estos dos puntos (y1-y2)/(x1-x2) donde 1 es uno de los puntos y 2 es el otro. Esto es a partir de la solución de la forma y=mx+c para m para los dos puntos (ecuaciones simultáneas). A continuación, utilice uno de estos puntos para calcular c sustituyendo de nuevo en la ecuación y=m*x+c para uno de los dos puntos, vamos a usar más adelante.

Dividir -1 por este gradiente, llamado mn (calcula la pendiente de la normal, una línea perpendicular a la línea original), y luego calcular cn=y-mn*x, donde x e y son su punto inicial.

Usted entonces tiene dos líneas de lo que usted tiene que resolver las ecuaciones simultáneas y=mn*x+cn y y=m*x+c para x e y. Esa es su respuesta!

Answer 4

El algoritmo básico es comprobar cada segmento del polígono y encontrar el punto más cercano. Esta será la perpedicular punto (si es que en el segmento) o uno de los extremos.

Después de hacer esto para todos los segmentos, el de escoger el punto con la menor diferencia total.

Así que en tu ejemplo sería el de los segmentos:

• AB, exterior, pick B
• BC, en el interior, tratar de que el punto de
• CD, utside, trate de C
• DE, fuera de, tratar D
• EA, fuera, intenta Un

Cuando se comparan las diferencias, usted verá que la perpendicular desde el punto del segmento BC es la coincidencia más cercana. También se puede hacer esta comparación, en el mismo plazo.