10

ポイント配列 (ポイントは、 forとfor の 2 つfloatの型を持つ構造体です) を特別な方法で並べ替える必要があります。xy

ポイントを並べ替える必要があるため、トラバースするときに、左上のポイントから始まり、右上のポイント、次に左から 2 番目のポイント、右から 2 番目のポイントなどに移動するジグザグ パターンを形成します。

図

これは、任意のポリゴンをトライアングル ストリップ配列に変換し、GLes を使用して描画できるようにするために必要です。ポインターを使用する (つまり、ポインターをポイント構造に渡して再配置する) か、構造内のデータを直接コピーして移動することによって、これらのポイントを並べ替える最も効率的な方法は何でしょうか?

4

7 に答える 7

3

@stefan が指摘したように、qsort() をカスタムの compare() 関数と共に使用します。この関数は、y で降順に並べ替え、x を (最大/最小) 交互に並べ替えます。

于 2012-08-31T15:52:53.640 に答える
2

Delaunay Triangulationを使用することを強くお勧めします。OpenCV (C で利用可能) には優れた実装があります。

于 2012-08-31T16:01:33.663 に答える
1

私はあなたが明確な順序を与えたとは思わない。たとえば、ポイントが次のようになっている場合、ポイントはどのような順序で接続する必要がありますか。

*

         *
                 *
*
    *
    *
于 2012-08-31T16:09:21.670 に答える
1

あなたは、解決策への正しい道を進んでいると信じて、元の問題の縮小版を私たちに提示しているようです。私は間違っているかもしれませんが、あなたのようには見えません。

最終的には三角形分割を探しているようです (他の質問から判断すると) 。そして、 (独立した点の集合ではなく) 1つまたは複数の多角形の三角形分割である可能性が非常に高いです。もしそうなら、単調分解に基づくものなど、いくつかの基本的な三角測量アルゴリズムを検討することをお勧めします。あなたがここで提示した問題は、実際には単調な分解に似た何かをしようとする [おそらく見当違いの] 試みのように見えます。

于 2012-08-31T16:46:53.527 に答える
0

最初に、ポイントの中央値（中央値）を見つける必要があります（水平値に基づく）。これにより、ポイントのセットが左右に分割されます。次に、垂直方向の値に基づいて2つのセットを並べ替えます。次に、各セットから上から繰り返すことができます。左のセットから上の要素を取得し、次に右のセットから上の要素を取得します。

中央値を見つけるために、クイックソートに基づく短いアルゴリズムがあります。しかし、クイックソートよりも高速です。中央値がある部分で再帰するだけです（クイックソートのように両方ではありません）。

逆の方法でも実行できるはずです。最初に垂直方向の値で並べ替えてから、水平方向で分割します（ポイントの数が奇数の場合は、これが適している可能性があります）。

于 2012-08-31T17:16:57.827 に答える
0

ある種の単調な多角形チェーンを再発明しようとしているようです。いくつかの多角形の三角形分割方法は、wikiで簡単に説明されており、ここにコードへのリンクがあります

于 2012-08-31T16:45:05.310 に答える
0

構造から直接データを移動することをお勧めします。

ポイント構造体のサイズはわずか 8 ～ 16 バイト (float が 8 バイトの場合は 16 バイト) です。ポインターを介して配列をソートすると、ほぼ同じ量のデータがコピーされます (または、64 ビット システムで float が 4 バイトおよび 8 バイトのポインターの場合は同じ量のデータ)。

構造体が大きい場合は、ポインターでソートすることをお勧めします。

于 2012-08-31T16:36:41.703 に答える