带预处理的平移多边形与圆角矩形相交检测的常数/次线性算法问询

针对你提出的批量判断平移后2D多边形与固定圆角矩形相交的需求，确实存在次线性时间的查询算法，核心思路是通过预处理多边形的关键几何特征，将每次查询的时间复杂度降低到与多边形顶点数N的对数成正比，或依赖远小于N的凸包顶点数。以下是具体实现逻辑：

问题等价转化 #

圆角矩形可拆解为：中心轴对齐的核心矩形 + 四个角落的四分之一圆，也等价于「核心矩形与半径r圆盘的闵可夫斯基和」。平移后的多边形P'(dx, dy)与圆角矩形R相交，等价于以下任一条件成立：

1. P'与核心矩形直接相交；
2. P'的顶点落在任意一个圆角区域内；
3. P'的边与任意一个圆角圆弧相交；
4. 某个圆角区域完全被P'包含。

预处理步骤（O(N logN) 时间） #

预处理仅需执行一次，成本可摊薄到批量查询中：

1. 计算多边形的AABB与凸包
   • 计算原多边形的轴对齐包围盒（AABB），用于快速排除完全不相交的情况；
   • 计算多边形的凸包H：由于凸包是包含原多边形的最小凸集，且凸集与凸集的相交判断等价于原多边形与凸集的相交判断，凸包顶点数k通常远小于N，可大幅降低后续相交判断的复杂度。
2. 预处理凸包的分离轴信息
   对凸包的每条边，预处理其法向量，用于后续快速判断平移后的凸包与核心矩形是否相交（分离轴定理）。
3. 针对四个圆角中心的预处理
   设核心矩形的四个顶点为圆角中心C₁~C₄（如右上角中心为(w/2, h/2)，w、h为核心矩形的长、宽）：
   • 对所有多边形顶点，计算其相对于每个Cᵢ的坐标偏移量，并构建kd树或范围索引，用于快速查询平移后是否有顶点落在圆角区域内；
   • 对所有多边形边，计算其相对于每个Cᵢ的最小距离、直线方程参数，并构建边的空间索引，用于快速筛选可能与圆角圆弧相交的边；
   • 计算多边形到每个Cᵢ的最小距离（顶点到Cᵢ的最小距离与边到Cᵢ的最小距离中的较小值）。

单次查询步骤（O(logN) + O(k) 时间，次线性） #

对每个平移量(dx, dy)，按以下流程判断：

1. 快速排除：AABB相交检测
   计算平移后多边形的AABB，与圆角矩形的AABB比较，若不相交直接返回「不相交」（O(1) 时间）。
2. 核心矩形相交判断
   用分离轴定理判断平移后的凸包与核心矩形是否相交：遍历凸包的分离轴与核心矩形的轴，若不存在分离轴则返回「相交」（O(k) 时间，k为凸包顶点数，远小于N）。
3. 圆角区域相交判断
   若与核心矩形不相交，仅需检查四个圆角区域：
   • 快速排除不可能相交的圆角：根据平移后多边形的坐标范围，判断是否与当前圆角的覆盖范围有重叠，无重叠则跳过（O(1) 时间/每个圆角）；
   • 顶点是否在圆角内：通过预处理的kd树查询，判断是否存在平移后的顶点满足「到对应圆角中心的距离≤r」且位于角落区域（O(logN) 时间），存在则返回「相交」；
   • 边是否与圆角圆弧相交：通过边的空间索引筛选出可能相交的边，判断线段与四分之一圆弧的相交性（O(logN) 时间），相交则返回「相交」；
   • 圆角是否被多边形包含：判断圆角中心是否在平移后的多边形内部，且多边形到该中心的最小距离≥r，满足则返回「相交」。
4. 所有条件不满足时，返回「不相交」

关键结论 #

通过上述预处理与查询流程，每次批量查询的时间复杂度为次线性（相对于原多边形顶点数N）：当多边形凸包顶点数k远小于N时，查询时间接近O(logN)；即使k较大，也远低于遍历所有N个顶点/边的线性时间。

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