8
\$\begingroup\$

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?

Point Facing Rectangle

\$\endgroup\$
3
  • \$\begingroup\$ Can you explain more what you're asking? I'm really not getting it. \$\endgroup\$
    – user9471
    Sep 5, 2011 at 5:46
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 5, 2011 at 5:49
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Sep 5, 2011 at 7:30

4 Answers 4

6
\$\begingroup\$

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

\$\endgroup\$
9
\$\begingroup\$

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
}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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/

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .