A collection of TPoint related functions

Problem/Question/Abstract:

A collection of TPoint related functions

Answer:

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;