點(diǎn)在多邊形經(jīng)典算法

再經(jīng)典不過的算法了：//功能：判斷點(diǎn)是否在多邊形內(nèi)//方法：求解通過該點(diǎn)的水平線與多邊形各邊的交點(diǎn)//結(jié)論：?jiǎn)芜吔稽c(diǎn)為奇數(shù)，成立!//參數(shù)：//POINTp指定的某個(gè)點(diǎn)//LPPOINTptPolygon多邊形的各個(gè)頂點(diǎn)坐標(biāo)（首末點(diǎn)可以不一致）//intnCount多邊形定點(diǎn)的個(gè)數(shù)BOOLPtInPolygon(POINTp,LPPOINTptPolygon,intnCount){intnCross=0;for(inti=0;i<nCount;i++){POINTp1=ptPolygon[i];POINTp2=ptPolygon[(i+1)%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)--------------------------------------------------------------doublex=(double)(p.y-p1.y)*(double)(p2.x-p1.x)/(double)(p2.y-p1.y)+p1.x;if(x>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+S2+S3>原來的三角形面積就不在三角形范圍中.可以使用海倫公式。推廣一下是否可以得到面向凸多邊形的算法？（不確定）3.角度和判別法（適用于任意多邊形）doubleangle=0;realPointList::iteratoriter1=points.begin();for(realPointList::iteratoriter2=(iter1+1);iter2<points.end();++iter1,++iter2){doublex1=(*iter1).x-p.x;doubley1=(*iter1).y-p.y;doublex2=(*iter2).x-p.x;doubley2=(*iter2).y-p.y;angle+=angle2D(x1,y1,x2,y2);}if(fabs(angle-span::PI2)<0.01)returntrue;elsereturnfalse;另外，可以使用boundingbox來加速。if(p.x<(*iter)->boundingBox.left||p.x>(*iter)->boundingBox.right||p.y<(*iter)->boundingBox.bottom||p.y>(*iter)->boundingBox.top)。。。。。。對(duì)于多邊形來說，計(jì)算boundingbox非常的簡(jiǎn)單。只需要把水平和垂直方向上的最大最小值找出來就可以了。對(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ù)。還有一些特殊情況要考慮。假如考慮邊(P1,P2)，1)如果射線正好穿過P1或者P2,那么這個(gè)交點(diǎn)會(huì)被算作2次，處理辦法是如果P的從坐標(biāo)與P1,P2中較小的縱坐標(biāo)相同，則直接忽略這種情況2)如果射線水平，則射線要么與其無交點(diǎn)，要么有無數(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)，以無窮遠(yuǎn)為終點(diǎn)作平行于X軸的直線line(x,y;-∞,y)；3.循環(huán)取得(for(i=0;i<n;i++))多邊形的每一條邊side(xi,yi;xi+1,yi+1)，且判斷是否平行于X軸，如果平行continue，否則，i++；4.同時(shí)判斷point(x,y)是否在side上，