Processing math: 100%

C++ 中点线生成算法

一条线连接两点。它是图形的基本元素。要绘制一条线，您需要两点，您可以在屏幕上这两点之间绘制一条线，在图形方面，我们将这些点称为像素，每个像素都与整数坐标相关联。我们以 (x1, y1) 和 (x2, y2) 的形式给出整数坐标，其中 x1 < x2 且 y1 < y2。任务是使用中点线生成算法计算点 1 即 (x1, y1) 和点 2 即 (x2, y2) 之间的所有中点。

有三种不同的算法用于在屏幕上执行线生成，它们是：

  • DDA 算法

  • Bresenham 线生成算法

  • 中点算法

中点算法

使用中点线算法绘制线条的步骤：

  • 使用当前定位点计算中点，即东点 (Xp+1, Yp) 和东北点 (Xp+1, Yp+1) 是中点 (Xp+1, Yp+1/2)。

  • 现在，中点将决定屏幕上下一个坐标的位置，即：

    • 如果中点在直线上方，则下一个坐标将在东侧。

    • 如果中点在直线下方，则下一个坐标将在东北侧。

让我们看看这种情况的各种输入输出场景：

输入 - 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) 并将 x_2 增加 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, x_2 = 2, y_1 = 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

    • 检查 IF dy 小于或等于 dx，则将 d 设置为 dy - (dx / 2)，并将 first_pt 设置为 x_1，并将 second_pt 设置为 y_1

    • 打印 first_pt 和 second_pt。

    • 启动 while first_pt 小于 x_2，然后将 first_pt 加 1，并检查 IF 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 并打印 first_pt 和 second_pt。

    • 启动 WHILE second_pt 小于 y_2。在 WHILE 内部，将 second_pt 加 1。检查 IF d 小于 0，则将 d 设置为 d + dx。否则，将 d 设置为 d + (dx - dy) 并将 first_pt 加 1。

    • 打印 first_pt 和 second_pt。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

Open Compiler
#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

更新于：2021年10月22日

3K+ 次浏览

启动您的 职业生涯

完成课程获得认证

开始学习
广告