判斷一個(gè)點(diǎn)是否在指定區(qū)域內(nèi)
在圖像處理時(shí)，我們會(huì)經(jīng)常需要判斷一個(gè)點(diǎn)是否位于多邊形區(qū)域內(nèi)，這里介紹2種比較巧妙的算法。
射線法
第一種是射線法，算法思想非常巧妙：從待判斷的點(diǎn)向某一個(gè)方向引射線，計(jì)算和多邊形交點(diǎn)的個(gè)數(shù)，如果個(gè)數(shù)是偶數(shù)或者0則點(diǎn)在多邊形外，如果是奇數(shù)，則在多邊形內(nèi)，如下圖：
這里有二種特殊情況：
1. 射線經(jīng)過(guò)頂點(diǎn)：當(dāng)射線經(jīng)過(guò)頂點(diǎn)時(shí)，判斷就會(huì)出現(xiàn)異常情況。
2. 點(diǎn)在邊上：這種情況也不能用交點(diǎn)個(gè)數(shù)的奇偶性來(lái)判斷了，要快速地判斷這個(gè)點(diǎn)是否在邊上。C的實(shí)現(xiàn)如下：
參考自：Determining if a point lies on the interior of a polygon
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#define MIN(x,y) (x < y ? x : y) #define MAX(x,y) (x > y ? x : y) typedef struct { double x,y; } Point; int InsidePolygon(Point *polygon,int N,Point p) { int counter = 0; int i; double xinters; Point p1,p2; p1 = polygon[0]; for (i=1;i<=N;i++) { p2 = polygon[i % N]; if (p.y > MIN(p1.y,p2.y)) { //低 if (p.y <= MAX(p1.y,p2.y)) { //高 if (p.x <= MAX(p1.x,p2.x)) { //右 if (p1.y != p2.y) { //簡(jiǎn)單忽略平行X軸這種情況 xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x; //交叉點(diǎn)坐標(biāo) 參考http:///media/point-and-polygon/xinters.jpg if (p1.x == p2.x || p.x <= xinters) counter++; } } } } p1 = p2; } if (counter % 2 == 0) return 0; else return 1; } |
再來(lái)個(gè)C#版的
1 2 3 4 5 6 7 8 9 10 11 12 |
public static bool Contains( Point[] points, Point p ) { bool result = false; for( int i = 0; i < points.Length - 1; i++ ) { if( ( ( ( points[ i + 1 ].Y <= p.Y ) && ( p.Y < points[ i ].Y ) ) || ( ( points[ i ].Y <= p.Y ) && ( p.Y < points[ i + 1 ].Y ) ) ) && ( p.X < ( points[ i ].X - points[ i + 1 ].X ) * ( p.Y - points[ i + 1 ].Y ) / ( points[ i ].Y - points[ i + 1 ].Y ) + points[ i + 1 ].X ) ) { result = !result; } } return result; } |
值得一提的是射線法對(duì)于帶島的多邊形依然有效：
改進(jìn)：傳統(tǒng)的射線法一開(kāi)始就直接計(jì)算點(diǎn)和多邊形的交點(diǎn)個(gè)數(shù)，這樣的話，會(huì)花費(fèi)大量的時(shí)間來(lái)作拓?fù)潢P(guān)系的判斷，我們可以首先計(jì)算出最小外包矩形，迅速排除不在矩形內(nèi)部的點(diǎn)，然后再做上面的判斷。
第二種是也很巧妙
如下圖：
我們可以把多邊形可以看做是一條從某點(diǎn)出發(fā)的閉合路，可以觀察到在內(nèi)部的點(diǎn)永遠(yuǎn)都在路的同一邊。
給定線段的兩個(gè)點(diǎn)P0(x0,y0)和P1(x1,y1)，目標(biāo)點(diǎn)P(x,y),它們有如下的關(guān)系：
計(jì)算(y - y0) (x1 - x0) - (x - x0) (y1 - y0)如果答案小于0則說(shuō)明P在線段的右邊，大于0則在左邊，等于0說(shuō)明在線段上。
除了上面兩種，還有很多方法
比如面積法：就是計(jì)算所有邊和目標(biāo)點(diǎn)組成的三角形面積和是否等于總的多邊形面積，如果相等，則點(diǎn)在該區(qū)域的內(nèi)部。
這種方法計(jì)算量較大，多邊形的面積計(jì)算也是比較麻煩；
還有夾角法：判斷所有邊和目標(biāo)點(diǎn)的夾角和是否為360度，計(jì)算量同樣很大。
