Page 1 of 2 12 LastLast
Results 1 to 10 of 14

Thread: Challenge: PointInRect and RectInRect

  1. #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).

  2. #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]
    The views expressed on this programme are bloody good ones. - Fred Dagg

  3. #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

  4. #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]

  5. #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]

  6. #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.

  7. #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.

  8. #8

    Challenge: PointInRect and RectInRect

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

  9. #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
    Peregrinus, expectavi pedes meos in cymbalis
    Nullus norvegicorum sole urinat

  10. #10

    Challenge: PointInRect and RectInRect

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

Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

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