OpenCV で星座検出(2) - 星座はグラフである

前回に引き続き、星座検出ソフトを作ります。
前回は南斗六星を書けるプログラムを書き、もうほぼ完成したかのような心持ちでいましたが、いざいて座全体を書くとなると全く違う厳しさがありました。その辺について書きます。

1. どうやって分岐する？

南斗六星→いて座へのステップアップでもっとも重要なのが、たとえば南斗六星はえんぴつで書こうとしたら一度も紙から離さず、重複することなく書くことができます。しかし、いて座を書こうと思うと、線を元に戻るか、一度えんぴつを紙から離してまたつけるという動作が必要になります。
ようは、「ペンを紙に着けろ」「線を引け」「方向転換しろ」「ペンを置け」という 命令で済んでいたものに、「前の点まで戻れ」「また進め」「書かずに移動しろ」などなどの命令が必要になり、かなり複雑になることがわかると思います(実際にはちょっとちがうことをやっていますが、困難さのイメージ的にはこんな感じ)。
 さて、どのように分岐を実装しましょう。まず最初に考えたのは、「書きながら移動する」「書かずに移動する」の二つの状態を持たせ、スタートからゴールまでつなげてしまう方法です。

赤のところではペンを離して動かせばぐるっと移動できる

 しかし、実際に実装してみて困ったことがありました。今の点の指定方法では、正しく以前の点と全く同じ場所に帰ってこられるとは限らないのです。……というか、もうわかっている点なのにまた探すのってもったいなくない？と気づいてしまいました。

2. 星座はグラフなので…

どうすれば無駄なく分岐させられるんだろうと考えているとき、星座の形状をよく見ていたら、これ木じゃん！と気づきました。

 木（き、英: tree）とは、連結で閉路を持たない(無向)グラフである。(Wikipedia より)

星座はおそらくすべて連結です。いて座に関しては閉路がないので木ですが、一般的には閉路があったりするのでグラフですね。
木だとわかれば、データ構造を木にすればいいのです。やった！授業で学んだことが活きたぞ！と思うと同時に、星座というロマンチックなものに数学を当てはめる自分が愚かに思えてきます。
これを踏まえると、今まで基準点と呼んでいた星は根(root)だといえます。プログラムは、根から葉(leaf)まで走査し、葉にたどり着いたら分岐している先祖ノードを探して、また走査を始める…ということを繰り返せばよいことになります。よくわからない方は木構造(データ構造) - Wikipedia 読むとわかりやすいです。
結局やることはふたつで、

1. 星座のデータを木構造データにする
2. 星座を探す関数を再帰的にする

となります。1つ目については親子関係がわかっていて、分岐点も明示しておけば十分だと思います。
2つ目もデータに従って定義し直せばいいだけですが……僕は再帰が苦手で……(まさか趣味で書いてるコードで再帰書くと思ってなかった)。

3. 再帰的に定義する

再帰的定義（Recursive Definition）は、再帰的な定義、すなわち、あるものを定義するにあたってそれ自身を定義に含むものを言う。無限後退を避けるため、定義に含まれる「それ自身」はよく定義されていなければならない。同義語として帰納的定義（Inductive Definition）がある。(Wikipedia より)

プログラミングにおいてはわりと基本ですが、わりと難関だと(個人的には)思っています。ただ最近ちょっと掴めてきた気がしていて、意気揚々と書き直し始めたら余裕で数時間かかりました。終点を正しく設定するのがコツだと思います。今回で言えば

• 次に線を伸ばせる星があれば、そこに移動してまた実行(再帰)。 
• 次に線を伸ばせる星がなければ、失敗したことを示す(終点1)。
• もし葉(最後の星)であれば、成功したことを示す(終点2)。

こういう風に最初に組み立てられると楽だと思いました。次回以降の教訓にします。

4. できぐあい

いて座の上半身が書けるようになりました！(下半身は写ってる写真が少ないため断念)

ほかにも前回との違いがあって、線は円にくっついたところで描画をやめるようにして、円内の星を見えやすくしています。

• 安定化
• 他の星座

について、頑張ります。