判斷點(diǎn)在多邊形內(nèi)的多種寫(xiě)法

1、/ 功能：判斷點(diǎn)是否在多邊形內(nèi) / 方法：求解通過(guò)該點(diǎn)的水平線與多邊形各邊的交點(diǎn) / 結(jié)論：?jiǎn)芜吔稽c(diǎn)為奇數(shù)，成立!/參數(shù)： / POINT p 指定的某個(gè)點(diǎn) / LPPOINT ptPolygon 多邊形的各個(gè)頂點(diǎn)坐標(biāo)（首末點(diǎn)可以不一致） / int nCount 多邊形定點(diǎn)的個(gè)數(shù)BOOL PtInPolygon (POINT p, LPPOINT ptPolygon, int nCount) int nCross = 0;for (int i = 0; i < nCount; i+) POINT p1 = ptPolygoni; POINT p2 = ptPolygon(i + 1)

2、% nCount;/ 求解 y=p.y 與 p1p2 的交點(diǎn)if ( p1.y = p2.y ) / p1p2 與 y=p0.y平行 continue;if ( p.y < min(p1.y, p2.y) ) / 交點(diǎn)在p1p2延長(zhǎng)線上 continue; if ( p.y >= max(p1.y, p2.y) ) / 交點(diǎn)在p1p2延長(zhǎng)線上 continue;/ 求交點(diǎn)的 X 坐標(biāo) - double x = (double)(p.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x;if ( x >

3、 p.x ) nCross+; / 只統(tǒng)計(jì)單邊交點(diǎn) / 單邊交點(diǎn)為偶數(shù)，點(diǎn)在多邊形之外 - return (nCross % 2 = 1); 1. 叉乘判別法（只適用于凸多邊形）想象一個(gè)凸多邊形，其每一個(gè)邊都將整個(gè)2D屏幕劃分成為左右兩邊，連接每一邊的第一個(gè)端點(diǎn)和要測(cè)試的點(diǎn)得到一個(gè)矢量v，將兩個(gè)2維矢量擴(kuò)展成3維的，然后將該邊與v叉乘，判斷結(jié)果3維矢量中Z分量的符號(hào)是否發(fā)生變化，進(jìn)而推導(dǎo)出點(diǎn)是否處于凸多邊形內(nèi)外。這里要注意的是，多邊形頂點(diǎn)究竟是左手序還是右手序，這對(duì)具體判斷方式有影響。2. 面積判別法（只適用于凸多邊形）第四點(diǎn)分別與三角形的兩個(gè)點(diǎn)組成的面積分別設(shè)為S1,S2,S3，只要S1+S

4、2+S3>原來(lái)的三角形面積就不在三角形范圍中.可以使用海倫公式 。推廣一下是否可以得到面向凸多邊形的算法？（不確定）3. 角度和判別法（適用于任意多邊形）double angle = 0;realPointList:iterator iter1 = points.begin();for (realPointList:iterator iter2 = (iter1 + 1); iter2 < points.end(); +iter1, +iter2) double x1 = (*iter1).x - p.x; double y1 = (*iter1).y - p.y; double

5、x2 = (*iter2).x - p.x; double y2 = (*iter2).y - p.y; angle += angle2D(x1, y1, x2, y2); if (fabs(angle - span:PI2) < 0.01) return true;else return false;另外，可以使用bounding box來(lái)加速。if (p.x < (*iter)->boundingBox.left | p.x > (*iter)->boundingBox.right | p.y < (*iter)->boundingBox.bott

6、om | p.y > (*iter)->boundingBox.top) 。對(duì)于多邊形來(lái)說(shuō)，計(jì)算bounding box非常的簡(jiǎn)單。只需要把水平和垂直方向上的最大最小值找出來(lái)就可以了。對(duì)于三角形：第四點(diǎn)分別與三角形的兩個(gè)點(diǎn)的交線組成的角度分別設(shè)為j1,j2,j3，只要j1+j2+j3>360就不在三角形范圍中。4. 水平/垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形）注意到如果從P作水平向左的射線的話，如果P在多邊形內(nèi)部，那么這條射線與多邊形的交點(diǎn)必為奇數(shù)，如果P在多邊形外部，則交點(diǎn)個(gè)數(shù)必為偶數(shù)（0也在內(nèi)）。所以，我們可以順序考慮多邊形的每條邊，求出交點(diǎn)的總個(gè)數(shù)。還有一些特殊情況要考

7、慮。假如考慮邊(P1,P2)，1)如果射線正好穿過(guò)P1或者P2,那么這個(gè)交點(diǎn)會(huì)被算作2次，處理辦法是如果P的從坐標(biāo)與P1,P2中較小的縱坐標(biāo)相同，則直接忽略這種情況2)如果射線水平，則射線要么與其無(wú)交點(diǎn)，要么有無(wú)數(shù)個(gè)，這種情況也直接忽略。3)如果射線豎直，而P0的橫坐標(biāo)小于P1,P2的橫坐標(biāo)，則必然相交。4)再判斷相交之前，先判斷P是否在邊(P1,P2)的上面，如果在，則直接得出結(jié)論：P再多邊形內(nèi)部。射線算法1. 已知點(diǎn)point(x,y)和多邊形Polygon（x1,y1;x2,y2;.xn,yn;）；2. 以point為起點(diǎn)，以無(wú)窮遠(yuǎn)為終點(diǎn)作平行于X軸的直線line(x,y; -,y)；3

8、. 循環(huán)取得(for(i=0;i<n;i+)多邊形的每一條邊side(xi,yi;xi+1,yi+1)，且判斷是否平行于X軸，如果平行continue，否則，i+；4. 同時(shí)判斷point(x,y)是否在side上，如果是，則返回1(點(diǎn)在多邊形上)，否則繼續(xù)下面的判斷；5. 判斷線side與line是否有交點(diǎn)，如果有則count+，否則，i+。6. 判斷交點(diǎn)的總數(shù)，如果為奇數(shù)則返回0（點(diǎn)在多邊形內(nèi)），偶數(shù)則返回2（點(diǎn)在多邊形外）。代碼：/* 射線法判斷點(diǎn)q與多邊形polygon的位置關(guān)系，要求polygon為簡(jiǎn)單多邊形，頂點(diǎn)逆時(shí)針排列 如果點(diǎn)在多邊形內(nèi)： 返回0 如果點(diǎn)在多邊形邊上： 返

9、回1 如果點(diǎn)在多邊形外： 返回2*/const double INFINITY = 1e10;const double ESP = 1e-5;const int MAX_N = 1000; struct Point double x, y;struct LineSegment Point pt1, pt2;typedef vector<Point> Polygon; / 計(jì)算叉乘 |P0P1| × |P0P2|double Multiply(Point p1, Point p2, Point p0)return ( (p1.x - p0.x) * (p2.y - p0.y

10、) - (p2.x - p0.x) * (p1.y - p0.y) );/ 判斷線段是否包含點(diǎn)pointbool IsOnline(Point point, LineSegment line)return( ( fabs(Multiply(line.pt1, line.pt2, point) < ESP ) &&( ( point.x - line.pt1.x ) * ( point.x - line.pt2.x ) <= 0 ) &&( ( point.y - line.pt1.y ) * ( point.y - line.pt2.y ) <

11、= 0 ) );/ 判斷線段相交bool Intersect(LineSegment L1, LineSegment L2)return( (max(L1.pt1.x, L1.pt2.x) >= min(L2.pt1.x, L2.pt2.x) &&(max(L2.pt1.x, L2.pt2.x) >= min(L1.pt1.x, L1.pt2.x) &&(max(L1.pt1.y, L1.pt2.y) >= min(L2.pt1.y, L2.pt2.y) &&(max(L2.pt1.y, L2.pt2.y) >= min(

12、L1.pt1.y, L1.pt2.y) &&(Multiply(L2.pt1, L1.pt2, L1.pt1) * Multiply(L1.pt2, L2.pt2, L1.pt1) >= 0) &&(Multiply(L1.pt1, L2.pt2, L2.pt1) * Multiply(L2.pt2, L1.pt2, L2.pt1) >= 0);/ 判斷點(diǎn)在多邊形內(nèi)bool InPolygon(const Polygon& polygon, Point point)int n = polygon.size();int count = 0;Li

13、neSegment line;line.pt1 = point;line.pt2.y = point.y;line.pt2.x = - INFINITY; for( int i = 0; i < n; i+ ) / 得到多邊形的一條邊LineSegment side;side.pt1 = polygoni;side.pt2 = polygon(i + 1) % n; if( IsOnline(point, side) ) return1 ; / 如果side平行x軸則不作考慮if( fabs(side.pt1.y - side.pt2.y) < ESP ) continue; if( IsOnline(side.pt1, line)