image-processing - 我们可以将四叉树应用于非方形矩形吗？

Question

我正在尝试使用四叉树实现二维快速碰撞检测。

AFAIK，四叉树将一个区域分为 4 个子区域，西北、东北、东南和西南。这种划分与正方形完美配合。但是如果这个区域是一个非正方形的矩形呢？在那种情况下，我们不能将长边和短边平均分割，而短边决定了我们可以分割多远。

我说得对吗？是这样的吗？

Answer 1

只需将感兴趣区域的边界框的宽度、高度的最大值作为四叉树的边长。

另一种解决方案：我见过的两个四叉树实现在内部使用了一个矩形，因此即使提供的根边界不是正方形，它也会开箱即用。它们在每个细分步骤中划分边界的宽度和高度。
但请注意，有超过 10 种不同的四叉树类型。我说的是矩形四叉树。

一种实现明确地使用除以 2 的 aa 边长，因此对于非平方根边界将无法正常工作。

但是，我仍然推荐我的第一句话，最好使用平方作为根边界。这适用于所有四叉树类型。