# Thread: Challenge: PointInRect and RectInRect

1. ## Challenge: PointInRect and RectInRect

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
[pascal]TRect=record
Left, Top, Right, Top : Integer;
end[/pascal]
Type2
[pascal]TRect=record
X, Y, Width, Height : Integer;
end[/pascal]

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

As with the first one, here is one solution to the problem (for Type1 only):
[pascal]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;[/pascal]

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

2. ## Challenge: PointInRect and RectInRect

Did you forget to include right

[pascal]
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; [/pascal]  Reply With Quote

3. ## Challenge: PointInRect and RectInRect

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  Reply With Quote

4. ## Challenge: PointInRect and RectInRect

Here my IsIntersectRect (=RectInRect) and GetIntersectRect procedures:

[pascal]
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;
[/pascal]  Reply With Quote

5. ## Challenge: PointInRect and RectInRect

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().

[pascal]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;[/pascal]

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.

[pascal]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;[/pascal]  Reply With Quote

6. ## Challenge: PointInRect and RectInRect

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.  Reply With Quote

7. ## Challenge: PointInRect and RectInRect

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

[pascal]
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;[/pascal]

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

8. ## Challenge: PointInRect and RectInRect Originally Posted by grudzio
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.  Reply With Quote

9. ## Challenge: PointInRect and RectInRect

[pascal]
+--+
| |
+--+--+-+
| | | |
+--+--+-+
| |
+--+
[/pascal]

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

10. ## Challenge: PointInRect and RectInRect Originally Posted by JSoftware
[pascal]
+--+
| |
+--+--+-+
| | | |
+--+--+-+
| |
+--+
[/pascal]

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.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•
Comodo SSL