Python 计算两个多边形重叠面积（无需第三方库）

要计算两个多边形的重叠面积，可以使用边界框（bounding box）的方法。\n\n首先，找到两个多边形的边界框，即最小矩形框，它们完全包围住了多边形。边界框的坐标可以通过找到多边形的最小和最大 x、y 坐标来确定。\n\n然后，检查两个边界框是否相交。如果边界框不相交，那么两个多边形也不会相交，重叠面积为 0。\n\n如果边界框相交，那么两个多边形可能相交。接下来，我们需要判断两个多边形是否真正相交。我们可以使用射线相交算法（Ray Casting Algorithm）来判断两个多边形是否相交。\n\n射线相交算法是通过发射一条射线，然后计算与多边形的边的交点的数量来判断多边形是否与射线相交。如果交点数量是奇数，那么多边形与射线相交，否则不相交。\n\n为了计算重叠面积，我们可以在一个多边形内发射一条射线，然后计算与另一个多边形的边的交点的数量。然后，我们可以通过计算两个多边形的面积之和减去两个多边形的重叠面积来得到结果。\n\n下面是一个示例代码：\n\npython\ndef overlap_area(polygon1, polygon2):\n # 计算多边形的边界框\n min_x1, min_y1, max_x1, max_y1 = get_bounding_box(polygon1)\n min_x2, min_y2, max_x2, max_y2 = get_bounding_box(polygon2)\n\n # 检查边界框是否相交\n if not is_intersect(min_x1, min_y1, max_x1, max_y1, min_x2, min_y2, max_x2, max_y2):\n return 0\n\n # 计算重叠面积\n area1 = calculate_area(polygon1)\n area2 = calculate_area(polygon2)\n intersection_area = calculate_intersection_area(polygon1, polygon2)\n\n return area1 + area2 - intersection_area\n\ndef get_bounding_box(polygon):\n min_x = min(polygon, key=lambda p: p[0])[0]\n min_y = min(polygon, key=lambda p: p[1])[1]\n max_x = max(polygon, key=lambda p: p[0])[0]\n max_y = max(polygon, key=lambda p: p[1])[1]\n return min_x, min_y, max_x, max_y\n\ndef is_intersect(min_x1, min_y1, max_x1, max_y1, min_x2, min_y2, max_x2, max_y2):\n return not (max_x1 < min_x2 or max_x2 < min_x1 or max_y1 < min_y2 or max_y2 < min_y1)\n\ndef calculate_area(polygon):\n n = len(polygon)\n area = 0\n for i in range(n):\n j = (i + 1) % n\n area += polygon[i][0] * polygon[j][1] - polygon[j][0] * polygon[i][1]\n return abs(area) / 2\n\ndef calculate_intersection_area(polygon1, polygon2):\n intersection_area = 0\n n1 = len(polygon1)\n n2 = len(polygon2)\n for i in range(n1):\n p1 = polygon1[i]\n p2 = polygon1[(i + 1) % n1]\n for j in range(n2):\n q1 = polygon2[j]\n q2 = polygon2[(j + 1) % n2]\n if is_intersecting(p1, p2, q1, q2):\n intersection_point = calculate_intersection_point(p1, p2, q1, q2)\n intersection_area += calculate_area([p1, intersection_point, p2])\n return intersection_area\n\ndef is_intersecting(p1, p2, q1, q2):\n return (is_left_turn(p1, p2, q1) != is_left_turn(p1, p2, q2)) and (is_left_turn(q1, q2, p1) != is_left_turn(q1, q2, p2))\n\ndef is_left_turn(p, q, r):\n return (q[0] - p[0]) * (r[1] - p[1]) - (r[0] - p[0]) * (q[1] - p[1]) > 0\n\ndef calculate_intersection_point(p1, p2, q1, q2):\n x1, y1 = p1\n x2, y2 = p2\n x3, y3 = q1\n x4, y4 = q2\n x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4))\n y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / ((x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4))\n return x, y\n\n# 示例多边形\npolygon1 = [(0, 0), (0, 2), (2, 2), (2, 0)]\npolygon2 = [(1, 1), (1, 3), (3, 3), (3, 1)]\n\n# 计算重叠面积\noverlap = overlap_area(polygon1, polygon2)\nprint("重叠面积:", overlap)\n\n\n在这个示例中，我们定义了一个 overlap_area 函数来计算重叠面积。它首先计算两个多边形的边界框，然后检查边界框是否相交。如果边界框不相交，返回重叠面积为 0。如果边界框相交，我们使用射线相交算法来计算两个多边形的交点数量。最后，我们计算两个多边形的面积之和减去交点数量得到重叠面积。\n\n你可以将自己的多边形坐标输入到 polygon1 和 polygon2 变量中，然后运行代码来计算重叠面积。