calculating distance between a point and a rectangular box (nearest point)

Question

is there a easy formula to calculate this? i've been working on some math but i can only find a way to calculate the distance directed to the center of the box, not directed to the nearest point.. are there some resources on this problem?

Beret

Is the box axis aligned? references to solutions for AABB and OBB are here – Klara

Answer 1

Here is a single formula that avoids all the case logic. (I happen to be working in JS right now, so here's a JS implementation). Let rect = {max:{x:_, y:_}, min:{x:_, y:_}} and 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);
}

Explanation: This breaks down the problem into calculating the x distance dx and the y distance dy. It then uses distance formula.

For calculating dx, here is how that works. (dy is analogous)

Look at the tuple being provided to the max function: (min-p, 0, p-max). Let's designate this tuple (a,b,c).

If p is left of min, then we have p < min < max, which means the tuple will evaluate to (+,0,-), and so the max function will correctly return a = min - p.

If p is between min and max, then we have min < p < max, which means the tuple will evaluate to (-,0,-). So again, the max function will correctly return b = 0.

Lastly, if p is to the right of max, then we have, min < max < p, and the tuple evaluates to (-,0,+). Once again, Math.max correctly returns c = p - max.

So it turns out all the case logic is taken care of by Math.max, which leads to a nice 3-line, control-flow-free function.

Kenya

+1 This is a very nice, concrete solution. If the box is not oriented with the coordinate axes, it can still be used by rotating the problem. It doesn't really avoid "all the case logic"; it captures it (in each axis) with a single call to Math.max. I believe it even generalizes to 3D by simply adding an analogous dz component. – Enormous

what if box has rotation? – Hunyadi

The last line could also be return Math.hypot(dx, dy);. This will usually be slower, but reduces the risk of underflow or overflow for extreme values of dx and/or dy. – Enormous

@M.kazemAkhgary I think it will fail for rotation. – Gabler

Yes, it will fail for rotation. You will either need to rotate / rotate back, or do the math so that it is parallel to the axes, or find a different solution. – Kenya

This is doing nearest vertex, correct? It's more complicated if you're trying to calculate the nearest distance to a side of the rectangle. – Nickelic

@JoseSolorzano This is correct for an axis aligned box. – Bathsheb

The Java version of this looks like: 'calculateDistanceFromRectange(Rect rect, int x, int y){ int dx = Math.max(0,Math.max(rect.left - x, x - rect.right)); int dy = Math.max(0,Math.max(rect.top - y, y - rect.bottom)); return Math.sqrt(dxdx + dydy); }' – Misdeed

Answer 2

I think you need to analyze cases; there's no single formula. It's easier to illustrate in two dimensions:

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

The edges of the box (extended) divide the outside into 9 regions. Region 0 (inside the box) is solved by computing the distance to each edge and taking the minimum. Every point in region 1 is closest to the top left vertex, and similarly for regions 3, 6, and 8. For regions 2, 4, 5, and 7, you need to find the distance from the point to the closest edge, which is a fairly simple problem. You can determine which region a point is in by classifying it with respect to each edge. (It's easier to see how to do this by directing the edges say, counter-clockwise.) This will also tell you if the point is inside the box.

In 3D, the logic is exactly the same except that you classify with respect to the six faces and you have more cases.

The problem is simpler if the edges of the box are parallel to the coordinate axes.

Enormous

Answer 3

Let's say that the point is named P and ABCD is our rectangle. Then the problem can be decomposed into the following set of subproblems:

(1) Develop a function dist(P, AB) that calculates the distance between a point P and an arbitrary segment AB.

(2) Calculate four distances between your point P and each side of the rectangle (each side is a segment) and take the shortest of the four

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

That's your answer.

Now, we need to know how to calculate the distance between point P and an arbitrary segment AB, i.e. how to calculate dist(P, AB). This is done as follows

(1) Perform a perpendicular projection of the point P to the line AB. You get the new point P' on AB.

(2) If P' lies between A and B, then dist(P, AB) is the distance between P and P'.

(3) Otherwise, dist(P, AB) is the distance between P and either A or B, whichever is shorter.

That's it. There are some obvious ways to optimize the procedure, but even if implemented literally, it will work very well already.

P.S. Of course, one can ask how to perform a projection of a point to a line. I'll leave it as an exercise to the reader :)

Vltava

This is better than the top-voted answer by MultiRRomero because that will fail for rotation cases. – Gabler

An "exercise to the reader" might be funny but is not really helpful, as on stackoverflow a complete answer is prefered. – Alderson

It fails if the point is inside the rectangle. You can check it if the sign of z axe of the vectorial product (PP') x (AB) has the same sign for all four segments (AB, BC, CD, DA) – Diver

Answer 4

Kikito's answer is not correct, in fact if P is in the regions 2, 4, 5 or 7 of Ted Hopp's scheme, it returns the minimum distance from the vertices, which is different (bigger) from the minimum distance from the edges.

I would fix kikito's function distance_aux by returning 0 instead of min(p - lower, upper - p), and everything works apart from the 0 region where P is inside the box. In my opinion that region should be managed separately, depending on what you want to achieve, whether the distance from the area or the distance from the perimeter of the box. If you want to obtain the distance from the area of the box, I would say that it is zero when the point is inside the box.

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

Gradatim

I think this answer considers your cases. what are your thoughts? – Gabler

Answer 5

Lightly optimized C# alternative (although there should probably be some tolerance when comparing doubles against 0). I also recommend creating some kind of Rect or Point extension methods for these.

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;
        }
    }
}

Lusatia

Answer 6

For AABBs:

Maybe not the best performing, but certainly the simplest method:

p = your point

c = centre of the cube

s = half size of the cube

r = the point we are looking for

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

Osage

If you keep the center of the cube constant and p constant but rotate the cube then the closest point on the cube should move around. However your formula doesn't take into account cube orientation so it is clearly wrong. – Overmatch

If you do a world to local transform beforehand this works for non-AABBs as well + you can skip the "c" part alltogether. – Beyer

Answer 7

This is easy to achieve with dot products. In fact it has been answered in 3d already for the non axis aligned case.

https://mcmap.net/q/340471/-how-to-find-the-closest-point-on-a-right-rectangular-prism-3d-rectangle

But in 2D you can achieve the same

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
}

The function to return the closest point

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;
}

Overmatch

Answer 8

For the AABB I believe this is a bit more straightforward:

function clamp(value: number, min: number, max: number) {
    return Math.max(min, Math.min(value, max));
}

type Point = { x: number; y: number };
type Rect = { x: number; y: number; width: number; height: number };

export function rectDistance(point: Point, rect: Rect) {
    const left = rect.x;
    const top = rect.y;
    const right = rect.x + rect.width;
    const bottom = rect.y + rect.height;

    const nearestX = clamp(point.x, left, right);
    const nearestY = clamp(point.y, top, bottom);

    const dx = point.x - nearestX;
    const dy = point.y - nearestY;

    return Math.sqrt(dx * dx + dy * dy);
}

Quinquefid

Answer 9

Is this a 3D box or a 2D rectangle? Either way you're probably best off getting the point-line (for 2D) or point-plane (3D) distance for each side, then selecting the minimum.

Edit: there's a much better way described here (last post). It involves transforming your point coordinates into box space, then "saturating" the coordinates with the box size to find the point on the box closest to the point. I haven't tried it, but it looks right to me.

Dietsche

Come to think of it, you'll need to check that the nearest point in the plane is actually on the box... – Dietsche

The referenced post has miraculously disappeared. :/ Oh, how I wish I could find a cached version. – Industrialize

Well I’m sorry but if the link is dead and the information can’t be found, this needs downvoting. – Chelton

MS seem to have restructured the forum. The new link is: xboxforums.create.msdn.com/forums/t/58243.aspx – Thad

Both the link in the answer and the corrected link in the comment above are broken. – Monsour

Answer 10

I have been looking for this and I think I have a solution, for the case on which the box is axis-aligned (a fairly common case)

I believe that in that case you can calculate the distance like this:

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

This can be extended to z, of course.

Unscientific

the third return in distanace_aux should return 0 (if p is between lower and upper, the distance is 0) – Diver