Is there a simple "point in rect" algorithm for a wraparound map?

Question

I'm trying to build a rectangular grid that can wrap around at the edges. Anyone who plays video games will probably be familiar with the concept: go far enough in one direction on the world map and you'll end up back where you started. This causes some difficulty in setting up the viewport, though, since the edges can scroll into negative coordinate territory.

It's easy enough to take a negative coordinate and determine its real value:

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

where AddPoints and ModPoints simply apply the + and mod operators, respectively, to each coordinate of the two inputs to produce an output value.

The trouble is reversing this operation. Given a point in which both coordinates are positive and a TRect in which the Top and Left values could be positive or negative, (and the Bottom or Right could be beyond the edges of the map,) and with MAP_SIZE declared at global scope, is there any way to determine whether the point falls within the territory covered by the viewing rectangle without having to run the same calculation up to four different times?

Answer 1

I believe so.

The worst possible case I can think of (grid=[0,1)x[0,1) ) is this: Top=-0.25,Left=-0.25, Bottom=0.25, Right=0.25

This looks like (when wrapped):

 ______
|_|  |_|
|      |
|_    _|
|_|__|_|

Right now, you have to test the four corners to see if the point lies inside them. However, I believe that by performing the test in the space [1,2)x[1,2), you can avoid the problem, because once again it becomes a rectangle.

 ______
|      |
|      |
|     _|_
|____|   |
     |___|

Simplify the problem by calculating the width and height of the rectangle.

Width=Mod(Right-Left+MAP_SIZE,MAP_SIZE)
Height=Mod(Bottom-Top+MAP_SIZE,MAP_SIZE)

Now, calculate a wrapped location for the top-left

LeftNew=Mod(Left+MAP_SIZE,MAP_SIZE)
TopNew=Mod(Top+MAP_SIZE,MAP_SIZE)

Calculate the new Bottom and Right:

RightNew=LeftNew+Width
BottomNew=TopNew+Height

Now, for every point you wish to test, add MAP_SIZE, and test if it's inside the new rect!

TestNew=AddPoints(Test,MAP_SIZE)

If (TestNew.X>=LeftNew && TestNew.X<=RightNew && TestNew.Y>=TopNew && TestNew.T<=BottomNew)
{
  We have a point inside!
}

I've not tested this exhaustively, but I currently believe it to be correct.

Answer 2

With this you can test if your point is within the rectangle.

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;

But if I understand your description properly, you want something like this:

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 3

Think about it in 1-dimension before you do it in two dimensions. You want to figure out if a number is in a range which might wrap around, eg. is 3 in the range from 7 to 2 on a clock. Once you have that, you can just perform the test for both the X and Y coordinates.

My solution for the simpler problem:

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

Which generalizes to:

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