頂点のエッジ (ポリゴン) を見つけるための最適なアルゴリズム

Question

大量の頂点の配列があり、その一部はエッジであり、一部は冗長 (シェイプ内) なので、それらを削除したいと考えています。

私が思いつく最も単純なアルゴリズムは、それらが他のものによって形成された形状に一致するかどうかを 1 つずつチェックすることです。しかし、それは非常に遅いアルゴリズムであるはずです。

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

なにか提案を？

Answer 1

多面体を表現し、表現の間の変換は、高価であることができる複数の方法があるので

多面体アルゴリズムとのトリックは、あなたの入力及び希望の出力に適したものを選択しています。このケースでは、ポイントで始まり、頂点で終了したいので、グラハムはのアルゴリズムをスキャンしていますそれが拡張するいくつかの努力を取るかもしれませんが凸包するの頂点を計算するためには、トリックを行う必要がありますその2-Dの場合、過去。これは、入力頂点の数がO（ NログN ）です。

Answer 2

私はそのポリゴンを見つける最適なアルゴリズムがあるが、あなたが探しているポリゴンが「凸包」と呼ばれているのか分からない。

そのために検索することにより、あなたはマッチングアルゴリズムを見つける必要があります。

Answer 3

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