二维圆形 – 矩形碰撞,最有效的方法

假设我有一个圆形与一个矩形相交,理想的情况是两者之间最不密集的cpu方式是什么?

  1. 方法A

    1. 计算矩形边界
    2. 循环通过圆的所有点,并为每个人,检查是否在矩形里面。
  2. 方法B

    1. 计算矩形边界
    2. 检查圆的中心在哪里,与矩形比较
    3. 为以下职位制作9个开关/案例陈述:

      • 顶部,底部,左侧,右侧
      • 左上角,右上角,左下角,右下角
      • 里面的矩形
    4. 使用圆的半径检查只有一个距离取决于发生圆的地方。

我知道还有其他方法肯定比这两个更好,如果能指出我与他们的联系,将是伟大的,但在这两者之间,你认为哪一个更好,关于性能和质量/精度?

提前致谢。

方法B对于一个完美的圆更精确。 在方法A中,你正在讨论循环中的每一个点,并且我假设这个点数不是很less(可能至less是12)。 那么考虑一下,你正在循环点 – 条件比非条件操作慢。

另一方面,方法B使用平方根。 这并不便宜,但是一个平方根几乎肯定比n条件好。

说了这么多,我相当肯定方法B将是你最好的select,如果你想要的准确性和良好的速度。

正确和标准的方法实际上是这样的:

方法C

  1. 计算矩形边界(如果没有矩形旋转,则是它们自己的边界,如果它们在平面中旋转,则是边界框)。
  2. 计算每个圆的矩形边界。
  3. 在x和y轴的每个轴上应用快速范围重叠testing来检查对象A和B(可能是矩形和圆形)之间的边界交集。 如果重叠,继续,否则中断,因为如果它们的边界不重叠,它们不可能重叠。
  4. 应用更昂贵的testing圆圈或直圆圈相交testing,看看他们是否真的重叠。 这是有些昂贵的平方根操作进入,以确定给定矩形的4个点中的每一个是否在圆的半径内。

像这样的分层方法,在这种情况下,通过增加(有条件的)成本的顺序来testing连续消除的可能性,在所有forms的碰撞检测中都是无处不在的。

最终,尽可能避免条件句,特别是冗长的循环语句。 看到这个线程有一个优先的想法。 这就是为什么像C这样的低级语言提供循环展开作为编译时优化的原因。

编辑 opatut已经注意到,平方根不是方法B&C(见注释)的要求,留下方法A作为最明显的最坏的方法。