## 2010. április 24., szombat

### A collection of TPoint related functions

Problem/Question/Abstract:

A collection of TPoint related functions

function CCW(p0, p1, p2: TPoint): Integer;

{Purpose:
Determines, given three points, if when travelling from the first to the second
to the third, we travel in a counterclockwise direction.
Return Value:
(int) 1 if the movement is in a counterclockwise direction, -1 if not.}

var
dx1, dx2: LongInt;
dy1, dy2: LongInt;
begin
dx1 := p1.x - p0.x;
dx2 := p2.x - p0.x;
dy1 := p1.y - p0.y;
dy2 := p2.y - p0.y;
{This is basically a slope comparison: we don't do divisions because
of divide by zero possibilities with pure horizontal and pure vertical lines.}
if ((dx1 * dy2) > (dy1 * dx2)) then
Result := 1
else
Result := -1;
end;

function Intersect(p1, p2, p3, p4: TPoint): Boolean;

{Purpose: Given two line segments, determine if they intersect.
Return Value: TRUE if they intersect, FALSE if not.}

begin
Result := (((CCW(p1, p2, p3) * CCW(p1, p2, p4)) <= 0) and
((CCW(p3, p4, p1) * CCW(p3, p4, p2) <= 0)));
end;

function G_PtInPolyRect(PolyPoints: array of TPoint; ptTest: TPoint;
var prbound: TRect): Boolean;

{Purpose:
This routine determines if a point is within the smallest rectangle that encloses a polygon.
Return Value:
(BOOL) True or False depending on whether the point is in the rect or not.}

var
xmin, xmax, ymin, ymax: Integer;
pt: TPoint;
i: Word;
begin
xmin := MaxInt;
ymin := MaxInt;
xmax := -MaxInt;
ymax := -MaxInt;
for i := 0 to High(PolyPoints) do
begin
pt := PolyPoints[i];
if (pt.x < xmin) then
xmin := pt.x;
if (pt.x > xmax) then
xmax := pt.x;
if (pt.y < ymin) then
ymin := pt.y;
if (pt.y > ymax) then
ymax := pt.y;
end;
prbound := Rect(xmin, ymin, xmax, ymax);
Result := PtInRect(prbound, ptTest);
end;

function G_PtInPolygon(PolyPoints: array of TPoint; ptTest: TPoint): Boolean;

{Purpose:
This routine determines if the point passed is in the polygon. It uses the classical polygon hit-testing algorithm: A horizontal ray starting at the point is extended infinitely rightwards and the number of polygon edges that intersect the ray are counted. If the number is odd, the point is inside the polygon.
Return Value:
(BOOL) True if the point is inside the polygon, False if not.}

var
i: Integer;
pt1, pt2: TPoint;
wnumintsct: Word;
prbound: TRect;
begin
wnumintsct := 0;
Result := False;
if (not G_PtInPolyRect(PolyPoints, ptTest, prbound)) then
Exit;
pt1 := ptTest;
pt2 := ptTest;
pt2.x := prbound.Right + 50;
{Now go through each of the lines in the polygon and see if it intersects}
for i := 0 to High(PolyPoints) - 1 do
if (Intersect(ptTest, pt2, PolyPoints[i], PolyPoints[i + 1])) then
Inc(wnumintsct);
{And the last line}
if (Intersect(ptTest, pt2, PolyPoints[High(PolyPoints)], PolyPoints[0])) then
Inc(wnumintsct);
{If wnumintsct is odd then the point is inside the polygon}
Result := Odd(wnumintsct);
end;