check if a point belongs to the interior of a polygon?
Author: Sven Luafersweiler
http://www.swissdelphicenter.ch/torry/showcode.php?id=1778
function PtInRgn(TestPolygon : array of TPoint; const P : TPoint): boolean;
var
ToTheLeftofPoint, ToTheRightofPoint : byte;
np : integer;
OpenPolygon : boolean;
XIntersection : real;
begin
ToTheLeftofPoint := 0;
ToTheRightofPoint := 0;
OpenPolygon := False;
{Pr üfen ob das Polygon geschlossen ist}
{tests if the polygon is closed}
if not ((TestPolygon[0].X = TestPolygon[High(TestPolygon)].X) and
(TestPolygon[0].Y = TestPolygon[High(TestPolygon)].Y)) then
OpenPolygon := True;
{Tests für jedes Paar der Punkte, um zu sehen wenn die Seite zwischen
ihnen, die horizontale Linie schneidet, die TestPoint durchläuft}
{tests for each couple of points to see if the side between them
crosses the horizontal line going through TestPoint}
for np := 1 to High(TestPolygon) do
if ((TestPolygon[np - 1].Y <= P.Y) and
(TestPolygon[np].Y > P.Y)) or
((TestPolygon[np - 1].Y > P.Y) and
(TestPolygon[np].Y <= P.Y))
{Wenn es so ist} {if it does}
then
begin
{berechnet die x Koordinate des Schnitts}
{computes the x coordinate of the intersection}
XIntersection := TestPolygon[np - 1].X +
((TestPolygon[np].X - TestPolygon[np - 1].X) /
(TestPolygon[np].Y - TestPolygon[np - 1].Y)) * (P.Y - TestPolygon[np - 1].Y);
{Zähler entsprechend verringern}
{increments appropriate counter}
if XIntersection < P.X then Inc(ToTheLeftofPoint);
if XIntersection > P.X then Inc(ToTheRightofPoint);
end;
{Falls das Polygon offen ist, die letzte Seite testen}
{if the polygon is open, test for the last side}
if OpenPolygon then
begin
np := High(TestPolygon); {Thanks to William Boyd - 03/06/2001}
if ((TestPolygon[np].Y <= P.Y) and
(TestPolygon[0].Y > P.Y)) or
((TestPolygon[np].Y > P.Y) and
(TestPolygon[0].Y <= P.Y)) then
begin
XIntersection := TestPolygon[np].X +
((TestPolygon[0].X - TestPolygon[np].X) /
(TestPolygon[0].Y - TestPolygon[np].Y)) * (P.Y - TestPolygon[np].Y);
if XIntersection < P.X then Inc(ToTheLeftofPoint);
if XIntersection > P.X then Inc(ToTheRightofPoint);
end;
end;
if (ToTheLeftofPoint mod 2 = 1) and (ToTheRightofPoint mod 2 = 1) then Result := True
else
Result := False;
end; {PtInRgn}
---------------------------------------
function ptInPolygon(x,y : integer; Points: array of TPoint) : boolean;
var
rgn:HRGN;
bmp : Tbitmap;
begin
bmp := Tbitmap.create;
BeginPath(bmp.canvas.handle); //开始记录路径
bmp.Canvas.Polygon(points);
EndPath(bmp.canvas.handle); // 闭合路径
rgn:= PathToRegion(bmp.canvas.handle); // 简切视窗
result := PtInRegion(rgn,x,y); // 判断
bmp.free;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
if ptinpolygon(1000,1000,[Point(10, 10), Point(30, 10),
Point(130, 30), Point(240, 120)]) then showmessage('In!')
else showmessage('out!');
end;
***********************************
下面是真正的实现的算法：
huizhang (1998-12-31 8:01:35)
实在对不起, 那个算法确实有问题, 缺少一点判断。
现在给你另外一个算法，叫做"跳栅栏算法"。其原理如下：
假设有一个栅栏，你从现在所站地点沿着一个方向跑过去，遇到栅栏时就跳过去，记住你跳了几次。如果次数是单数，则你在栅栏内；如果是双数，则你在栅栏外。以下算法是向东跑过去的实现方法。该算法虽然用了一点除法，但是由于排除了不相关的栅栏，故速度也很快。此外它的优点是与多边形的排列方向无关。
function TForm1.PointInFence(p: TPoint; Fence: Array of TPoint): boolean;
var
p1: TPoint;
ar: integer;
i, j: integer;
begin
ar:=0;
for i:=0 to PtNos-1 do
begin
if i=PtNos-1 then j:=0 else j:=i+1;
//如果在所站点的水平方向上有栅栏存在
if ((((p.y>=Fence[i].y) and (p.y<fence[j].y)) or
((p.y>=fence[j].y) and (p.y<fence[i].y))) and
//且栅栏在我的右方
(p.x<(fence[j].x-fence[i].x)*(p.y-fence[i].y)/(fence[j].y-fence[i].y)+fence[i].x)) then
ar := Ar+1;
end;
result:= (Ar and $1) > 0;
end;