資源簡(jiǎn)介
這是一個(gè)水平/垂直交叉點(diǎn)數(shù)判別法判斷點(diǎn)是否在凹（凸）多邊形內(nèi)部（適用于任意多邊形包括凹凸邊形）
注意到如果從P作水平向左的射線的話，如果P在多邊形內(nèi)部，那么這條射線與多邊形的交點(diǎn)必為奇數(shù)，如果P在多邊形外部，則交點(diǎn)個(gè)數(shù)必為偶數(shù)（0也在內(nèi)）。所以，我們可以順序考慮多邊形的每條邊，求出交點(diǎn)的總個(gè)數(shù)。還有一些特殊情況要考慮，具體見代碼。程序運(yùn)行后，首先輸入多邊形頂點(diǎn)個(gè)數(shù)，然后輸入頂點(diǎn)坐標(biāo)xy值，回車確定后。yes表示點(diǎn)在多邊形內(nèi)部。反之，在外部。
代碼片段和文件信息
//offset為多邊形坐標(biāo)上限???
//on_edge表示點(diǎn)在多邊形邊上時(shí)的返回值???
#include???
#include???
#include???
#include???
#include???
#include???
using?namespace?std;??
const?int?offset=1000;??
const?double?eps=1e-8;??
struct?Point
{?
????double?xy;??
}p[105];?
?
double?cross（Point?piPoint?pjPoint?pk）?//改為
{?//?（pipj）X（pipk）?
//輸入：三個(gè)點(diǎn)的橫、縱坐標(biāo)
//輸出：點(diǎn)k在線段ij的哪一側(cè)
????return?（pj.x-pi.x）*（pk.y-pi.y）-（pj.y-pi.y）*（pk.x-pi.x）;??
}??
int?InPolygon（const?Point?*arrconst?int?&lenconst?Point?&pint?on_edge=1）
{??
//輸入：凹或凸多邊形區(qū)域端點(diǎn)的坐標(biāo)arr[i]
//輸入：多邊形端點(diǎn)個(gè)數(shù)
//輸入：需要判定的點(diǎn)P
//輸出：返回值為1：點(diǎn)在多邊形內(nèi)；返回值為0：點(diǎn)在多邊形外
Point?q;??
int?i=0counter;??
while（i
q.x=rand（）+offset;//隨機(jī)取一個(gè)足夠遠(yuǎn)的點(diǎn)q???
q.y=rand（）+offset;//以p為起點(diǎn)q為終點(diǎn)做射線L???
f ?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????文件???????1831??2013-10-22?12:16??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\22.cpp
?????文件???????3353??2013-10-22?11:33??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\22.dsp
?????文件????????512??2013-10-22?11:35??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\22.dsw
?????文件??????41984??2013-11-12?21:20??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\22.ncb
?????文件??????54784??2013-11-12?21:20??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\22.opt
?????文件???????1120??2013-11-12?21:17??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\22.plg
?????文件?????278608??2013-11-12?21:17??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\Debug\22.exe
?????文件?????387820??2013-11-12?21:17??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\Debug\22.ilk
?????文件??????15401??2013-11-12?21:17??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\Debug\22.obj
?????文件????2013816??2013-11-12?21:17??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\Debug\22.pch
?????文件?????590848??2013-11-12?21:17??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\Debug\22.pdb
?????文件??????74752??2013-11-12?21:17??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\Debug\vc60.idb
?????文件?????102400??2013-11-12?21:17??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\Debug\vc60.pdb
?????目錄??????????0??2013-11-12?21:21??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）\Debug
?????目錄??????????0??2013-11-12?21:21??水平垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形包括凹凸邊形）
-----------?---------??----------?-----??----
??????????????3567229????????????????????15
評(píng)論
共有 條評(píng)論