algorithm - 重叠 AABB-Arc 和 AABB-Pie

Question

我正在寻找一种简单的算法来检测 aabb 的区域是否与圆弧(由绳索闭合)或饼图(通过圆心闭合)的区域重叠。

我已经找到了这个答案:Intersection of rectangle and circle (or arc)

但这并不是我要找的东西，因为我对形状轮廓的交点不感兴趣，只是想知道这些区域是否重叠。

例如，非常小的 AABB 仅包含馅饼的中心但 AABB 的边缘不与馅饼的圆相交的情况不会包含在链接的答案中。同样，弧完全包含 AABB 且 AABB 的边甚至不与绳索相交的情况也不会被覆盖。

现在，在我开始重新发明轮子之前，我想问一下是否有用于这种重叠检查的已知算法。

AABB 扇区示例:

Answer 1

考虑到配置的多样性，这不是一个简单的问题。

您可以通过以十字为中心分割扇形来简化问题，这样水平线或垂直线就不会与圆弧相交两次，并分别处理这些部分。

然后考虑其中一个部分并在“收缩”矩形的同时“膨胀”它。更准确地说，扇区的每个点都变成了从它开始的矩形(左上角)，而矩形缩小到它的右下角。

您获得的形状(绿色区域)是所谓的 Minkowski 和(又名膨胀)。

如您所见，它有 5 条直边和一条曲线。您可以轻松预测所有扇形方向的形状。

如果缩小到一个点的矩形位于这个曲线六边形内，则存在交点。您检查该点是否属于使用极坐标(r < R 和 Θ' < Θ < Θ")的扇区，并通过标准多边形点测试检查(直)六边形的内部。

类似的推理适用于圆段(弦)。

---

这种几何变换允许使用“轨迹”方法，即将解集可视化为几何形状，以支持推理。鉴于域的性质(凸六边形)，我们可以得出结论，在最坏的情况下，4 次比较(涉及线性或二次项)足以通过二分法得到答案!