C說話完成的PNPoly算法代碼例子。本站提示廣大學習愛好者：（C說話完成的PNPoly算法代碼例子）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話完成的PNPoly算法代碼例子正文
寫C說話的試驗用到的一個算法，斷定一個點能否在多邊形的外部。C的代碼以下：
int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
if ( ((verty[i]>testy) != (verty[j]>testy)) &&
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) /
(verty[j]-verty[i]) + vertx[i]) )
c = !c;
}
return c;
}
個中nvert是多邊形極點的個數，vertx和verty分離是多邊形極點橫、縱坐標的數組，textx和testy是待測點的坐標。這個算法是由W. Randolph Franklin提出的，依據Jordan curve theorem，多邊形將立體分為表裡兩個區域，假定待測點在多邊形外部，從待測點引出一條射線必定會與多邊形有至多一個交點。該射線與多邊形第一次訂交時將“沖出”多邊形，第二次訂交將“進入”多邊形，依此類推，若射線與多邊形有奇數個交點，則該點在多邊形外部，反之則在內部。
PNPoly算法恰是從待測點引出一條程度向右的射線，並盤算與多邊形的交點個數。說明一下這段代碼：for (i = 0, j = nvert-1; i < nvert; j = i++)輪回的寄義就是一直讓j = i – 1，假如i = 0那末j = nvert – 1，從而順次磨練多邊形的每條邊。接上去的重點就是前提語句，(verty[i]>testy) != (verty[j]>testy)很好懂得，就是一條邊上的兩個極點分離在待測點的上方和下方，經由過程這條語句可以曉得從待測點向右引出的射線有能夠與該條邊訂交（只需待測點在邊的左邊便可）。
但詳細斷定訂交就要交給解析幾何了。建系寫出該條邊地點直線的方程：
變形一下：
代入待測點坐標，依據圖形關系獲得這個不等式：
也就是語句testx < vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]了.
