Bresenham直线算法_星海水滴的博客-程序员宅基地

技术标签：算法

基本原理

以0<斜率k<1的斜线为例，红点为判定为依据点，绿点是应绘制的像素点，直线在红点下方则y坐标不增，反之y坐标自增1。
在这里插入图片描述

一、算法1思路

根据两点坐标算出斜率k=dy/dx（通常为浮点数）
斜线与x=x1的交点y坐标y=x1+k ->往后自增k
y0、y1中点y坐标 middle=x1+0.5 ->往后根据两者位置增1或不变
判别式：y>=middle
参考代码：

void OLED_ShowLine(u8 x1,u8 y1,u8 x2,u8 y2)
{
    	
	u8 dx = x2 - x1;
	u8 dy = y2 - y1;
	float k = (float)(dy) / dx;
	u8 x = x1 + 1;		    //直线与x=x1的交点的x坐标
	float y = k;	        //直线与x=x1的交点的y坐标,由于在判别式中y1相消，可以去掉y1
	float middle = 0.5;     //第一个中点，由于在判别式中y1相消，可以去掉y1
	
	OLED_DrawPoint(x1,y1,1);//画起点
	OLED_DrawPoint(x2,y2,1);//画终点
	
	while( x < x2 )			//中间线段
	{
    
		if(y >= middle)		//若直线点在中点或之上
		{
    
			y1++;
			middle++;
		}
		OLED_DrawPoint(x,y1,1);//画点
		x++;
		y += k;
	}
}

缺点：存在浮点运算，应用方面较局限，对起止点及其他们的斜率有要求

二、算法2思路

针对算法1解决浮点数问题，改用整数运算，方法：同比例放大法
针对判别式修改：k>0.5，即dy/dx>0.5，两边乘以2倍dx，得2dy>dx
此时斜线与x=x1的交点y坐标y=2dy ->往后自增2dy
y0、y1中点y坐标 middle=dx ->往后根据两者位置增2dx或不变
参考代码：

void OLED_ShowLine(u8 x1,u8 y1,u8 x2,u8 y2)
{
    	
	u8 dx = x2 - x1;
	u8 dy = y2 - y1;
	u8 x = x1 + 1;		    //直线与x=x1的交点的x坐标
	u16 y = (dy<<1);	        //直线与x=x1的交点的y坐标,由于在判别式中y1相消，可以去掉y1
	u16 middle = dx;     //第一个中点，由于在判别式中y1相消，可以去掉y1
	
	OLED_DrawPoint(x1,y1,1);//画起点
	OLED_DrawPoint(x2,y2,1);//画终点
	
	//y=dy/dx + dy/dx  >=  middle=0.5 + 1
	
	while( x < x2 )			//中间线段
	{
    
		if(y >= middle)		//若直线点在中点或之上
		{
    
			y1++;
			middle+=(dx<<1);
		}
		OLED_DrawPoint(x,y1,1);//画点
		x++;
		y += (dy<<1);
	}
}

三、算法3思路

针对算法2解决斜率和其他象限不可用问题
引入坐标轴变换，保证dx为最长轴，交换后标记
引入sign_x及sign_y标记符，当起始点大于终点则signe_x或sign_y为-1
参考代码：

void OLED_ShowLine(u8 x1,u8 y1,u8 x2,u8 y2)
{
    	
	u8 i=0,temp=0;
	u8 interChange = 0;
	u8 dx=0,dy=0;
	int sign_x=0,sign_y=0;	
	u8 x = 0;		   
	u16 y = 0;	       
	u16 middle = 0;    
	
	//取绝对值，并标记
	x2-x1>=0?(dx=x2-x1,sign_x=1):(dx=x1-x2,sign_x=-1);
	y2-y1>=0?(dy=y2-y1,sign_y=1):(dy=y1-y2,sign_y=-1);
	
	if(dx<dy)				//交换坐标轴,保证dx为长轴
	{
    
		temp = dx;
		dx = dy;
		dy = temp;
		interChange = 1;	//标记
	}
	
	x = x1;            		//直线与x=x1的交点的x坐标
	y = (dy<<1);       		//直线与x=x1的交点的y坐标,由于在判别式中y1相消，可以去掉y1
	middle = dx;       		//第一个中点，由于在判别式中y1相消，可以去掉y1
	
	OLED_DrawPoint(x1,y1,1);//画起点
	OLED_DrawPoint(x2,y2,1);//画终点
	
	
	for(i=0;i<(dx-1);i++)	//中间线段
	{
    
		
		if(interChange==0)
		{
    
			x+=sign_x;
		}else{
    
			y1+=sign_y;
		}

		if(y > middle)		//若直线点在中点或之上
		{
    
			if(interChange==0)
				y1+=sign_y;
			else
				x+=sign_x;
			middle+=(dx<<1);
		}
		
		OLED_DrawPoint(x,y1,1);//画点
		
		y += (dy<<1);
	}
}

参考视频链接https://www.bilibili.com/video/BV1eE411p7tn?t=3233

本文链接：https://blog.csdn.net/qq_44370363/article/details/106382341

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【bzoj2938】[Poi2000]病毒 AC自动机-程序员宅基地

Description二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。示例：例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病

Java 集合深入理解（九）：优先队列（PriorityQueue）之源码解读，及最小顶堆实现研究_priorityqueue lessthan_踩踩踩从踩的博客-程序员宅基地

前言queue :一个队列就是一个先入先出（FIFO）的数据结构Queue接口也是继承自AbstractCollection 标志者，实现queue接口的，它也是一个集合，并在集合基础增加一些队列自带的方法PriorityQueue 就是队列queue的一种实现，PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。这种实现：它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。而对于什么是优先级最高的_priorityqueue lessthan

C++11 新特性总结_-std=c++11-程序员宅基地

【0】g++/gcc 支持c++11/c11标准{(0)为了让g++能够支持和编译c++11新特性代码，需在编译时候加上指定条件：-std=c++11g++ newFeature.cpp -o app -std=c++11(1)使用-std=c11来让gcc支持c11新特性gcc 文件名.c -o 可执行文件名 -std=c11}【1】静态断言（static_assert）: #include <assert.h>{(1)断言概念所谓“断..._-std=c++11

js逆向-新榜资讯-程序员宅基地

需要用到的模块：···requests···execjs···csv**1，我们要获取的数据是，标题，简介，来源，时间，**对于右边的抖音资讯要用的加密参数是一样的只需要改一下链接就行，这里就不说它了。**2 ，找到数据来源**数据我们已经找到，接下来查看请求参数，有哪些是固定值，那些是变化的keyword：是你搜索的关键字，如果不进行搜索，就是空pageNumber：页数pageSize：一页的数据量nonce：变化的（需要破解的参数）xyz：变化的（需要破解的

Python学习之路10—认识字符串_爱偷懒的小贼猫的博客-程序员宅基地

一、字符串的定义字符串是最常用的数据类型，一般使用引号来创建。我们可以先来一个例子来看看，以前学习过通过使用type来检测代码的数据类型，可见“hello world”是“str”类型，即字符串类型。a = 'hello world'print(a)print(type(a))输出的是：hello world<class 'str'>二、关于字符串的写法，有三种：单引号，双引号，三引号。如下所示，三种都是字符串的写法。a = 'hello my name is Ca

InfluxDB在Win10安装与简单入门_influx cli windows-程序员宅基地

文前瞎扯InfluxDB是一个由InfluxData开发的开源时序型数据库[note 1]。它由Go写成，着力于高性能地查询与存储时序型数据。InfluxDB被广泛应用于存储系统的监控数据，IoT行业的实时数据等场景。引用来自维基百科 - InfluxDB刚接触InfluxDB一段时间，感叹到了作为一个时序数据库的特性，简单易用。虽接触不久，但却勾起了我的强烈兴趣，是一个值得深入研究的数..._influx cli windows