Challenge: PointInRect and RectInRect

[jdarling]

Ok, so my first "Challenge" didn't get much attention. Makes sense, as I had already posed the question on the board. So I have a new one for this week, its a common problem that we run into in game and game engine development. Rectangle and Point intersection.

The challenge this week is: Write the fastest routines to find out if a point is in a rectangle and if a rectagle intersects another rectangle. The windows API surfaces methods for both of these, but they are known to be slow.

For extra credit, make a version for both common rectangle types:
Type1
TRect=record
Left, Top, Right, Top : Integer;
end
Type2
TRect=record
X, Y, Width, Height : Integer;
end

Here are the prototypes that should be used:
function PointInRect(Pt : TPoint; R : TRect) : Boolean;
function RectInRect(R1, R2 : TRect) : Boolean

As with the first one, here is one solution to the problem (for Type1 only):
function PointInRect(Pt : TPoint; R : TRect) : Boolean;
begin
result := (Pt.X>=R.Left) and (Pt.X<R>=R.Top) and (Pt.Y<=R.Bottom)
end;

function RectInRect(R1, R2 : TRect) : Boolean;
begin
result := PtInRect(Point(R1.Left, R1.Top), R2) or
PtInRect(Point(R1.Right, R1.Bottom), R2) or
PtInRect(Point(R1.Left, R1.Bottom) R2) or
PtInRect(Point(R1.Right, R1.Top), R2) or

PtInRect(Point(R2.Left, R2.Top), R1) or
PtInRect(Point(R2.Right, R2.Bottom), R1) or
PtInRect(Point(R2.Left, R2.Bottom) R1) or
PtInRect(Point(R2.Right, R2.Top), R1);
end;

Of course, the above methods are not at all optimized. Lets do two categories; assembly (windows only) and cross platform (native pascal).

[czar]

Did you forget to include right


function PointInRect(Pt : TPoint; R : TRect) : Boolean;
begin
result := (Pt.X>=R.Left) and(Pt.X<=R.right) and (Pt.X<R>=R.Top) and (Pt.Y<=R.Bottom)
end;

[jdarling]

Yep, I forgot it :). Updated the code above to include (Pt.X<=R.right) and changed functiono to function :)

Thanks for the sanity check czar

[BeRo]

Here my IsIntersectRect (=RectInRect) and GetIntersectRect procedures:


FUNCTION IsIntersectRect(CONST R1,R2:TRect):BOOLEAN;
BEGIN
RESULT:=(R2.Right>=R1.Left) AND (R2.Bottom>=R1.Top) AND (R1.Right>=R2.Left) AND (R1.Bottom>=R2.Top);
END;

FUNCTION Min(A,B:INTEGER):INTEGER;
BEGIN
IF A<B THEN BEGIN
RESULT:=A;
END ELSE BEGIN
RESULT:=B;
END;
END;

FUNCTION Max(A,B:INTEGER):INTEGER;
BEGIN
IF A>B THEN BEGIN
RESULT:=A;
END ELSE BEGIN
RESULT:=B;
END;
END;

FUNCTION GetIntersectRect(OUT DestRect:TRect;CONST R1,R2:TRect):BOOLEAN;
BEGIN
RESULT:=(R2.Right>=R1.Left) AND (R2.Bottom>=R1.Top) AND (R1.Right>=R2.Left) AND (R1.Bottom>=R2.Top);
IF RESULT THEN BEGIN
DestRect.Left:=Max(R1.Left,R2.Left);
DestRect.Right:=Min(R1.Right,R2.Right);
DestRect.Top:=Max(R1.Top,R2.Top);
DestRect.Bottom:=Min(R1.Bottom,R2.Bottom);
END ELSE BEGIN
FILLCHAR(DestRect,SIZEOF(TRect),#0);
END;
END;

[Sly]

First of all I had to fix your PointInRect function. You were comparing Pt.X against R.Top. Also, use the const directive so you are not passing the record by value.

Secondly, I would make an overloaded PointInRect() so you are not creating new TPoint instances all the time just to pass to PointInRect() from RectInRect().

function PointInRect(const Pt: TPoint; const R: TRect) : Boolean; overload;
begin
Result := (Pt.X >= R.Left) and (Pt.X <R>= R.Top) and (Pt.Y <R>= R.Left) and (X <R>= R.Top) and (Y <= R.Bottom);
end;

There was another version of PointInRect() in that code that took X, Y: Single instead of const Pt: TPoint, but the forum software is refusing to show it. :evil:

Also, you should be able to get away with just four of the conditions in RectInRect(). I think you will find that it would not get into the second four at all due to short-circuit evaluation.

function RectInRect(const R1: TRect; const R2 :TRect): Boolean;
begin
Result := PtInRect(R1.Left, R1.Top, R2) or
PtInRect(R1.Right, R1.Bottom, R2) or
PtInRect(R1.Left, R1.Bottom, R2) or
PtInRect(R1.Right, R1.Top, R2);
end;

[jdarling]

Sly, nice try, but no. You have to check for R1 points intersecting R2 and R2 points intersecting R1 due to the fact that R1 or R2 may be completely inside of each other. In witch case, if you test only the inner rect and not the outer rect, you will get a false false.

I'll edit my post above and fix (Pt.X>=R.Top) to (Pt.Y>=R.Top). Thats what I get for not copy/pasting working code :).

The idea is still to find the fastest way to find if a point is in a given rectangle and/or if two rectangles are within or touching one another.

Also, using CONST is a matter of openion. Not using it lets you change the values held within locally w/o having a temp var. You can always write it using const, as it will run in the testbed either way.

[grudzio]

Sly is right that RectInRect function can be reduced to four PointInRect checks.


function RectInRect(R1, R2 : TRect) : Boolean;
begin
Result := PointInRect(R1.Left,R1.Top,R2) or
PointInRect(R1.Right,R1.Bottom,R2) or
PointInRect(R2.Right,R2.Top,R1) or
PointInRect(R2.Left,R2.Bottom,R1);
end;

It uses two diagonal points of the first rect and two points of second rect taken from second diagonal.

[Sly]

Sly is right that RectInRect function can be reduced to four PointInRect checks.

It uses two diagonal points of the first rect and two points of second rect taken from second diagonal.
My theory was right, but my proof was wrong. :)

Using const in this case will help with performance because it will not be copying the records to pass by value. Since the records are not being modified within the functions, use const for the performance benefit.

Also use the PointInRect that takes two Singles and a const TRect as it will be faster than calling another function to return a TPoint by value then passing that TPoint to RectInRect.

[JSoftware]

+--+
| |
+--+--+-+
| | | |
+--+--+-+
| |
+--+


Shall this condition evaluate true in the RectInRect function?
If yes, then Sly's code isn't complete

[grudzio]

+--+
| |
+--+--+-+
| | | |
+--+--+-+
| |
+--+


Shall this condition evaluate true in the RectInRect function?
If yes, then Sly's code isn't complete

Good question. Note that even JDarlings function will not detect this, since there are no corner points inside any of the rects.

[grudzio]

All right. Here is another version that works for all cases including JSoftware's one.

function RectInRect(R1,R2 : TRect) : boolean;
var
w,h : integer;
x1,x2,y1,y2 : integer;
begin
w := (R1.Right - R1.Left) + (R2.Right - R2.Left);
h := (R1.Bottom - R1.Top) + (R2.Bottom - R2.Top);

x1 := min(R1.Left, R2.Left);
x2 := max(R1.Right, R2.Right);
y1 := min(R1.Top, R2.Top);
y2 := max(R1.Bottom, R2.Bottom);

Result := ((x2-x1) < w) and ((y2-y1) < h);
end;


This function uses the fact that if two rects overlap then the difference
between smallest left and biggest right coordinate must be smaller then the sum of their widths. Same with Top and Bottom values.
What is your opinion? Any thoughts on improving?

[Nitrogen]

You could have early-outs so the function doesnt have to compute needless information:

function RectInRect(R1,R2 : TRect) : boolean;
var
w,h : integer;
x1,x2,y1,y2 : integer;
begin
w := (R1.Right - R1.Left) + (R2.Right - R2.Left);

x1 := min(R1.Left, R2.Left);
x2 := max(R1.Right, R2.Right);

if ((x2-x1) < w) then begin result := false; exit; end;

h := (R1.Bottom - R1.Top) + (R2.Bottom - R2.Top);

y1 := min(R1.Top, R2.Top);
y2 := max(R1.Bottom, R2.Bottom);

Result := ((y2-y1) < h);
end;

[jdarling]

Well, JSoftware points out a situation that should work. I have to admit that my code doesn't work in that situation :(. Course, the idea is to post a common problem and hopefully find a fast solution for anyone to use, idealy the sample code I provide would work, but in this case, seems I goofed.

[User137]

Here's my versions:

Makes check for rectangle first and turn it around if needed... reading above solutions this may not be fastest :s

// Switches 2 any variables
procedure SwitchVar(p1,p2: Pointer; Size: Integer);
var temp: pointer;
begin
getmem(temp,size);
try
movememory(temp,p1,Size);
movememory(p1,p2,Size);
movememory(p2,temp,Size);
finally
freemem(temp);
end;
end;

function PointInRect2(p: TPoint; r: TRect): boolean;
begin
if r.Left>r.Right then switchvar(@r.left,@r.right,4);
if r.Top>r.Bottom then switchvar(@r.top,@r.bottom,4);
result:=(p.x>=r.Left) and (p.x<=r.Right) and
(p.y>=r.Top) and (p.y<=r.Bottom);
end;


I found this function in other language who knows where.. anyway i just tested every possible situation with it to success. Only exception for fail is if rectangles are not made normally; top left to bottom right.

function RectCollide(x0,y0,x1,y1,x2,y2,x3,y3: single): boolean;
begin
result:=not( ((x0<x2) and (x1<x2)) or
((x0>x3) and (x1>x3)) or
((y0<y2) and (y1<y2)) or
((y0>y3) and (y1>y3)) );
end;

Edit: Had to remove all BBCode etc. because they removed parts of code...