生成包含指定2D点集的有效矩形的快速算法求解

给定输入 #

• 存储2D点的数组all_points，每个点以元组(x, y)表示
• 存储all_points中点索引的数组musthave_points
• 整数m，满足m < len(all_points)

输出要求 #

返回矩形列表，每个矩形由4个顶点构成的元组((x0, y0), (x1, y1), (x2, y2), (x3, y3))表示，需满足以下条件：

1. 恰好包含all_points中的m个点，且这些点完全处于矩形内部，不得落在四条边的任意一条上
2. 必须包含musthave_points中的所有点，若musthave_points为空则仅需满足第一个条件
3. 若两个矩形包含的点子集完全相同则判定为重复，输出中不得包含重复矩形；不存在符合要求的矩形则返回空列表

现有逻辑为枚举所有包含musthave_points的m个点的组合，为每个组合生成最小外接矩形后验证合法性，时间复杂度为组合阶乘级，当点总数超过30、m和n差值较小时完全无法运行。 #

核心依据：任意点集的最小面积外接矩形的边，必然与点集凸包的某一条边平行，因此无需枚举所有点组合，仅需枚举有限的矩形方向即可覆盖所有可能的合法矩形。

具体步骤 #

1. 预处理候选方向
   提取musthave_points对应的所有坐标，计算其凸包，提取凸包所有边的方向后去重，得到所有需要枚举的矩形旋转角度θ，方向总数最多为凸包边数，通常远小于点总数。
2. 按方向投影转换问题
   对每个候选角度θ：
   • 将所有点投影到θ方向和垂直于θ的两个正交轴上，每个点得到两个投影坐标(u, v)
   • 计算musthave_points投影后的u坐标上下界[u_must_min, u_must_max]、v坐标上下界[v_must_min, v_must_max]，合法矩形的投影区间必须完全包含这两个区间
   • 问题转换为在投影平面上寻找开区间(U1, U2)和(V1, V2)，满足U1 < u_must_min、U2 > u_must_max、V1 < v_must_min、V2 > v_must_max，且恰好有m个点的u落在(U1, U2)、v落在(V1, V2)
   • 该步骤可通过排序+双指针/滑动窗口实现，单方向时间复杂度为O(n log n)
3. 矩形还原与去重
   • 对找到的合法投影区间，逆旋转还原为原始坐标系下的矩形顶点
   • 对每个矩形对应的内部点集合计算哈希值去重，避免重复输出

• 点是否在矩形内的判断无需每次构造Polygon，直接用对应方向的投影坐标判断即可，速度可提升10倍以上
• 若m远大于len(all_points)-m，可反向枚举排除的点，进一步降低计算量

内容的提问来源于stack exchange，提问作者khanhdtq