代码之家 › 专栏 › 技术社区 › Mason Wheeler

有没有一个简单的“点在矩形”算法的包围地图?

coordinates geometry math delphi algorithm

Mason Wheeler · 技术社区 · 16 年前

我正在尝试建立一个矩形网格,可以在边缘环绕。任何玩电子游戏的人都可能熟悉这个概念:在世界地图上朝一个方向走足够远,你就会回到你开始的地方。但是,这会给设置视区带来一些困难,因为边缘可以滚动到负坐标区域。

取负坐标并确定其实际值很容易:

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

其中,addpoints和modpoints只应用 + 和 mod 运算符分别对两个输入的每个坐标生成一个输出值。

故障是使这个操作倒退。如果一个点的两个坐标都是正的,并且左上角的值可以是正的或负的(右下角的值可以超出地图的边缘),并且在全局范围内声明了地图大小,那么是否有任何方法可以确定该点是否位于观察矩形所覆盖的区域内?不需要运行相同的计算多达四次不同的时间?

3 回复 | 直到 16 年前

Wouter van Nifterick Andrey 16 年前

通过这个,您可以测试您的点是否在矩形内。

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;

Dave Gamble 16 年前

我相信是这样的。

我能想到的最坏情况(网格=[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)

计算新的底部和右侧:

RightNew=LeftNew+Width
BottomNew=TopNew+Height

现在,对于您想要测试的每一个点,添加地图大小,并测试它是否在新rect中!

TestNew=AddPoints(Test,MAP_SIZE)

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

我并没有详尽地测试过这个问题,但我现在认为它是正确的。

Craig Gidney Mihai 16 年前

先从一维考虑,然后再从二维考虑。你想知道一个数字是否在一个可能环绕的范围内,例如,在时钟上是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);
}