理解：给定两个点，画出两个点的连线经过的栅格。
求解思路：
1.
bresenham贝汉明算法_Bimme军的博客-CSDN博客
2.
若干计算机图形学算法实现_JulyThirteenth的博客-CSDN博客
// grid traversal
void gridTraversal(const dPoint &start, const dPoint &goal, const double resolution, std::vector<iPoint> &visited_grid)
`{`
`iPoint s_grid = {static_cast<int>(std::floor(start.x / resolution)), static_cast<int>(std::floor(start.y / resolution))};`
`iPoint g_grid = {static_cast<int>(std::floor(goal.x / resolution)), static_cast<int>(std::floor(goal.y / resolution))};`
`dPoint vector = {goal.x - start.x, goal.y - start.y};`
`double stepX = (vector.x > 0) ? 1 : -1;`
`double stepY = (vector.y > 0) ? 1 : -1;`
`double next_grid_boundary_x = (s_grid.x + stepX) * resolution;`
`double next_grid_boundary_y = (s_grid.y + stepY) * resolution;`
`double tMaxX = (vector.x != 0) ? (next_grid_boundary_x - start.x) / vector.x : DBL_MAX;`
`double tMaxY = (vector.y != 0) ? (next_grid_boundary_y - start.y) / vector.y : DBL_MAX;`
`double tDeltaX = (vector.x != 0) ? resolution / vector.x * stepX : DBL_MAX;`
`double tDeltaY = (vector.y != 0) ? resolution / vector.y * stepY : DBL_MAX;`
`iPoint diff = {0, 0};`
`iPoint c_grid = {s_grid.x, s_grid.y};`
`visited_grid.push_back(c_grid);`
`bool negative = false;`
`if (s_grid.x != g_grid.x && vector.x < 0)`
`{`
`diff.x--, negative = true;`
`}`
`if (s_grid.y != g_grid.y && vector.y < 0)`
`{`
`diff.y--, negative = true;`
`}`
`if (negative)`
`{`
`c_grid.x += diff.x;`
`c_grid.y += diff.y;`
`visited_grid.push_back(c_grid);`
`}`
`double tx = tMaxX;`
`double ty = tMaxY;`
`while (!(c_grid == g_grid))`
`{`
`if (tx < ty)`
`{`
`c_grid.x += stepX;`
`tx += tDeltaX;`
`}`
`else`
`{`
`c_grid.y += stepY;`
`ty += tDeltaY;`
`}`
`visited_grid.push_back(c_grid);`
`}`
`}`算法理解
我们首先找到当前栅格的下一个 x 和 y 方向的栅格 1 和 2 ；
计算下 1 和 2 距离开始节点的 x 向 和 y 向的距离 xd 和 yd 占起止点之间在 x y 向的距离的百分比 x% y%;
假如 x% < y% 那么下一个栅格就是 当前节点的 x 加 1 或者 -1 ；
注意更新 x% , 也就是 x% 变为了 新的当前节点到开始节点 x 向的距离占起止节点之间 x 向的距离的百分比了。
TARE 里面有类似的实现代码
int 栅格作为输入的代码：
//!bresenham 算法
//!https://www.guyuehome.com/41384
#include <iostream>
#include <stdio.h>
#include<string.h>
#define H 16 //触摸框宽度
#define W 16
using namespace std;
unsigned short Array[H][W];
void Bresenham(unsigned short x1, unsigned short y1, unsigned short x2, unsigned short y2, unsigned short(*array)[W]){
int dx = abs(x2 - x1);
int dy = abs(y2 - y1);
bool is_great_than_45_degree = false;
if (dx <= dy)
{
// 大于45度
// Y 方向上变化速率快于 X 方向上变化速率，选择在 Y 方向上迭代，在每次迭代中计算 X 轴上变化；
is_great_than_45_degree = true;
}
int fx = (x2 - x1) > 0 ? 1 : -1;
int fy = (y2 - y1) > 0 ? 1 : -1;
if (dy == 0)//0°
fy = 0;
if (dx == 0)//90°
fx = 0;
int ix = x1;
int iy = y1;
int p1 = 2 * dy - dx; //小于等于45°
int p2 = 2 * dx - dy; //大于45°
if (is_great_than_45_degree){
while (iy != y2){
//Array[num - iy - 1][ix] = 0;
*(*(array + (H- iy - 1)) + ix) = 1;
//p2>0
if (p2 > 0){
p2 += 2 * (dx - dy);
ix += fx;
}
else{
p2 += 2*dx;
}
iy += fy;
//Array[num - iy - 1][ix] = 0;
*(*(array + (H - iy - 1)) + ix) = 1;
}
}
else{
while (ix != x2){
//Array[num - iy - 1][ix] = 0;
*(*(array + (H - iy - 1)) + ix) = 1;
//p1>0
if (p1 > 0){
p1 += 2 * (dy - dx);
iy += fy;
}
else{
p1 += 2 * dy;
}
ix += fx;
//Array[num - iy - 1][ix] = 0;
*(*(array + (H - iy - 1)) + ix) = 1;
}
}
}
int main(){
memset(Array, 0, H*W);
unsigned short (*arr)[W] = Array;
Bresenham(2, 7, 5, 1, arr);
for (int i = 0; i < H; ++i){
for (int j = 0; j < W; ++j){
cout << int(Array[i][j]) << " ";
}
cout << endl;
}
system("pause");
return 0;
}//!文章来源：https://www.toymoban.com/news/detail-692983.html
https://www.guyuehome.com/41384 代码
//!
https://zhuanlan.zhihu.com/p/493330783 公式推导文章来源地址https://www.toymoban.com/news/detail-692983.html
到了这里，关于Bresenham 贝汉明算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
