вычисление расстояния между точкой и прямоугольником (ближайшая точка)

Question

Есть ли простая формула для расчета этого?я работал над какой-то математикой, но я могу только найти способ рассчитать расстояние, направленное к центру поля, а не к ближайшей точке ... есть ли ресурсы по этой проблеме?

Answer 1

Вот одна формула, которая избегает всей логики регистра.(Я сейчас работаю в JS, так что вот реализация JS).Пусть 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);
}

Объяснение: Это разбивает задачу на вычисление расстояния x dx и расстояния y dy.Затем он использует формулу расстояния.

Для расчета dx, вот как это работает.(dy аналогично)

Посмотрите на кортеж, предоставляемый функции max: (min-p, 0, p-max).Обозначим этот кортеж (a,b,c).

Если p осталось от min, тогда p (+,0,-), и поэтому функция max вернёт правильно a = min - p.

Если p находится между min и max, то у нас есть min

(-,0,-).Итак, еще раз, функция max будет правильно возвращать b = 0.

Наконец, если p находится справа от max, то мы имеем, min (-,0,+).Еще раз, Math.max корректно возвращает c = p - max.

Таким образом, получается, что Math.max заботится обо всей логике кейса, что приводит к хорошей трехстрочной функции без контроля потока.

Answer 2

Я думаю, вам нужно проанализировать случаи;нет единой формулы.Проще проиллюстрировать это в двух измерениях:

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

Края коробки (расширенные) делят наружу на 9 областей.Область 0 (внутри рамки) решается путем вычисления расстояния до каждого ребра и взятия минимума.Каждая точка в области 1 находится ближе всего к верхней левой вершине, и аналогично для областей 3, 6 и 8. Для областей 2, 4, 5 и 7 вам нужно найти расстояние от точки до ближайшего ребра, котороеэто довольно простая проблема.Вы можете определить, в какой области находится точка, классифицируя ее по каждому ребру.(Легче понять, как это сделать, направив края, скажем, против часовой стрелки.) Это также скажет вам, находится ли точка внутри рамки.

В 3D логика точно такая же, за исключениемвы классифицируете по шести граням, и у вас будет больше случаев.

Проблема проще, если края рамки параллельны осям координат.

Answer 3

Скажем, точка называется P, а ABCD - это наш прямоугольник.Затем задачу можно разложить на следующий набор подзадач:

(1) Разработать функцию dist(P, AB), которая вычисляет расстояние между точкой P и произвольным отрезок AB.

(2) Рассчитайте четыре расстояния между вашей точкой P и каждой стороной прямоугольника (каждая сторона является отрезком) и выберите самое короткое изчетыре

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

Это ваш ответ.

Теперь нам нужно знать, как рассчитать расстояние между точкой P и произвольным отрезком AB, т.е. как рассчитать dist(P, AB).Это делается следующим образом

(1) Выполнение перпендикулярной проекции точки P на линию AB.Вы получаете новую точку P' на AB.

(2) Если P' лежит между A и B, тогда dist(P, AB) - это расстояние междуP и P'.

(3) В противном случае dist(P, AB) - это расстояние между P и A или B, в зависимости от того, что меньше.

Вот и все.Есть несколько очевидных способов оптимизировать процедуру, но даже если она реализована буквально, она уже будет работать очень хорошо.

PS Конечно, можно спросить, как выполнить проекцию точки на линию.Я оставлю это как упражнение читателю:)

Answer 4

Слегка оптимизированная альтернатива C # (хотя, вероятно, должна быть некоторая терпимость при сравнении значений типа double с 0). Я также рекомендую создать какие-то методы расширения Rect или Point для них.

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 5

Ответ Kikito неверен, фактически, если P находится в областях 2, 4, 5 или 7 схемы Теда Хоппа, он возвращает минимальное расстояние от вершин, которое отличается (больше) от минимального расстояния от края.

Я бы исправил функцию кикито distance_aux, возвращая 0 вместо min (p - нижний, верхний - p), и все работает отдельно от 0 области, где P находится внутри блока. На мой взгляд, этот регион должен управляться отдельно, в зависимости от того, чего вы хотите достичь, будь то расстояние от области или расстояние от периметра бокса. Если вы хотите получить расстояние от области рамки, я бы сказал, что оно равно нулю, когда точка находится внутри рамки.

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 6

Этого легко достичь с помощью точечных продуктов. На самом деле уже дан ответ в 3d для случая без выравнивания по оси.

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

Но в 2D вы можете добиться того же

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
}

Функция для возврата ближайшей точки

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 7

Для AABB:

Возможно, не самый эффективный, но, безусловно, самый простой метод:

p = ваша точка

с = центр куба

с = половинный размер куба

r = точка, которую мы ищем

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

Answer 8

Я искал это, и я думаю, что у меня есть решение для случая, когда прямоугольник выровнен по оси (довольно распространенный случай)

Я считаю, что в этом случае вы можете рассчитать расстояние следующим образом:

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

Конечно, это можно расширить до z.

Answer 9

Это 3D коробка или 2D прямоугольник? В любом случае вам лучше всего получить точечную линию (для 2D) или точечную плоскость (3D) для каждой стороны, а затем выбрать минимум.

Редактировать: здесь описан гораздо лучший способ здесь (последнее сообщение).Он включает в себя преобразование координат вашей точки в пространство блока, а затем «насыщение» координат размером блока, чтобы найти точку на блоке, ближайшем к точке.Я не пробовал, но мне кажется, что это правильно.