Geek Answers Handbook

Is there a simple point in rect algorithm for wrapping?

I am trying to build a rectangular grid that can wrap around the edges. Anyone who plays video games is likely to be familiar with the concept: go far enough one way on the world map and you will return to where you started. This creates certain difficulties when adjusting the viewing area, however, since the edges can scroll to the negative territory of coordinates.

It is easy 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 to each coordinate of the two inputs, respectively, to create an output value.

The problem is changing this operation. Given the point at which both coordinates are positive, and TRect, where the Top and Left values ​​can be positive or negative (and the bottom or right can be outside the borders of the map) and with MAP_SIZE declared globally, is there any is there any way to determine if this point falls into the territory covered by the viewing rectangle without having to perform the same calculation up to four different times?

+4
source share
3 answers

With this, you can check if your point is inside 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 correctly, you need 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;
+3
source

I think so.

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

It looks (on packaging):

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

Right now, you need to check the four corners to see if there is a point in them. However, I believe that by running the test in the space [1,2) x [1,2), you can avoid the problem because it becomes a rectangle again.

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

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 the wrapped location for the top left

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

Calculate the new one from bottom to right:

 RightNew=LeftNew+Width BottomNew=TopNew+Height

Now, for each point you want to test, add MAP_SIZE and check if it is 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 have not tested this exhaustively, but currently I think that is correct.

+4
source

Think about it in 1-dimensional form before doing this in two dimensions. You want to find out if a number is in a range that can be wrapped around, for example. is 3 in the range of 7 to 2 on the watch. After that, you can simply run the test for the X and Y coordinates.

My solution for a simpler task:

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

What 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); }
0
source

More articles:


All Articles