重叠AABB-圆弧和AABB-Pie

Question

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

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

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

例如，一个非常小的AABB只包含饼的中心，但AABB的边缘不相交，馅饼的圆圈将不会覆盖在链接的答案中。同样，电弧完全包含AABB和AABB的两侧甚至不相交的情况下，脐带也不会被覆盖。

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

AABB的一个例子-部门：

​

​

Answer 1

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

您将使问题更简单，通过分裂扇区与一个交叉通过中心，这样一条水平或垂直线将不会遇到两次弧线，并分别处理。

然后，考虑其中的一部分，“充气”，而你“放气”的矩形。更准确地说，扇区的每个点都变成了源自它的矩形(左上角)，而矩形则缩小到它的右下角。

你得到的形状(绿色区域)是所谓的Minkowski和(也就是膨胀)。

正如你所看到的，它有5条直边和一条弯曲边。您可以很容易地预测所有扇区方向的形状。

​

​

现在有一个交点，如果矩形收缩到一个点，在这个曲线六边形内。使用极坐标(r < R和Θ' < Θ < Θ")检查点是否属于扇区，并通过标准的多边形点对点测试检查(直)六边形的不平顺性。

类似的推理也适用于圆形段(chord)。

​

​

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

Answer 2

部门和部门的情况不同。

关于某一部分：

• 如果圆段的AABB不相交，那就不是。
• 如果和弦与AABB相交(或在AABB内)，则回答是肯定的。这是线段到矩形的测试，我想你知道怎么做。
• 这只剩下AABB在圆段内或与弧线相交的情况.要做到这一点，至少其中一方的一部分必须在部分(或整个部分将包含和弦，我们会发现在前面的步骤)。
• 因此，将矩形看作四条线，对于每一行
  • 通过与圆的交点计算圆内的线段
  • 如果存在，则通过与和弦的比较，检查线的任何一端是否位于圆圈段的内部。

​

对于扇区，可以将其视为一个段加一个三角形，或者：

• 如果圆形的AABB不相交，那就不是。
• 如果任何一条径向线相交，那么是的。
• 否则，将矩形视为四个线段，并对每个线段：
  • 通过与圆的交点计算圆内的线段。
  • 如果存在，则计算位于第一条径向线正确一侧的子段。
  • 如果存在，则计算位于第二条径向线正确一侧的子段。

​