C語言實(shí)現(xiàn)的PNPoly算法代碼例子
寫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是待測(cè)點(diǎn)的坐標(biāo)。這個(gè)算法是由W. Randolph Franklin提出的，根據(jù)Jordan curve theorem，多邊形將平面分為內(nèi)外兩個(gè)區(qū)域，假設(shè)待測(cè)點(diǎn)在多邊形內(nèi)部，從待測(cè)點(diǎn)引出一條射線必然會(huì)與多邊形有至少一個(gè)交點(diǎn)。該射線與多邊形第一次相交時(shí)將“沖出”多邊形，第二次相交將“進(jìn)入”多邊形，依此類推，若射線與多邊形有奇數(shù)個(gè)交點(diǎn)，則該點(diǎn)在多邊形內(nèi)部，反之則在外部。
PNPoly算法正是從待測(cè)點(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)分別在待測(cè)點(diǎn)的上方和下方，通過這條語句可以知道從待測(cè)點(diǎn)向右引出的射線有可能與該條邊相交（只要待測(cè)點(diǎn)在邊的左側(cè)即可）。
但具體判斷相交就要交給解析幾何了。建系寫出該條邊所在直線的方程：
變形一下：
代入待測(cè)點(diǎn)坐標(biāo)，根據(jù)圖形關(guān)系得到這個(gè)不等式：
也就是語句testx < vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]了.
- C語言位圖算法詳解
- C語言快速冪取模算法小結(jié)
- C語言實(shí)現(xiàn)的排列組合問題的通用算法、解決方法
- C語言實(shí)現(xiàn)字符串匹配KMP算法
- 馬爾可夫鏈算法（markov算法）的awk、C++、C語言實(shí)現(xiàn)代碼
- C語言實(shí)現(xiàn)排序算法之歸并排序詳解
- C語言對(duì)堆排序一個(gè)算法思路和實(shí)現(xiàn)代碼
- c語言實(shí)現(xiàn)冒泡排序、希爾排序等多種算法示例
- C語言的數(shù)字游戲算法效率問題探討實(shí)例
- c語言實(shí)現(xiàn)單鏈表算法示例分享
- 純C語言：貪心Prim算法生成樹問題源碼分享
- C程序?qū)崿F(xiàn)整數(shù)的素?cái)?shù)和分解問題
相關(guān)文章
這篇文章主要介紹了C語言對(duì)歸并排序算法的使用,歸并排序算法的平均事件復(fù)雜度為(n\log n),需要的朋友可以參考下2016-05-05
一篇文章帶你了解C語言二分查找的簡(jiǎn)單應(yīng)用
這篇文章主要介紹了二分查找算法在C語言程序中的使用示例,文中最后提到了使用二分查找法一個(gè)需要注意的地方,需要的朋友可以參考下2021-08-08
我們今天要給大家講的底層的IO看上去簡(jiǎn)單，實(shí)則抽象。并且在它之上衍生出了語言層面用于實(shí)戰(zhàn)的技術(shù)，比如我們熟悉的java語言中的NIO或者像Netty這樣的框架2021-06-06
C++實(shí)現(xiàn)教職工信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)教職工信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
C/C++ 原生API實(shí)現(xiàn)線程池的方法
線程池，簡(jiǎn)單來說就是有一堆已經(jīng)創(chuàng)建好的線程，接下來通過本文給大家介紹C/C++ 原生API實(shí)現(xiàn)線程池的方法，感興趣的朋友跟隨小編一起看看吧2021-11-11
八分音符醬作為一款聲音控制類游戲，當(dāng)時(shí)還是很受大家的喜愛的。本文將用Matlab制作一款簡(jiǎn)易版的八分音符醬游戲，感興趣的可以學(xué)習(xí)一下2022-02-02
這篇文章主要介紹了如何讓Dev-C++支持auto關(guān)鍵字問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12
程序在運(yùn)行過程中，有對(duì)也就有錯(cuò)，正確那么就不用說了，但是如果錯(cuò)誤，那么我們?nèi)绾慰焖俚亩ㄎ坏藉e(cuò)誤的位置，以及知道發(fā)生了什么錯(cuò)誤。當(dāng)一個(gè)函數(shù)發(fā)現(xiàn)自己無法處理的異常，就會(huì)拋出一個(gè)異常，讓函數(shù)調(diào)用者直接或者間接的處理這個(gè)錯(cuò)誤。本文將詳解介紹c++中的異常2021-06-06
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)密碼本小項(xiàng)目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要介紹了C++基于棧實(shí)現(xiàn)鐵軌問題,實(shí)例分析了C++使用棧實(shí)現(xiàn)鐵軌問題的思路與解決方法,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-04-04