【JavaScript】凸包(グラハムスキャン)を可視化・アニメーション【Canvas】

目次

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

概要

前回に引き続き 凸包(グラハムスキャン)のスキャンする様子をアニメーションにして可視化してみた。 ライブラリとかは使わず、Canvasにそのまま描画する。

凸包

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

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

が、ある。

このうちのグラハムスキャンを実装してみることにした。

DEMO

デモ Link

参考

凸包を求める（Grahamスキャン） INTRODUCTION TO ALGORITHMS 【JavaScript】凸包(ギフト包装法)を可視化・アニメーション【Canvas】