5

私は頂点の大きな配列を持っています.それらのいくつかはエッジであり、いくつかは冗長であり(シェイプ内)、それらを削除したいと思います.

私が考えることができる最も単純なアルゴリズムは、それらが他のものによって形成された形状に当たるかどうかを1つずつチェックすることです. しかし、それは非常に遅いアルゴリズムでなければなりません。

エッジから 1 つ (例ごとに原点から最も遠いもの) を選択し、この開始点からの最長パスを計算することを考えました...エッジ パスを取得する必要がありますよね?

なにか提案を？

4

3 に答える 3

8

多面体アルゴリズムの秘訣は、入力と目的の出力に適合するものを選択することです。多面体を表す方法は複数あり、表現間の変換にはコストがかかる可能性があるためです。この場合、ポイントで開始し、頂点で終了する必要があるため、凸包の頂点を計算するグラハム スキャンアルゴリズムでうまくいくはずですが、2 次元のケースを超えて拡張するには多少の労力が必要になる場合があります。入力頂点数でO( n log n ) です。

于 2009-01-25T16:44:51.887 に答える
6

その多角形を見つけるための最適なアルゴリズムが何であるかはわかりませんが、探している多角形は「凸包」と呼ばれます。

それを検索すると、一致するアルゴリズムが見つかるはずです。

于 2009-01-25T16:22:17.987 に答える
4

凸包は、計算幾何学でさらに研究されている問題の1つです。グラハムスキャンは、より単純な凸型船体アルゴリズムの1つですが、確かに1つだけではありません。ジャービスマーチとも呼ばれるギフト包装アルゴリズムは、私が知っている中で最も単純なものです。Stony Brookアルゴリズムリポジトリには、CおよびC++での凸包アルゴリズムの実装がいくつかあります。Geometry in Actionは、主に凸包のアプリケーションを示しています。これは、低次元および任意次元の凸包計算プログラムのコレクションです。

于 2009-01-26T07:10:36.600 に答える