細線化と凸包

• Hilditch’s Algorithm for Skeletonization
• Convex Hull – Algorithmist
• 凸包 (Andrew’s Monotone Chain) – Spaghetti Source

両者はまったく関係ないですが、必要だったのでメモ。

細線化（Thinning, Skeletonization）は他にもアルゴリズムはあったけど、 線の端が Y の字のように分かれてしまうものが多かったので。 上で挙げた文書にある通り、 Hilditch のアルゴリズムではダメな場合があるらしいと いうことは覚えておこう。今回は充分に用は足りたけど。

凸包（Convex Hull）は今後も必要そうだから少しがんばってみた（?）。 分かり易そうだったので Graham Scan を使ってみました。

Cで書くのはちょっとつらかったです。（何

という感じで 2006 年は終わりであった。電脳空間カウボーイズ聴いたら寝るよ!