How to find the nearest point in the perimeter of a rectangle to a given point?

Question

This is a language-agnostic question. Given a rectangle's dimensions with l,t,w,h (left, top, width, height) and a point x,y, how do I find the nearest point on the perimeter of the rectangle to that point?

I have tried to resolve it in Lua, but any other language would do. So far this is my best effort:

local function nearest(x, a, b)
  if a <= x and x <= b then
    return x
  elseif math.abs(a - x) < math.abs(b - x) then
    return a
  else
    return b
  end
end

local function getNearestPointInPerimeter(l,t,w,h, x,y)
  return nearest(x, l, l+w), nearest(y, t, t+h)
end

This works for a point outside of the perimeter or in the perimeter itself. But for points inside of the perimeter it fails (it just returns x,y)

My gut tells me that the solution should be simple, but I don't seem to find it.

Droopy

Answer 1

This time I'm trying to catch the minimum distance of the point toward any side of the rectangle.

local abs, min, max = math.abs, math.min, math.max

local function clamp(x, lower, upper)
  return max(lower, min(upper, x))
end

local function getNearestPointInPerimeter(l,t,w,h, x,y)
  local r, b = l+w, t+h

  x, y = clamp(x, l, r), clamp(y, t, b)

  local dl, dr, dt, db = abs(x-l), abs(x-r), abs(y-t), abs(y-b)
  local m = min(dl, dr, dt, db)

  if m == dt then return x, t end
  if m == db then return x, b end
  if m == dl then return l, y end
  return r, y
end

Yim

Unfortunately, it doesn't. Your algorithm returns the coordinates of the nearest corner. The nearest point in the perimeter is not always one of the corners. – Droopy

I edited my answer with another algorithm. I tested it with some values on lua.org/cgi-bin/demo and it seems to work well. – Yim

Sorry, I don't think it works. I'm getting very random values - sometimes even outside of the rectangle itself. – Droopy

Which values do you used? I tried points inside and outside and for me it works – Yim

I think I fixed bug. Please revert if it's not really any better. – Anarthrous

@DavidCary I modified my answer as you suggested (your edit was rejected) – Yim

Thanks Keeper, this works magnificently. Do you mind if I edit your answer to make it more Lua-like? – Droopy

Edits done. I think it looks gorgeous. Thanks again. – Droopy

Very nice edit! I wrote the more "agnostic" version so anyone not proficient with Lua could understand the solution easier :-) – Yim

Answer 2

Let C1,C2,C3,C4 be the vertices of the rectangle.
From the given point A which you have, draw the 2 lines which are
perpendicular to the sides of the rectangle. Let B1, B2, B3, B4
be their intersecting points with the lines determined by the
sides of the rectangle (some of these Bk may coincide too
e.g. if A = Ck for some k). Your solution is one of the points Bk
or one of the points Ck, just brute-force check the 8 points
(again, some of these 8 points may coincide but that doesn't matter).

Billings

some or all may also fail to exist, consider rectangle 0,0,1,1 and point 2,2 – Raymund

OK, I edited my answer, I believe this works. I just need to prove it :) which should not be too hard unless my intuition played a trick on me. – Billings

Yes, OK, the proof is trivial if one breaks the plane into 9 sectors (which happens if one lengthens the sides of the rectangle) and thinks where point A may lie (in which sector). – Billings

I would really prefer something that doesn't require brute-forcing all the possible candidates. This piece of code is going to be used in a time-critical path of the library I am building (collision detection) so time is of the essence. – Droopy

@Raymund Fail to exist - no. I meant these Bk - the intersecting points with the lines determined by the rectangle's sides, not with the sides themselves. – Billings

@Droopy Then 1) break the plane into these 9 sectors which I mentioned, see in which sector point A is, give your answer directly based on that. But I think this would be more time-consuming than 2) always calculating the 8 points and just checking the 8 points at the end (which is an O(1) operation anyway). I would always choose 2) (based on my previous experience). A more general solution doesn't mean slower in all cases. This is my opinion. – Billings

@peter.petrov, well you use the term "line" in a very confusing manner -- there are only 2 lines perpendicular to the sides of a rectangle; there may be up to 4 such line segments though (and hence my assumption you use "line" to mean "line segment"). – Raymund

@Raymund I spoke in general. If you have 1 point and 4 distinct lines in a plane you generally have 4 perpendicular lines from the point to the given 4 lines. But here, as sides of the rectangle are parallel in pairs, yes, indeed you have only 2 perpendicular lines (which makes the task a bit simpler actually). Anyway, maybe I didn't explain it very well. – Billings

Answer 3

Another possible algorithm (similar to my 1st answer) can be found here - the one from Dinre.

Calculating the distance between polygon and point in R

Looks quite simple, actually it is a simplified (maybe better) version of my 1st answer here.

Find the two nearest rectangle vertices Ci and Cj to the given point A.

Find the point M where the perpendicular line from A to the line (Ci,Cj) crosses the line (Ci,Cj).

Your solution is either Ci or Cj or M.

Seems to me like this works for all cases (no matter where the point A lies in the plane).

Billings

That is a good alternative. I believe that is what @Yim is doing (implicitly) on his answer. – Droopy

I didn't look at this code. Most probably it is so. The implementation should be trivial if you use this algorithm. I can write it in Java or C# or in something I know some time later ;) I don't know your language really. Anyway, good luck. – Billings

Answer 4

Are you looking for something like this? Inspired by Keeper's code:

local function getNearestPointInPerimeter(l,t,w,h, x,y)
  -- x axis increases to the right
  -- y axis increases down
  local r = l + w
  local b = t + h
  local inside = true -- unless later proven otherwise
  -- if the point (x,y) is outside the rectangle,
  -- push it once to the nearest point on the perimeter, or
  -- push it twice to the nearest corner.
  if x < l then x = l; inside = false; end
  if x > r then x = r; inside = false; end
  if y < t then y = t; inside = false; end
  if y > b then y = b; inside = false; end
  -- if the point (x,y) is inside the rectangle,
  -- push it once to the closest side.
  if inside then
      local dt = math.abs (y - t)
      local db = math.abs (y - b)
      local dl = math.abs (x - l)
      local dr = math.abs (x - r)
      if dt <= db and dt <= dl and dt <= dr then
        y = t
      elseif db <= dl and db <= dr then
        y = b
      elseif dl <= dr then
        x = l
      else
        x = r
      end
  end
  return x,y
end

Anarthrous

Thanks for answering, I will take Keeper's answer. – Droopy

Answer 5

Thanks for the question and answers! Here is my python-translated version of the chosen answer in case anyone needs it. The only custom part is the clamp in-line function definition using lambda.

I used this successfully in a GUI with Qt's QRect and QPoint to make sure something showed up in a QGraphcsView.

def getNearestPointInPerimeter(self, left, top, width, height, x, y):
    right = left + width
    bottom = top + height

    clamp = lambda value, minv, maxv: max(min(value, maxv), minv)
    x = clamp(x, left, right)
    y = clamp(y, top, bottom)

    dl = abs(x - left)
    dr = abs(x - right)
    dt = abs(y - top)
    db = abs(y - bottom)
    m = min(dl, dr, dt, db)

    if m == dt:
        result = (x, top)
    elif m == db:
        result = (x, bottom)
    elif m == dl:
        result = (left, y)
    else:
        result = (right, y)

    return result

Fall

Answer 6

For those looking for the Keeper's answer in C#

public static Point GetNearestPointInPerimeter(Point point, Rectangle rectangle)
{
    point.X = Math.Max(rectangle.Left, Math.Min(rectangle.Right, point.X));
    point.Y = Math.Max(rectangle.Top, Math.Min(rectangle.Bottom, point.Y));

    var dl = Math.Abs(point.X - rectangle.Left);
    var dr = Math.Abs(point.X - rectangle.Right);
    var dt = Math.Abs(point.Y - rectangle.Top);
    var db = Math.Abs(point.Y - rectangle.Bottom);

    var m = new[] { dl, dr, dt, db }.Min();

    if (m == dt) return new Point(point.X, rectangle.Top);
    if (m == db) return new Point(point.X, rectangle.Bottom);
    if (m == dl) return new Point(rectangle.Left, point.Y);
    return new Point(rectangle.Right, point.Y);
}

Toxophilite