Find rectangle boundary point at an angle from point that is not in the middle of the rectangle

Question

I am trying to display where, in a rectangle, is player aiming in my game. He's in such a square:

image description

I found an algorithm to find rectangle point by angle, applied it and the results were wrong (real game screenshot):

image description

I soon realized this is because player is not in the center of the rectangle. So I replaced the center point in the algorighm with my point. But the result is just shifted point by constant distance:

image description

So I guess my current algorithm needs more than just one change. My code:

  function boudaryatangle(theta, point) {
    // reduce the theta  
    theta =  theta % 360; 
    // force it to be the positive remainder, so that 0 <= theta < 360  
    theta = (theta + 360) % 360;  
    // force into the minimum absolute value residue class, so that -180 < theta <= 180  
    if (theta > 180)  
        theta -= 360;  
    // Convert to radians
    theta = (theta * Math.PI / 180);
    // Get a rectangle that has width and height properties
    var rect = this.game.pixels;
    var width = rect.width;
    var height = rect.height;
    // If refference point wasn't provided as second argument
    //TODO: MAKE IT WORK WITH OTHER THEN RECTANGLE CENTRE POINT!
    if(typeof point=="undefined") {
      point = new Float32Array(2);
      point[0] = width/2;
      point[1] = height/2;
    }
    // Here be mysterious math and stuff - all bellow explained here
    var rectAtan = Math.atan2(height, width);
    var tanTheta = Math.tan(theta);
    // By default, region 1 and 3
    var region = true;

    var xFactor = 1;
    var yFactor = 1;

    if ((theta > -rectAtan) && (theta <= rectAtan)) {
        yFactor = -1;  // REGION 1
    } else if ((theta > rectAtan) && (theta <= (Math.PI - rectAtan))) {
        yFactor = -1;  // REGION 2
        region = false;
    } else if ((theta > (Math.PI - rectAtan)) || (theta <= -(Math.PI - rectAtan))) {
        xFactor = -1;  // REGION 3
    } else {
        xFactor = -1;  // REGION 4
        region = false;
    }

    // If region 1, 3
    if (region) {
      point[0] += xFactor * (width / 2.);                                     // "Z0"
      point[1] += yFactor * (width / 2.) * tanTheta;
    } else {
      point[0] += xFactor * (height / (2. * tanTheta));                        // "Z1"
      point[1] += yFactor * (height /  2.);
    }
    return point;
  }

Where else do I have to apply refference point location to get it to work? It's not required that this function returns sane results if point is out of the rectangle.

MBo · Answer 1 · 2015-10-19T06:17:41.247

We have:
- point with (px, py) coordinates (relative to the rectangle corner)
- direction vector (dx, dy) where dx = Cos(theta), dy = Sin(theta)
- width, height of rectangle.

We need to find the first point of ray intersection with rectangle. So make some equations:

if dx = 0 then
  t = Infinity
else 
if dx > 0 then
  px + dx * t = width
else
  px + dx * t = 0

if dy = 0 then
  u = Infinity
else 
if dy > 0 then
  py + dy * u = height
else
  py + dy * u = 0

Solve these equations for t and u. Don't forget Find min value from t and u: v = Min(t, u) - this is the first intersection point. It's coordinates are: (px + v * dx, py + v * dy)

Example

P = (10, 20) 
theta = 135deg = 3 * Pi/4 => D = (-0.707, 0.707)
W = 40, H = 50

t ~ 14
u ~ 42
v = Min(t,u) = 14
Int.X = 10 - 14 * 0.707 = 0 
// really there is is not need to calculate this value, 
//because we determined that the first intersection occurs for left edge
Int.Y = 20 + 14 * 0.707 = 30

score 1 · Answer 2 · answered Oct 19 '15 at 06:09

Many parts of your algorithm, for example height / 2., suggest that you still assume that the point is in the centre of the rectangle. If your point can be anywhere in the rectangle you must adapt all numbers, so that you use, for example, y or height - y, depending on wether your ray pointes upward or downward.

A simplification that you can't do anymore when your points are arbitrary is that there is a symmetry between the angles to the four corners. That means you can't use your region approach; at least it will be more complicated.

Another approach is to calculate the intersections of the ray with the four borders and see whether they lie on the rectangle:

function borderPoint(rect, pt, angle) {

    // catch cases where point is outside rectangle
    if (pt.x < rect.left) return null;
    if (pt.x > rect.left + rect.width) return null;
    if (pt.y < rect.top) return null;
    if (pt.y > rect.top + rect.height) return null;

    var dx = Math.cos(angle);
    var dy = Math.sin(angle);

    if (dx < 1.0e-16) {         // left border
        var y = (rect.left - pt.x) * dy / dx + pt.y;

        if (y >= rect.top && y <= rect.top + rect.height) {
            return {x: rect.left, y: y};
        }
    }

    if (dx > 1.0e-16) {         // right border
        var y = (rect.left + rect.width - pt.x) * dy / dx + pt.y;

        if (y >= rect.top && y <= rect.top + rect.height) {
            return {x: rect.left + rect.width, y: y};
        }
    }

    if (dy < 1.0e-16) {         // top border
        var x = (rect.top - pt.y) * dx / dy + pt.x;

        if (x >= rect.left && x <= rect.left + rect.width) {
            return {x: x, y: rect.top};
        }
    }

    if (dy > 1.0e-16) {         // bottom border
        var x = (rect.top + rect.height - pt.y) * dx / dy + pt.x;

        if (x >= rect.left && x <= rect.left + rect.width) {
            return {x: x, y: rect.top + rect.height};
        }
    }

    return null;
}

This code uses the mathematical definition of an angle, that is 0 is east, π/2 is north, π is west and 3·π/2 is south. If you use other definitions, you should adapt the code.

The code returns null when the point lies outside the rectangle or when no solution can be found.

score 1 · Answer 3 · 2015-10-19T09:37:48.837

The player "sees" on of the corners, and depending on which side of the corner he is aiming at, the collision occurs on the vertical or horizontal side.

Let us denote c = cos Θ, s = sin Θ. The equation of the line from (x, y) in the direction (c, s) is (X - x) s - (Y - y) c = 0. The expression on the left-hand side is positive on a side of the line and negative on the other side.

In the first quadrant (c, s > 0), the corner is (w, h), and the V/H decision depends on the sign of (w - x) s - (h - y) c. If the intersection is with the vertical side, we have

X = w, (w - x) s - (Y - y) c = 0, or Y = y + (w - x) s / c.

For the horizontal side,

Y = h, (X - x) s - (h - y) c = 0, or X = x + (h - y) c / s.

We can write

Corner (w, h):
    if (w - x) s < (h - y) c:
        X= w; Y= y + (w - x) s / c
    else:
        X= x + (h - y) c / s; Y= h

Notice that if c==0 or s==0, the solution is still valid because the branch that will be taken is such that no division by zero can arise. Whether < or <= is used in the comparison makes no difference (in case of equality the corner itself is found, both ways).

This can be micro-optimized as

Corner (w, h):
    S= (w - x) s; C= (h - y) c
    if S < C:
        X= w; Y= y + S / c
    else:
        X= x + C / s; Y= h

The same discussion can be repeated for the four quadrants, replacing w and/or h by 0. The final code structure is

if s >= 0:
    if c >= 0:
        Corner (w, h)
    else:
        Corner (0, h)
else:
    if c >= 0:
        Corner (w, 0)
    else:
        Corner (0, 0)

Take care to adjust the direction of the comparison correctly for the four quadrants.

This formulation was chosen to try to reach a minimum amount of computation, while remaining numerically reliable. We list

two sign tests for the selection of the quadrants,
one comparison involving two products and two additions,
one addition and one division for the intersection computation.

Find rectangle boundary point at an angle from point that is not in the middle of the rectangle

3 Answers3

Linked