寫C語言的實(shí)驗(yàn)用到的一個(gè)算法，判斷一個(gè)點(diǎn)是否在多邊形的內(nèi)部。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是多邊形頂點(diǎn)的個(gè)數(shù)，vertx和verty分別是多邊形頂點(diǎn)橫、縱坐標(biāo)的數(shù)組，textx和testy是待測點(diǎn)的坐標(biāo)。這個(gè)算法是由W. Randolph Franklin提出的，根據(jù)Jordan curve theorem，多邊形將平面分為內(nèi)外兩個(gè)區(qū)域，假設(shè)待測點(diǎn)在多邊形內(nèi)部，從待測點(diǎn)引出一條射線必然會(huì)與多邊形有至少一個(gè)交點(diǎn)。該射線與多邊形第一次相交時(shí)將“沖出”多邊形，第二次相交將“進(jìn)入”多邊形，依此類推，若射線與多邊形有奇數(shù)個(gè)交點(diǎn)，則該點(diǎn)在多邊形內(nèi)部，反之則在外部。

PNPoly算法正是從待測點(diǎn)引出一條水平向右的射線，并計(jì)算與多邊形的交點(diǎn)個(gè)數(shù)。解釋一下這段代碼：for (i = 0, j = nvert-1; i < nvert; j = i++)循環(huán)的含義就是始終讓j = i – 1，如果i = 0那么j = nvert – 1，從而依次檢驗(yàn)多邊形的每條邊。接下來的重點(diǎn)就是條件語句，(verty[i]>testy) != (verty[j]>testy)很好理解，就是一條邊上的兩個(gè)頂點(diǎn)分別在待測點(diǎn)的上方和下方，通過這條語句可以知道從待測點(diǎn)向右引出的射線有可能與該條邊相交（只要待測點(diǎn)在邊的左側(cè)即可）。

但具體判斷相交就要交給解析幾何了。建系寫出該條邊所在直線的方程：

變形一下：

代入待測點(diǎn)坐標(biāo)，根據(jù)圖形關(guān)系得到這個(gè)不等式：

也就是語句testx < vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]了.
 

最新評論