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

CSS




概要

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

凸包

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

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

が、ある。

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

DEMO


デモ Link

参考

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