Point-in-Rectangle Detection Algorithm for Arbitrary Orientation: Geometric Principles and Implementation Analysis

Geometric Problem Definition and Background

In computer graphics, game development, geographic information systems, and other fields, determining whether a point lies inside a rectangle is a fundamental geometric operation. When the rectangle is axis-aligned, the problem simplifies to coordinate range comparison; however, for arbitrarily rotated rectangles, more general geometric algorithms are required. This paper, based on convex polygon detection theory, provides an in-depth analysis of point-inclusion detection methods applicable to rectangles of any orientation.

General Detection Principle for Convex Polygons

For any convex polygon, point-inclusion detection can be performed using the edge orientation test. Assuming polygon vertices are ordered counterclockwise, for each edge, test whether the target point lies to the left of the edge (i.e., in the left half-plane). If all edge tests pass, the point is inside the polygon; otherwise, it is outside.

Given edge endpoints (x1, y1) and (x2, y2), and test point (xp, yp), compute the determinant:

D = (x2 - x1) * (yp - y1) - (xp - x1) * (y2 - y1)

If D > 0, the point is left of the edge; D < 0 indicates right; D = 0 means on the edge. This computation requires only addition, subtraction, and multiplication, avoiding floating-point rotation operations.

Equivalent Line Equation Form

The determinant method is equivalent to a line equation test. For edge (x1, y1)-(x2, y2), construct the line equation A * x + B * y + C = 0, where:

A = -(y2 - y1)
B = x2 - x1
C = -(A * x1 + B * y1)

Compute D = A * xp + B * yp + C, with sign interpretation as above. Algebraic expansion proves the equivalence of the two forms:

D = A*xp + B*yp + C
  = -(y2-y1)*xp + (x2-x1)*yp - (-(y2-y1)*x1 + (x2-x1)*y1)
  = (x2-x1)*(yp-y1) - (y2-y1)*(xp-x1)

This is exactly the determinant form. The equivalence highlights the mathematical connection between vector cross products and line equations.

Rectangle-Specific Optimization Analysis

While the general method works for any convex polygon, rectangles as special parallelograms have symmetric parallel edges that allow further optimization. Considering a rectangle defined by three points A, B, C, with AB perpendicular to BC, a vector projection approach can be used:

0 <= dot(AB, AM) <= dot(AB, AB) &&
0 <= dot(BC, BM) <= dot(BC, BC)

where dot denotes the dot product, and AM, BM are vectors. This method projects the point coordinates onto two adjacent edges of the rectangle and checks if the projections lie within the edge lengths. The following JavaScript implementation demonstrates this algorithm:

function pointInRectangle(m, r) {
    var AB = vector(r.A, r.B);
    var AM = vector(r.A, m);
    var BC = vector(r.B, r.C);
    var BM = vector(r.B, m);
    var dotABAM = dot(AB, AM);
    var dotABAB = dot(AB, AB);
    var dotBCBM = dot(BC, BM);
    var dotBCBC = dot(BC, BC);
    return 0 <= dotABAM && dotABAM <= dotABAB && 0 <= dotBCBM && dotBCBM <= dotBCBC;
}

function vector(p1, p2) {
    return { x: p2.x - p1.x, y: p2.y - p1.y };
}

function dot(u, v) {
    return u.x * v.x + u.y * v.y;
}

In an example, with rectangle points A(50,0), B(0,20), C(10,50), D(60,30) and test point M(40,20), the function returns true. The projection method leverages the orthogonal properties of rectangles to reduce computation but requires explicit rectangle representation.

Algorithm Comparison and Selection Recommendations

The general edge test method is suitable for any convex polygon, requires no special rectangle representation, offers strong robustness, and has computational complexity of O(n), or O(4) for rectangles. The vector projection method is optimized for rectangles, needing only two dot product range checks, but depends on the perpendicular assumption and three-point representation. In practice, if rectangles may be degenerate or incompletely represented, the general method is recommended; if rectangle structure is well-defined and performance is critical, projection optimization can be considered.

Implementation Considerations and Extensions

During implementation, floating-point precision issues must be addressed, especially for points on or near edges. A tolerance parameter epsilon can be introduced, extending D = 0 to |D| < epsilon. Additionally, the algorithm can be extended to three-dimensional space by testing points against plane equations for convex polyhedra. For non-convex polygons, methods like ray casting or winding number are required, but for rectangles as a convex polygon special case, the approaches discussed here are fully applicable.

In summary, the core of point detection in arbitrarily oriented rectangles lies in utilizing vector geometric properties to avoid coordinate rotation. By deeply understanding the geometric significance of determinants and line equations, developers can select optimal implementations based on specific scenarios, balancing generality and efficiency.