この発言は
#00077　Dia             さんのある点が三角形の中か外か
に対するコメントです

この発言に対し以下のコメントが寄せられています

#00787　裏目小僧        さん　RE:多角形の内と外の判定

#00788　裏目小僧        さん　線分の上かどうか（多角形)





 ３角形を含む任意の多角形の内外判定  

 点 x,y と n多角形 ptを与えて 点が内側か外側かを判定
function PolygonExterior(x,y,n:integer;pt:array of TPoint):boolean;
var i,ct,nx,dx,dy,rx,ry:integer;
begin
pt[n]:=pt[0]; {始点は終点と等しいとします}
ct :=0;
 for i:=0 to n-1 do begin
  rx:=x-pt[i].x;
  nx:=x-pt[i+1].x;
   if ((rx<0)and(nx>=0)) or ((rx>=0) and (nx<0))  then begin
    ry:=y-pt[i].y;
    dx:= pt[i+1].x- pt[i].x;
    dy:= pt[i+1].y- pt[i].y;
    if longint(rx)*longint(dy)<longint(ry)*longint(dx)
       then Inc (ct) else Dec(ct);
   end;
  end;
  Result:=ct=0;
end;

アルゴリズム解説:
  点を通る直線を引いて何度線分が横切るかを調べる方法もありますが、今回
  は、点の位置に立って多角形データを順に眺めていって自分の体が１回転す
  るかどうかを調べます。自分が内側に立っていれば体は1回転しますね？
    詳しく角度を調べると遅いので、180度単位に横切るかどうかを調べます
   自分の体を回す代わりに、多角形の線分が自分より上下右左にあるかで
   上にあって左から->右に変化すれば +1 右から左なら-1とします。
   下にあって左から->右に変化すれば -1 右から左なら+1とします。
                              A -> B -> C -> D -> E -> F -> G -> H ->A  計
  A-------------------B   P0    +1   0    0    0    0    0   +1    0    2
  |                   |   P1    +1   0    0    0    -1   0   0     0    0
  |   F-----------E   |   P2    +1   0   +1    0    0    0   0     0    2
  |P0 | P1        |P2 |
  |   |           |   |
  H---G           |   |
                  D---C
  左右の変化を判定してる部分が
    if ((rx<0)and(nx>=0)) or ((rx>=0) and (nx<0))  then  ....
  上か下かを判定してる部分が
    if longint(rx)*longint(dy)<longint(ry)*longint(dx) then ...

コメント:
 整数演算だけで判定していますから、TPointのbit数*2<=LongIntのビット数 
 である必要があります。
 多角形上に完全に一致した場合どうなるかはご自分で調べてみて下さい。

使用例:
  マウスを動かしながらクリックすると多角形が描かれ、クリックせずに
  動かすとその内側が赤く塗られます。

type
  TForm1 = class(TForm)
    procedure FormPaint(Sender: TObject);
    procedure FormMouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    procedure FormMouseMove(Sender: TObject; Shift: TShiftState; X,
      Y: Integer);
  private
    { Private 宣言 }
  public
    { Public 宣言 }
  end;

var
  Form1: TForm1;
  n:integer;
  pt :array [0..101] of TPoint;

implementation

{$R *.DFM}

procedure TForm1.FormPaint(Sender: TObject);
var i:integer;
begin
if n>0 then   begin
 Form1.Canvas.MoveTo (pt[n-1].x,pt[n-1].y);
for i:=0 to n-1 do
 with pt[i] do Form1.Canvas.LineTo (x,y);
 end;
end;

procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
if n <99 then begin
  pt[n].x:=X;
  pt[n].y:=Y;
  inc(n);
  end;
 Invalidate;
end;

procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,
  Y: Integer);
begin
if not PolygonExterior(x,y,n,pt) then  Canvas.Pixels[x,y]:=clRed;
end;
end.

Original document by 裏目小僧        氏 ID:(GGA03463)

ここにあるドキュメントは NIFTY SERVEの Delphi Users' Forum の16番会議室「玉石混淆みんなで作るSample蔵」に投稿されたサンプルです。これらのサンプルはボーランド株式会社がサポートする公式のものではありません。また、必ずしも動作が検証されているものではありません。これらのサンプルを使用したことに起因するいかなる損害も投稿者、およびフォーラムスタッフはその責めを負いません。使用者のリスクの範疇でご使用下さい。