面试算法题：实现判断点是否在任意旋转矩形内的IsInside函数

这里采用向量投影法实现，无需计算矩形旋转角度，计算效率高，适配任意旋转的矩形场景：

• 基于逆时针给出的矩形顶点，取左上角顶点为原点，构建两条相邻边的方向向量
• 构造原点到待判断点的向量，分别投影到两条边的方向向量上
• 只要两个投影的长度比值都落在[0, 1]区间内，即可判定点在矩形内部

class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
}

function isInside(boxCorners, p) {
    const A = boxCorners[0];
    const B = boxCorners[1];
    const D = boxCorners[3];

    // 构造两条相邻边的向量
    const AB = {x: B.x - A.x, y: B.y - A.y};
    const AD = {x: D.x - A.x, y: D.y - A.y};
    // 构造矩形左上角到待判断点的向量
    const AP = {x: p.x - A.x, y: p.y - A.y};

    // 计算点积，直接用平方长度对比避免开根号，提升计算效率
    const dotABAP = AB.x * AP.x + AB.y * AP.y;
    const dotABAB = AB.x * AB.x + AB.y * AB.y;
    const dotADAP = AD.x * AP.x + AD.y * AP.y;
    const dotADAD = AD.x * AD.x + AD.y * AD.y;

    // 极小容差处理浮点数计算精度问题，可根据业务需求调整
    const epsilon = 1e-6;
    return dotABAP >= -epsilon && dotABAP <= dotABAB + epsilon
        && dotADAP >= -epsilon && dotADAP <= dotADAD + epsilon;
}

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def is_inside(box_corners, p):
    A = box_corners[0]
    B = box_corners[1]
    D = box_corners[3]

    # 构造两条相邻边的向量
    AB = (B.x - A.x, B.y - A.y)
    AD = (D.x - A.x, D.y - A.y)
    # 构造矩形左上角到待判断点的向量
    AP = (p.x - A.x, p.y - A.y)

    # 计算点积对比平方长度，避免开根号
    dot_ab_ap = AB[0] * AP[0] + AB[1] * AP[1]
    dot_ab_ab = AB[0] * AB[0] + AB[1] * AB[1]
    dot_ad_ap = AD[0] * AP[0] + AD[1] * AP[1]
    dot_ad_ad = AD[0] * AD[0] + AD[1] * AD[1]

    # 浮点数精度容差
    epsilon = 1e-6
    return -epsilon <= dot_ab_ap <= dot_ab_ab + epsilon \
        and -epsilon <= dot_ad_ap <= dot_ad_ad + epsilon

说明 #

• 代码默认包含边界判断，如果你需要严格判断点在矩形内部（不包含边界），去掉等号并移除epsilon容差即可
• 该方法的时间复杂度为O(1)，性能远高于通用凸多边形点包含判断的射线法

内容的提问来源于stack exchange，提问作者Nazehs