网格上求交点四边形的java算法

Question

这是我的问题

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

一个对象永远不能比一个区域长或宽。因此，它不能同时位于4个以上的区域

棘手的部分是，对象的矩形是使用2D中的分离轴定理定向的边界框，因此它们可以旋转

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

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一边的问题。这些案件的处理取决于程序惯例