GrahamScan点群の凸包を求める 問題 与えられた2次元の点群を包み込む多角形を求める問題です。下の□が与えられた点群で、多角形がそれを覆う凸包です。 手法 ここでの手法 セジビック著 「アルゴリズムC++」 を参考にしました。図も著書を引用させていただきます。ここでは、概略しか説明しません。詳細は、本を参照してください。最初に以下の点が与えられたとします。まず、一番下でかつ右にある基礎となる点を求めます。ここでは、B点になります。 セジビック著 「アルゴリズムC++」より B点から各点への角度を求め、この角度で点を整列します。 B,M,J,L,N,P,K,... となります。 セジビック著 「アルゴリズムC++」より BとMは凸包の点です。次にJを加えます。この時点では、J も凸包の点とします。しかし、次にLを加えますとBJLは凸でなくなります。そこで、Jを凸包から除外しLを加えます。こ
