つづき

つづき

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

!●直線の方程式による

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

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