c++ - 使用 bresenham 线算法循环二维数组

Question

我目前正在尝试使用 bresenham 线算法绘制一些有角度的线，该算法可以循环大小为 21x21 的二维数组，作为从 0 - 2pi 倾斜的线。

lines from bresenham

所以这个想法是程序必须输出线在网格中经过的值..

以 5x5 为例

Angle:0
     _ _ _ _ _ 
    |_|_|_|_|_|
    |_|_|_|_|_|
    |_|_|.|.|.|
    |_|_|_|_|_|
    |_|_|_|_|_|

Angle: 45
     _ _ _ _ _ 
    |_|_|_|_|.|
    |_|_|_|.|_|
    |_|_|.|_|_|
    |_|_|_|_|_|
    |_|_|_|_|_|

等等..

这里的问题是它看起来不像我的程序那样做..端点位于给定的半径长度内..

我确信我搞砸了数学..所以我希望你们中的一些人能在这里帮助我..

#include <iostream>
#include <math.h>
using namespace std;
typedef std::pair<int,int> coordinate;

int sign(double x ){ return (x > 0) ? 1 : ((x < 0) ? -1 : 0); }

coordinate endpoint(double angle, int x1 , int y1, int lenght)
{
    double radians = (M_PI/180)*angle;

    double x2 = x1 + (lenght * cos(radians));
    double y2 = y1 + (lenght * sin(radians));

    return std::make_pair(round(x2),round(y2));
}

void bresenham(coordinate start, coordinate end)
{
    //restriction a.x < b.x  and 0 < H/W < 1
    int y =  start.second;
    int w = end.first - start.first;
    int h = end.second - start.second;
    int f = 2*h-w; // current error term

    for (int x = start.first; x<= end.first; x++)
    {
        cout << "mark: " << x << "," << y << endl;
        if (f < 0)
        {
            f = f + 2*h;
        }
        else
        {
            y++;
            f=f+2*(h-w);
        }
    }
}


int main(int argc, const char * argv[])
{

    coordinate start = make_pair(0,0);
    for (int i = 0; i <= 45; i++)
    {
        coordinate end = endpoint(i,0,0,10);
        cout << "    endPos: "<< "(" << end.first <<","  << end.second   <<")"    << " Angle: " << i << "       " << endl;
        cout << "--------------------------------------------" << endl;
        bresenham(start, end);
        cout << "--------------------------------------------" << endl;
    }

    return 0;
}

这是输出。

    endPos: (10,0) Angle: 0       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,0
mark: 6,0
mark: 7,0
mark: 8,0
mark: 9,0
mark: 10,0
--------------------------------------------
    endPos: (10,0) Angle: 1       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,0
mark: 6,0
mark: 7,0
mark: 8,0
mark: 9,0
mark: 10,0
--------------------------------------------
    endPos: (10,0) Angle: 2       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,0
mark: 6,0
mark: 7,0
mark: 8,0
mark: 9,0
mark: 10,0
--------------------------------------------
    endPos: (10,1) Angle: 3       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
    endPos: (10,1) Angle: 4       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
    endPos: (10,1) Angle: 5       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
    endPos: (10,1) Angle: 6       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
    endPos: (10,1) Angle: 7       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
    endPos: (10,1) Angle: 8       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,0
mark: 4,0
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,1
mark: 9,1
mark: 10,1
--------------------------------------------
    endPos: (10,2) Angle: 9       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
    endPos: (10,2) Angle: 10       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
    endPos: (10,2) Angle: 11       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
    endPos: (10,2) Angle: 12       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
    endPos: (10,2) Angle: 13       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
    endPos: (10,2) Angle: 14       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,0
mark: 3,1
mark: 4,1
mark: 5,1
mark: 6,1
mark: 7,1
mark: 8,2
mark: 9,2
mark: 10,2
--------------------------------------------
    endPos: (10,3) Angle: 15       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
    endPos: (10,3) Angle: 16       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
    endPos: (10,3) Angle: 17       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
    endPos: (10,3) Angle: 18       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,2
mark: 9,3
mark: 10,3
--------------------------------------------
    endPos: (9,3) Angle: 19       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,3
mark: 9,3
--------------------------------------------
    endPos: (9,3) Angle: 20       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,1
mark: 5,2
mark: 6,2
mark: 7,2
mark: 8,3
mark: 9,3
--------------------------------------------
    endPos: (9,4) Angle: 21       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
    endPos: (9,4) Angle: 22       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
    endPos: (9,4) Angle: 23       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
    endPos: (9,4) Angle: 24       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
    endPos: (9,4) Angle: 25       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
    endPos: (9,4) Angle: 26       
--------------------------------------------
mark: 0,0
mark: 1,0
mark: 2,1
mark: 3,1
mark: 4,2
mark: 5,2
mark: 6,3
mark: 7,3
mark: 8,4
mark: 9,4
--------------------------------------------
    endPos: (9,5) Angle: 27       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
    endPos: (9,5) Angle: 28       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
    endPos: (9,5) Angle: 29       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
    endPos: (9,5) Angle: 30       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
    endPos: (9,5) Angle: 31       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,2
mark: 5,3
mark: 6,3
mark: 7,4
mark: 8,4
mark: 9,5
--------------------------------------------
    endPos: (8,5) Angle: 32       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,3
mark: 5,3
mark: 6,4
mark: 7,4
mark: 8,5
--------------------------------------------
    endPos: (8,5) Angle: 33       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,1
mark: 3,2
mark: 4,3
mark: 5,3
mark: 6,4
mark: 7,4
mark: 8,5
--------------------------------------------
    endPos: (8,6) Angle: 34       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
    endPos: (8,6) Angle: 35       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
    endPos: (8,6) Angle: 36       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
    endPos: (8,6) Angle: 37       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
    endPos: (8,6) Angle: 38       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
    endPos: (8,6) Angle: 39       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
    endPos: (8,6) Angle: 40       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,2
mark: 4,3
mark: 5,4
mark: 6,5
mark: 7,5
mark: 8,6
--------------------------------------------
    endPos: (8,7) Angle: 41       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,4
mark: 6,5
mark: 7,6
mark: 8,7
--------------------------------------------
    endPos: (7,7) Angle: 42       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------
    endPos: (7,7) Angle: 43       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------
    endPos: (7,7) Angle: 44       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------
    endPos: (7,7) Angle: 45       
--------------------------------------------
mark: 0,0
mark: 1,1
mark: 2,2
mark: 3,3
mark: 4,4
mark: 5,5
mark: 6,6
mark: 7,7
--------------------------------------------

我做错了什么？...我知道可能必须修改 bresenham 算法以克服大于 1 和小于 0 的斜率。

--更新澄清问题--

我正在尝试使用 bresenham 线算法以循环方式迭代二维数组。

该算法应从二维阵列的中心开始，并以 0 - 2pi 之间的角度“射出”光束。光束必须从中心开始到矩阵的边缘结束，希望它更有意义..

 _ _ _ _ _ _ _ _ _ _ _ 
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|.|.|.|.|.|.|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|

 _ _ _ _ _ _ _ _ _ _ _ 
|_|_|_|_|_|_|_|_|_|.|.|
|_|_|_|_|_|_|_|_|.|_|_|
|_|_|_|_|_|_|_|.|_|_|_|
|_|_|_|_|_|_|.|_|_|_|_|
|_|_|_|_|_|.|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|

Answer 1

1. 您只有第一个八分圆的 Bresenham (dx>=0,dy>=0,dx>=dy)

   所以当你在外面使用角度时 <0,45>度将无法正常工作。你有更多的选择来解决这个问题:

   • 使用 8 个分支，每个分支都有自己的插值 ( dx>=0, dx<0 combined with dy>=0, dy<0)
   • 使用 2 个分支 ( |dx|>=|dy|, |dx|<|dy| )这里不是 x++,y++,x--,y--使用 x+=sx,y+=sy而不是sx,sy是插值前预先计算的步长方向。 (在 asm 中通常使用可自动修改的常量，但在 C/C++ 中你需要为此使用变量)

   不要忘记将具有较大绝对变化的轴用作主插值轴 所以如果(|dx|>=|dy|)主轴是x这意味着 x在每个 for 中递增(dec)通过和 y仅在 if声明...

2. 端点错误

   正如 Nico Schertler 指出的那样，端点是错误的。使用矩阵较大的一半大小作为半径，并更改 bresenham 插值以在 x 时停止。或 y超出矩阵范围...

   另一种选择是将主轴设置为矩阵的边缘(取决于八分圆)并通过 sin 计算第二个轴或 cos (是90度三角形)