判斷一個點是否在指定區(qū)域內(nèi)
在圖像處理時，我們會經(jīng)常需要判斷一個點是否位于多邊形區(qū)域內(nèi)，這里介紹2種比較巧妙的算法。
射線法
第一種是射線法，算法思想非常巧妙：從待判斷的點向某一個方向引射線，計算和多邊形交點的個數(shù)，如果個數(shù)是偶數(shù)或者0則點在多邊形外，如果是奇數(shù)，則在多邊形內(nèi)，如下圖：
這里有二種特殊情況：
1. 射線經(jīng)過頂點：當射線經(jīng)過頂點時，判斷就會出現(xiàn)異常情況。
2. 點在邊上：這種情況也不能用交點個數(shù)的奇偶性來判斷了，要快速地判斷這個點是否在邊上。C的實現(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) { //簡單忽略平行X軸這種情況 xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x; //交叉點坐標 參考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; } |
再來個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; } |
值得一提的是射線法對于帶島的多邊形依然有效：
改進：傳統(tǒng)的射線法一開始就直接計算點和多邊形的交點個數(shù)，這樣的話，會花費大量的時間來作拓撲關系的判斷，我們可以首先計算出最小外包矩形，迅速排除不在矩形內(nèi)部的點，然后再做上面的判斷。
第二種是也很巧妙
如下圖：
我們可以把多邊形可以看做是一條從某點出發(fā)的閉合路，可以觀察到在內(nèi)部的點永遠都在路的同一邊。
給定線段的兩個點P0(x0,y0)和P1(x1,y1)，目標點P(x,y),它們有如下的關系：
計算(y - y0) (x1 - x0) - (x - x0) (y1 - y0)如果答案小于0則說明P在線段的右邊，大于0則在左邊，等于0說明在線段上。
除了上面兩種，還有很多方法
比如面積法：就是計算所有邊和目標點組成的三角形面積和是否等于總的多邊形面積，如果相等，則點在該區(qū)域的內(nèi)部。
這種方法計算量較大，多邊形的面積計算也是比較麻煩；
還有夾角法：判斷所有邊和目標點的夾角和是否為360度，計算量同樣很大。
