C++で実装する中点線分生成アルゴリズムの解説

線とは2つの点を結ぶものであり、コンピュータグラフィックスにおける最も基本的な要素です。線を描画するには、画面上に線を引くための2つの点が必要です。グラフィックスの世界では、これらの点を「ピクセル」と呼び、すべてのピクセルには整数座標が割り当てられています。

本記事では、x1 < x2 かつ y1 < y2 を満たす整数座標 (x1, y1) と (x2, y2) が与えられたとき、中点線分生成アルゴリズム(Midpoint Line Generation Algorithm)を用いて、点1 (x1, y1) と点2 (x2, y2) の間の中間点をすべて計算する方法を解説します。

画面上で線を生成するために使われる代表的なアルゴリズムには、以下の3種類があります。

• DDAアルゴリズム(Digital Differential Analyzer)
• ブレセンハムの線分生成アルゴリズム(Bresenham's Line Generation)
• 中点アルゴリズム(Mid-Point Algorithm)

中点アルゴリズム(Mid-Point Algorithm)とは

中点線分アルゴリズムで線を描画する手順は以下の通りです。

• 現在位置している点をもとに中点を計算します。候補となるのは東(East)方向の点 (Xp+1, Yp) と北東(North East)方向の点 (Xp+1, Yp+1) であり、この2つの中点は (Xp+1, Yp+1/2) となります。
• この中点の位置によって、画面上の次の座標が決定されます。
  • 中点が理想の線より上にある場合 → 次の座標は東(EAST)を選択します。
  • 中点が理想の線より下にある場合 → 次の座標は北東(NORTH EAST)を選択します。

入出力例

具体的な入出力シナリオを見てみましょう。

入力 − int x_1 = 3, int y_1 = 3, int x_2 = 10, int y_2 = 8

出力 − 中点線分生成アルゴリズムによる中間点: 3,3 4,4 5,5 6,5 7,6 8,7 9,7 10,8

説明 − 座標として x_1 = 3、x_2 = 10、y_1 = 3、y_2 = 8 が与えられています。まず dx = x_2 − x_1 = 10 − 3 = 7、dy = y_2 − y_1 = 8 − 3 = 5 を計算し、dy が dx より小さいことを確認します。続いて判定値 d を 5 − (7 ÷ 2) = 2 として求めます。最初の出力点は (x_1, y_1) です。その後、x_1 < x_2 が成り立つ間、x_1 を1ずつ増加させながら、d が0未満であれば d を d + dy に更新し、そうでなければ d を d + (dy − dx) に更新して y_1 を1増加させます。

入力 − int x_1 = 2, int y_1 = 2, int x_2 = 3, int y_2 = 4

出力 − 中点線分生成アルゴリズムによる中間点: 2,2 3,3 3,4

説明 − 座標として x_1 = 2、y_1 = 2、x_2 = 3、y_2 = 4 が与えられています。中点線分生成アルゴリズムを適用することで、始点から終点までのすべての中間点ピクセルが出力として得られます。

プログラムのアプローチ

• 整数の点を int x_1, int y_1, int x_2, int y_2 として受け取り、線を生成するために関数 Mid_Point(x_1, y_1, x_2, y_2) を呼び出します。
• 関数 Mid_Point(x_1, y_1, x_2, y_2) 内部の処理は以下の通りです。
  • dx を x_2 − x_1、dy を y_2 − y_1 として計算します。
  • dy ≤ dx の場合:d を dy − (dx ÷ 2) に設定し、first_pt を x_1、second_pt を y_1 に初期化します。
  • first_pt と second_pt を出力します。
  • first_pt < x_2 の間ループ処理を行い、first_pt を1増加させます。d < 0 なら d を d + dy に更新し、そうでなければ d を d + (dy − dx) に更新して second_pt を1増加させます。その都度 first_pt と second_pt を出力します。
  • dx < dy の場合:d を dx − (dy ÷ 2) に設定し、first_pt を x_1、second_pt を y_1 に初期化して出力します。
  • second_pt < y_2 の間ループ処理を行い、second_pt を1増加させます。d < 0 なら d を d + dx に更新し、そうでなければ d を d + (dx − dy) に更新して first_pt を1増加させます。
  • 各ステップで first_pt と second_pt を出力します。

サンプルコード(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

このように中点アルゴリズムを使えば、浮動小数点演算を最小限に抑えながら、整数演算のみで効率的に線分を構成するピクセル列を求めることができます。ブレセンハム法と同様に、描画速度が重視されるグラフィックス処理で広く活用されている手法です。