1. 序章

閉じた形状を描画するために接続したい平面上の点のセットがあると想像してみましょう。 まず、これらのポイントを並べ替える必要があります。

このチュートリアルでは、ポイントを時計回りに並べ替えることができる方法について説明します。

2. 問題の説明

2Dポイントのセット（それぞれが座標で表される）を前提として、これらのポイントを時計回りに並べ替えます。まず、これらのポイントを中心点の周りに表示する必要があります。 この中心点は、座標にある場合もあれば、2D平面上の任意の点にある場合もあります。 要件に基づいて、どちらの中心点が優れているかを選択できます。

このシナリオでは、見積もりを行います与えられた点の平均としての中心点。 これは次の図に示すように、中心点を中心に3つの点が並べ替えられています。

ここで注意すべき点がいくつかあります。 まず、凸包（すべての点をカプセル化する凸包）を推定していませんが、すべての点を時計回りに通過する閉じたパスを見つけたいと思います。[ X190X]したがって、次の方法でいくつかのポイントを並べ替えることができます。

ただし、同じセットのポイントについて、凸包を推定する場合、次のようにポイント1、2、3、および5のみが含まれます。

最後に注意すべきことは、すべての点が直線上にあるという例外的なケースについては説明しないということです。

3. アルゴリズムのアイデア

ポイントのセット、、、、、、およびが示されているように、例を見ていきましょう。

最初に行う必要があるのは、指定されたポイントの中心点を見つけることです。

次に、各点と中心の間の角度を推定します。

ポイントを時計回りに並べ替える必要があるため、最初のポイントは象限にあるポイントになります。 次は、象限に入るポイントになります。 ポイントとは象限にあります。 ただし、に近いほど最初に来て、次に来ます。 最後に、点と象限がありますが、どちらも角度があります。 このチュートリアルでは、中心からの距離でタイを解除することにしました。

ポイントはポイントよりも中心に近いため、ポイントになり、順序の最後のポイントになります。

与えられた例の最終的な順序は、、、、、、、です。

4. フローチャート

それでは、アルゴリズムの設計方法の詳細を見てみましょう。

高レベルの観点から、いくつかの基準に従ってソートする必要があるポイントの配列があります。 任意の並べ替えアルゴリズムを使用して、その仕事を行うための適切なコンパレータを提供できます。 ただし、この場合、前処理と後処理の手順をいくつか追加する必要があります。

のために前処理ステップでは、中心点を取得するために点をループする必要があります。 次に、指定されたすべてのポイントからこの中心点を減算しますすべての点を新しい原点（中心点）に変換します。

次に、関数を使用して sorting アルゴリズム（QuicksortやBubble-Sortなど）を呼び出し、定義された基準に従ってポイントをソートします。 最後に、ソートされたポイントに中心点を再度追加して、元の位置に変換し直します。

4.1. ソートポイントのフローチャート

次のフローチャートに示されている高レベルのアイデアから始めましょう。

4.2. ポイント比較フローチャート

それでは、関数の内部をさらに深く掘り下げてみましょう。 この関数では、入力として2つのポイントを取得し、最初のポイントが2番目のポイントの前にある場合は戻る必要があります。それ以外の場合は戻る必要があります。 からの中心点に対する任意の点の角度を示す別の関数があると仮定すると、2つの角度を直接比較できます。 。 同点の場合、各点と中心点の間の距離を比較して、最小のものを選択できます。

次のフローチャートは、このアイデアを示しています。 中心点は、前処理ステップで中心点の周りのすべての点を変換したためです。

および関数の詳細は、擬似コードに記載されます。

5. 擬似コード

次に、アルゴリズムの単純な擬似コードを見てみましょう。 擬似コードは、中心点を見つける一般的なアルゴリズムから始まり、次にすべての点をこの中心に変換します。 次に、カスタム関数を使用してsort関数を呼び出します。 最後に、ソートされたポイントを元の場所に戻します。

次に、関数はポイントの各ペアに対してand関数を呼び出します。 この関数は、最初の角度が2番目の角度よりも大きい場合に戻ります。 角度が等しい場合、または最初の距離が2番目の距離よりも小さい場合：

それでは、角度を推定する方法を見てみましょう。 多くのプログラミング言語に存在するような関数を使用していると仮定します。 この関数は、との値に基づいて逆tanを使用して角度を推定し、からの範囲の結果を返します。 この場合、角度はとの間である必要があります。 これを行う1つの方法は角度が、未満の場合は、を追加します。 したがって、角度の最終的な値は、から：までの望ましい範囲になります。

距離については、単純なユークリッド距離を、すべての軸の差の2乗の合計の平方根（）として使用できます。 実際には、平方根ステップを取り除き、2乗距離を返すことができます（このシナリオでは、距離は常にある点と中心点の間にあります）：

並べ替えアルゴリズム自体は、このチュートリアルの範囲外であることに注意してください。 Quicksort のような利用可能なソートアルゴリズムを使用して、の複雑さを取得できます。

6. 複雑

私たちのアルゴリズムの時間計算量は、選択したソートアルゴリズムの複雑さです。 クイックソートを選択した場合、全体的なアルゴリズムの複雑さはになります。 その理由は、前処理と後処理の複雑さのループしかないためです。 次に、カスタム比較関数を使用して並べ替えアルゴリズムを呼び出します。

スペースの複雑さに関しては、アルゴリズムは中心点以外の情報を格納する必要はありません。 したがって、スペースの複雑さは。

7. 結論

この記事では、ポイントを時計回りに並べ替える方法を紹介しました。 アイデアは、いくつかの前処理および後処理ステップを伴う一般的なソートアルゴリズムに依存します。 例、フローチャート、および擬似コードを使用してアルゴリズムを説明しました。 最後に、提示された方法の空間と時間の複雑さの単純な複雑さの分析を提供しました。