見た目をあまり変えずにポリゴンの頂点の数を減らすための良いアルゴリズムは何ですか?
入力: ポイントのリストとして表される多角形で、頂点が多すぎます: たとえば、マウスからの生の入力。
出力: 頂点の数がはるかに少なく、元のポリゴンとよく似たポリゴン: たとえば、衝突検出に使用できるもの (必ずしも凸面である必要はありません)。
編集：これに対する解決策は、グラフ上で最適な複数セグメントの線を見つけることに似ています。私のアルゴリズムの本では、セグメント化された最小二乗法と呼ばれています。
Edit2: Douglas Peucker Algorithm は、私が本当に欲しいものです。
編集：ああ、ポリゴンの単純化
衝突検出について言及しました。あなたは本当に単純に行き、その周りのバウンディング凸包を計算することができます.
凹面領域を気にする場合は、ポリゴンの重心を取得し、開始点を選択することで、凹面ハルを計算できます。開始点から重心を中心に回転し、保持する各頂点を見つけて、それをバウンディング ハルの次の頂点として割り当てます。アルゴリズムの複雑さは、どの頂点を保持するかをどのように決定するかにかかっていますが、それについてはすでに考えていると思います。重心に対する位置に基づいて、すべての頂点をバケットに入れることができます。バケットが任意の数以上の頂点でいっぱいになると、それを分割できます。次に、バウンディング ハルで使用する頂点として、そのバケット内の頂点の平均をとります。または、バケツを忘れて、重心の周りを移動しているときに、最後のポイントからの距離が指定された距離を超えている場合にのみポイントを選択します。
実際には、おそらくポリゴン内のすべての頂点を「点群」として使用し、その周りの凹包を計算することができます。アルゴリズムのリンクを探します。これに関する最悪のケースは、完全な凸多角形です。
もう 1 つの方法は、外接する四角形から始めることです。長方形の各頂点について、点から多角形までの距離を見つけます。最も遠い頂点については、それをさらに 2 つの頂点に分割し、それらを移動します。頂点または領域のいずれかの割合が満たされるまで繰り返します。細かいところはもう少し考えないといけないですね。
自己交差ポリゴンの場合でも、ポリゴンが実際に似ていることに関心がある場合は、別のアプローチが必要になりますが、衝突検出について尋ねたので、それは必要ないように聞こえます。
この投稿には、凸包部分に関する詳細が記載されています。
そこにはたくさんの資料があります。「メッシュの縮小」、「メッシュの単純化」、「メッシュの最適化」などをグーグルで検索してください。