同じ行の隣接する点の比較

Question

同じ行の点のリストが与えられたら、各点の隣接する点を見つける必要があります。 See the image for illustration

私はすべての点の座標を知っています。これらのポイントは入力リストでランダムに並べられます。

私のアプローチ：

1. 、リスト内の最初のポイントを選択してください。この点からすべての点までのベクトルを見つけます。
2. 各ベクトルについて、反時計回りの角度を見つけます。
3. 可能なのは2つの角度（a1、a2）だけです。角度a1を有するすべての点のリストと、角度a2を有する点のリストを形成する。
4. 各リストについて、ユークリッド距離/ベクトル長を調べてください。
5. このリストを昇順に並べ替えます。これを使用して相対的な順序付けを行うことができます。

例：P2は、リスト内の最初のポイントであることを起こる場合、次に、小さい方の角度が大きく時計回りの角度がそう210 なり、30であると仮定すると、P1は、一つのリストにあるであろう。 p3、p4、p2は他のリストにあります。今、私は点の相対的な順序を得ることができます。

もっと良い解決策はありますか？

Answer 1

1. 最初の2点のY軸を比較して、行が垂直かどうかを調べます。 （O（1））
2. 垂直場合、ソートY軸（O（nlogn））によって
3. 隣接点を見つけるためにソートX軸（O（nlogn））
4. によって、垂直ではない場合、検索バイナリサーチ（O（logn））によってソートされたリストをポイントし、前後のポイントを取る。