# Find the closest point along a rectangle, given an another point and direction

Given a rectangle, and a point with a vector direction towards the rectangle. How can I find the closest point on the outside of that rectangle to the point in question?

• Can you explain more what you're asking? I'm really not getting it. – user9471 Sep 5 '11 at 5:46
• Let's say I have a character facing an object (a rectangle), and I draw an imaginary line from that character to the rectangle. I would like to know how I can tell which point along the outside of the rectangular object the line is touching. – onedayitwillmake Sep 5 '11 at 5:49
• They keyword to look up in Google is "AABB" (axis-aligned bounding box). If your "box" (rectangle) isn't axis-aligned yet, a simple transformation matrix - used on all items you care about, obviously - can be used first to change it into one. – Martin Sojka Sep 5 '11 at 7:30

One technique which you could use is called "ray casting". It is commonly used for rendering graphics, but has other applications such as line-of-sight (as you are wanting to do) and path-finding. In general terms it works by finding the intersection of a ray and an object. In your example the ray is the vector for the character's direction.

A useful reference for ray/object intersections (and incidentally other object/object intersections) is www.realtimerendering.com/intersections.html (look under the references for ray/aabb and ray/obb).

The rectangle has four sides. Each side is a line segment.

Test each of the four sides for intersection with the ray. Track the closest hit.

Here's some code to find out where on the segment the ray hits:

bool intersect(const ray& ray, const segment& segment,point& hit) {
// where do we intersect this line?
float t = ((ray.direction.x * ray.origin.y + ray.direction.y *
(segment[0].x - ray.origin.x)) -
(ray.direction.x * segment[1].y)) /
(ray.direction.y * (segment[0].x + segment[1].x) -
ray.direction.x * (segment[0].y + segment[1].y));
if(t >= 0.0 && t<=1.0) { // in the segment
hit = segment[0] + (segment[1]-segment[0]*t);  // lerp
return true;
}
return false; // no hit
}


Well, you can use just linear algebra (analytic geometry, to be more specific) to solve this. It depends on how you modeled the rectangle.

Here's a general case: http://paulbourke.net/geometry/lineline2d/

If your box is axis aligned, you just have to clamp each coordinate axis to the box if the point is outside the box.

From RTCD pg 130:

// Do this for all 3 axes
if( point.x < min.x )  point.x = min.x ;
else if( point.x > max.x )  point.x = max.x ;


If you do this for x, y, z axes, then the point will be slammed to the nearest wall of the box, if it is outside the box to begin with. if it is already inside the box, it will be left alone (where it is).