是否有算法环绕式地图简单的“矩形中的点”？

Question

我试图建立一个矩形网格，可以在边缘处回绕。任何人谁玩视频游戏可能会是熟悉的概念：远远不够在一个方向上的世界地图上，你会最终回到开始的地方。这导致在设置该视口，但是，由于边缘可以滚动到负坐标领地一些困难。

这是很容易采取负坐标和确定其实际值：

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

其中AddPoints和ModPoints简单地套用+和mod运营商，分别的两个输入端的每个坐标以产生输出值。

麻烦的正反转此操作。给定一个点，其中两个坐标为正，TRect其中上和左值可以是正的或负的，（底部或右可能是超出了地图的边缘处），并与MAP_SIZE在全局范围内声明的，是有任何方式确定点是否落入由观看矩形所覆盖的领域内，而不必运行相同的计算多达四个不同的时间？

Answer 1

通过这一点，如果你的意思是在矩形内，你可以测试一下。

function PointInRect(aPoint:TPoint;aRect:TRect):boolean;
begin
  Result:=(aPoint.X >= aRect.Left  ) and 
          (aPoint.X <  aRect.Right ) and 
          (aPoint.Y >= aRect.Top   ) and 
          (aPoint.Y <  aRect.Bottom);
end;

但是，如果我正确地理解你的描述，你想是这样的：

function NormalisePoint(aPoint:TPoint;aRect:TRect):TPoint;
var Width,Height:integer;
begin
  Width  := aRect.Right-aRect.Left;
  Height := aRect.Bottom-aRect.Top;

  if (Width=0) then
    aPoint.X := aRect.Left
  else
  begin
    while (aPoint.X< aRect.Left  ) do inc(aPoint.X,Width );
    while (aPoint.X>=aRect.Right ) do dec(aPoint.X,Width );
  end;

  if (Height=0) then
    aPoint.Y := aRect.Top
  else
  begin
    while (aPoint.Y< aRect.Top   ) do inc(aPoint.Y,Height);
    while (aPoint.Y>=aRect.Bottom) do dec(aPoint.Y,Height);
  end;
  Result := aPoint;
end;

Answer 2

我相信如此。

在最坏的情况下可能我能想到的（网格= [0,1）×[0,1））是这样的： 顶= -0.25，左= -0.25，底= 0.25，右= 0.25

这看起来像（包装时）：

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

现在，你必须测试的四个角落，看看如果点在他们里面。 但是，我认为，在空间[1,2）×[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)

计算新的下和右：

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!
}

我没有测试这种详尽的，但我现在相信这是正确的。

Answer 3

想一想在一维您在两个维度上做到这一点了。你要弄清楚，如果一个数是可能环绕，如范围。是3在从7到2上的时钟的范围内。一旦你有，你可以进行测试的X和Y坐标两者。

我对简单的问题的解决方案：

//assumes start and end are both in [0, divisor). (Because .net and most other languages do modulus WRONG.)
double ClockDistance(double start, double end, double clockSize) {
    return (end - start + clockSize) % clockSize;
}
//assumes inclusive bounds
bool ClockBetween(int n, double start, double end, double clockSize) {
    return ClockDistance(start, n, clockSize) 
           <= ClockDistance(start, end, clockSize);
}

哪些推广到：

//assumes rects oriented so bottom < top, not the other way around like in UI
bool RectContains(double x, double y, double left, double bottom, double right, double top, double worldWidth, double wordlHeight) {
    return ClockBetween(x, left, right, worldWidth) 
           && ClockBetween(y, bottom, top, worldHeight);
}