你知道一條簡單的直線是怎么顯示在計算機屏幕上嗎肤寝？有人說育苟，就是一個個像素點啊筹裕，將一個個像素點連起來就顯示為一條直線了醋闭。但是這些點是如何排布的呢？通過什么樣的算法展示給坐在電腦前面的你呢朝卒？讓我們一起來研究一下证逻。
有能力的同志可以先參考：維基百科-Bresenham's line algorithm，看不懂沒關(guān)系抗斤，兩行哥帶你一步一步分析囚企。
一、計算機是如何顯示直線的
在屏幕上我們看到了一條直線瑞眼，但是它真的是一條直線嗎龙宏？我們用最簡單的方法驗證一下：
打開Windows的畫圖，畫一條直線伤疙，看到了什么银酗？讓我們看看圖1。
貌似是一條直線掩浙，但是我們放大后看看花吟，看到了什么秸歧？如圖2所示厨姚，這并不是一條直線，而是一條條較短的水平線键菱，近似地拼接成一條直線谬墙。
為什么會出現(xiàn)上面的現(xiàn)象？讓我們再次放大這條直線经备，如圖3所示：
圖中的黑色直線是我們理想中要顯示的目標直線（實際上并沒有被繪制出來）拭抬。但是在柵格圖像中（即位圖，比如我們的計算機顯示屏）侵蒙，像素點是一個個分割的小型區(qū)域（如圖中的方格）造虎，如果想要表示一條直線，只能通過一定的算法纷闺，確定要顯示的目標區(qū)域（如圖中的標記為灰色的方格）算凿，這些目標區(qū)域就組成了一條近似直線的圖像，展示給用戶犁功，這就是我們真正看到的直線氓轰。
顯然，如果我們確定了直線的起始點startPoint和結(jié)束點endPoint浸卦，我們還需要一定的算法來確定這兩點中間還有哪些方格需要顯示（變成灰色）署鸡，哪些方格不需要顯示（依舊為白色），然后再繪制一條“類直線”，接下來靴庆，我們就來建立數(shù)學模型时捌，看看這個算法是怎么實現(xiàn)的。
二撒穷、基本Bresenham直線算法
Bresenham直線算法是用來描繪由兩點所決定的直線的算法匣椰，它會算出一條線段在n維光柵上最接近的點。這個算法只會用到較為快速的整數(shù)加法端礼、減法和位元移位禽笑，常用于繪制電腦畫面中的直線。是計算機圖形學中最先發(fā)展出來的算法蛤奥。
這里就引入我們計算機圖形學中Bresenham算法佳镜，讓我們以上圖3為基礎(chǔ)，從建立坐標系開始凡桥，一點一點進行推演蟀伸。
如圖4所示，我們建立了左上角為原點的坐標系（通常計算機圖形學中的原點位于左上角）缅刽，x軸正方向向右啊掏，y軸正方向向下。以每個小方格（柵格）的中心（如圖4中柵格中的紅色點）作為標準點衰猛，以每個柵格的邊長為坐標軸單位長度迟蜜，即每個柵格的邊長計為1。
觀察上述建立的坐標系啡省，原點為左上角第一個柵格的中心娜睛。假設(shè)目標直線的起始點坐標為圖中的（x1，y1)卦睹，終點為圖中的（x2畦戒，y2），并且斜率介于0與1之間结序，即與x軸正方向的夾角小于45°（圖中用深黑色直線表示）障斋，那么如何確定出與這條直線擬合度最大的柵格呢（圖中的灰色方塊們）？
觀察圖中的相鄰柵格B1（x3徐鹤，y3）以及柵格B2（x4垃环，y4），兩者滿足x3=x4且y4-y3=1凳干。在Y軸方向上晴裹，柵格B1與目標直線的偏差為d1，柵格B2與目標直線的偏差為d2救赐。比較d1與d2的大小涧团，若d1<=d2只磷，則認為距離目標直線最近的柵格為B1，若d1>d2泌绣，則認為距離目標直線最近的柵格為B2钮追。
在目標直線穿過的所有柵格中，取目標直線在X軸方向的投影阿迈，對于投影區(qū)間[x1元媚，x2]中的每個x的值，在Y軸方向上都有一個或多個柵格與之對應(yīng)苗沧。如果僅有一個柵格與之對應(yīng)刊棕，顯示該柵格（圖中即標灰色），如果有多個柵格與之對應(yīng)待逞，取距離目標直線最近的柵格顯示（標記為灰色）甥角。
還以上文的相鄰柵格B1（x3，y3）與柵格B2（x4识樱，y4）為例嗤无，B1、B2都被目標直線穿過怜庸，并且它們擁有同樣的X軸坐標（兩者滿足x3=x4且y4-y3=1）当犯。此時對于目標直線在X軸方向上的投影區(qū)間[x1，x2]中的x3值而言割疾，有兩個不同y值的柵格B1（x3嚎卫，y3）和B2（x4，y4）與之對應(yīng)杈曲。我們?nèi)【嚯x目標直線較近的柵格來顯示驰凛。上文我們已經(jīng)假設(shè)過胸懈，每個柵格的邊長為1（坐標軸單位長度為1）担扑，在Y軸方向上，如果柵格（x趣钱，y）中心與目標直線的偏差d<=1/2涌献，即顯示該柵格，如果柵格中心與目標直線的偏差d>1/2首有，即顯示Y軸方向的下一個柵格燕垃，即柵格（x，y+1）井联，此柵格的中心與目標直線在Y軸方向上的偏差為d - 1卜壕。而對于目標直線在X軸方向上的投影區(qū)間[x1，x2]中的x1值只有一個y值為y1的柵格（x1烙常，y1）與之對應(yīng)轴捎，直接顯示該柵格即可。
弄清楚原理之后，可以開始我們的推演了侦副。在圖4的坐標系中侦锯，目標直線對應(yīng)的代數(shù)表達式為：
y = （ y2 - y1 ） / （ x2 - x1 ） * （ x - x1 ） + y1
下面我們用偽代碼來繪制這些最擬合目標直線的柵格們。
假定drawPoint（x秦驯，y）為繪制該柵格的方法尺碰，drawLine（startX，startY译隘，endX亲桥，endY）為繪制直線的方法。
//startX：直線的起點坐標x
//startY：直線的起點坐標y
//endX：直線的終點坐標x
//endY：直線的終點坐標y
function drawLine(startX固耘，startY两曼，endX，endY){
int diffX = endX - startX;
int diffY = endY - startY;
float error = 0F;//記錄柵格中心與目標直線在Y軸方向上的偏差值玻驻，如果error > 0表示直線在該柵格中心的下方悼凑，如果error < 0，表示直線在該柵格中心的上方
int y = startY;
for( x = startX ; x <= endX ; x++){
draw( x , y );
error = error + diffY / diffX;
if( error > 0.5F ){
//如果在Y軸方向上璧瞬，該柵格中心與目標直線的偏差大于0.5F户辫，就使用Y軸方向上的下一個柵格，即y = y + 1
y = y + 1;
//因為使用了Y軸方向上的下一個柵格嗤锉，所以需要重新計算柵格中心與目標直線的偏差值
error = error - 1.0F;
}
}
}
三渔欢、Bresenham直線算法擴展
上面我們假設(shè)目標直線是斜率介于0與1之間，并且由左上至右下的直線瘟忱，現(xiàn)對其進行擴展奥额。
1.對于從右下到左上（繪制直線的方向與之前相反）：
此時判斷是否startX大于endX，如果是访诱，將目標直線的起始點和終點進行交換即可垫挨；
2.對于負斜率（介于-1與0之間）：
此時目標直線的startX > endX，我們把偏差大于0.5F時y = y + 1改為y = y - 1即可触菜；
3.對于斜率絕對值大于1：
我們不直接使用斜率大于1的目標直線九榔，而是使用目標直線關(guān)于y = x對稱的直線，此直線的斜率小于1涡相。此時我們將計算過程中的x與y調(diào)換哲泊，同時將drawPoint（）方法的參數(shù)調(diào)換。
新增定義取value絕對值的方法abs（value）催蝗，交換兩個變量值的方法swap（ a 切威，b），此時的偽代碼如下：
//startX：直線的起點坐標x
//startY：直線的起點坐標y
//endX：直線的終點坐標x
//endY：直線的終點坐標y
function drawLine(startX丙号，startY先朦，endX且预，endY){
boolean needExchange = abs（endY - startY） > abs（endX - startX）
if( needExchange ){//交換x與y
swap( x1 , y1 );
swap( x2 , y2 );
}
if( x1 > x2 ){//交換開始點與結(jié)束點
swap( x1 , x2 );
swap( y1 , y2);
}
int diffX = endX - startX;
int diffY = abs( endY - startY );
float error = 0F;
int y = startY;
for( x = startX ; x <= endX ; x++){
if( needExchange ){
draw( y , x );
}else{
draw( x , y );
}
error = error + diffY / diffX;
if( error > 0.5F ){
if( y1 <= y2 ){
y = y + 1;
}else{
y = y - 1;
}
error = error - 1.0F;
}
}
}
至此，已經(jīng)實現(xiàn)了完整的Bresenham直線算法烙无。
四锋谐、Bresenham直線算法整數(shù)化
電腦處理浮點運算的速度比較慢，而error的計算是浮點運算截酷。此外涮拗，error的值經(jīng)過多次浮點數(shù)加法之后，可能有累積誤差（計算機中浮點運算是不精確的）迂苛。使用整數(shù)運算可令算法更快三热、更準確。只要將以上所有的分數(shù)數(shù)值乘以diffX三幻，我們就可以用整數(shù)來表示它們就漾。唯一的問題是程序中的常數(shù)0.5F—我們可以通過改變error的初始方法，以及將error的計算由遞增改為遞減來解決念搬。整數(shù)化后的邏輯如下：
//startX：直線的起點坐標x
//startY：直線的起點坐標y
//endX：直線的終點坐標x
//endY：直線的終點坐標y
function drawLine(startX抑堡，startY，endX朗徊，endY){
boolean needExchange = abs（endY - startY） > abs（endX - startX）
if( needExchange ){//交換x與y
swap( x1 , y1 );
swap( x2 , y2 );
}
if( x1 > x2 ){//交換開始點與結(jié)束點
swap( x1 , x2 );
swap( y1 , y2);
}
int diffX = endX - startX;
int diffY = abs( endY - startY );
float error = diffX / 2;
int y = startY;
for( x = startX ; x <= endX ; x++){
if( needExchange ){
draw( y , x );
}else{
draw( x , y );
}
error = error - diffY;
if( error < 0 ){
if( y1 <= y2 ){
y = y + 1;
}else{
y = y - 1;
}
error = error + diffX;
}
}
}
有個疑問首妖，為什么error的初始值取為diffX / 2呢？其實我們先將error由遞增改為了遞減爷恳，error取值0.5F有缆，如果error遞減后的值小于0，則對y進行相應(yīng)操作温亲。而我們的目的是將0.5F化為整數(shù)棚壁，因此將error乘以diffX，即error = diffX / 2栈虚。
至此袖外，我們的Bresenham直線算法已經(jīng)講解完畢，這與我們OpenCV中的LineType參數(shù)有很大的關(guān)聯(lián)节芥。
五在刺、LineType參數(shù)詳解
OpenCV中LineType有三種類型：
LINE_AA = 16
LINE_8 = 8
LINE_4 = 4
先講LINE_4和LINE_8逆害。LINE_4和LINE_8表示繪制的直線為4連通直線或8連通直線头镊。要理解4連通直線或8連通直線，我們先引入鄰域概念魄幕，若存在柵格點P（x相艇，y）：
1.四領(lǐng)域
如圖5，像素P(x纯陨，y)的四鄰域是：（x+1坛芽，y）留储、（x-1，y）咙轩、（x获讳，y+1）、（x活喊，y-1）丐膝，即圖中的4個黃色柵格。
2.對角鄰域
如圖6钾菊，像素P（x帅矗，y）的對角鄰域是：（x+1，y+1）煞烫；（x+1浑此，y-1）；（x-1滞详，y+1）凛俱；（x-1，y-1）料饥，即圖中的4個黃色柵格最冰。
3.八鄰域
如圖7，像素P（x稀火，y）的八鄰域是其四鄰域和對角鄰域的和暖哨，即圖中的8個黃色柵格。
那么LINE_4和LINE_8代表的直線繪制上有什么不同呢凰狞？觀察圖8和圖9：
圖8中篇裁，點A的下一個連接點B位于點A的四鄰域中，因此直線是四連通直線赡若。圖9中达布，點A的下一個連接點B位于點A的八鄰域中，因此直線是八連通直線逾冬。這里留意一下黍聂，因為八鄰域已經(jīng)包含了四鄰域，所以通常我們認為：點A的下一個連接點B位于點A的對角鄰域中身腻，此直線為八連通直線产还，而在四鄰域中（在四鄰域中一定在八鄰域中）的話，我們依舊認為直線為四連通直線嘀趟。
那么我們上文分析的直線繪制方法繪制出來的是什么直線呢脐区？很明顯是八連通直線。如何將八連通直線算法改造為四連通直線算法呢她按？留給讀者自己思考（提示：y = y + 1時牛隅，x是否需要 + 1炕柔？）
至于LINE_AA，則是抗鋸齒直線媒佣，采用了高斯濾波匕累，本文就不詳細介紹了，如果考慮性能默伍，我們一般使用LINE_4和LINE8哩罪。
