ポリゴンの頂点数を大幅に変更することなく、ポリゴンの頂点数を減らすための良いアルゴリズムとは何ですか？ポリゴン頂点の最小化
入力：ポイントのリストとして表され、あまりにも多くの頂点を持つ多角形：マウスからの生の入力など。
出力：まだ元のようにたくさん見えるくらい少ないverticiesとポリゴン：衝突検出のために使用可能なものを、例えば（必ずしも凸）。
編集：これに対する解決策は、グラフに複数のセグメント化された線を見つけることに似ています。これは、私のアルゴリズムの本の中でSegmented Least Squaresと呼ばれています。
Edit2：ダグラスピッカーアルゴリズムは、私が本当に欲しいものです。
編集のようなもののためのgoogle。あなたは本当に簡単に行くことができ、その周りの境界凸包を計算することができます。
凹面領域を気にしていた場合は、ポリゴンの重心をとり、始点を選択することで凹面を計算できます。始点からセントロイドの周りを回転させて、保持したい各頂点を見つけ、それを境界外郭の次の頂点として割り当てます。アルゴリズムの複雑さはどの頂点を保持するかを決める方法になりますが、あなたはそれをすでに考えていたと確信しています。重心との相対的な位置に基づいて、すべての頂点をバケットに投げることができます。バケットに任意の数の頂点がいっぱいになると、分割することができます。次に、そのバケット内の頂点の平均を頂点として取って、あなたの外枠に使用します。または、バケットを忘れて、セントロイドの周りを移動しているときは、最後のポイントから所定の距離以上離れていればポイントを選択します。
実際には、ポリゴンのすべての頂点を「ポイントオブクラウド」として使用し、その周囲の凹面を計算することができます。私はアルゴリズムのリンクを探します。最悪の場合、これは完全に凸の多角形になります。
もう1つの方法は、境界矩形で開始することです。矩形の各頂点について、点からポリゴンまでの距離を求めます。一番遠い頂点については、さらに2つの頂点に分割し、いくつかの頂点に移動します。頂点または面積のいずれかの割合が満たされるまで繰り返す。私はもう少し詳しくこれについて考えなければならないだろう。
ポリゴンが実際に似ているかどうか気になる場合は、自己交差ポリゴンの場合でも、別のアプローチが必要ですが、衝突検出について尋ねられてから必要なことはありません。
このpostには、凸包部分に関する詳細がいくつかあります。
私はcgal.orgのアルゴリズムを使って、後で衝突検出のためにポリゴンを凸状の構成要素に分解することができます。赤ちゃんには申し訳ありません。 –
そこには多くの素材があります。ああ、あなたは衝突検出を述べ、Simplifying Polygons
を見て：ちょうど「メッシュ化」、「メッシュ簡素化」、など「メッシュの最適化」、
これらのメッシュアルゴリズムのほとんどは、多くの三角形を期待しています。私はちょうど1つのポリゴンの頂点を減らそうとしています。 –
ポリゴンがすでに三角形のメッシュで表されていない場合は、それをメッシュに変換して上記のアルゴリズムを使用できませんか？ – Joe
うわー！このアルゴリズムはちょうどロック！ ：D –