PanCakeのCIRCLEの描画アルゴリズムの推測を試みた (未解決)

# CIRCLEの描画アルゴリズムの推測

[PanCake](http://pancake.shizentai.jp/) の `CIRCLE` コマンドは、中心の座標・半径・色を指定して円を描くコマンドである。
とりあえず、描画を試してみる。

```
10 'PanCake CIRCLE ﾃｽﾄ
20 ?"PC CLEAR 00"
30 R=0
40 X=R
50 ?"PC CIRCLE ";HEX$(X,2);" 16 ";HEX$(R,2);" 01"
60 X=X+R+2+(R+1)
70 R=R+1
80 IF X<=#4F GOTO50
```

![描画結果 1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/50c75d82-90d2-7039-5aab-b145f139aec8.png)

どちらかといえば、横長に潰れている印象がある。
しかし、よく見ると、縦幅と横幅は同じである。
また、縦および横それぞれ線対称になっていそうである。

あまり複雑なアルゴリズムではないと予想し、まずはPythonを用いてそれぞれの横位置 (または縦位置) に対応する縦位置 (または横位置) を求めてみる。

```python
def calc(r):
  return [math.sqrt(r*r-i*i) for i in range(r+1)]

for i in range(7 + 1):
  print(calc(i))
```

以下の実行結果が得られた。

```
[0.0]
[1.0, 0.0]
[2.0, 1.7320508075688772, 0.0]
[3.0, 2.8284271247461903, 2.23606797749979, 0.0]
[4.0, 3.872983346207417, 3.4641016151377544, 2.6457513110645907, 0.0]
[5.0, 4.898979485566356, 4.58257569495584, 4.0, 3.0, 0.0]
[6.0, 5.916079783099616, 5.656854249492381, 5.196152422706632, 4.47213595499958, 3.3166247903554, 0.0]
[7.0, 6.928203230275509, 6.708203932499369, 6.324555320336759, 5.744562646538029, 4.898979485566356, 3.605551275463989, 0.0]
```

よく見比べてみると、端を除く縦方向の中心からの距離が、ここで求めた値を四捨五入した値になっていそうである。
見やすくするために、四捨五入する処理を追加する。

```python
def calc2(r):
  return [int(round(math.sqrt(r*r-i*i))) for i in range(r+1)]

for i in range(7 + 1):
  print(calc2(i))
```

以下の実行結果が得られた。

```
[0]
[1, 0]
[2, 2, 0]
[3, 3, 2, 0]
[4, 4, 3, 3, 0]
[5, 5, 5, 4, 3, 0]
[6, 6, 6, 5, 4, 3, 0]
[7, 7, 7, 6, 6, 5, 4, 0]
```

一番上の行からの差を見ると、図形と数値が対応していることがわかりやすい。

もう少し大きい半径でも試してみる。
先ほどのプログラムを1行書き換え、半径の初期値を大きくする。
前回は半径7までの円を描画できたので、半径8から開始する。

```
30 R=8
```

![描画結果 2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/fbe320ae-a96f-5d7e-5804-8bd9f23ccba2.png)

位置の計算も試してみる。

```python
for i in range(8, 12):
  print(calc2(i))
```

以下の実行結果が得られた。

```
[8, 8, 8, 7, 7, 6, 5, 4, 0]
[9, 9, 9, 8, 8, 7, 7, 6, 4, 0]
[10, 10, 10, 10, 9, 9, 8, 7, 6, 4, 0]
[11, 11, 11, 11, 10, 10, 9, 8, 8, 6, 5, 0]
```

残念ながら法則が破れてしまった。

* 半径10の円の左から2列目において、計算結果は4だが、描画された位置は5である
* 半径11の円の左から3列目において、計算結果は6だが、描画された位置は7である

法則が成り立っている部分で、前 (中心からの距離が大きい側) からの位置の差が2以上のときは、新しい (2以上減った) 値の側で前の値-1の位置から新しい値の位置まで線が引かれるらしいことも読み取れる。

半径11の円の左から3列目の中心からの距離 (四捨五入前) は 6.324555320336759 であり、これは半径7の円の左から5列目の中心からの距離 (四捨五入前) と同じである。
この仮説に基づいた計算では同じ値であるにもかかわらず、半径7の円では位置6に、半径11の円では位置7に描画されている。
よって、この仮説は間違いであったと考えるのがよさそうだ。

もう少しデータを取っておこう。

```
30 R=12
```

![描画結果 3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/a1e89918-32e1-7b46-7d78-983bfbdc7766.png)

```python
for i in range(12, 15):
  print(calc2(i))
```

```
[12, 12, 12, 12, 11, 11, 10, 10, 9, 8, 7, 5, 0]
[13, 13, 13, 13, 12, 12, 12, 11, 10, 9, 8, 7, 5, 0]
[14, 14, 14, 14, 13, 13, 13, 12, 11, 11, 10, 9, 7, 5, 0]
```

直径14の円の左から3列目において、計算結果は7だが、位置8に描画されている。
該当位置の四捨五入前の中心からの距離は 7.211102550927978 である。
ほかは、今回の仮説と合っていそうである。

ここまで、今回の仮説に基づく計算結果と実際の描画結果の違いが出たのは

* 端から2～3列目
* 計算結果より実際の描画結果の方が1だけ中心から遠い

というパターンであった。
何か法則がありそうな予感はするものの、現時点で新たな仮説は立てられていない。
現在の仮説で大部分は説明できているので、今回は一旦ここで調査・検証を終了する。

## 結論

横位置それぞれについて、平方根の四捨五入を用いて縦位置を計算し、描画することで、本家の描画結果に近い結果が得られるが、完全には一致せず、本家より中心に近い位置に描画されることがある。

今回のアルゴリズムを[IchigoJam](https://ichigojam.net/) BASIC で実装した。
[整数の平方根を四捨五入で求める - Qiita](https://qiita.com/mikecat_mixc/items/8fba1f3e79de5747ac4b)
で考えたアルゴリズムを使用した。
PanCakeの画面の左側に今回のアルゴリズムでの描画結果を、右側にCIRCLEコマンドでの描画結果を表示する。
80行目の条件 `M<92` は、オーバーフローによる誤判定防止のため入れてある。

```
10 'PanCake CIRCLE ｻｲｹﾞﾝ?
20 GOTO 100
30 IF N<=0 THEN S=0:RETURN
40 IF N=1 S=1:RETURN
50 L=0:G=N
60 IF L+1>=G:S=L:RETURN
70 M=L+(G-L)/2
80 IF M<92 AND (2*M-1)*(2*M-1)<=4*N L=M ELSE G=M
90 GOTO 60
100 X=#14:Y=#16:R=#0B
110 ?"PC CLEAR 00"
120 ?"PC CIRCLE 3C 16 ";HEX$(R,2);" 01"
130 P=R:FOR I=0 TO R
140 N=R*R-I*I:GOSUB 30
150 IF S<P P=P-1
160 FOR J=-1 TO 1 STEP 2:FOR K=-1 TO 1 STEP 2
170 ?"PC LINE ";HEX$(X+I*J,2);" ";HEX$(Y+P*K,2);" ";HEX$(X+I*J,2);" ";HEX$(Y+S*K,2);" 01"
180 NEXT:NEXT
190 P=S
200 NEXT
```

![再現の試み 描画結果](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/bcd29c80-4f5e-a08a-ae47-3936c0e645fe.png)

やはり、描画結果は近いが一致しない。

さらに、プログラム

```
210 K=INKEY()
220 IF K=#31 R=R+1:GOTO 110
230 IF K=#32 R=R-1:GOTO 110
240 GOTO 210
```

を加えると、1を入力すると半径を大きく、2を入力すると半径を小さくして試すことができる。

# おまけ

## PanCakeのLINEの描画アルゴリズムは？

```
?"PC CLEAR 00
?"PC LINE 00 10 20 11 01
?"PC LINE 00 20 20 1F 01
?"PC LINE 20 19 00 18 01
?"PC LINE 20 24 00 25 01
?"PC LINE 30 00 31 20 01
?"PC LINE 34 00 33 20 01
?"PC LINE 39 20 38 00 01
?"PC LINE 3F 20 40 00 01
```

![LINE の実験結果](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/b4397ffc-07cc-3265-f5ab-ca149bf23dc8.png)

IchigoJam の DRAW のアルゴリズム (座標の差の小さくない方向に、座標の小さい方から大きい方に、小数点以下切り捨てで線形補間) と同じかもしれない。(未確認)
[IchigoJamの線分描画アルゴリズムを推測してみた - Qiita](https://qiita.com/mikecat_mixc/items/e2e1bdc6bdb4b1d54d11)

## PanCake web での描画結果は？

[カラフルなスプライトを使ったプログラミングに挑戦 PanCake on IchigoJam web](https://fukuno.jig.jp/3184)
[IchigoJam web by jig.jp](https://fukuno.jig.jp/app/IchigoJam/pancake.html#10%20'PanCake%20CIRCLE%20%EF%BE%83%EF%BD%BD%EF%BE%84%0A20%20%3F%22PC%20CLEAR%2000%22%0A30%20R%3D0%0A40%20X%3DR%0A50%20%3F%22PC%20CIRCLE%20%22%3BHEX%24(X%2C2)%3B%22%2016%20%22%3BHEX%24(R%2C2)%3B%22%2001%22%0A60%20X%3DX%2BR%2B2%2B(R%2B1)%0A70%20R%3DR%2B1%0A80%20IF%20X%3C%3D%234F%20GOTO50%0ARUN%0A) (今回のプログラムを自動で実行する設定)

![PanCake web での描画結果 1](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/8b790220-9fe5-52be-91dd-cd2ce02348de.png)
![PanCake web での描画結果 2](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/3d56932b-3ab6-202a-7a48-181990da26c3.png)
![PanCake web での描画結果 3](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/6ec4b886-c83b-71f6-654b-1eb7a5b2f1b3.png)

描画結果が実機と異なる。
描かれてる点が増えて4近傍で繋がる部分が多くなっているし、半径によっては上下左右で線対称になっていない。
また違うアルゴリズムが使われているようだ。
今回は解析を行わない。

## おまじない

※IchigoJamはjig.jpの登録商標です。