C++ 위-아래 테스트로 직선에 대한 점의 위치 판별하기

컴퓨터 그래픽스나 계산 기하학(Computational Geometry) 분야에서는 어떤 점이 주어진 직선을 기준으로 어느 쪽에 놓여 있는지 판별해야 하는 경우가 매우 많습니다. 이 글에서는 위-아래 테스트(Above-Below Test)를 적용해 직선에 대한 점의 상대적 위치를 찾는 C++ 프로그램을 단계별로 살펴보겠습니다.

수학적 배경

평면상의 임의의 점 t(xt, yt)가 두 점 m과 n을 지나는 직선 L에 대해 어디에 위치하는지는 다음 스칼라 값을 계산하면 알 수 있습니다.

Y = A·xt + B·yt + C

계산 결과에 따른 판정 기준은 다음과 같습니다.
· Y < 0 → 점 t는 직선 L의 시계 방향(cw) 반평면, 즉 선의 왼쪽(아래)에 위치
· Y > 0 → 점 t는 반시계 방향(ccw) 반평면, 즉 선의 오른쪽(위)에 위치
· Y = 0 → 점 t는 직선 L 위에 있음

이 판별식은 두 벡터의 외적(cross product) 부호를 활용한 것으로, 세 점이 이루는 회전 방향(시계/반시계)을 확인하는 것과 본질적으로 같은 원리입니다.

알고리즘

시작
    점의 좌표를 입력받는다.
    rand 함수를 사용해 매 컴파일 시 직선의 계수(x1, x2, y1, y2)에 대한 난수를 생성한다.
    s를 다음 식으로 계산한다: (y2 - y1) * x + (x1 - x2) * y + (x2 * y1 - x1 * y2)
    만약 (s < 0)이면
        "점은 직선 아래 또는 왼쪽에 위치합니다."를 출력한다.
    그렇지 않고 (s > 0)이면
        "점은 직선 위 또는 오른쪽에 위치합니다."를 출력한다.
    그렇지 않으면
        "점은 직선 위에 위치합니다."를 출력한다.
종료

예제 코드

#include<stdlib.h>
#include<iostream>
#include<math.h>
#include<time.h>
using namespace std;

const int L = 0;
const int H = 20;

int main(int argc, char **argv) {
    time_t seconds;
    time(&seconds);
    srand((unsigned int) seconds);

    int x1, x2, y1, y2;
    x1 = rand() % (H - L + 1) + L;
    x2 = rand() % (H - L + 1) + L;
    y1 = rand() % (H - L + 1) + L;
    y2 = rand() % (H - L + 1) + L;

    cout << "첫 번째 직선의 방정식 : (" << (y2 - y1) << ")x+(" << (x1 - x2) << ")y+(" << (x2 * y1 - x1 * y2) << ") = 0\n";

    int x, y;
    cout << "\n점을 입력하세요:";
    cin >> x;
    cin >> y;

    int s = (y2 - y1) * x + (x1 - x2) * y + (x2 * y1 - x1 * y2);
    if (s < 0)
        cout << "점은 직선 아래 또는 왼쪽에 위치합니다";
    else if (s > 0)
        cout << "점은 직선 위 또는 오른쪽에 위치합니다";
    else
        cout << "점은 직선 위에 위치합니다";
    return 0;
}

코드에서는 time 함수로 현재 시각을 시드(seed)로 사용해 srand를 초기화하므로, 프로그램을 실행할 때마다 서로 다른 직선이 생성됩니다. 좌표 범위는 상수 L=0, H=20으로 설정되어 0부터 20 사이의 난수가 만들어집니다.

실행 결과

첫 번째 직선의 방정식 : (7)x+(0)y+(-105) = 0

점을 입력하세요:7
6
점은 직선 아래 또는 왼쪽에 위치합니다

위 실행 예제에서 생성된 직선은 7x − 105 = 0, 즉 x = 15인 수직선입니다. 입력한 점 (7, 6)의 x좌표가 15보다 작으므로 프로그램은 점이 직선의 왼쪽(아래)에 있다고 올바르게 판별합니다. 이처럼 위-아래 테스트는 간단한 부호 계산만으로 점과 직선의 위치 관계를 빠르게 확인할 수 있는 실용적인 기법입니다.