【JavaScript】凸包(ギフト包装法)を可視化・アニメーション【Canvas】

HTML




概要

凸包(ギフト包装法)のスキャンする様子をアニメーションにして可視化してみた。
ライブラリとかは使わず、Canvasにそのまま描画する。

凸包

凸包 – WikiPedia
凸包を解くためのアルゴリズムは様々なものが存在し、
代表的なものを上げると、

  • グラハムスキャン
  • 分割統治法
  • ギフト包装法

が、ある。

パフォーマンスが優れているのは、グラハムスキャンだが、
比較的にわかりやすいギフト包装法を可視化してみることにした。

DEMO


デモ Link

参考

凸包を求める(Grahamスキャン)
Canvasで凸包を描画する