ループで反時計回りの線分でぐるりと一周囲まれた内部を塗りつぶしたいです。

Question

プチコン3号で反時計回りの線分でぐるりと一周囲まれた内部をループで塗りつぶしたいです。
何故ならば、いちいち一つの頂点枚に計算していたら冗長すぎて面倒です。
そこで配列とループで出来ないかどうか知りたいです。

以下のプログラムをループで求めたいです。
これを何に使いたいかというと応用としてレーシングゲームでコースアウトしたかどうかを
知りたいのです。

以下実行結果です。
リンク内容

DIM LINEX[4]:DIM LINEY[4]'LINE ﾉ X ﾄ Y
ADD=80 'ﾎｾｲﾁ

LINEX[0]=50/2+ADD:LINEY[0]=20/2+ADD
LINEX[1]=10/2+ADD:LINEY[1]=200/2+ADD
LINEX[2]=380/2+ADD:LINEY[2]=230/2+ADD
LINEX[3]=320/2+ADD:LINEY[3]=30/2+ADD

DIM S[4]
GCLS 'ｶﾞﾒﾝｦｼｮｳｷｮ
MINX=MIN(LINEX):MINY=MIN(LINEY) 'ｻｲｼｮｳﾁﾉ X ﾄ Y
MAXX=MAX(LINEX):MAXY=MAX(LINEY) 'ｻｲﾀﾞｲﾁﾉ X ﾄ Y

FOR Y2=MINY TO MAXY
FOR X2=MINX TO MAXX
TX=X2:TY=Y2
GOSUB @L
IF ANS1<0 && ANS2<0 && ANS3<0 && ANS4<0 THEN GPSET X2,Y2
'ANS1ﾄANS2ﾄANS3ﾄANS4ｶﾞ0ﾖﾘｼﾀﾅﾗGPSETﾃﾞ ﾃﾝ ｦ ｴｶﾞｸ
NEXT
NEXT
END

@L 'ｺｺｶﾗ ｼﾀｦ ﾙｰﾌﾟﾃﾞ ﾓﾄﾒﾀｲ
VX1=(LINEX[1]-LINEX[0])
VY1=(LINEY[1]-LINEY[0])
VX2=TX-LINEX[0]
VY2=TY-LINEY[0]
ANS1=VX1VY2-VY1VX2

VX1=(LINEX[2]-LINEX[1])
VY1=(LINEY[2]-LINEY[1])
VX2=TX-LINEX[1]
VY2=TY-LINEY[1]
ANS2=VX1VY2-VY1VX2

VX1=(LINEX[3]-LINEX[2])
VY1=(LINEY[3]-LINEY[2])
VX2=TX-LINEX[2]
VY2=TY-LINEY[2]
ANS3=VX1VY2-VY1VX2

VX1=(LINEX[0]-LINEX[3])
VY1=(LINEY[0]-LINEY[3])
VX2=TX-LINEX[3]
VY2=TY-LINEY[3]
ANS4=VX1VY2-VY1VX2

GLINE LINEX[0],LINEY[0],LINEX[1],LINEY[1]
GLINE LINEX[1],LINEY[1],LINEX[2],LINEY[2]
GLINE LINEX[2],LINEY[2],LINEX[3],LINEY[3]
GLINE LINEX[3],LINEY[3],LINEX[0],LINEY[0]

RETURN

Comments

[thkana]

タグのCとC++は無関係ですね。外して下さい。

塗りの話だったら口をだそうかとも思ってたけど話が変わってしまったので与太話だけ。
低スペックマシン/遅い言語ですから、マジメに1ドットずつ動かして管理しようなんて思わないで、8x8ドットぐらいを単位にして位置も動きも管理/制御してやればどうでしょう。プログラムは大幅に楽になるでしょうし、それでも人間の感覚は結構騙されてくれます。
#Z80の「マイコン」時代のおじさんの感覚では。

[littlestream]

Ｚ８０ですか、アセンブラをゲームボーイのカスタムCPU版で少し前にちょこっといじった覚えがあります。
ソースを見るとLDって命令が結構出てくる印象でした。
あと、16ビットの値も弄れるのも素晴らしい設計だと思いました。
少し前に調べた時に知ったのはゲームボーイの他にもアップルIIやMSXにも採用されているようですね。

[thkana]

爺にそういうことを話しかけると昔を思い出してうるさくなります。
Apple ][のCPUは基本6502です(Z80カードもありましたけど)。初代ファミコンと一緒。ゼロページアドレッシングとか呟くといろいろ釣れるかも知れません。
Z80は、ナマの機械語を喋る人たちが一部にいます。6809は当時としては相対ジャンプが多くて...

往時はそれこそ320x240とかの「高解像度グラフィックス」で塗りつぶしをやろうとして、BASICの遅さに悲鳴を上げて機械語に走ったりしていたわけですから、その辺鍛えられている人も多いでしょう。斜め線の部分で漏れ出してしまって画面全面塗ってしまうのがお約束。まぁ、当時のBASICにはPAINT文なんてのがあることも多かったですけれど。

[littlestream]

6502CPUはギリギリ自分もファミコン世代なので
カービィとかくにおくんとか、マリオとかよくやりました。
で、大人になってからインターネットが発達して
ギコ猫でもわかるファミコンプログラミングというサイトで勉強して、6502の基本を覚えました。
PC-エンジンやスーパーファミコンにもノウハウの継承が（一部だけ）出来たのは心強かったです。
(一行ずつ書いていたら行数が多くなってしまうのでこういう書き方は本来良くないのですが）
LDA #$3F、STA $2006、LDA #$00、STA $2006、
LDX #0、.LOOP LDA PAL,X、STA $2007、INX、CPX #32、BNE .LOOPとか、
LDX #0,LDY #0、STX $2005、STY $2005とか、
よくI/Oレジスタも覚えてたりしたのですが、
今でもスクロールしながらBG書き換えが出来なかったりします。

[x_x]

せっかくの「SMILEBASIC」タグですがタグ説明が残念なことになっていますね……

[littlestream]

>x_xさん
SMILEBASICじゃなくてPETIT COMPUTERと入れるべきだったでしょうか。。。

Answer 1

こんな感じです。何かマズい点がありましたらご指摘お願いします。

'ｶｲﾄｳ ﾉ ｲﾁﾚｲ ﾆ ﾅﾚﾊﾞ ｻｲﾜｲ ﾃﾞｽ.
DIM POLYX[10]:DIM POLYY[10]
DIM POLYX2[10]:DIM POLYY2[10]
DIM LEFT[240]:DIM RIGHT[240]'ﾌﾟﾁｺﾝ ﾉ ﾀﾃ ﾉ ｶｲｿﾞｳﾄﾞ ﾊ x=0-400,y=0-240
Z80=65816 'Z ﾊﾁﾏﾙ CPU ﾄ ｽｰﾊﾟｰﾌｧﾐｺﾝ ﾉ 65816 CPU
JX=0:JY=0
GCLS 'ｶﾞﾒﾝ ﾉ ｼｮｳｷｮ
INX=0:INX2=0
@INIT
INPUTPOLY 100,20
INPUTPOLY 45,120
INPUTPOLY 80,230
INPUTPOLY 160,220
INPUTPOLY 200,140
'ｿﾄｶﾞﾜ ﾉ ﾁｮｳﾃﾝ ﾉ ﾀﾞｲﾆｭｳ

INPUTPOLY2 100,80
INPUTPOLY2 60,120
INPUTPOLY2 80,200
INPUTPOLY2 160,195
INPUTPOLY2 150,120
'ｳﾁｶﾞﾜ ﾉ ﾁｮｳﾃﾝ ﾉ ﾀﾞｲﾆｭｳ
@MAIN
GCLS

FOR I=0 TO 240-1
   LEFT[I]=Z80
   MINX[I]=Z80
   RIGHT[I]=-Z80
   MAXX[I]=-Z80
NEXT

SCANX POLYX[0],POLYY[0],POLYX[1],POLYY[1]
SCANX POLYX[1],POLYY[1],POLYX[2],POLYY[2]
SCANX POLYX[2],POLYY[2],POLYX[3],POLYY[3]
SCANX POLYX[3],POLYY[3],POLYX[4],POLYY[4]
SCANX POLYX[4],POLYY[4],POLYX[0],POLYY[0]

SCANX2 POLYX2[0],POLYY2[0],POLYX2[1],POLYY2[1]
SCANX2 POLYX2[1],POLYY2[1],POLYX2[2],POLYY2[2]
SCANX2 POLYX2[2],POLYY2[2],POLYX2[3],POLYY2[3]
SCANX2 POLYX2[3],POLYY2[3],POLYX2[4],POLYY2[4]
SCANX2 POLYX2[4],POLYY2[4],POLYX2[0],POLYY2[0]

@MAIN2
GCLS 'ｸﾞﾗﾌｨｯｸ ｶﾞﾒﾝ ﾉ ｼｮｳｷｮ
CLS 'ｷｬﾗｸﾀｰ ｶﾞﾒﾝ ﾉ ｼｮｳｷｮ

IF (BUTTON(0)AND 1)==1 THEN JY=JY-2 'UE
IF (BUTTON(0)AND 2)==2 THEN JY=JY+2 'SITA
IF (BUTTON(0)AND 4)==4 THEN JX=JX-2 'LEFT
IF (BUTTON(0)AND 8)==8 THEN JX=JX+2 'RIGHT

MINY=MIN(POLYY)
MAXY=MAX(POLYY)

FOR Y=0 TO 240-1

    IF LEFT[Y]==Z80 && RIGHT[Y]==-Z80 THEN CONTINUE
    GLINE LEFT[Y],Y,RIGHT[Y],Y,RGB(0,255,0) 'LEFT TO RIGHT

    IF LEFT[Y]<JY && JX<RIGHT[Y] && JY==Y && !(MINX[Y]<JX && JX<MAXX[Y]) THEN LOCATE 100/8,0:COLOR 3:PRINT "IN!"
    
NEXT

GCIRCLE JX,JY,2,RGB(255,0,255) 'ｴﾝ(ｸﾙﾏ ﾉ ﾂﾓﾘ) ｦ ｴｶﾞｸ(ｶｿｸﾄﾞ ﾄｶ ﾏｻﾂｹｲｽｳ ﾊ ｱﾄﾃﾞ ｶﾝｶﾞｴﾙ)

GLINE POLYX2[0],POLYY2[0],POLYX2[1],POLYY2[1]
GLINE POLYX2[1],POLYY2[1],POLYX2[2],POLYY2[2]
GLINE POLYX2[2],POLYY2[2],POLYX2[3],POLYY2[3]
GLINE POLYX2[3],POLYY2[3],POLYX2[4],POLYY2[4]
GLINE POLYX2[4],POLYY2[4],POLYX2[0],POLYY2[0]

VSYNC 2

GOTO @MAIN2

DEF SCANX X1,Y1,X2,Y2
   FOR I=0 TO 512
      X=(X1*(512-I)+X2*I)/512
      Y=(Y1*(512-I)+Y2*I)/512
      IF RIGHT[Y]<X THEN RIGHT[Y]=X
      IF LEFT[Y]>X THEN LEFT[Y]=X
   NEXT
END

'SCANX2 ﾓ SCANX ﾄ ﾄﾞｳﾖｳ ﾆ MINX ﾄ MAXX ｦ ﾓﾄﾒﾙ

DEF INPUTPOLY X,Y
   POLYX[INX]=X
   POLYY[INX]=Y

   INX=INX+1
END

DEF INPUTPOLY2 X,Y
   POLYX2[INX2]=X
   POLYY2[INX2]=Y

   INX2=INX2+1
END

Comments

[littlestream]

FOR Y=0 TO 240-1

IF LEFT[Y]==Z80 && RIGHT[Y]==-Z80 THEN CONTINUE
GLINE LEFT[Y],Y,RIGHT[Y],Y,RGB(0,255,0) 'LEFT TO RIGHT①

IF LEFT[Y]<JY && JX<RIGHT[Y] && JY==Y && !(MINX[Y]<JX && JX<MAXX[Y]) THEN LOCATE 100/8,0:COLOR 3:PRINT "IN!"'②

NEXT

以上の①は塗りつぶしを行う部分ですが、コースアウトを判定する②は、よく考えると
IF LEFT[JY]<JY && JX<RIGHT[JY] && !(MINX[JY]<JX && JX<MAXX[JY]) THEN LOCATE 100/8,0:COLOR 3:PRINT "IN!"'②改
とすればいちいちスキャンラインを使う必要はなくなるばかりか、塗りつぶしを行うコストもなくなります。これで、コースアウトの判定は大分分かってきたので解決といたします。

[littlestream]

FOR Y=0 TO 240-1と
NEXTは要らないのと、GLINEとIF LEFT[Y]==Z80...CONTINUEも要らないです。

Answer 2

直面している問題点（というか解決すべき課題）が何なのかイマイチわかりませんが…

凸包（←提示コードからそうだと判断）の塗りつぶしであれば，普通に

• 三角形を塗りつぶす処理を用意する
• 凸包を複数の三角形に分割して↑を利用して塗る

ではダメなのでしょうか？

---

（本質は「塗りつぶし処理」ではなく，多角形の内外判定だということですので…）

とりあえず多角形が凸であるならば，
判定したい点を通る直線と多角形との交点を求めて，位置関係から判断する方法が割と有名(?)かと思います．
（実際やってみると面倒な事柄が出てきたりはしますが）

• 交点が２点無ければ，少なくとも「内側」ではない
• 交点が２点ある場合，判定したい点が２点の間であれば「内側」

Comments

[littlestream]

回答ありがとうございます。
自分がしたいことは塗りつぶしもそうですが、応用として
疑似３Ｄレーシングゲームでのコースアウトしたかどうかのチェックです。
しかし、このソースの場合は単にとある座標が多角形内に存在しているかを調べたいので、いろいろな
座標でも塗りつぶせるか試すプログラムを書きました。なので、三角形を塗りつぶす処理が
多角形内でとある座標に存在しているか？という問題に解決できるのかが分からないです。
ただし、持ち合わせている本で外積を利用して三角形を塗りつぶす処理が載っていたので試してみます。

[fana]

質問タイトル，質問文冒頭，共に「塗りつぶしたいです」なので，それが本件の課題であると捉えました．
> コースアウトしたかどうかのチェック
という用途に，あらかじめ「塗りつぶし処理」を用いて作成しておいたマスクデータを使うような話なのかと．

[littlestream]

何故塗りつぶしを行ったかの説明がfanaさんや他の閲覧者様に行き届いていないみたいなので説明しますが、もともと塗りつぶしを行う必要はなくて、塗りつぶしを行う必要はテストプログラムである本件のプログラムにしか必要ないものでした。あえてデバッグも兼ねて可視化して塗りつぶしを行う事で確かにいろいろな座標でコースアウトしていない事を確かめるための意味合いがありました。他にも理由はありますが、混乱を招くだけなので割愛させてもらいます。

[fana]

（回答を行った時点では上記のコメントのような話かと捉えた，ということで，最初のコメントを頂いた時点で「塗りつぶしは単なるアルゴリズムのテストのための可視化手段」という話の理解は大丈夫です．）

[fana]

（くだらない余談）
大昔にBASICでレースゲームのようなものを作ったときには，
「世界の中心(コースという閉ループの内側に存在する１点)」からの距離で判定できるようにコースのデータに（形状表現の自由度が低くなる）制約を設けていた思い出．

[fana]

とりあえず多角形の話を１例追記しましたが，
「多角形　内外判定」などで検索すると，もっとまとも（凸でなくてよいとか，計算が楽とか）な方法や，うまくすればその実装例なども見つかるのではないかと思います．

[littlestream]

今回はポリゴンの描画の自作ソースを参考にしてみました。
ソースは2DSからPCに移植するのに時間がかかるので、後程行うとしてYOUTUBEの動画を
見てほしいです。基本的な考え方は多角形の左端より右側にあり、なおかつ、多角形の右側より左側にあり、かつ、スキャンラインを通っていれば多角形の内部にあると判定しました。
https://youtu.be/gxUr-nrK_DA

[littlestream]

外側へのIN,OUTは求まったので内側へも判定を行おうとしたのですが、よくよく考えると
内側へは外側の内部からポリゴンの内外判定の否定で内部も判定できる事に気づいたので解決
としたいですが、一応作ってから納得して解決としたいです。

[littlestream]

https://youtu.be/p_5StvtX1_k
上のURLに実行中の画面を載せました。
只今外出中なのでスマホから書き込んでおり2DSのプチコン3号で実装しました。ソースコードは、帰宅時にしばらくしてから載せます。

[fana]

> 今回はポリゴンの描画の自作ソースを参考にしてみました。

状況がよくわかりませんが，実施されている事柄がこの回答と関係ない(関係が薄い，アルゴリズムが異なる，etc)ようであれば，このサイトの使い方としては，自己解決的（自分の質問に自分で回答を書いて，それをBAにする）な形にすると良いのかと思います．

[littlestream]

分かりました。先ほど帰宅して夕食を食べ終わった所です。
自分としては、回答を元に自分のソースを弄りながら作ったので自分の質問に自分で
回答に書いてみて、これだと、こういう部分がマズい、とかご指摘がありましたら宜しくお願いします。