JavaScriptで原点に最も近い座標ポイントを見つける方法

この記事では、JavaScriptを使って「原点(0, 0)に最も近い座標ポイント」を効率よく見つける方法を解説します。配列操作とユークリッド距離の計算を組み合わせた、シンプルかつ実用的なアルゴリズムを紹介します。

問題の定義

まず、次のような要件を持つJavaScript関数を作成します。

• 第1引数として、複数の座標を格納した配列 arr を受け取る
• 第2引数として、取得したいポイントの数 num を受け取る
• 原点 (0, 0) から num 番目まで近いポイントを見つけて返す

なお、平面上の2点間の距離はユークリッド距離(直線距離)を使用します。ユークリッド距離は次の式で求められます。

distance = √(x² + y²)

入力例と期待される出力

例として、以下の入力が関数に渡された場合を考えてみましょう。

const arr = [[3,3],[5,-1],[-2,4]];
const num = 2;

この場合、各ポイントの原点からの距離は以下のようになります。

• [3, 3] → √18 ≒ 4.24
• [5, -1] → √26 ≒ 5.10
• [-2, 4] → √20 ≒ 4.47

したがって、期待される出力は次のとおりです。

const output = [[3,3],[-2,4]];

解決コード

実装のアプローチはシンプルです。Array.prototype.sort() メソッドを使って、各ポイントを原点からの距離で昇順にソートし、先頭から num 個の要素を取り出します。

const arr = [[3,3],[5,-1],[-2,4]];
const num = 2;

const closestPoints = (arr = [], num = 1) => {
  arr.sort(([a, b], [c, d]) => {
    return Math.sqrt(a * a + b * b) - Math.sqrt(c * c + d * d);
  });
  return arr.slice(0, num);
};

console.log(closestPoints(arr, num));

コードの解説

• 分割代入: コールバック関数の引数 ([a, b], [c, d]) により、各座標配列から x 座標と y 座標を直接取り出しています。
• 距離の計算: Math.sqrt(a * a + b * b) で各ポイントの原点からのユークリッド距離を算出します。なお、平方根は単調増加するため、実際には a * a + b * b のまま比較しても同じ結果が得られ、計算コストも抑えられます。
• ソートと切り出し: 距離の昇順にソートした後、slice(0, num) で上位 num 件を返します。

実行結果

上記のコードをコンソールで実行すると、次の出力が得られます。

[ [ 3, 3 ], [ -2, 4 ] ]

まとめ

この方法では、ソートベースのアプローチにより時間計算量 O(n log n) で問題を解いています。より大量のデータを扱う場合は、優先度付きキュー(ヒープ)を使えば O(n log k) まで計算量を削減できるため、パフォーマンスが重要な場面では検討するとよいでしょう。