☰

点の集合を囲む多角形 質問する

tag-icon • tag-icon algorithm language-agnostic geometry polygon
点の集合を囲む多角形 質問する

点の集合 S (2D : x と y で定義) があり、集合のすべての点を囲む最小の (つまり、点の数が最も少ない) 多角形 P を見つけたいとします。P は S の順序付きサブセットです。

これを計算するための既知のアルゴリズムはありますか? (この分野における私の教養のなさは驚くべきものです...)

ご協力いただきありがとうございます

ベストアンサー1

この問題には多くのアルゴリズムがあります。これは「最小境界ボックス「。検索すると解決策も見つかります」凸包"、 特にここ。

1 つの方法は、最も左の点を見つけてから、他のすべての点が線 p(n-1)p(n) の右側にある点の検索を繰り返すことです。

おすすめ記事