|
1. 叉乘判別法（只適用于凸多邊形）
想象一個凸多邊形，其每一個邊都將整個2D屏幕劃分成
為左右兩邊，連接每一邊的第一個端點(diǎn)和要測試的點(diǎn)得到一個矢量v，將兩個2維矢量擴(kuò)展成3維的，然后將該邊與v叉乘，判斷結(jié)果3維矢量中Z分量的符號是否
發(fā)生變化，進(jìn)而推導(dǎo)出點(diǎn)是否處于凸多邊形內(nèi)外。這里要注意的是，多邊形頂點(diǎn)究竟是左手序還是右手序，這對具體判斷方式有影響。
2. 面積判別法（只適用于凸多邊形）
第四點(diǎn)分別與三角形的兩個點(diǎn)組成的面積分別設(shè)為S1,S2,S3，只要S1+S2+S3>原來的三角形面積就不在三角形范圍中.可以使用海倫公式 。推廣一下是否可以得到面向凸多邊形的算法？（不確定）
3. 角度和判別法（適用于任意多邊形）
double angle = 0;
realPointList::iterator iter1 = points.begin();
for (realPointList::iterator iter2 = (iter1 + 1); iter2 < points.end(); ++iter1, ++iter2)
{
double x1 = (*iter1).x - p.x;
double y1 = (*iter1).y - p.y;
double x2 = (*iter2).x - p.x;
double y2 = (*iter2).y - p.y;
angle += angle2D(x1, y1, x2, y2);
}
if (fabs(angle - span::PI2) < 0.01) return true;
else return false;
另外，可以使用bounding box來加速。
if (p.x < (*iter)->boundingBox.left ||
p.x > (*iter)->boundingBox.right ||
p.y < (*iter)->boundingBox.bottom ||
p.y > (*iter)->boundingBox.top) 。。。。。。
對于多邊形來說，計(jì)算bounding box非常的簡單。只需要把水平和垂直方向上的最大最小值找出來就可以了。
對于三角形：第四點(diǎn)分別與三角形的兩個點(diǎn)的交線組成的角度分別設(shè)為j1,j2,j3，只要j1+j2+j3>360就不在三角形范圍中。
4. 水平/垂直交叉點(diǎn)數(shù)判別法（適用于任意多邊形）
注意到如果從P作水平向左的射線的話，如果P在多邊形內(nèi)部，那么這條射線與多邊形的交點(diǎn)必為奇數(shù)，如果P在多邊形外部，則交點(diǎn)個數(shù)必為偶數(shù)（0也在內(nèi)）。所以，我們可以順序考慮多邊形的每條邊，求出交點(diǎn)的總個數(shù)。還有一些特殊情況要考慮。假如考慮邊(P1,P2)，
1)如果射線正好穿過P1或者P2,那么這個交點(diǎn)會被算作2次，處理辦法是如果P的從坐標(biāo)與P1,P2中較小的縱坐標(biāo)相同，則直接忽略這種情況
2)如果射線水平，則射線要么與其無交點(diǎn)，要么有無數(shù)個，這種情況也直接忽略。
3)如果射線豎直，而P0的橫坐標(biāo)小于P1,P2的橫坐標(biāo)，則必然相交。
4)再判斷相交之前，先判斷P是否在邊(P1,P2)的上面，如果在，則直接得出結(jié)論：P再多邊形內(nèi)部。
|
