判断一个点是否在矩形内部

判断一个点是否在矩形内部

题目

在二维坐标系中，所有的值都是double类型，那么一个矩形可以由4个点来代表，
（x1，y1）为最左的点、（x2，y2）为最上的点、（x3，y3）为最下的点、（x4， y4）为最右的点。
给定4个点代表的矩形，再给定一个点（x，y），判断（x，y）是否在矩形中。

算法思路

我第一反应想到的转换为是否在多条直线范围内，也可以扩展至判断多边形。
两点可代表一条直线，可以求出直线方程式
也可以使用叉积，判断点在线的侧方位。具体见判断一个点是否在三角形内 方法二向量法。

针对矩形，有更简洁的想法。

首先，对于边平行于坐标轴的矩形，极易判断。
通过旋转坐标轴，使一般矩形变成边平行于坐标轴的矩形，当然点的坐标会发生相应改变。
$x = cos\theta \times x + sin\theta \times y \\ y = -sin\theta \times x + cos\theta \times y \\ 其中\theta为坐标轴逆时针旋转的弧度，代码中用t表示$x=cosθ×x+sinθ×yy=−sinθ×x+cosθ×y其中θ为坐标轴逆时针旋转的弧度，代码中用t表示

注意：
按顺时针点的位置依次为1，2，4，3

Python3代码

# 判断特殊矩形：矩形的边平行于坐标轴
def isInParRect(x1, y1, x4, y4, x, y):
    if x <= x1:
        return False
    if x >= x4:
        return False
    if y >= y1:
        return False
    if y <= y4:
        return False
    return True

# 判断一个点是否在矩阵内
# 旋转坐标系，使一般矩形变成边平行于坐标轴的矩形
def isInRect(x1, y1, x2, y2, x3, y3, x4, y4, x, y):
    # 使一般矩形旋转，使之平行于坐标轴
    if x1 != x4:
        # 坐标系以(x3, y3)为中心，逆时针旋转t至(x4, y4)
        dx = x4 - x3
        dy = y4 - y3
        ds = (dx**2 + dy**2)**0.5
        cost = dx / ds
        sint = dy / ds
        # python特性：隐含临时变量存储值
        x, y = cost * x + sint * y, -sint * x + cost * y
        x1, y1 = cost * x1 + sint * y1, -sint * x1 + cost * y1
        x4, y4 = cost * x4 + sint * y4, -sint * x4 + cost * y4
    return isInParRect(x1, y1, x4, y4, x, y)

有任何疑问和建议，欢迎在评论区留言和指正！

感谢您所花费的时间与精力！