沙田镇做网站,上海专业建站最低价,无货源电商怎么找货源,电子商务网站设计与管理在数学上,直线就是由无穷多个点组成的, 在计算机屏幕显示的话, 需要做一些处理,对于光栅显示器#xff0c;就是用有限多个点去逼近直线, 我们需要知道每一个像素点的坐标(都是整数)
数学上直线的方程如下 y k x b ykxb ykxb#xff0c;给定直线的起点坐标 P 0 ( x 0 , y…在数学上,直线就是由无穷多个点组成的, 在计算机屏幕显示的话, 需要做一些处理,对于光栅显示器就是用有限多个点去逼近直线, 我们需要知道每一个像素点的坐标(都是整数)
数学上直线的方程如下 y k x b ykxb ykxb给定直线的起点坐标 P 0 ( x 0 , y 0 ) P_0(x_0,y_0) P0(x0,y0)终点坐标 P 1 ( x 1 , y 1 ) P_1(x_1,y_1) P1(x1,y1)水平方向的位移 Δ x x 1 − x 0 \Delta xx_1-x_0 Δxx1−x0垂直方向的位移 Δ y y 1 − y 0 \Delta yy_1-y_0 Δyy1−y0 在直线的光栅化算法中要通过 Δ x 和 Δ y \Delta x 和 \Delta y Δx和Δy 的大小来确定绘图的主位移方向主位移方向执行 ± 1 \pm1 ±1
条件主方向 Δ x Δ y \Delta x\Delta y ΔxΔyx方向 Δ x Δ y \Delta x\Delta y ΔxΔyx方向或y方向 Δ x Δ y \Delta x\Delta y ΔxΔyy方向
DDA算法
直线的斜截式方程用微分的形式表示为 d y d x Δ y Δ x k \frac{dy}{dx}\frac{\Delta y}{\Delta x}k dxdyΔxΔyk 那么可以得到直线上的像素点 P i 1 和 P i P_{i1}和P_{i} Pi1和Pi的递推关系 { x i 1 x i Δ x y i 1 y i Δ y y i k Δ x \begin{cases} x_{i1}x_i\Delta x \\ y_{i1}y_i \Delta yy_ik\Delta x \end{cases} {xi1xiΔxyi1yiΔyyikΔx 以斜率 0 ≤ k 1 0\leq k 1 0≤k1为例有 Δ x Δ y \Delta x\Delta y ΔxΔy ,主方向是x那么上面的式子就变成了 { x i 1 x i 1 y i 1 y i k \begin{cases} x_{i1}x_i1 \\ y_{i1}y_i k \end{cases} {xi1xi1yi1yik 设点 E ( x i 1 , y i k ) E(x_i1,y_ik) E(xi1,yik)是理想直线和线 x i 1 x i 1 的交点 x_{i1}x_i1的交点 xi1xi1的交点那么用来逼近这个点的可能的像素点有两个 D ( x i 1 , y i 1 ) 和 C ( x i 1 , y i ) D(x_i1,yi1)和C(x_i1,y_i) D(xi1,yi1)和C(xi1,yi)具体选择那个就根据k的值确定( y i k y_i k yik四舍五入 y i 1 i n t ( y_{i1}int( yi1int(y_ik0.5 ) ) ))
下面给出DDA算法画任意斜率直线的主要代码
void CLine::DrawLine(CDC* pDC)
{int dx m_p2.x - m_p1.x;//m_p1,m_p2(CPoint)int dy m_p2.y - m_p1.y;double k (double)(dy) / (double)(dx); //斜率//确定主方向int e abs(k) 1 ? abs(dy) : abs(dx);double xadd (double)(dx) / (double)(e);double yadd (double)(dy) / (double)(e);double x (double)(m_p1.x);double y (double)(m_p1.y);for (int i 0; i e; i) {pDC-SetPixel((int)(x 0.5), (int)(y 0.5), RGB(0, 0, 0));x xadd;y yadd;}
}Bresenham算法 Bresenham算法在主位移方向上也是移动一个单位另一个方向移动0还是1取决于像素点和理想直线的距离d 还是以斜率 0 ≤ k 1 0\le k 1 0≤k1为例x方向是主位移方向点 Q ( x i 1 , y i 1 ) Q(x_{i1},y_{i1}) Q(xi1,yi1)是理想直线和 x i 1 x i 1 x_{i1}x_i1 xi1xi1的交点两个可能的像素的 P u p ( x i , y i 1 ) 和 P d o w n ( x i , y i ) P_{up}(x_i,y_i1) 和P_{down}(x_i,y_i) Pup(xi,yi1)和Pdown(xi,yi),选那一个就取决于Q点和 P d o w n P_{down} Pdown的距离 d i 1 d_{i1} di1,对于误差项d的计算向x方向递增1个单位就有 d i 1 d i k d_{i1}d_ik di1dik如果向y方向递增一个单位就还要减1。 d 0 0 y i 1 { y i 1 , d i 1 ≥ 0.5 y i , d i 1 0.5 d_00 \\ \\ y_{i1}\begin{cases} y_{i}1 ,d_{i1}\geq 0.5\\ y_i,d_{i1}0.5 \end{cases} d00yi1{yi1,di1≥0.5yi,di10.5 不过通常不是用误差项d进行计算取一个变量e, e 0 − Δ x e_0-\Delta x e0−Δx,沿x方向每递增一个单位就有 e i 1 e i 2 Δ y e_{i1}e_i2\Delta y ei1ei2Δy,当 e i 1 ≥ 0 e_{i1}\geq 0 ei1≥0时下一个像素点就是( x i 1 , y i 1 x_i1,y_i1 xi1,yi1),并且要更新 e i 1 e i 1 − 2 Δ x e_{i1}e_{i1}-2\Delta x ei1ei1−2Δx;否则下一个像素点就是( x i 1 , y i x_i1,y_i xi1,yi)。
原始的Bresenham只能画指向第一象限并且斜率小于1的直线但实际有这么多种情况但是别慌可以利用直线的对称性解决。
对于相同象限, 斜率不同的情况, 其实就是将斜率在0到1之间的线作关于函数y x 对称而得到。对应到代码中就是将所有的y和所有的x调换位置。比如, e 0 − Δ y e_0-\Delta y e0−Δy e i 1 e i 2 Δ x e_{i1}e_i2\Delta x ei1ei2Δx,当 e i 1 ≥ 0 e_{i1}\geq 0 ei1≥0时下一个像素点就是( x i 1 , y i 1 x_i1,y_i1 xi1,yi1),并且要更新 e i 1 e i 1 − 2 Δ y e_{i1}e_{i1}-2\Delta y ei1ei1−2Δy;否则下一个像素点就是( x i 1 , y i x_i1,y_i xi1,yi)。 下面给出通用的Bresenham算法
void CLine::DrawLine(CDC* pDC)
{int dx abs(m_p2.x - m_p1.x);//m_p1,m_p2(CPoint)int dy abs(m_p2.y - m_p1.y);double k (double)(dy) / (double)(dx); //斜率BOOL wayChange FALSE;//主方向是否发生改变默认是x方向int e,mainway,subway;e -dx;mainway dx;subway dy;int addx, addy;addx (m_p2.x m_p1.x) ? 1 : ((m_p2.x m_p1.x) ? -1 : 0);addy (m_p2.y m_p1.y) ? 1 : ((m_p2.y m_p1.y) ? -1 : 0);if (dy dx) {//主方向是ymainway dy;subway dx;wayChange TRUE;}CPoint p m_p1;for (int i 0; i mainway; i) {pDC-SetPixel(p, RGB(0, 255, 0));if (wayChange)p.y addy;elsep.x addx;e 2 * subway;if (e 0) {if (wayChange)p.x addx;elsep.y addy;e - 2 * mainway;}}
}
