랩어라운드 맵에 대한 간단한 "직접 점" 알고리즘이 있습니까?

Question

가장자리를 둘러쌀 수 있는 직사각형 격자를 만들려고 합니다.비디오 게임을 하는 사람이라면 누구나 다음 개념에 익숙할 것입니다.세계 지도에서 한 방향으로 충분히 이동하면 시작한 곳으로 다시 돌아올 수 있습니다.하지만 가장자리가 음의 좌표 영역으로 스크롤될 수 있으므로 뷰포트를 설정하는 데 약간의 어려움이 발생합니다.

음의 좌표를 취해 실제 값을 결정하는 것은 쉽습니다.

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

여기서 AddPoint와 ModPoint는 단순히 + 그리고 mod 연산자를 각각 두 입력의 각 좌표에 연결하여 출력 값을 생성합니다.

문제는 이 작업을 취소하는 것입니다.두 좌표가 모두 양수이고 위쪽 및 왼쪽 값이 양수 또는 음수일 수 있고(아래쪽 또는 오른쪽이 지도 가장자리 너머에 있을 수 있음) TRect가 전역 범위에서 선언된 MAP_SIZE를 사용하는 점은 다음과 같습니다. 동일한 계산을 최대 4번까지 실행할 필요 없이 점이 보기 직사각형으로 덮힌 영역 내에 있는지 여부를 확인할 수 있는 방법이 있습니까?

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

나는 그렇다고 믿는다.

(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)

새로운 아래쪽과 오른쪽을 계산합니다.

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

2차원으로 작업하기 전에 1차원으로 생각해 보세요.숫자가 둘러싸일 수 있는 범위에 있는지 확인하고 싶습니다.시계의 7에서 2 사이의 3입니다.그런 다음 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);
}