3d - vertical - optimizacion distancia minima

calcular la distancia entre un punto y una caja rectangular(el punto más cercano)

Question

¿Hay una fórmula fácil para calcular esto? He estado trabajando en algunas matemáticas pero solo puedo encontrar una manera de calcular la distancia dirigida al centro de la caja, no al punto más cercano ... ¿hay algunos recursos sobre este problema?

Answer 1

¿Es esta una caja 3D o un rectángulo 2D? De cualquier manera, es mejor que obtengas la distancia entre la point-line (para 2D) o point-plane (3D) para cada lado, luego seleccionando el mínimo.

Edición: hay una manera mucho mejor descrita here (última publicación). Implica transformar sus coordenadas de punto en espacio de cuadro, luego "saturar" las coordenadas con el tamaño del cuadro para encontrar el punto en el cuadro más cercano al punto. No lo he probado, pero me parece correcto.

Answer 2

Alternativa de C # ligeramente optimizada (aunque probablemente debería haber cierta tolerancia al comparar los dobles con 0). También recomiendo crear algún tipo de método de extensión Rect o Point para estos.

public static class GeometryUtils
{
    public static double Distance(Point point, Rect rect)
    {
        var xDist = MinXDistance(point, rect);
        var yDist = MinYDistance(point, rect);
        if (xDist == 0)
        {
            return yDist;
        }
        else if (yDist == 0)
        {
            return xDist;
        }

        return Math.Sqrt(Math.Pow(xDist, 2) + Math.Pow(yDist, 2));
    }

    private static double MinXDistance(Point point, Rect rect)
    {
        if (rect.Left > point.X)
        {
            return rect.Left - point.X;
        }
        else if (rect.Right < point.X)
        {
            return point.X - rect.Right;
        }
        else
        {
            return 0;
        }
    }

    private static double MinYDistance(Point point, Rect rect)
    {
        if (rect.Bottom < point.Y)
        {
            return point.Y - rect.Bottom;
        }
        else if (rect.Top > point.Y)
        {
            return rect.Top - point.Y;
        }
        else
        {
            return 0;
        }
    }
}

Answer 3

Creo que necesitas analizar los casos; No hay una fórmula única. Es más fácil de ilustrar en dos dimensiones:

1          2          3
    +-------------+
    |             |
4   |      0      |   5
    |             |
    +-------------+
6          7          8

Los bordes de la caja (extendidos) dividen el exterior en 9 regiones. La región 0 (dentro de la caja) se resuelve calculando la distancia a cada borde y tomando el mínimo. Cada punto en la región 1 es el más cercano al vértice superior izquierdo, y de manera similar para las regiones 3, 6 y 8. Para las regiones 2, 4, 5 y 7, debe encontrar la distancia desde el punto hasta el borde más cercano, que Es un problema bastante simple. Puede determinar en qué región se encuentra un punto clasificándolo con respecto a cada borde. (Es más fácil ver cómo hacer esto dirigiendo los bordes, en sentido contrario a las agujas del reloj). Esto también le dirá si el punto está dentro de la caja.

En 3D, la lógica es exactamente la misma, excepto que usted clasifica con respecto a las seis caras y tiene más casos.

El problema es más simple si los bordes de la caja son paralelos a los ejes de coordenadas.

Answer 4

Digamos que el punto se llama P y ABCD es nuestro rectángulo. Luego, el problema se puede descomponer en el siguiente conjunto de subproblemas:

(1) Desarrolle una función dist(P, AB) que calcula la distancia entre un punto P y un segmento arbitrario AB .

(2) Calcule cuatro distancias entre su punto P y cada lado del rectángulo (cada lado es un segmento) y tome la más corta de las cuatro

  distance = min(dist(P, AB), dist(P,BC), dist(P, CD), dist(P, DA))

Esa es tu respuesta.

Ahora, necesitamos saber cómo calcular la distancia entre el punto P y un segmento arbitrario AB , es decir, cómo calcular dist(P, AB) . Esto se hace de la siguiente manera

(1) Realice una proyección perpendicular del punto P a la línea AB . Obtienes el nuevo punto P'' en AB .

(2) Si P'' encuentra entre A y B , entonces dist(P, AB) es la distancia entre P y P'' .

(3) De lo contrario, dist(P, AB) es la distancia entre P y A o B , lo que sea más corto.

Eso es. Hay algunas formas obvias de optimizar el procedimiento, pero incluso si se implementa literalmente, ya funcionará muy bien.

PS Por supuesto, uno puede preguntar cómo realizar una proyección de un punto a una línea. Lo dejo como un ejercicio para el lector :)

Answer 5

Esto es fácil de lograr con productos de puntos. De hecho, ya se ha respondido en 3D para el caso no alineado con el eje.

https://.com/a/44824522/158285

Pero en 2D puedes conseguir lo mismo.

public struct Vector2 {
   double X; double Y

   // Vector dot product
   double Dot(Vector2 other)=>X*other.X+Y*other.Y;


   // Length squared of the vector
   double LengthSquared()=>Dot(this,this);

   // Plus other methods for multiplying by a scalar
   // adding and subtracting vectors etc
}

La función para devolver el punto más cercano.

public Vector2 ClosestPointTo
    (Vector2 q, Vector2 origin, Vector3 v10, Vector3 v01)
{
    var px = v10;
    var py = v01;


    var vx = (px - origin);
    var vy = (py - origin);


    var tx = Vector2.Dot( q - origin, vx ) / vx.LengthSquared();
    var ty = Vector3.Dot( q - origin, vy ) / vy.LengthSquared();


    tx = tx < 0 ? 0 : tx > 1 ? 1 : tx;
    ty = ty < 0 ? 0 : ty > 1 ? 1 : ty;

    var p = tx * vx + ty * vy + origin;

    return p;
}

Answer 6

He estado buscando esto y creo que tengo una solución para el caso en el que la caja está alineada con el eje (un caso bastante común)

Creo que en ese caso puedes calcular la distancia así:

function distance_aux(p, lower, upper)
  if p < lower then return lower - p end
  if p > upper then return p - upper end
  return min(p - lower, upper - p)
end

function distance(point, box)
  local dx = distance_aux(point.x, box.left, box.right)
  local dy = distance_aux(point.y, box.top, box.bottom)
  return sqrt(dx * dx + dy * dy)
end

Esto se puede extender a z, por supuesto.

Answer 7

La respuesta de Kikito no es correcta, de hecho, si P está en las regiones 2, 4, 5 o 7 del esquema de Ted Hopp, devuelve la distancia mínima de los vértices, que es diferente (más grande) de la distancia mínima de los bordes.

Arreglaría la función distance_aux de kikito devolviendo 0 en lugar de min (p - lower, upper - p), y todo funciona aparte de la región 0 donde P está dentro de la caja. En mi opinión, la región debe administrarse por separado, dependiendo de lo que quiera lograr, ya sea la distancia desde el área o la distancia desde el perímetro de la caja. Si desea obtener la distancia desde el área del cuadro, yo diría que es cero cuando el punto está dentro del cuadro.

function inside(point, box)
    return (point.x > box.left AND point.x < box.right AND point.y > box.top AND point.y < box.bottom)
end

function distance_aux(p, lower, upper)
    if p < lower then return lower - p end
    if p > upper then return p - upper end
    return 0
end

function distance(point, box)
    local dx = distance_aux(point.x, box.left, box.right)
    local dy = distance_aux(point.y, box.top, box.bottom)
    if (inside(point, box))
        return min(dx, dy)    // or 0 in case of distance from the area
    else
        return sqrt(dx * dx + dy * dy)
    endif
end

Answer 8

Para AABBs:

Tal vez no sea el mejor desempeño, pero ciertamente el método más simple:

p = tu punto

c = centro del cubo

s = la mitad del tamaño del cubo

r = el punto que estamos buscando

v = p - c;
m = max_abs(v);
r = c + ( v / m * s );

Answer 9

Aquí hay una fórmula única que evita toda la lógica del caso. (Resulta que estoy trabajando en JS en este momento, así que aquí hay una implementación de JS). Sea rect = {max:{x:_, y:_}, min:{x:_, y:_}} p={x:_, y:_}

function distance(rect, p) {
  var dx = Math.max(rect.min.x - p.x, 0, p.x - rect.max.x);
  var dy = Math.max(rect.min.y - p.y, 0, p.y - rect.max.y);
  return Math.sqrt(dx*dx + dy*dy);
}

Explicación: Esto divide el problema en el cálculo de la distancia x dx y la y distancia dy . A continuación, utiliza la fórmula de la distancia.

Para calcular dx , aquí está cómo funciona. ( dy es análogo)

Mire la tupla que se proporciona a la función max: (min-p, 0, p-max) . Designemos esta tupla (a,b,c) .

Si p está a la izquierda de min, entonces tenemos p <min <max, lo que significa que la tupla se evaluará a (+,0,-) , y la función max devolverá correctamente a = min - p .

Si p está entre min y max, entonces tenemos min <p <max, lo que significa que la tupla evaluará a (-,0,-) . Así que de nuevo, la función max devolverá correctamente b = 0 .

Por último, si p está a la derecha de max, entonces tenemos min <max <p, y la tupla se evalúa como (-,0,+) . Una vez más, Math.max devuelve correctamente c = p - max .

Así que resulta que Math.max se ocupa de toda la lógica del caso, lo que lleva a una buena función de 3 líneas, sin control ni flujo.