90 度未満の回転した長方形です。時計回りまたは反時計回りの場合があります。これらのポイントを長方形の元のシーケンスとして並べ替えるのが好きです。テキスト注釈のように、1、2、3、4......
私のアルゴリズムは次のとおりです。1.左、右、上、下のほとんどのポイントを見つけ、2.top.xとbottom.xを比較します。3.比較した値に従って、4つのコーナーシーケンスを見つけることができます 4.四隅の点から、長方形の辺の線関数を計算し、他の点を配置します。
この問題を解決するための、より効率的またはエレガントなアルゴリズムが他にあるかどうかはわかりません。ありがとうございました。
長方形が時計回りに 90 度未満の角度だけ回転したとします。その場合、一番上の行の (i+1) 番目の点は常に i 番目の点の右下にあることに注意してください。したがって、行を剥がすことができます。
そのような点が見つかった場合:
さもないと：
これは O(n^2) アルゴリズムです。行の右端のポイントが見つかると、次の行を処理するために一番上から開始する前に、残りのすべてのポイントを無駄にウォークスルーするためです。おそらくこれで十分ですが、時間の複雑さは O(nlog n) に減らすことができます左から右に並べられたすべてのポイントを含む別のリンクされたリストを維持し、左から右のリストの対応するノードを指す上から下のリストの各ノードに追加のフィールドを提供します。一番上の行の右端のポイントは常にポイント セット全体の右端のポイントであるため、削除されたばかりのポイントが全体の最後のポイントに対応するかどうかをテストすることで、行がちょうど O(1) 時間で終了したことを検出できます。左から右へのリスト。ポイントが上から下へのリストから削除される場合は常に、左から右へのリストからも削除する必要があります。
しかし、長方形を反時計回りに回転させたらどうなるでしょうか。 コメンター nm が指摘しているように、このケースを時計回りの回転と区別する方法は、さらなる情報なしではありません。反時計回りに d 度回転した n x m の長方形は、時計回りに (90-d) 度回転した m x n の長方形とまったく同じように見えます。これらのケースを区別する他の情報がある場合は、前と同じアルゴリズムを使用して反時計回りの回転を処理できますが、最初の (または任意の) 行の幅に注意し、後でラベルを再配置します。