【JavaScript】4つの座標点から正方形を判定するアルゴリズム

問題の概要

JavaScriptで、4つの引数を受け取る関数 validSquare を作成することを目標とします。各引数は「数値2つからなる配列」であり、平面上の四角形(または閉じた・開いた任意の図形)の4つの頂点座標を表しています。

この関数の役割は、与えられた4つの頂点が正方形を形成しているかどうかを判定することです。正方形であれば true を、そうでなければ false を返します。

入力例

const c1 = [1, 0];
const c2 = [-1, 0];
const c3 = [0, 1];
const c4 = [0, -1];

出力例

const output = true;

この4点は原点を中心とした一辺2、面積4平方単位の正方形を形成するため、結果は true になります。

判定のアプローチ:「距離の種類数」に注目する

正方形かどうかを見分けるカギは頂点同士の距離です。4つの頂点から作られるペアは全部で C(4,2) = 6 通りあり、正方形の場合その内訳は次のようになります。

• 辺: 4本(すべて等しい長さ)
• 対角線: 2本(すべて等しい長さ)

つまり、正方形であれば「辺の長さ」と「対角線の長さ」というちょうど2種類の距離だけで構成されます。一方、ひし形や長方形などの場合は3種類以上の距離が現れるため、この性質を利用して正方形だけを正確に識別できます。

また、同一座標の頂点が存在する場合は図形として成立しないため、その時点で false を返すようにします。

実装コード

const c1 = [1, 0];
const c2 = [-1, 0];
const c3 = [0, 1];
const c4 = [0, -1];

const validSquare = (c1, c2, c3, c4) => {
  // 2点間のユークリッド距離を計算するヘルパー関数
  const dist = (p1, p2) =>
    Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2));

  const points = [c1, c2, c3, c4];
  const lens = new Set(); // 出現した距離の種類を格納

  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      // 同じ座標の頂点があれば正方形ではない
      if (points[i][0] === points[j][0] && points[i][1] === points[j][1]) {
        return false;
      }
      lens.add(dist(points[i], points[j]));
    }
  }

  // 「辺」と「対角線」の2種類の距離だけで構成されていれば正方形
  return lens.size === 2;
};

console.log(validSquare(c1, c2, c3, c4));

実行結果

true

コードのポイント解説

• dist 関数: 三平方の定理(ピタゴラスの定理)を用いて、2点間の直線距離を求めています。
• 二重ループ: 変数 i と j の組み合わせにより、6通りの頂点ペアをすべて走査します。j を i + 1 から始めることで、同じペアの重複計算を防いでいます。
• 重複チェック: 座標が完全に一致する頂点が見つかった時点で、正方形は成立しないため即座に false を返します。
• Set の活用: Set は同じ値を自動的にまとめてくれるため、「距離の種類数」を簡単に数えられます。最終的なサイズが 2(辺+対角線)であれば正方形と判定できます。

注意点:浮動小数点誤差への対策

Math.sqrt を使用すると、浮動小数点数の誤差によって意図しない比較結果になる可能性があります。より堅牢な実装にしたい場合は、sqrt を取らずに「距離の2乗」をそのまま Set に追加して比較する方法がおすすめです。整数座標であれば誤差の心配なく、正確かつ高速に判定できます。