java - 在网格上查找相交四边形的算法

Question

这是我的问题。

我的游戏，为了高效的渲染和碰撞被划分成区域。每个区域中都会有许多动态移动的对象。当它们移动时，我需要一种方法来快速确定它们所在的区域。

一个对象永远不能比一个区域长或宽。因此它永远不会同时在超过 4 个区域。

棘手的部分是对象的矩形是在 2D 中使用分离轴定理的 Oriented Bounding Boxes，因此它们可以旋转。

我想到的主要方法是确定每个点的区域:

static public int colFromPos(float startX,float width, float x)
{
    x -= startX;
    return (int)Math.floor(x / width);

}

static public int rowFromPos(float startY,float height, float y)
{
    y -= startY;
    return (int)Math.floor(y / height);

}

这看起来相当快。

我想到了几种方法来做到这一点:

1. I generate a bounding rectangle of the OBB and find the 4 regions of this rectangle. The drawback here is that a furthur test must then be done to determine if the object really is in.
2. I determine the region of each corner and each midpoint of the OBB.

是否有更好、更快的方法来解决这个问题？我的解决方案中的任何一个都是好主意吗？

谢谢

Answer 1

确定包含 OBB 每个顶点的区域。

如果所有四个都在同一区域，则返回该区域。

如果所有四个区域都位于共享 X 坐标或共享 Y 坐标的一对区域中，则返回该对区域。

如果它们位于四个不同的区域，则返回该组四个区域。

如果这些条件都不适用，则您有两个不同的区域 X 坐标和两个不同的区域 Y 坐标，定义一组四个区域在一个顶点 V 处相遇。

如果 V 在 OBB 内，则返回所有四个区域。

如果 V 在 OBB 之外，并且 OBB 顶点位于三个不同的区域，则返回这三个区域。

剩下的情况是一对对角相邻的区域包含OBB的顶点，V在OBB之外。选择连接不在同一区域的顶点的 OBB 的一侧。返回两个包含顶点的区域，以及该线穿过的第三个区域。

我还没有解决例如问题V 正好在 OBB 的一侧。这些情况的处理取决于程序约定。