How to find the nearest point in the perimeter of

问题:

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.

回答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

回答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).

回答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).

回答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

回答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