如何从大量线段中高效检测旋转矩形？Python技术咨询

DevOps 小满

2026-7-13

问题描述

我当前面临一项技术挑战：需要从给定的线段集合（总计约5000条）中检测可组成的旋转矩形，性能优化是关键问题。为便于理解问题，以下是示例：

segments = [
    [(0, 0), (10, 0)],
    [(10, 0), (10, 10)],
    [(10, 10), (0, 10)],
    [(0, 10), (0, 0)],
]

上述示例中的线段可组成一个非旋转矩形，但实际场景中可能存在旋转矩形，我需要实现对这类矩形的检测。请问如何高效判断给定线段集合能否组成旋转矩形？是否有现成的算法或Python库可协助实现？

我尝试的代码

import cv2
import numpy as np
import pandas as pd
from tqdm import tqdm


def find_rectangles(segments):
    """
    在线段列表中查找所有矩形。

    参数:
      segments: 线段列表。

    返回:
      矩形列表。
    """
    rectangles = []
    segments = np.array(segments)
    for i in tqdm(range(len(segments))):
        l1 = segments[i]
        l2 = None
        l3 = None
        l4 = None
        for j in range(len(segments)):
            if are_perpendicular(l1, segments[j]):
                l2 = segments[j]
                break
        if l2 is None:
            continue
        for j in range(len(segments)):
            # l3: 与l2垂直、与l1平行且和l2相邻
            if are_parallel(l1, segments[j]) and are_perpendicular(l2, segments[j]):
                l3 = segments[j]
                break
        if l3 is None:
            continue
        for j in range(len(segments)):
            # l4: 与l1垂直、与l2平行且和l3相邻
            if (
                are_perpendicular(l1, segments[j])
                and are_parallel(l2, segments[j])
                and are_perpendicular(l3, segments[j])
            ):
                l4 = segments[j]
                break
        if l4 is None:
            continue
        lines = np.array([l1, l2, l3, l4])
        points = lines.reshape(-1, 2)
        x = points[:, 0]
        y = points[:, 1]
        xmin, ymin, xmax, ymax = min(x), min(y), max(x), max(y)

        rectangles.append(Rectangle(xmin, ymin, xmax, ymax))
        print("找到矩形: ", rectangles[-1])
    return rectangles


def are_parallel(v1, v2):
    """
    判断两条线段是否平行。

    参数:
      v1: 第一条线段。
      v2: 第二条线段。

    返回:
      平行返回True，否则返回False。
    """
    slope1 = compute_slope(v1)
    slope2 = compute_slope(v2)
    return slope1 == slope2


def are_adjacent(segment1, segment2):
    """
    判断两条线段是否相邻（有公共端点）。

    参数:
      segment1: 第一条线段。
      segment2: 第二条线段。

    返回:
      相邻返回True，否则返回False。
    """
    p1, p2 = segment1
    p3, p4 = segment2
    return (p1 == p3).all() or (p1 == p4).all() or (p2 == p3).all() or (p2 == p4).all()

def compute_slope(seg):
    seg = seg[1] - seg[0]
    angle = np.angle(complex(*(seg)), deg=True)
    return angle


def are_perpendicular(v1, v2):
    """
    判断两条线段是否垂直。

    参数:
      v1: 第一条线段。
      v2: 第二条线段。

    返回:
      垂直返回True，否则返回False。
    """
    # 排除重叠线段
    points = np.array([v1[0], v1[1], v2[0], v2[1]])
    xmin, ymin, xmax, ymax = min(points[:, 0]), min(points[:, 1]), max(points[:, 0]), max(points[:, 1])
    is_overlap = (xmin == xmax) or (ymin == ymax)
    if is_overlap:
        return False
    # 检查是否相邻
    if not are_adjacent(v1, v2):
        return False
    # 检查角度差是否为90度
    s1 = compute_slope(v1) # 角度（度）
    s2 = compute_slope(v2) # 角度（度）
    cond3 = np.abs(s1 - s2) == 90

    return cond3


class Rectangle:
    """
    表示一个矩形。

    属性:
      top_left: 矩形的左上角坐标。
      bottom_right: 矩形的右下角坐标。
    """

    def __init__(self, xmin, ymin, xmax, ymax):
        """
        初始化矩形实例。

        参数:
          xmin: 最小x坐标。
          ymin: 最小y坐标。
          xmax: 最大x坐标。
          ymax: 最大y坐标。
        """
        self.top_left = (xmin, ymin)
        self.bottom_right = (xmax, ymax)

    def __str__(self):
        """返回矩形的字符串表示"""
        return "Rectangle(top_left=({}, {}), bottom_right=({}, {}))".format(
            self.top_left[0],
            self.top_left[1],
            self.bottom_right[0],
            self.bottom_right[1],
        )


def draw_line(df):
    x = df["x0"].values.tolist() + df["x1"].values.tolist()
    y = df["y0"].values.tolist() + df["y1"].values.tolist()
    xmin, ymin, xmax, ymax = min(x), min(y), max(x), max(y)
    mat = np.zeros((ymax - ymin + 1, xmax - xmin + 1, 3), dtype=np.uint8)
    df[["x0", "x1"]] = df[["x0", "x1"]] - xmin
    df[["y0", "y1"]] = df[["y0", "y1"]] - ymin
    for x0, y0, x1, y1 in tqdm(df[["x0", "y0", "x1", "y1"]].values.tolist()):
        cv2.line(mat, (x0, y0), (x1, y1), (255, 255, 255), 1)
    cv2.imwrite("mat.png", mat)
    print('已保存线段图像')

if __name__ == "__main__":
    segments = [
                [(0, 0), (10, 0)],
                [(10, 0), (10, 10)],
                [(10, 10), (0, 10)],
                [(0, 10), (0, 0)],
                ]
    # 查找所有矩形
    rectangles = find_rectangles(segments)

    # 打印结果
    for rectangle in rectangles:
        print(rectangle)

优化思路与解决方案

1. 现有代码的核心问题

当前代码采用四层嵌套循环，时间复杂度为O(n⁴)，对于5000条线段来说完全无法运行，必须重构逻辑降低复杂度。

2. 核心优化方向

矩形的几何本质是：

两组平行且等长的线段
不同组的线段互相垂直
四条线段首尾相连形成闭合图形

基于此可以从以下方向优化：

（1）预分组平行线段

计算所有线段的标准化方向向量（例如将向量归一化，同时统一方向：x分量非负，x为0时y分量非负），把同方向的线段归为一组。后续操作基于组进行，避免全量遍历，分组时间复杂度为O(n)。

（2）利用矩形的顶点特征

矩形的四个顶点满足：

每个顶点是两条垂直线段的交点
对角线长度相等且互相平分
任意两点间的距离仅存在两种值（边长和对角线长，对角线长为边长的√2倍）

可以先收集所有线段的端点，通过空间索引快速查找符合条件的点集，再验证是否能组成闭合矩形。

（3）空间索引加速查询

用SciPy的spatial.KDTree对线段端点建立空间索引，快速查找距离某点一定范围内的其他点，或查找与某线段垂直且相邻的线段，将查找复杂度从O(n)降至O(log n)。

3. 可用的Python工具

NumPy/SciPy：NumPy用于向量运算与浮点精度处理，SciPy的KDTree实现空间快速查询。
Shapely：专业几何库，可便捷判断线段平行/垂直关系，构建多边形并验证是否为矩形。
OpenCV：可通过cv2.minAreaRect()从点集提取最小外接矩形，但需先将线段转换为点集。

4. 优化后的算法步骤示例

预处理线段：将每条线段转换为标准化方向向量、长度、端点集合，用阈值（如1e-6）替代直接相等判断，处理浮点精度问题。
分组平行线段：按标准化方向向量分组，每组内按线段长度排序。
匹配矩形边对：从一组中取一条线段，在垂直方向的组中寻找等长的线段，检查是否能作为矩形的邻边，再寻找另外两条对应边。
验证闭合性：确认四条线段首尾相连形成闭合图形，同时去重（如用排序后的顶点组合作为唯一标识）。

5. 关键细节处理

浮点精度：禁止用==判断角度或坐标相等，必须用阈值范围判断。
重复矩形：检测到矩形后，通过顶点的有序组合生成唯一标识，避免重复记录。
线段方向：同一矩形的边可能存在反向（如A→B和B→A），预处理时需统一方向。

内容的提问来源于stack exchange，提问作者Nguyễn Anh Bình

如何从大量线段中高效检测旋转矩形？Python技术咨询

1. 现有代码的核心问题 #

2. 核心优化方向 #