Существует ли простой алгоритм “точка в прямоугольнике” для круговой карты?

Question

Я пытаюсь построить прямоугольную сетку, которая может обтекаться по краям.Любой, кто играет в видеоигры, вероятно, знаком с этой концепцией:пройдите достаточно далеко в одном направлении по карте мира, и вы вернетесь к тому, с чего начали.Однако это вызывает некоторые трудности при настройке видового экрана, поскольку края могут прокручиваться в область с отрицательными координатами.

Достаточно легко взять отрицательную координату и определить ее реальное значение:

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

где AddPoints и ModPoints просто применяют + и mod операторы, соответственно, к каждой координате двух входных данных для получения выходного значения.

Проблема в том, чтобы обратить вспять эту операцию.Учитывая точку, в которой обе координаты положительные, и направление, в котором верхнее и левое значения могут быть положительными или отрицательными (а Нижнее или правое могут находиться за пределами краев карты), и с 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

Я верю в это.

Наихудший возможный случай, который я могу придумать (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

Подумайте об этом в 1-м измерении, прежде чем делать это в двух измерениях.Вы хотите выяснить, находится ли число в диапазоне, который может обтекаться, например.равно 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);
}