Существует ли простой алгоритм «точка в прямоугольнике» для карты с циклическим переходом? - PullRequest
Новая
       27

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

4 голосов
/ 12 июля 2009

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

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

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

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

Проблема в том, что эта операция отменена. Учитывая точку, в которой обе координаты положительны, и значение TRect, в котором значения Top и Left могут быть положительными или отрицательными (а Bottom или Right могут быть за пределами границ карты), а MAP_SIZE, объявленный в глобальной области видимости, Есть ли способ определить, попадает ли точка на территорию, покрытую прямоугольником обзора, без необходимости выполнять один и тот же расчет до четырех раз?

Ответы [ 3 ]

4 голосов
/ 12 июля 2009

Я верю в это.

Худший возможный случай, о котором я могу подумать (grid = [0,1) x [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!
}

Я не исчерпывающе проверил это, но в настоящее время считаю, что это правильно.

3 голосов
/ 12 июля 2009

С этим вы можете проверить, находится ли ваша точка внутри прямоугольника. 

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;
0 голосов
/ 13 июля 2009

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