我正在寻找一种简单的算法来检测 aabb 的区域是否与圆弧(由绳索闭合)或饼图(通过圆心闭合)的区域重叠。
我已经找到了这个答案:Intersection of rectangle and circle (or arc)
但这并不是我要找的东西,因为我对形状轮廓的交点不感兴趣,只是想知道这些区域是否重叠。
例如,非常小的 AABB 仅包含馅饼的中心但 AABB 的边缘不与馅饼的圆相交的情况不会包含在链接的答案中。 同样,弧完全包含 AABB 且 AABB 的边甚至不与绳索相交的情况也不会被覆盖。
现在,在我开始重新发明轮子之前,我想问一下是否有用于这种重叠检查的已知算法。
AABB 扇区示例:
最佳答案
考虑到配置的多样性,这不是一个简单的问题。
您可以通过以十字为中心分割扇形来简化问题,这样水平线或垂直线就不会与圆弧相交两次,并分别处理这些部分。
然后考虑其中一个部分并在“收缩”矩形的同时“膨胀”它。更准确地说,扇区的每个点都变成了从它开始的矩形(左上角),而矩形缩小到它的右下角。
您获得的形状(绿色区域)是所谓的 Minkowski 和(又名膨胀)。
如您所见,它有 5 条直边和一条曲线。您可以轻松预测所有扇形方向的形状。
如果缩小到一个点的矩形位于这个曲线六边形内,则存在交点。您检查该点是否属于使用极坐标(r < R
和 Θ' < Θ < Θ"
)的扇区,并通过标准多边形点测试检查(直)六边形的内部。
类似的推理适用于圆段(弦)。
这种几何变换允许使用“轨迹”方法,即将解集可视化为几何形状,以支持推理。鉴于域的性质(凸六边形),我们可以得出结论,在最坏的情况下,4 次比较(涉及线性或二次项)足以通过二分法得到答案!
关于algorithm - 重叠 AABB-Arc 和 AABB-Pie,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32744344/