新しく発言する  EXIT  インデックスへ
点が多角形の外部・内部にあるかの判定

  点が多角形の外部・内部にあるかの判定 山中和義 2007/12/28 13:12:00 
  つづき 山中和義 2007/12/28 19:06:51 

  点が多角形の外部・内部にあるかの判定 山中和義 2007/12/28 13:12:00   ツリーへ

点が多角形の外部・内部にあるかの判定  返事を書く  ノートメニュー
山中和義 <drdlxujciw> 2007/12/28 13:12:00
凸多角形の場合(頂点は反時計まわりに定義する)


!●直線の方程式による

DEF f(x1,y1,x2,y2, X,Y)=(y1-y2)*(x1-X) + (x1-x2)*(Y-y1) !2点(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





!●行列式による

!2点(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

  つづき 山中和義 2007/12/28 19:06:51   ツリーへ

Re: 点が多角形の外部・内部にあるかの判定  返事を書く  ノートメニュー
山中和義 <drdlxujciw> 2007/12/28 19:06:51
つづき

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


!●直線の方程式による

FUNCTION check(x1,y1,x2,y2, a,b) !2点(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) !2点(x1,y1)、(x2,y2)を結ぶ線分と水平線y=b
LET xx=(b-y1)/t+x1 !交点のX座標
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


 インデックスへ  EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。