SRL Archive - SRL-OSR Snippets

I found a function online to return whether or not a point is inside of a polygon, and I thought I would share it here:

Original link: http://wiki.freepascal.org/Geometry_in_Pascal

[spoiler=Original code:]

function IsPointInPolygon(AX, AY: Integer; APolygon: array of TPoint): Boolean;
var
  xnew, ynew: Cardinal;
  xold,yold: Cardinal;
  x1,y1: Cardinal;
  x2,y2: Cardinal;
  i, npoints: Integer;
  inside: Integer = 0;
begin
  Result := False;
  npoints := Length(APolygon);
  if (npoints < 3) then Exit;
  xold := APolygon[npoints-1].X;
  yold := APolygon[npoints-1].Y;
  for i := 0 to npoints - 1 do
  begin
    xnew := APolygon[i].X;
    ynew := APolygon[i].Y;
    if (xnew > xold) then
    begin
      x1:=xold;
      x2:=xnew;
      y1:=yold;
      y2:=ynew;
    end
    else
    begin
      x1:=xnew;
      x2:=xold;
      y1:=ynew;
      y2:=yold;
    end;
    if (((xnew < AX) = (AX <= xold))         // edge "open" at left end
      and ((AY-y1)*(x2-x1) < (y2-y1)*(AX-x1))) then
    begin
      inside := not inside;
    end;
    xold:=xnew;
    yold:=ynew;
  end;
  Result := inside <> 0;
end;

[/spoiler]
[spoiler=Converted to fit our needs:(very small changes)]

function R_inPolygon(Area: TPointArray): Boolean;
var
  xnew, ynew, xold, yold, X1, Y1, X2, Y2: Cardinal;
  i, numpoints, inside, X, Y: Integer;
begin
  numpoints := Length(Area);
  X := R_GetTileGlobal.x;
  Y := R_GetTileGlobal.y;
  if (numpoints < 3) then Exit;
  xold := Area[numpoints - 1].x;
  yold := Area[numpoints - 1].y;
  for i := 0 to (numpoints - 1) do
  begin
    xnew := Area[i].x;
    ynew := Area[i].y;
    if (xnew > xold) then
    begin
      X1 := xold;
      X2 := xnew;
      Y1 := yold;
      Y2 := ynew;
    end
    else
    begin
      X1 := xnew;
      X2 := xold;
      Y1 := ynew;
      Y2 := yold;
    end;
    if (((xnew < X) = (X <= xold)) and ((Y - Y1) * (X2 - X1) < (Y2 - Y1) * (X - X1))) then
      inside := not inside;
    xold := xnew;
    yold := ynew;
  end;
  Result := inside <> 0;
end;

[/spoiler]

You need > 3 points for it to properly work.

A while ago I was thinking of (using some basic calculus stuff) finding where the slopes between points in a polygon are positive or negative using the derivative, and then doing some stuff that im too high to explain to create a function that returns a string that, kind of like a dtm, represents a series of booleans and points and stuff to create like an artificial simba polygon,

good stuff tho mr barbrady, move along people nothing to see here

From: Nebula
A while ago I was thinking of (using some basic calculus stuff) finding where the slopes between points in a polygon are positive or negative using the derivative, and then doing some stuff that im too high to explain to create a function that returns a string that, kind of like a dtm, represents a series of booleans and points and stuff to create like an artificial simba polygon,

good stuff tho mr barbrady, move along people nothing to see here

Can you expand on that later when your not high?

why not use Sign? didnt really look at the math behind that function but from my engine, cba converting…

	public float Sign(PointD PointD_A, PointD PointD_B, PointD PointD_C) {
		return (PointD_A.X() - PointD_C.X()) * (PointD_B.Y() - PointD_C.Y())
				- (PointD_B.X() - PointD_C.X()) * (PointD_A.Y() - PointD_C.Y());
	}

	public boolean PointInTri(PointD PointD_P, PointD PointD_A,
			PointD PointD_B, PointD PointD_C) {

		boolean[] boolArrTemp = new boolean[3];

		boolArrTemp[0] = (Sign(PointD_P, PointD_A, PointD_B) <= 0.0F);
		boolArrTemp[1] = (Sign(PointD_P, PointD_B, PointD_C) <= 0.0F);
		boolArrTemp[2] = (Sign(PointD_P, PointD_C, PointD_A) <= 0.0F);

		return (boolArrTemp[0] == boolArrTemp[1])
				&& (boolArrTemp[1] == boolArrTemp[2]);
	}