Есть ли простой алгоритм «point in rect» для обходной карты?

Question

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

Это достаточно легко принять отрицательные координаты и определить его реальную стоимость:

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

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

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

Теперь рассчитать обернутое место для верхнего левого

Вычислить новое нижнее и правый:

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); 
}