2次元点列の凸包計算アルゴリズム

Wikibooks Algorithm Implementation/Geometry/Convex hull/Monotone chain

こちらのサイトに、コピペするだけで動く凸包計算のサンプルコードがあります。

こういうアルゴリズムは安定性を確保するのが難しいのかと思いきや、非常に頑健性の高い実装になっているようで、殆ど失敗無く計算できるようです。

C++のソースには、

// Implementation of Andrew's monotone chain 2D convex hull algorithm.
// Asymptotic complexity: O(n log n).
// Practical performance: 0.5-1.0 seconds for n=1000000 on a 1GHz machine.

とあるので、速度的にも問題なさそう。

ただし関数がvectorをそのまま返すようになっていたり若干無駄があるコードになっています。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

カレンダー
01 | 2018/02 | 03
- - - - 1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 - - -
最新記事
カテゴリ
Qt (21)
SDL (2)
MFC (2)
検索フォーム
月別アーカイブ
最新コメント
最新トラックバック
RSSリンクの表示
リンク
リンク(管理用)
FC2カウンター