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

Question

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?

Answer 1

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

Answer 2

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
}

Answer 3

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

Answer 4

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/