algorithm - 回転した長方形のポイントを並べ替えるにはどうすればよいですか?

Question

90 度未満の回転した長方形です。時計回りまたは反時計回りの場合があります。これらのポイントを長方形の元のシーケンスとして並べ替えるのが好きです。テキスト注釈のように、1、2、3、4......

私のアルゴリズムは次のとおりです。1.左、右、上、下のほとんどのポイントを見つけ、2.top.xとbottom.xを比較します。3.比較した値に従って、4つのコーナーシーケンスを見つけることができます 4.四隅の点から、長方形の辺の線関数を計算し、他の点を配置​​します。

この問題を解決するための、より効率的またはエレガントなアルゴリズムが他にあるかどうかはわかりません。ありがとうございました。

Answer 1

長方形が時計回りに 90 度未満の角度だけ回転したとします。その場合、一番上の行の (i+1) 番目の点は常に i 番目の点の右下にあることに注意してください。したがって、行を剥がすことができます。

1. すべてのポイントを y 座標の降順 (つまり、上から下) に並べ替えます。
2. これらの並べ替えられたポイントをリンクされたリストに入れます。(これは必須ではありませんが、ポイントの削除がより効率的になります。)
3. i = 1 に設定します。
4. lastX = -inf に設定します。
5. ソートされた点のリストの最初の要素を指すように p を設定します。残りの要素がなければ、完了です。
6. p から始めて、x 座標が lastX よりも大きい点 (前に追加した点の右側にあることを示す) が見つかるまで、点のリストをスキャンします。(すべての行の最初の繰り返しで、これは常にリストの最初のポイントを取ります。)

7. そのような点が見つかった場合:

   • リンクされたリストからこの点を削除し、i とラベル付けします。
   • p をリストの次の点に設定します。
   • i = i + 1 に設定します。
   • 追加したばかりの点の x 座標に lastX を設定します。
   • 6 に移動して、この行の次の点を見つけます。

   さもないと：

   • この行が終了し、その中のすべてのポイントがリンク リストから削除されました。4 に移動して次の行を開始します。

これは O(n^2) アルゴリズムです。行の右端のポイントが見つかると、次の行を処理するために一番上から開始する前に、残りのすべてのポイントを無駄にウォークスルーするためです。おそらくこれで十分ですが、時間の複雑さは O(nlog n) に減らすことができます左から右に並べられたすべてのポイントを含む別のリンクされたリストを維持し、左から右のリストの対応するノードを指す上から下のリストの各ノードに追加のフィールドを提供します。一番上の行の右端のポイントは常にポイント セット全体の右端のポイントであるため、削除されたばかりのポイントが全体の最後のポイントに対応するかどうかをテストすることで、行がちょうど O(1) 時間で終了したことを検出できます。左から右へのリスト。ポイントが上から下へのリストから削除される場合は常に、左から右へのリストからも削除する必要があります。

しかし、長方形を反時計回りに回転させたらどうなるでしょうか。 コメンター nm が指摘しているように、このケースを時計回りの回転と区別する方法は、さらなる情報なしではありません。反時計回りに d 度回転した n x m の長方形は、時計回りに (90-d) 度回転した m x n の長方形とまったく同じように見えます。これらのケースを区別する他の情報がある場合は、前と同じアルゴリズムを使用して反時計回りの回転を処理できますが、最初の (または任意の) 行の幅に注意し、後でラベルを再配置します。