Bezdepbonusu7Программирование: статьи и ответы
Меню

Вопрос

Есть ли простая точка в прямоугольном алгоритме для карты с закруглением?

Автор вопроса: Mason WheelerОтветов: 3

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

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

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, объявленным в глобальной области видимости, Есть ли способ определить, попадает ли точка на территорию, охватываемую прямоугольником просмотра, без необходимости выполнять один и тот же расчет до четырех разных раз?

coordinatesdelphialgorithmmathgeometry

Ответы

Ответ 1 · рейтинг 3 · Wouter van Nifterick

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

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;

Ответ 2 · рейтинг 4 · Dave Gamble

Я так считаю.

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

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

Ответ 3 · Craig Gidney

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

Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.

Похожие материалы