python判断多边形是否相交

判断多边形是否相交可以使用以下两种方法：

1. Ray Casting Algorithm（射线法）：对于任意两个多边形，分别对其中一个多边形的每个顶点作一条水平向右的射线，统计与另一个多边形的交点数，如果是奇数则说明两个多边形相交，偶数则不相交。该算法时间复杂度为O(n^2)，其中n为多边形的顶点数。

2. Separating Axis Theorem（分离轴定理）：对于两个凸多边形，找出两个多边形所有可能的分离轴，即两个多边形所围成的区域不相交的轴。如果找到了一个分离轴，则两个多边形不相交。如果没有找到，则两个多边形相交。该算法时间复杂度为O(n)，其中n为多边形的边数。

以下是使用第二种方法的Python代码示例：

def project_polygon_onto_axis(polygon, axis):
    # 投影多边形到指定轴上
    min_proj = float('inf')
    max_proj = -float('inf')
    for point in polygon:
        proj = np.dot(point, axis) / np.dot(axis, axis)
        min_proj = min(min_proj, proj)
        max_proj = max(max_proj, proj)
    return (min_proj, max_proj)

def check_intersection(p1, p2):
    # 判断两个凸多边形是否相交
    for axis in np.concatenate((p1, p2)):
        axis = np.array([-axis[1], axis[0]]) # 得到垂直于当前边的轴
        min_proj1, max_proj1 = project_polygon_onto_axis(p1, axis)
        min_proj2, max_proj2 = project_polygon_onto_axis(p2, axis)
        if max_proj1 < min_proj2 or max_proj2 < min_proj1:
            return False # 找到了一个分离轴，两个多边形不相交
    return True # 没有找到分离轴，两个多边形相交

# 示例：判断两个凸多边形是否相交
p1 = np.array([[0, 0], [0, 1], [1, 1], [1, 0]])
p2 = np.array([[0.5, -0.5], [0.5, 0.5], [1.5, 0.5], [1.5, -0.5]])
print(check_intersection(p1, p2)) # 输出True