C++로 구현하는 중점 선분 생성 알고리즘(Midpoint Line Algorithm)

선(line)은 두 점을 연결하는 그래픽스의 가장 기본적인 요소입니다. 화면에 선을 그리려면 시작점과 끝점, 두 개의 점이 필요하며, 그래픽스에서는 이 점들을 픽셀(pixel)이라고 부릅니다. 모든 픽셀은 정수 좌표를 가지므로, 우리는 x1 < x2이고 y1 < y2를 만족하는 정수 좌표 (x1, y1)와 (x2, y2)를 입력으로 받습니다.

이 글에서는 중점 선분 생성 알고리즘(Midpoint Line Generation Algorithm)을 사용하여 첫 번째 점 (x1, y1)과 두 번째 점 (x2, y2) 사이의 모든 중간 픽셀 좌표를 계산하는 방법을 단계별로 살펴봅니다.

선분 생성에 사용되는 3가지 대표 알고리즘

컴퓨터 그래픽스에서 화면에 선을 그릴 때 널리 사용되는 알고리즘은 다음 세 가지입니다.

DDA 알고리즘(Digital Differential Analyzer) — 기울기를 이용해 매 단계마다 좌표를 증분 계산하는 방식
브레젠험(Bresenham) 선분 생성 알고리즘 — 정수 연산만으로 오차를 누적 보정하며 픽셀을 선택하는 방식
중점(Mid-Point) 알고리즘 — 브레젠험 알고리즘을 일반화한 형태로, 후보 픽셀들의 중점과 실제 직선의 위치를 비교해 다음 픽셀을 결정하는 방식

중점 선분 생성 알고리즘의 동작 원리

중점 알고리즘으로 선을 그리는 절차는 다음과 같습니다.

현재 픽셀을 기준으로 동쪽(East) 후보 지점 (Xp+1, Yp)과 북동쪽(North East) 후보 지점 (Xp+1, Yp+1) 사이의 중간점 (Xp+1, Yp+½)을 계산합니다.
이 중간점이 실제 직선의 위에 있는지 아래에 있는지 판단하여 다음 픽셀의 위치를 결정합니다.
- 중간점이 직선보다 위에 있는 경우 → 다음 픽셀은 동쪽(EAST)으로 선택합니다.
- 중간점이 직선보다 아래에 있는 경우 → 다음 픽셀은 북동쪽(NORTH EAST)으로 선택합니다.

이 과정은 부동소수점 연산 없이 정수 연산만으로 처리할 수 있어 계산 효율이 매우 높으며, 전체 시간 복잡도는 O(max(dx, dy))입니다.

입출력 예시

예시 1

입력 — x₁ = 3, y₁ = 3, x₂ = 10, y₂ = 8

출력 — 3,3 4,4 5,5 6,5 7,6 8,7 9,7 10,8

풀이 — 먼저 dx = x₂ − x₁ = 10 − 3 = 7, dy = y₂ − y₁ = 8 − 3 = 5를 계산합니다. dy ≤ dx이므로 초기 판정 변수 d = dy − (dx / 2) = 5 − 3 = 2로 설정하고 첫 점 (3, 3)을 출력합니다. 이후 x₁ < x₂인 동안 x₁을 1씩 증가시키며, d < 0이면 d = d + dy로 갱신하고, 그렇지 않으면 d = d + (dy − dx)로 갱신한 뒤 y값을 1 증가시킵니다. 이 과정을 반복하면 위와 같은 픽셀 좌표열을 얻을 수 있습니다.

예시 2

입력 — x₁ = 2, y₁ = 2, x₂ = 3, y₂ = 4

출력 — 2,2 3,3 3,4

풀이 — dx = 1, dy = 2로 기울기가 1보다 큰 경우입니다. 이때는 x 대신 y를 기준으로 반복하며, d = dx − (dy / 2)로 초기화한 뒤 동일한 방식으로 중간 픽셀들을 결정합니다.

구현 접근 방식

정수 좌표 x₁, y₁, x₂, y₂를 입력받고, 선을 생성하기 위해 Mid_Point(x₁, y₁, x₂, y₂) 함수를 호출합니다.
Mid_Point 함수 내부의 동작은 다음과 같습니다.
- dx = x₂ − x₁, dy = y₂ − y₁을 계산합니다.
- dy ≤ dx인 경우(완만한 기울기): d = dy − (dx / 2)로 설정하고 first_pt = x₁, second_pt = y₁로 초기화한 뒤 두 좌표를 출력합니다.
- first_pt < x₂인 동안 first_pt를 1 증가시키고, d < 0이면 d = d + dy로, 그렇지 않으면 d = d + (dy − dx)로 갱신하며 second_pt를 1 증가시킵니다. 매 반복마다 현재 좌표를 출력합니다.
- dx < dy인 경우(가파른 기울기): d = dx − (dy / 2)로 설정하고 first_pt = x₁, second_pt = y₁로 초기화한 뒤 두 좌표를 출력합니다.
- second_pt < y₂인 동안 second_pt를 1 증가시키고, d < 0이면 d = d + dx로, 그렇지 않으면 d = d + (dx − dy)로 갱신하며 first_pt를 1 증가시킵니다. 매 반복마다 현재 좌표를 출력합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;

void Mid_Point(int x_1, int y_1, int x_2, int y_2){
    int dx = x_2 - x_1;
    int dy = y_2 - y_1;

    if(dy <= dx){
        int d = dy - (dx / 2);
        int first_pt = x_1;
        int second_pt = y_1;

        cout<< first_pt << "," << second_pt << "\n";
        while(first_pt < x_2){
            first_pt++;
            if(d < 0){
                d = d + dy;
            }
            else{
                d = d + (dy - dx);
                second_pt++;
            }
            cout << first_pt << "," << second_pt << "\n";
        }
    }
    else if(dx < dy){
        int d = dx - (dy/2);
        int first_pt = x_1;
        int second_pt = y_1;
        cout << first_pt << "," << second_pt << "\n";
        while(second_pt < y_2){
            second_pt++;
            if(d < 0){
                d = d + dx;
            }
            else{
                d += (dx - dy);
                first_pt++;
            }
            cout << first_pt << "," << second_pt << "\n";
        }
    }
}
int main(){
   int x_1 = 3;
   int y_1 = 3;
   int x_2 = 10;
   int y_2 = 8;
   cout<<"Mid-Points through Line Generation Algorithm are: ";
   Mid_Point(x_1, y_1, x_2, y_2);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Mid-Points through Line Generation Algorithm are:
3,3
4,4
5,5
6,5
7,6
8,7
9,7
10,8

마무리

중점 선분 생성 알고리즘은 부동소수점 연산을 배제하고 정수 연산만으로 다음 픽셀을 결정하기 때문에 소프트웨어 래스터라이저는 물론 하드웨어 그래픽 시스템에서도 널리 활용됩니다. DDA 알고리즘과 브레젠험 알고리즘과 함께 비교하며 학습하면 컴퓨터 그래픽스의 래스터 변환(rasterization) 원리를 더 깊이 이해할 수 있습니다.