C++での中点線生成アルゴリズム

線は2点を接続します。これはグラフィックスの基本的な要素です。線を引くには、画面上に線を引くことができる2つのポイントが必要です。グラフィックスでは、ポイントをピクセルと呼び、すべてのピクセルは整数座標に関連付けられています。 （x1、y1）および（x2、y2）の形式で整数座標が与えられます。ここで、x1

画面上でライン生成を実行するために使用されている3つの異なるアルゴリズムがあり、それらは-

• DDAアルゴリズム

• ブレゼンハムのライン生成

• 中間点アルゴリズム

ミッドポイントアルゴリズム

中点線アルゴリズムを使用して線を引く手順は次のとおりです-

• 現在配置されているポイントを使用して中点を計算します。つまり、東（Xp + 1、Yp）と北東（Xp + 1、Yp + 1）は中点（Xp + 1、Yp + 1/2）です。

• これで、ミドルポイントが画面上の次の座標の位置を決定します。つまり

  • 中点が線より上にある場合、次の座標はEASTになります。

  • 中点が線より下にある場合、次の座標は北東になります。

このためのさまざまな入出力シナリオを見てみましょう-

で − int x_1 =3、int y_1 =3、int x_2 =10、int y_2 =8

アウト −ライン生成アルゴリズムによる中間点は次のとおりです。3,34,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

で − int x_1 =2、int y_1 =2、int x_2 =3、int y_2 =4

アウト −ライン生成アルゴリズムによる中間点は次のとおりです。2,23,3 3,4

説明 −座標はx_1 =2、x_2 =2、y_1 =3、y_2 =4として与えられます。したがって、中点線生成アルゴリズムを適用することにより、すべての中点ピクセルを出力として計算します。

以下のプログラムで使用されているアプローチは次のとおりです

• 整数点をintx_1、int y_1、int x_2、inty_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ずつインクリメントし、IFdが0未満であることを確認してからdをd+ dy ELSEに設定し、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に設定して、first_ptとsecond_ptを出力します。

  • y_2未満のwHILEsecond_ptを開始します。 WHILE内で、second_ptを1ずつインクリメントします。IFdが0未満であることを確認してから、dをd+dxに設定します。 ELSE、dからd +（dx --dy）で、first_ptを1ずつインクリメントします。

  • first_ptとsecond_ptを印刷します。

例

#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