jdarling

17-01-2007, 01:35 AM

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

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