convex hull
多数の点が与えられたとき、全ての点を含む最少の凸多角形が一意に決まる。これを凸包と呼ぶ。
素朴なアルゴリズム
全ての三点の組を調べて、対応する三角形に含まれる点を除いていく。
凸包内部の全ての点を除いた後、偏角順に点を並べると凸包が完成する。
平面上に与えられたn点の凸包を求める問題の計算複雑度は
$ \Theta(n \log n)
である。
Jarvis's march
凸包
https://scrapbox.io/files/640f2c894e85ff001c0722a9.jpg
#コンピュータジオメトリ
#計算幾何