2010. április 24., szombat

A collection of TPoint related functions


A collection of TPoint related functions


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

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

  dx1, dx2: LongInt;
  dy1, dy2: LongInt;
  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
    Result := -1;

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

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

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

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

  xmin, xmax, ymin, ymax: Integer;
  pt: TPoint;
  i: Word;
  xmin := MaxInt;
  ymin := MaxInt;
  xmax := -MaxInt;
  ymax := -MaxInt;
  for i := 0 to High(PolyPoints) do
    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;
  prbound := Rect(xmin, ymin, xmax, ymax);
  Result := PtInRect(prbound, ptTest);

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

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

  i: Integer;
  pt1, pt2: TPoint;
  wnumintsct: Word;
  prbound: TRect;
  wnumintsct := 0;
  Result := False;
  if (not G_PtInPolyRect(PolyPoints, ptTest, prbound)) then
  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
  {And the last line}
  if (Intersect(ptTest, pt2, PolyPoints[High(PolyPoints)], PolyPoints[0])) then
  {If wnumintsct is odd then the point is inside the polygon}
  Result := Odd(wnumintsct);

Nincsenek megjegyzések:

Megjegyzés küldése