与えられた4つの点が正方形を形成しているかどうかを判定するアルゴリズム

概要

2次元平面上に4つの点が与えられたとき、このアルゴリズムはそれらの点が正方形を形成しているかどうかを判定します。

点が正方形を形成しているかを確認するためには、以下の条件を満たしている必要があります。

• 与えられた4つの点で構成される4つの辺がすべて同じ長さであること
• 隣接する2つの辺がすべて直角（90度）で交わっていること

入力と出力

入力:
4つの点 {(20, 10), (10, 20), (20, 20), (10, 10)}
出力:
点は正方形を形成しています。

アルゴリズム

isFormingSquare(p1, p2, p3, p4)

この手順では、squareDist(p1, p2) という補助メソッドを使用します。このメソッドは、与えられた2点間の距離の2乗（平方距離）を返します。実際の距離ではなく距離の2乗を使うことで、平方根の計算を避け、誤差や計算コストを抑えることができます。

入力: 4つの点。

出力: 与えられた点が正方形を形成する場合は true、そうでない場合は false。

Begin
    dist12 := squareDist(p1, p2)
    dist13 := squareDist(p1, p3)
    dist14 := squareDist(p1, p4)

    if dist12 = dist13 and 2*dist12 = dist14, then
        dist := squareDist(p2, p4)
        return true when dist = squareDist(p3, p4) and dist = dist12
    if dist13 = dist14 and 2*dist13 = dist12, then
        dist := squareDist(p2, p3)
        return true when dist = squareDist(p2, p4) and dist = dist13
    if dist12 = dist14 and 2*dist12 = dist13, then
        dist := squareDist(p2, p3)
        return true when dist = squareDist(p3, p4) and dist = dist12
    return false
End

判定ロジックのポイント

基準となる点 p1 から他の3点までの距離を比較します。正方形の場合、p1 から見て隣接する2点までの距離は等しく、対角線上にある点までの距離はその √2 倍（つまり平方距離で2倍）になります。どの組み合わせが隣接でどれが対角になるかは入力の順序によって変わるため、3通りのケースをすべてチェックしています。

C++による実装例

#include<iostream>
using namespace std;

struct Point {
    int x, y;
};

int squareDist(Point p, Point q) {
    return (p.x - q.x)*(p.x - q.x) + (p.y - q.y)*(p.y - q.y);
}

bool isSquare(Point p1, Point p2, Point p3, Point p4) {     // 4つの点が正方形を形成するか判定
    int dist12 = squareDist(p1, p2);      // p1 から p2 への距離
    int dist13 = squareDist(p1, p3);      // p1 から p3 への距離
    int dist14 = squareDist(p1, p4);      // p1 から p4 への距離

    // p1-p2 と p1-p3 の長さが等しく、(p1-p4) の2乗が 2*(p1-p2) に等しい場合
    if (dist12 == dist13 && 2*dist12 == dist14) {
        int dist = squareDist(p2, p4);
        return (dist == squareDist(p3, p4) && dist == dist12);
    }

    // 残りの組み合わせについても同様の条件を確認
    if (dist13 == dist14 && 2*dist13 == dist12) {
        int dist = squareDist(p2, p3);
        return (dist == squareDist(p2, p4) && dist == dist13);
    }

    if (dist12 == dist14 && 2*dist12 == dist13) {
        int dist = squareDist(p2, p3);
        return (dist == squareDist(p3, p4) && dist == dist12);
    }
    return false;
}

int main() {
    Point p1 = {20, 10}, p2 = {10, 20}, p3 = {20, 20}, p4 = {10, 10};
    if(isSquare(p1, p2, p3, p4))
        cout << "Points are forming a square.";
    else
        cout << "Points are not forming a square";
}

実行結果

Points are forming a square.

このアルゴリズムの計算量は O(1) であり、点の数が固定されているため非常に効率的です。また、距離の2乗のみを扱うことで浮動小数点演算を回避でき、整数座標であれば厳密な判定が可能です。