凹包（Concave Hull）

デモを見る（github.io）

Adriano Moreira と Maribel Yasmina Santos によるK-近傍を用いた凹包（Concave Hull）の計算です。画像の灰色の線が凹包で、コンピュータで凹んだ形を認識するときなどに応用されています。

本来は画像のように字間がつながることは好ましくありません。論文によると、事前にクラスタリングを行った後、各クラスタに対して適用することでより良い結果となるそうです。