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

目次

1. 概要
2. 凸包
3. demo
4. 参考

概要

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

凸包

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

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

が、ある。

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

DEMO

デモ Link

参考

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