bresenham算法计算坐标(bresenman算法)

Bresenham直线演算法的演算方法

Bresenham直线算法描绘的直线。假设我们需要由 (x0, y0) 这一点，绘画一直线至右下角的另一点(x1, y1)，x,y分别代表其水平及垂直坐标，并且 x1 - x0 > y1 - y0。在此我们使用电脑系统常用的坐标系，即x坐标值沿x轴向右增长，y坐标值沿y轴向下增长。

bresenham算法计算坐标(bresenman算法)

dda法生成直线的基本原理是什么?为什么说Bersenham画圆的算法效率较高?

DDA算法主要是根据直线公式y = kx + b来推导出来的，其关键之处在于如何设定单位步进，即一个方向的步进为单位步进，另一个方向的步进必然是小于1。算法的具体思路如下：

1. 输入直线的起点、终点；

2. 计算x方向的间距：△X和y方向的间距：△Y。

3. 确定单位步进，取MaxSteps = max（△X，△Y）; 若△X>=△Y，则X方向的步进为单位步进，X方向步进一个单位，Y方向步进△Y/MaxSteps;否则相反。

4. 设置第一个点的像素值

5. 令循环初始值为1，循环次数为MaxSteps，定义变量x,y，执行以下计算：

a. x增加一个单位步进，y增加一个单位步进

b. 设置位置为（x,y）的像素值

Bresenham算法是DDA算法画线算法的一种改进算法。本质上它也是采取了步进的思想。不过它比DDA算法作了优化，避免了步进时浮点数运算，同时为选取符合直线方程的点提供了一个好思路。首先通过直线的斜率确定了在x方向进行单位步进还是y方向进行单位步进：当斜率k的|k|<1时，在x方向进行单位步进；当斜率k的|k|>1时，在y方向进行单位步进。

1. 输入线段的起点和终点。

2. 判断线段的斜率是否存在（即起点和终点的x坐标是否相同），若相同，即斜率不存在，

只需计算y方向的单位步进（△Y+1次），x方向的坐标保持不变即可绘制直线。

3. 计算线段的斜率k，分为下面几种情况处理

a. k等于0，即线段平行于x轴，即程序只需计算x方向的单位步进，y方向的值不变

b. |k|等于1，即线段的x方向的单位步进和y方向的单位步进一样，皆为1。直接循环△X次计算x和y坐标。

4. 根据输入的起点和终点的x、y坐标值的大小决定x方向和y方向的单位步进是1还是-1

6. 画出第一个点。

7. 若|k| <1，设m =0,计算P0，如果Pm>0，下一个要绘制的点为（Xm+单位步进，Ym），

Pm+1 = Pm -2△Y;

否则要绘制的点为（Xm+单位步进，Ym+单位步进）

Pm+1 = Pm+2△X-2△Y；

8. 重复执行第七步△X-1次；

9. 若|k| <1，设m =0,计算Q0，如果Qm>0，下一个要绘制的点为（Xm，Ym+单位步进），

Pm+1 = Pm -2△X;

否则要绘制的点为（Xm+单位步进，Ym+单位步进）

Pm+1 = Pm+2△Y-2△X；

10. 重复执行第9步△Y-1次；

关于Bresenham算法的求助

void Bresenham_Line(x0, y0, x1, y1, color)

int x0, y0, x1, y1, color;

{ int x, y, dx, dy;

float k, e;

dx=x1-x0; dy=y1-y0;

k=dy/dx; e=-0.5;

x=x0; y=y0;

for(i=0; i<=dx; i++)

{ putpixel(x, y, color);

x=x+1; e=e+k;

if(e>=0)

{ y=y+1; e=e-1;

} }}

算法原理：过各行、 各列像素中心构造一组虚拟网格线, 按直线从起点到终点的顺序计算直线与各垂直网格线的交点, 然后确定该列像素中与该交点近的像素

ja 已经圆心坐标（x0,y0）及圆上一点坐标(x1,y1)，及圆半径（r），求圆上任意一点的坐标，求高手解答急

Bresenham算法画圆，可以参考下

public void drawCircle(int x, int y, int d, Color frameColor){

int xc = x + d / 2;

int yc = y + d / 2;

int r = d / 2;

int dx = r;

int dy = 0;

int xChange = 1 - 2 r;

int yChange = 1;

int radiusError = 0;

while( dx >= dy){

plot8CirclePoints(xc, yc, dx, dy, frameColor);

dy++;

radiusError += yChange;

yChange += 2;

if(2 radiusError + xChange > 0){

dx--;

radiusError += xChange;

xChange += 2;

}}

}private void plot8CirclePoints(int x, int y, int dx, int dy, Color color){

graph.setArrayData(x + dx, y + dy, color);

graph.setArrayData(x - dx, y + dy, color);

graph.setArrayData(x - dx, y - dy, color);

graph.setArrayData(x + dx, y - dy, color);

graph.setArrayData(x + dy, y + dx, color);

graph.setArrayData(x - dy, y + dx, color);

graph.setArrayData(x - dy, y - dx, color);

graph.setArrayData(x + dy, y - dx, color);

}

使用整数Bresenham算法光栅化直线起点P0(2,1)到终点P1(14,10)。1)主位移方向？

在使用整数Bresenham算法光栅化直线之前，我们需要确定主位移方向。这是指在每个步骤中哪个方向上的像素会被涂色或改变状态。

对于起点P0(2,1)到终点P1(14,10)，我们可以通过将两个点的坐标相减并取来得出线段的斜率。即：$|m| = \frac{|y_1-y_0|}{|x_1 - x_0|} = \frac{|10-1|}{|14-2|} = \frac{9}{12} = \frac{3}{4}$

由于斜率小于1，则主要位移方向为水平方向（即x轴方向），而次要位移方向为竖直方向（即y轴方向）。因此，在每个步骤中，x值将增加1，而y值将根据Bresenham算法的规则增加或不变。

现在可以开始使用整数Bresenham算法光栅化直线从起点P0(2,1)到终点P1(14,10)。具体步骤如下：

1. 计算Δx和Δy

$\Delta x = x_1 - x_0 = 14 - 2 = 12$

$\Delta y = y_1 - y_0 = 10 - 1 = 9$

2. 计算初始决策参数d

$d_{ini} = 2\Delta y - \Delta x = 2(9) - 12 = 6$

3. 在起点P0(2,1)处绘制像素，即(x,y)=(2,1)

4. 接下来，根据Bresenham算法的规则，在主位移方向上逐步增加x值，同时在次要位移方向上根据决策参数d的值决定是否增加y值。

5. 对于每个新的像素位置，根据该像素是否涂色或改变状态来确定决策参数d的更新规则。

6. 重复步骤4和步骤5直到达到终点P1(14,10)。

下面是按照以上步骤为P0(2,1)到P1(14,10)计算出的结果（每个步骤中应该绘制的像素位置）：

Step 1: (x,y)=(2,1)

Step 2: (x,y)=(3,1), d=12

Step 3: (x,y)=(4,2), d=18

Step 4: (x,y)=(5,3), d=10

Step 5: (x,y)=(6,4), d=14

Step 6: (x,y)=(7,5), d=6

Step 7: (x,y)=(8,6), d=-2

Step 8: (x,y)=(9,7), d=-8

Step 9: (x,y)=(10,8), d=-12

Step 10: (x,y)=(11,9), d=-14

Step 11: (x,y)=(12,10), d=-14

Step 12: (x,y)=(13,10), d=-18

Step 13: (x,y)=(14,10)

因此，从起点P0(2,1)到终点P1(14,10)的整数Bresenham算法光栅化直线的像素位置为：(2,1), (3,1), (4,2), (5,3), (6,4), (7,5), (8,6), (9,7), (10,8), (11,9), (12,10), (13,10)和(14,10)。