DDA算法，是计算机图形学中一种基于直线的微分方程来生成直线的方法，由于有浮点数运算与取整，该算法不利于硬件实现。
其主要思想是由直线公式y = kx + b推导出来的。
我们已知直线段两个端点P0(x0,y0)和P1(x1,y1)，就能求出 k 和 b 。
在k，b均求出的条件下，只要知道一个x值，我们就能计算出一个y值。如果x的步进为1（x每次加1，即x = x +1），那么y的步进就为k+b；同样知道一个y值也能计算出x值，此时y的步进为1，x的步进为(1-b)/k。根据计算出的x值和y值，向下取整，得到坐标(x’,y’)，并在(x’,y’)处绘制直线段上的一点。
为进一步简化计算，通常可令b取0，将起点看作(0,0)。设当前点为(xi, yi)则用DDA算法求解(xi+1，yi+1)的计算公式可以概括为：
xi+1 = xi + xStep (1)
yi+1 = yi + yStep (2)
我们一般通过计算 Δx 和 Δy 来确定xStep和yStep：
如果 Δx > Δy ，说明x轴的最大差值大于y轴的最大差值，x轴方向为步进的主方向，xStep = 1，yStep = k；
如果 Δy> Δx，说明y轴的最大差值大于x轴的最大差值，y轴方向为步进的主方向，yStep = 1，xStep = 1 / k。
根据这个公式，就能通过(xi，yi)迭代计算出(xi+1、yi+1)，然后在坐标系中绘制计算出的(x,y)坐标点。
C++代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <GL/GLUT.H> #include <iostream> #include <math.h> //数值微分法 using namespace std; float xs = 0.0; float ys = 0.0; float xe = 0.0; float ye = 0.0; void LineDDA(int x0, int y0, int x1, int y1) { float x = 0.0; float y = 0.0; float m = 0.0; float dx = x1 - x0; float dy = y1 - y0; if (dx != 0) { m = dy / dx; if (m <= 1 && m >= -1) { y = y0; for (x = x0; x <= x1; x++) { glVertex2i(x, int(y + 0.5)); y += m; } } if (m>1 || m<-1) { m = 1 / m; x = x0; for (y = y0; y <= y1; y++) { glVertex2i(int(x + 0.5), y); x += m; } } } else { int x = x0; int y = 0; y = (y0 <= y1) ? y0 : y1; int d = fabs((double)(y0 - y1)); while (d >= 0) { glVertex2i(x, y); y++; d--; } } } void lineSegment() { glClear(GL_COLOR_BUFFER_BIT); glColor3f(0.0, 0.0, 0.0); glBegin(GL_POINTS); LineDDA(xs, ys, xe, ye); glEnd(); glFlush(); } int main(int argc, char *argv[]) { glutInit(&argc, argv); glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE); cout << "输入线段起始和终点坐标（范围为 0 - 500, 0-500，空格隔开四个数）:"; cin >> xs >> ys >> xe >> ye; glutInitWindowPosition(50, 100); glutInitWindowSize(500, 500); glutCreateWindow("DDA"); glClearColor(1.0, 1.0, 1.0, 1.0); glMatrixMode(GL_PROJECTION); gluOrtho2D(0.0, 500, 0.0, 500.0); glutDisplayFunc(lineSegment); glutMainLoop(); return 0; } |
效果图：
参考资料：https://blog.csdn.net/u010429424/article/details/77834046?utm_source=copy
