algorithm - 是否有用于环绕式 map 的简单 "point in rect"算法？

Question

我正在尝试构建一个可以在边缘环绕的矩形网格。任何玩电子游戏的人都可能熟悉这个概念:在世界地图上朝一个方向走得足够远，你最终会回到起点。不过，这会在设置视口(viewport)时造成一些困难，因为边缘可以滚动到负坐标区域。

获取负坐标并确定其实际值非常容易:

function GetRealCoords(value: TPoint): TPoint;
begin
   result := ModPoints(AddPoints(value, MAP_SIZE), MAP_SIZE);
end;

其中 AddPoints 和 ModPoints 简单地将 + 和 mod 运算符分别应用于两个输入的每个坐标以产生输出值。

麻烦在于反转这个操作。给定两个坐标均为正的点和 Top 和 Left 值可以为正或负的 TRect(并且 Bottom 或 Right 可以超出 map 的边缘)，并且在全局范围内声明 MAP_SIZE，是有什么方法可以确定该点是否落在查看矩形所覆盖的区域内，而无需最多四次不同地运行相同的计算？

Answer 1

我相信是的。

我能想到的最坏情况 (grid=[0,1)x[0,1) ) 是这样的:上=-0.25，左=-0.25，下=0.25，右=0.25

这看起来像(包裹后):

 ______
|_|  |_|
|      |
|_    _|
|_|__|_|

现在，您必须测试四个角，看看点是否在其中。但是，我相信通过在空间 [1,2)x[1,2) 中执行测试，您可以避免问题，因为它再次变成了一个矩形。

 ______
|      |
|      |
|     _|_
|____|   |
     |___|

通过计算矩形的宽和高来简化问题。

Width=Mod(Right-Left+MAP_SIZE,MAP_SIZE)
Height=Mod(Bottom-Top+MAP_SIZE,MAP_SIZE)

现在，计算左上角的环绕位置

LeftNew=Mod(Left+MAP_SIZE,MAP_SIZE)
TopNew=Mod(Top+MAP_SIZE,MAP_SIZE)

计算新的 Bottom 和 Right:

RightNew=LeftNew+Width
BottomNew=TopNew+Height

现在，对于您要测试的每个点，添加 MAP_SIZE，并测试它是否在新矩形内!

TestNew=AddPoints(Test,MAP_SIZE)

If (TestNew.X>=LeftNew && TestNew.X<=RightNew && TestNew.Y>=TopNew && TestNew.T<=BottomNew)
{
  We have a point inside!
}

我没有对此进行详尽的测试，但我目前认为它是正确的。