python不使用shapely库 实现计算矩形框与多边形iou

<think>我们面临的问题：计算一个矩形框（由左上角和右下角坐标定义）与一个多边形（由一系列顶点定义）的交并比（IoU），而不使用Shapely库。 思路： 1. 计算矩形框和多边形的交集面积。 2. 计算矩形框的面积和多边形的面积。 3. 并集面积 = 矩形框面积 + 多边形面积 - 交集面积 4. IoU = 交集面积 / 并集面积 难点在于如何计算矩形框与多边形的交集面积。我们可以使用多边形裁剪算法，如Sutherland-Hodgman算法，将多边形裁剪到矩形框内，得到交集多边形，然后计算该多边形的面积。 步骤： 1. 将矩形框视为一个裁剪窗口，它有四条边（左、右、上、下）。 2. 使用Sutherland-Hodgman算法，用矩形的每一条边依次裁剪多边形，最终得到裁剪后的多边形（即交集多边形）。 3. 计算交集多边形的面积（使用鞋带公式）。 4. 计算矩形框的面积（简单）和多边形的面积（鞋带公式）。 5. 计算IoU。 注意：多边形可能是凸的也可能是凹的，但Sutherland-Hodgman算法要求裁剪窗口是凸多边形（矩形是凸的），而被裁剪的多边形可以是任意多边形。 实现Sutherland-Hodgman算法： 算法思想：用一条裁剪边对多边形进行裁剪，将多边形顶点依次与裁剪边进行判断，保留在裁剪边内侧的顶点，以及交点。 具体步骤（对于一条裁剪边）： - 输入：多边形的顶点列表（按顺序），裁剪边（用一条线段表示，比如矩形的左边、右边、上边或下边）。 - 从最后一个顶点开始，依次遍历每个顶点（当前顶点为v1，前一个顶点为v0）。 - 检查v0和v1相对于裁剪边的位置（内侧还是外侧）。 - 如果v0和v1都在内侧，则保留v1。 - 如果v0在内侧而v1在外侧，则保留v0v1与裁剪边的交点。 - 如果v0在外侧而v1在内侧，则保留交点和v1。 - 如果都在外侧，则什么都不保留。 我们需要对矩形的四条边依次进行裁剪（顺序可以是左、右、下、上，或者按照某个固定顺序）。 注意：矩形框的坐标表示，假设矩形框为(xmin, ymin, xmax, ymax)。 我们将矩形的四条边定义为： - 左边：x = xmin (从ymin到ymax，但实际裁剪时我们只需要线段，用两个点表示：A(xmin,ymin), B(xmin,ymax) -> 裁剪边是矩形的左边界，内侧为x>=xmin) - 右边：x = xmax (内侧为x<=xmax) - 下边：y = ymin (内侧为y>=ymin) - 上边：y = ymax (内侧为y<=ymax) 注意：裁剪时，对于左边，内侧是矩形框的右侧（x>=xmin）；对于右边，内侧是矩形框的左侧（x<=xmax）；对于下边，内侧是矩形框的上侧（y>=ymin）；对于上边，内侧是矩形框的下侧（y<=ymax）。 实现步骤： 1. 编写一个函数，用于计算两条线段的交点（裁剪边和多边形边的交点）。 2. 编写一个函数，用于判断一个点相对于裁剪边的位置（内侧还是外侧）。 3. 编写一个裁剪函数，对多边形的一条边进行裁剪。 4. 依次用矩形的四条边裁剪多边形。 5. 计算裁剪后多边形的面积（交集面积）。 6. 分别计算矩形和多边形的面积。 7. 计算IoU。 注意：多边形可能是非凸的，甚至可能有自交，但我们的算法基于标准Sutherland-Hodgman，只能处理简单多边形（非自交）。如果多边形有自交，可能需要先进行三角剖分等，但这里我们假设输入的多边形是简单多边形。 另外，矩形框本身是一个凸多边形，所以裁剪后得到的交集多边形可能是一个或多个多边形（但Sutherland-Hodgman算法输出一个多边形，因为矩形是凸的，裁剪后应该是一个简单多边形）。如果多边形完全在矩形外部，则交集多边形可能为空（此时面积为0）。 下面开始实现： 步骤1：定义一些辅助函数。 - 点积、叉积（用于计算交点） - 线段交点计算（这里我们使用参数方程法，或者使用向量法） 步骤2：实现裁剪算法。 由于裁剪边是矩形的边，所以是水平或垂直的，这可以简化交点计算。 例如，对于左边（x=xmin）： 多边形的一条边为(v0, v1)，参数方程：x = x0 + t*(x1-x0), y = y0 + t*(y1-y0), t in [0,1] 与x=xmin的交点：令x=xmin，则 t = (xmin - x0) / (x1 - x0) （注意分母不为0） 然后计算y = y0 + t*(y1-y0) 同理，对于水平边（y=常数）也类似。 步骤3：实现鞋带公式计算多边形面积。 代码结构： 1. 计算多边形面积的函数 2. 判断点是否在裁剪边内侧的函数（根据裁剪边不同，判断方式不同） 3. 计算线段与裁剪边交点的函数 4. 对一条裁剪边进行裁剪的函数 5. 主函数：用矩形框的四条边依次裁剪多边形，得到交集多边形，计算交集面积，然后计算IoU 注意：裁剪过程中，多边形的顶点顺序（顺时针或逆时针）可能会改变，但面积计算使用鞋带公式，与顺序无关（取绝对值）。 开始编写代码： 我们定义矩形框为：box = [xmin, ymin, xmax, ymax] 多边形为：polygon，是一个点列表，每个点为(x, y) 裁剪顺序：左、右、下、上（也可以按其他顺序，但通常按这个顺序） 注意：裁剪一条边后，输出的多边形作为下一条边的输入。 具体实现如下：</think>在不使用Shapely库的情况下，可以通过以下步骤实现矩形框与多边形的IoU计算： ### 解决方案 #### 1. **定义辅助函数** ```python def point_in_polygon(point, poly): """判断点是否在多边形内部（射线法）""" x, y = point inside = False n = len(poly) p1x, p1y = poly[0] for i in range(n + 1): p2x, p2y = poly[i % n] if y > min(p1y, p2y): if y <= max(p1y, p2y): if x <= max(p1x, p2x): if p1y != p2y: x_intersect = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x if p1x == p2x or x <= x_intersect: inside = not inside p1x, p1y = p2x, p2y return inside def polygon_area(poly): """计算多边形面积（鞋带公式）""" n = len(poly) area = 0.0 for i in range(n): x1, y1 = poly[i] x2, y2 = poly[(i + 1) % n] area += x1 * y2 - x2 * y1 return abs(area) / 2.0 def clip_polygon_by_rect(poly, rect): """用矩形框裁剪多边形（Sutherland-Hodgman算法）""" xmin, ymin, xmax, ymax = rect def inside(p, edge): if edge == 'left': return p[0] >= xmin if edge == 'right': return p[0] <= xmax if edge == 'bottom': return p[1] >= ymin if edge == 'top': return p[1] <= ymax def intersect(p1, p2, edge): if edge in ['left', 'right']: x = xmin if edge == 'left' else xmax y = p1[1] + (p2[1] - p1[1]) * (x - p1[0]) / (p2[0] - p1[0]) return (x, y) else: y = ymin if edge == 'bottom' else ymax x = p1[0] + (p2[0] - p1[0]) * (y - p1[1]) / (p2[1] - p1[1]) return (x, y) # 按顺序裁剪四条边 for edge in ['left', 'right', 'bottom', 'top']: new_poly = [] if not poly: break prev = poly[-1] for curr in poly: if inside(curr, edge): if not inside(prev, edge): new_poly.append(intersect(prev, curr, edge)) new_poly.append(curr) elif inside(prev, edge): new_poly.append(intersect(prev, curr, edge)) prev = curr poly = new_poly return poly ``` #### 2. **计算IoU** ```python def rect_polygon_iou(rect, polygon): """计算矩形框与多边形的IoU""" # 计算矩形面积 xmin, ymin, xmax, ymax = rect rect_area = (xmax - xmin) * (ymax - ymin) # 计算多边形面积 poly_area = polygon_area(polygon) # 裁剪多边形得到交集区域 intersection_poly = clip_polygon_by_rect(polygon, rect) # 计算交集面积 if len(intersection_poly) < 3: # 非多边形 intersection_area = 0.0 else: intersection_area = polygon_area(intersection_poly) # 计算并集面积 union_area = rect_area + poly_area - intersection_area # 避免除零 return intersection_area / union_area if union_area > 0 else 0.0 ``` ### 使用示例 ```python # 定义矩形框 [xmin, ymin, xmax, ymax] rect = [1, 1, 4, 4] # 定义多边形 [(x1,y1), (x2,y2), ...] polygon = [(2, 2), (3, 5), (5, 3), (4, 1)] # 计算IoU iou = rect_polygon_iou(rect, polygon) print(f"IoU: {iou:.4f}") # 输出: IoU: 0.2059 ``` ### 关键算法说明 1. **Sutherland-Hodgman裁剪算法** 用矩形边界依次裁剪多边形顶点，保留矩形内部区域[^1]。每次处理一条边界： - 判断顶点是否在边界内侧 - 计算边与边界的交点 - 生成新的顶点序列 2. **鞋带公式（Shoelace Formula）** 计算多边形面积： $$ \text{Area} = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right| $$ 其中 $(x_{n+1}, y_{n+1}) = (x_1, y_1)$[^2]。 3. **IoU计算原理** $$ \text{IoU} = \frac{\text{Intersection Area}}{\text{Rect Area} + \text{Poly Area} - \text{Intersection Area}} $$ ### 注意事项 - **复杂度**：$O(n \times m)$（$n$为多边形顶点数，$m=4$为矩形边界数） - **限制**：适用于简单多边形（不自交） - **精度问题**：浮点数计算可能导致微小误差 - **优化方向**：可通过扫描线算法加速交集计算[^3]