주어진 4개의 점이 정사각형을 형성하는지 확인하는 알고리즘

2차원 평면 위에 네 개의 점이 주어졌을 때, 이 점들이 정사각형의 네 꼭짓점을 이루는지 판별하는 알고리즘입니다. 좌표 데이터를 수학적 조건 검증만으로 빠르고 정확하게 확인할 수 있습니다.

정사각형 판별 조건

주어진 네 점이 정사각형을 이루려면 다음 두 가지 조건을 모두 만족해야 합니다.

네 점으로 만들어지는 네 변의 길이가 모두 같아야 합니다.
서로 이웃한 두 변이 이루는 각이 모두 직각(90°)이어야 합니다.

입력과 출력

입력: 네 개의 점 {(20, 10), (10, 20), (20, 20), (10, 10)}
출력: 네 점은 정사각형을 형성합니다.

알고리즘 설계

판별 함수의 기본 골격은 다음과 같습니다.

isSquare(p1, p2, p3, p4)

이 과정에서는 squareDist(p1, p2) 함수를 사용합니다. 이 함수는 두 점 사이 거리의 제곱값을 반환합니다. 실제 거리 대신 제곱 거리를 사용하면 제곱근 계산을 생략할 수 있어, 부동소수점 오류 없이 정수 연산만으로도 정확한 비교가 가능하다는 장점이 있습니다.

입력: 네 개의 점

출력: 네 점이 정사각형을 이루면 참(true), 아니면 거짓(false)

핵심 아이디어

정사각형에서 한 꼭짓점에서 나머지 세 꼭짓점까지의 거리를 살펴보면, 두 개는 변의 길이(a)와 같고 하나는 대각선 길이(a√2)입니다. 제곱 거리로 표현하면 대각선의 제곱 거리는 변의 제곱 거리의 정확히 2배가 됩니다. 즉, p1에서 측정한 세 거리 중 두 값이 같고, 나머지 하나가 그 값의 2배라면 p1을 한 꼭짓점으로 하는 정사각형일 가능성이 있습니다. 알고리즘은 어떤 점이 대각선 반대편 꼭짓점인지에 따라 세 가지 경우를 순서대로 검사합니다.

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

    // 경우 1: p4가 p1의 대각선 반대편인 경우
    만약 dist12 = dist13 이고 2*dist12 = dist14 이면
        dist := squareDist(p2, p4)
        dist = squareDist(p3, p4) 이고 dist = dist12 일 때 참 반환

    // 경우 2: p2가 p1의 대각선 반대편인 경우
    만약 dist13 = dist14 이고 2*dist13 = dist12 이면
        dist := squareDist(p2, p3)
        dist = squareDist(p2, p4) 이고 dist = dist13 일 때 참 반환

    // 경우 3: p3가 p1의 대각선 반대편인 경우
    만약 dist12 = dist14 이고 2*dist12 = dist13 이면
        dist := squareDist(p2, p3)
        dist = squareDist(p3, p4) 이고 dist = dist12 일 때 참 반환

    거짓 반환
끝

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) {
    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×(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 << "네 점은 정사각형을 형성합니다.";
    else
        cout << "네 점은 정사각형을 형성하지 않습니다.";
}

실행 결과

네 점은 정사각형을 형성합니다.

복잡도 및 참고 사항

이 알고리즘은 고정된 개수의 거리만 계산하고 비교하므로 시간 복잡도는 O(1)입니다. 다만 네 점이 모두 같은 위치에 있는 등 퇴화(degenerate)된 입력에 대한 별도 처리가 필요할 수 있으므로, 실무에서는 거리가 0인 경우를 먼저 걸러내는 방어 코드를 추가하는 것이 좋습니다.