点が多角形の外部・内部にあるかの判定

凸多角形の場合（頂点は反時計まわりに定義する）

!●直線の方程式による

DEF f(x1,y1,x2,y2, X,Y)=(y1-y2)*(x1-X) + (x1-x2)*(Y-y1) !２点(x1,y1)、(x2,y2)を通る直線

LET N=3 !頂点の数

DIM x(N),y(N) !頂点の位置　※反時計まわりに定義
LET x(1)=0 !点A
LET y(1)=0
LET x(2)=1 !B
LET y(2)=0
LET x(3)=1/2 !C
LET y(3)=SQR(3)/2

SET WINDOW -1,2, -1,2 !表示領域
DRAW grid !座標

MAT PLOT LINES, LIMIT n: x,y !多角形を表示する
PLOT LINES: x(n),y(n); x(1),y(1) !閉じる

DO
MOUSE POLL mx,my,left,right !P

FOR i=1 TO N !各辺に対して
IF f(x(i),y(i),x(MOD(i,N)+1),y(MOD(i,N)+1), mx,my)>0 THEN EXIT FOR
NEXT i
IF i>N THEN PRINT "内部" ELSE PRINT "外部";i

LOOP UNTIL right=1 !右クリックで終了する

END

!●ベクトルによる

FUNCTION cross2d(ux,uy, vx,vy) !2Dの擬似外積u×v
LET cross2d=uy*vx-ux*vy
END FUNCTION

LET N=3 !頂点の数

DIM x(N),y(N) !頂点の位置　※反時計まわりに定義
LET x(1)=0 !点A
LET y(1)=0
LET x(2)=1 !B
LET y(2)=0
LET x(3)=1/2 !C
LET y(3)=SQR(3)/2

SET WINDOW -1,2, -1,2 !表示領域
DRAW grid !座標

MAT PLOT LINES, LIMIT N: x,y !多角形を表示する
PLOT LINES: x(N),y(N); x(1),y(1) !閉じる

DO
MOUSE POLL mx,my,left,right !P

FOR i=1 TO N !各辺に対して
IF cross2d(mx-x(i),my-y(i),x(MOD(i,N)+1)-x(i),y(MOD(i,N)+1)-y(i))<0 THEN EXIT FOR
NEXT i
IF i>N THEN PRINT "内部" ELSE PRINT "外部";i

LOOP UNTIL right=1 !右クリックで終了する

END

!●行列式による

!２点(x1,y1)、(x2,y2)を通る直線Lの陰関数形式
!L(X,Y)=│x1 y1 1│=│x1-X y1-Y│
!　　　 │x2 y2 1│ │x2-X y2-Y│
!　　　 │X Y 1│
FUNCTION orient2d(x1,y1,x2,y2, x,y) !直線との位置判定
DIM L(2,2)
LET L(1,1)=x1-x
LET L(1,2)=y1-y
LET L(2,1)=x2-x
LET L(2,2)=y2-y
LET orient2d=DET(L)

!DIM L(3,3)
!LET L(1,1)=x1
!LET L(1,2)=y1
!LET L(1,3)=1
!LET L(2,1)=x2
!LET L(2,2)=y2
!LET L(2,3)=1
!LET L(3,1)=x
!LET L(3,2)=y
!LET L(3,3)=1
!LET orient2d=DET(L) !正なら左側、負なら右側
END FUNCTION

LET N=3 !頂点の数

DIM x(N),y(N) !頂点の位置　※反時計まわりに定義
LET x(1)=0 !点A
LET y(1)=0
LET x(2)=1 !B
LET y(2)=0
LET x(3)=1/2 !C
LET y(3)=SQR(3)/2

SET WINDOW -1,2, -1,2 !表示領域
DRAW grid !座標

MAT PLOT LINES, LIMIT n: x,y !多角形を表示する
PLOT LINES: x(n),y(n); x(1),y(1) !閉じる

DO
MOUSE POLL mx,my,left,right !P

FOR i=1 TO N !各辺に対して
IF orient2d(x(i),y(i),x(MOD(i,N)+1),y(MOD(i,N)+1), mx,my)<0 THEN EXIT FOR
NEXT i
IF i>N THEN PRINT "内部" ELSE PRINT "外部";i

LOOP UNTIL right=1 !右クリックで終了する

END

点が多角形の外部・内部にあるかの判定	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/12/28 13:12:00
凸多角形の場合（頂点は反時計まわりに定義する） !●直線の方程式による DEF f(x1,y1,x2,y2, X,Y)=(y1-y2)(x1-X) + (x1-x2)(Y-y1) !２点(x1,y1)、(x2,y2)を通る直線 LET N=3 !頂点の数 DIM x(N),y(N) !頂点の位置　※反時計まわりに定義 LET x(1)=0 !点A LET y(1)=0 LET x(2)=1 !B LET y(2)=0 LET x(3)=1/2 !C LET y(3)=SQR(3)/2 SET WINDOW -1,2, -1,2 !表示領域 DRAW grid !座標 MAT PLOT LINES, LIMIT n: x,y !多角形を表示する PLOT LINES: x(n),y(n); x(1),y(1) !閉じる DO MOUSE POLL mx,my,left,right !P FOR i=1 TO N !各辺に対して IF f(x(i),y(i),x(MOD(i,N)+1),y(MOD(i,N)+1), mx,my)>0 THEN EXIT FOR NEXT i IF i>N THEN PRINT "内部" ELSE PRINT "外部";i LOOP UNTIL right=1 !右クリックで終了する END !●ベクトルによる FUNCTION cross2d(ux,uy, vx,vy) !2Dの擬似外積u×v LET cross2d=uyvx-uxvy END FUNCTION LET N=3 !頂点の数 DIM x(N),y(N) !頂点の位置　※反時計まわりに定義 LET x(1)=0 !点A LET y(1)=0 LET x(2)=1 !B LET y(2)=0 LET x(3)=1/2 !C LET y(3)=SQR(3)/2 SET WINDOW -1,2, -1,2 !表示領域 DRAW grid !座標 MAT PLOT LINES, LIMIT N: x,y !多角形を表示する PLOT LINES: x(N),y(N); x(1),y(1) !閉じる DO MOUSE POLL mx,my,left,right !P FOR i=1 TO N !各辺に対して IF cross2d(mx-x(i),my-y(i),x(MOD(i,N)+1)-x(i),y(MOD(i,N)+1)-y(i))<0 THEN EXIT FOR NEXT i IF i>N THEN PRINT "内部" ELSE PRINT "外部";i LOOP UNTIL right=1 !右クリックで終了する END !●行列式による !２点(x1,y1)、(x2,y2)を通る直線Lの陰関数形式 !L(X,Y)=│x1 y1 1│=│x1-X y1-Y│ !　　　 │x2 y2 1│ │x2-X y2-Y│ !　　　 │X Y 1│ FUNCTION orient2d(x1,y1,x2,y2, x,y) !直線との位置判定 DIM L(2,2) LET L(1,1)=x1-x LET L(1,2)=y1-y LET L(2,1)=x2-x LET L(2,2)=y2-y LET orient2d=DET(L) !DIM L(3,3) !LET L(1,1)=x1 !LET L(1,2)=y1 !LET L(1,3)=1 !LET L(2,1)=x2 !LET L(2,2)=y2 !LET L(2,3)=1 !LET L(3,1)=x !LET L(3,2)=y !LET L(3,3)=1 !LET orient2d=DET(L) !正なら左側、負なら右側 END FUNCTION LET N=3 !頂点の数 DIM x(N),y(N) !頂点の位置　※反時計まわりに定義 LET x(1)=0 !点A LET y(1)=0 LET x(2)=1 !B LET y(2)=0 LET x(3)=1/2 !C LET y(3)=SQR(3)/2 SET WINDOW -1,2, -1,2 !表示領域 DRAW grid !座標 MAT PLOT LINES, LIMIT n: x,y !多角形を表示する PLOT LINES: x(n),y(n); x(1),y(1) !閉じる DO MOUSE POLL mx,my,left,right !P FOR i=1 TO N !各辺に対して IF orient2d(x(i),y(i),x(MOD(i,N)+1),y(MOD(i,N)+1), mx,my)<0 THEN EXIT FOR NEXT i IF i>N THEN PRINT "内部" ELSE PRINT "外部";i LOOP UNTIL right=1 !右クリックで終了する END

Re: 点が多角形の外部・内部にあるかの判定	返事を書くノートメニュー
山中和義 <drdlxujciw> 2007/12/28 19:06:51
つづき凹多角形の場合（頂点は反時計まわりに定義する） !●直線の方程式による FUNCTION check(x1,y1,x2,y2, a,b) !２点(x1,y1)、(x2,y2)を結ぶ線分と点(a,b)との位置判定 LET check=0 IF y1<>y2 THEN !水平線以外なら IF b>=MIN(y1,y2) AND b<MAX(y1,y2) THEN !点がその範囲なら IF x1=x2 THEN !垂直線なら LET xx=x1 ELSE LET t=(y1-y2)/(x1-x2) !２点(x1,y1)、(x2,y2)を結ぶ線分と水平線y=b LET xx=(b-y1)/t+x1 !交点のＸ座標 END IF IF xx>a THEN LET check=1 !領域のどちら側か判定する END IF END IF END FUNCTION LET N=10 !頂点の数 !LET N=5 !頂点の数 DIM x(N),y(N) !頂点の座標 DATA 1,2 !x,y DATA 0.3,1 DATA -0.5,1 DATA 0,0.4 DATA -1,-1 DATA 0.5,0.2 DATA 2,-1 DATA 1.3,0.6 DATA 1.8,1 DATA 1.2,1 !DATA 1,2 !DATA -1,-1 !DATA 1.7,1 !DATA -0.5,1 !DATA 2,-1 FOR i=1 TO N READ x(i),y(i) NEXT i SET WINDOW -2,3, -2,3 !表示領域 DRAW grid !座標 MAT PLOT AREA, LIMIT N: x,y !多角形を表示する DO MOUSE POLL mx,my,left,right !P LET cnt=0 !交点の個数 FOR i=1 TO N !各辺に対して IF check(x(i),y(i),x(MOD(i,N)+1),y(MOD(i,N)+1), mx,my)<>0 THEN LET cnt=cnt+1 NEXT i IF MOD(cnt,2)<>0 THEN PRINT "内部" ELSE PRINT "外部" !奇数なら LOOP UNTIL right=1 !右クリックで終了する END