OpenGL研究3.0 多邊形區域填充

OpenGL研究3.0 多邊形區域填充

DionysosLai(906391500@qq.com)2014-06-22

???????? 所謂多邊形區域填充。就是將多邊形內部區域，所有已相同色塊填充。注意：這里討論的多邊形是簡單多邊形（即不考慮諸如五角星這樣的相交多邊形）。簡單多邊形，分為凹多邊形和凸多邊形。

???????? 多邊形區域填充有下面幾種方法：

1.??????逐點掃描方法：

? ? ? ? ?原理：掃描多邊形區域，逐點推斷點是否在多邊形內。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ?難點：在于怎樣推斷點是否在區域內;

? ? ? ? ?經常使用怎樣推斷點是否在區域內方法：射線法、面積法。

? ? ? ? ?面積法原理:取一個點。連接多邊形各個點，依據三個點形成一個三角形原理，我們能夠求得三角形面積。推斷面積的大小，就能夠推斷該店是否在多邊形內了。

???????? 射線法：這種方法。是我們這里要重點解說的一個方法。原理：取一個點。向左或者向右做一條射線過去，推斷射線與多邊形的交點。依據多邊形交點熟練和本身多邊形邊情況，推斷點是否在多邊形內。

???????? 首先，射線從左向右，最左邊點肯定在多邊形區域為（我們這里假定射線方向水平向左）。那么與多邊形相交第一個點，必定表明射線右部分在多變形內，與多邊形相交第二個點。表明射線右部分在多邊形外面。因此。通過推斷射線與多變的交點奇偶性。推斷點是否在多邊形內。

? ? ? ? ?這里。有幾種特殊情況，例如以下圖所看到的：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ?圖a，射線與多變形頂點相交，頂點算一個；圖b。射線與多邊形頂點的交點。不被計算在內（注意圖a和圖b的差別->頂點縱坐標大小差別）；圖c和圖d，射線與多邊形一條邊重合，這條邊被忽略不計。

? ? ? ? ?因此。我們能夠設計例如以下：取點向左做一條射線，1. 對于水平邊不做考慮；2. 對于多邊形頂點與射線交點情況。假設其縱坐標是所屬邊較大頂點，則計數（參考圖a），否則不計數（圖b）。3.對于點在多邊形上情況，可直接推斷點在多邊形內。

? ? ? ? ?偽代碼例如以下：

count ← 0;
以P為端點。作從右向左的射線L; 
for 多邊形的每條邊sdo if P在邊s上 then return true;if s不是水平的then if s的一個端點在L上if 該端點是s兩端點中縱坐標較大的端點then count ← count+1else if s和L相交then count ← count+1;
if count mod 2 = 1 then return true;
else return false;

? ? ? ? ?對應代碼例如以下：注：我是在coco2dx2.3版本號內測試的。因此可能移植要改些類名。

///@brief 推斷點是否在多邊形
///@param[in] p0--要推斷點， poly--多邊形點集合， numberOfPoints--多邊形點數量
///@return 2---點在多邊形內， 1---點在多邊邊上，0---點不在多邊形內
///@author DionysosLai,906391500@qq.com
///@retval 
///@post
///@version 1.0
///@data 2014-04-11
int HelloWorld::pointIsInPolygon(const CCPoint& p0, const CCPoint* poly, const unsigned int numberOfPoints)
{unsigned int count  = 0;		///< 用來標記射線L與多邊形的交點數；CCSize	winsize = CCDirector::sharedDirector()->getWinSize();/// 已點p0向左向右做一條射線L；CCPoint leftPoint = ccp(-100.0f, p0.y);CCPoint rightPoint = ccp(winsize.width+100.0f, p0.y);/// 推斷每條邊for (unsigned int i = 0; i < numberOfPoints-1; i++){/// 先推斷點p0是否在邊s上；if (pointIsAtLine(p0, poly[i], poly[(i+1)%(numberOfPoints)])){CCLOG("Point is at the %dth line", i);return 1;}/// 推斷邊s是否是平行線；if (poly[i].y != poly[(i+1)%(numberOfPoints)].y){		do {/// 推斷邊s的是否有端點在L上 同一時候 再推斷該點是否是邊s縱坐標較大的一個點if (pointIsAtLine(poly[i], leftPoint, rightPoint)){if (poly[i].y > poly[(i+1)%(numberOfPoints)].y){count += 1;}break;}	if (pointIsAtLine(poly[(i+1)%(numberOfPoints)], leftPoint, rightPoint)){if (poly[i].y < poly[(i+1)%(numberOfPoints)].y){count += 1;}break;}	/// 假設邊s沒有端點在L上，則推斷s與L是否相交if (segmentLineIsIntersect(leftPoint, rightPoint, poly[i], poly[(i+1)%(numberOfPoints)])){count += 1;}	} while (0);}}if (1 == count%2){CCLOG("Point is not in polygon!");return 0;}else{CCLOG("Point is in  polygon!");return 2;}
}

? ? ? ???這里有個pointIsAtLine。是用來推斷點是否在邊上函數；segmentLineIsIntersect。是用來推斷兩條線段是否相交函數。可參考我的還有一邊博文：http://blog.csdn.net/dionysos_lai/article/details/24418697計算幾何文檔一系列文章（眼下僅僅寫了一篇，實際上是幾乎相同寫了經常使用幾何算法，還沒寫成博文。怪樓主太懶了。）

???????? Ok，逐點掃描推斷方法就是差不都這樣了。

2.???????掃描線算法

? ? ? ???逐點掃描算法，沒有充分考慮到像素之間的連貫性。效率低。

掃描線算法。就是要利用像素之間的連貫性，提高算法效率。

? ? ? ???所謂連貫性：有三個概念，1.邊的連貫性，AB邊與掃描線1相交，也可能與掃描線2相交；2.掃描線連貫性：當前掃描線與多邊形邊交點順序，可能與下一條掃描線交點情況一致或者類似；3.區間連貫性：同一區間像素取同一顏色屬性。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ?掃描線原理：將整個多邊形區域掃描問題分解到一條條掃描線問題。僅僅要完畢每條掃描線的繪制，就實現了多邊形區域填充問題。

一條掃描線與多邊形有偶數個交點（0就不算了），按順序每2個點形成一個區間，僅僅要繪制這個區間就可以。

???????? 難點這與掃描線與多邊形邊交點推斷，這個是高中問題了，通過線段一般方程ax+by+c=0,兩立方程求解。

只是這樣的方法。要計算各種參數，比較費時，更好的方法是分成各種情況分開討論（盡管比較麻煩）。能夠關注我的《計算幾何算法》系類文章。