如何判定一點是否在給定頂點的不規則封閉區域內?

01-06

不規則區域的頂點已知，判斷點pt是否在不規則的區域內。不理解下面的程序代碼的判定原理。它的判定思路及涉及到的數學知識有哪些？謝謝！
代碼如下：
bool pointInRegion(cocos2d::CCPoint pt,vector& plist) { int nCross = 0;
for (int i = 0; i &< plist.size(); i++) { cocos2d::CCPoint p1; cocos2d::CCPoint p2; p1 = plist[i]; p2 = plist[(i+1)%plist.size()]; if ( p1.y == p2.y ) continue; if ( pt.y &< min(p1.y, p2.y)) continue; if ( pt.y &>= max(p1.y, p2.y)) continue; double x = (double)(pt.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x; if ( x &> pt.x ) nCross++; } if (nCross % 2 == 1) { return true; } else { return false; }
} ================================================================================= 2015-1-14 補充：在經過Milo Yip大神的解答之後，此問題在2014-11-10已經圓滿得到解決。題目沒有刪除或者關閉，是希望其他遇到此問題的人也可以得到參考。另外我覺得直接刪除他人認真回答的問題也是不禮貌的。我在當初提問時，不知道有Point in polygon 測試，更不知道通過計算射線與多邊形相交的次數可以判斷，就像一個人到網上問大家月球與地球之間的引力存在什麼關係一樣，他根本不知道有萬有引力這回事兒，所以他根本想不到要搜索「萬有引力」或者「物體之間力的關係」等等關鍵字。之所以做出上面的補充是，2015-1-14推送了一個匿名的回答，全身變得不舒服起來，那感覺就像你小的時候犯了一個愚蠢的錯誤，總有人隔一段時間熱心提醒你一下。

這個問題是Point in polygon測試[1]。

其中一個方法是計算射線與多邊形邊界相交的次數。

任一射線穿過多邊形，奇數段位於多邊形之內，偶數段位於多邊形之外。

檢查一點是否在多邊形之內，可以作一射線從該點往任意方向投射，若讓射線與多邊形邊的相交次數為奇，則點位於多邊形之內。為了簡化計算，一般會往水平或垂直方向投射。另外要考慮邊與射線平行及頂點與射線相交的情況，題目中的實現不正確。

另一個方法使用winding number [2]，可避免除數，也更準確。請參考Inclusion of a Point in a Polygon。

參考文獻

[1] Shimrat, Moshe. "Algorithm 112: position of point relative to polygon."Communications of the ACM 5.8 (1962): 434.

[2] Hormann, Kai, and Alexander Agathos. "The point in polygon problem for arbitrary polygons." Computational Geometry 20.3 (2001): 131-144. http://www.inf.usi.ch/hormann/papers/Hormann.2001.TPI.pdf

The definitive reference is "Point in Polygon Strategies" by

Eric Haines [Gems IV] pp. 24-46. Now also at

Point in Polygon Strategies.

The code in the Sedgewick book Algorithms (2nd Edition, p.354) fails

under certain circumstances. See

http://condor.informatik.Uni-Oldenburg.DE/~stueker/graphic/index.html

for a discussion.

The essence of the ray-crossing method is as follows.

Think of standing inside a field with a fence representing the polygon.

Then walk north. If you have to jump the fence you know you are now

outside the poly. If you have to cross again you know you are now

inside again; i.e., if you were inside the field to start with, the total

number of fence jumps you would make will be odd, whereas if you were

ouside the jumps will be even.

The code below is from Wm. Randolph Franklin &

(see URL below) with some minor modifications for speed. It returns

1 for strictly interior points, 0 for strictly exterior, and 0 or 1

for points on the boundary. The boundary behavior is complex but

determined; in particular, for a partition of a region into polygons,

each point is "in" exactly one polygon.

(See p.243 of [O"Rourke (C)] for a discussion of boundary behavior.)

int pnpoly(int npol, float *xp, float *yp, float x, float y)

{

int i, j, c = 0;

for (i = 0, j = npol-1; i &< npol; j = i++) {

if ((((yp[i]&<=y) (y& ((yp[j]&<=y) (y& (x &< (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))

c = !c;

}

return c;

}

The code may be further accelerated, at some loss in clarity, by

avoiding the central computation when the inequality can be deduced,

and by replacing the division by a multiplication for those processors

with slow divides. For code that distinguishes strictly interior

points from those on the boundary, see [O"Rourke (C)] pp. 239-245.

For a method based on winding number, see Dan Sunday,

"Fast Winding Number Test for Point Inclusion in a Polygon,"

Geometry Algorithms TOC, March 2001.

References:

Franklin"s code:

http://www.ecse.rpi.edu/Homepages/wrf/research/geom/pnpoly.html

[Gems IV] pp. 24-46

[O"Rourke (C)] Sec. 7.4.

[Glassner:RayTracing]

如侯鐵所說，這個代碼用的是ray-crossing演算法，原理很簡單，你google一下就知道了


關於這段代碼，我給你逐句添加註釋好了
bool pointInRegion(cocos2d::CCPoint pt,vector& plist)

{

	int nCross = 0;    // 定義變數，統計目標點向右畫射線與多邊形相交次數
	for (int i = 0; i &< plist.size(); i++) {   //遍歷多邊形每一個節點

		cocos2d::CCPoint p1;
		cocos2d::CCPoint p2;

		p1 = plist[i];
		p2 = plist[(i+1)%plist.size()];  // p1是這個節點，p2是下一個節點，兩點連線是多邊形的一條邊
// 以下演算法是用是先以y軸坐標來判斷的

		if ( p1.y == p2.y )
			continue;   //如果這條邊是水平的，跳過

		if ( pt.y &< min(p1.y, p2.y)) //如果目標點低於這個線段，跳過
			continue; 

		if ( pt.y &>= max(p1.y, p2.y)) //如果目標點高於這個線段，跳過

			continue;

//那麼下面的情況就是：如果過p1畫水平線，過p2畫水平線，目標點在這兩條線中間

		double x = (double)(pt.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x;

// 這段的幾何意義是 過目標點，畫一條水平線，x是這條線與多邊形當前邊的交點x坐標

		if ( x &> pt.x )

			nCross++; //如果交點在右邊，統計加一。這等於從目標點向右發一條射線（ray），與多邊形各邊的相交（crossing）次數

	} 
	if (nCross % 2 == 1) {
		return true; //如果是奇數，說明在多邊形里

	}

	else {
		return false; //否則在多邊形外 或 邊上

	}

}

A complete distance field representation和Generating signed distance fields from triangle meshes.這兩篇文章分別有針對二維線段和三維三角網格的Exact Sign Computation.

這類演算法只需要對最近點的法向和待求點到最近點方向向量求點乘即可判斷出內外。

下圖是二維例子:最近點在邊上只需與邊法向做點乘，最近點在頂點上，則與頂點相鄰的邊分別做點乘，用絕對值大的進行判斷。這個演算法可以直接擴展到三維情況，當最近點在邊上和面上是都是準確的，當最近點在三維頂點上時則需要用演算法二為頂點定義偽法線，再進行求解。

我是一塊磚，哪裡需要哪裡搬，最近參與一些前端開發的工作，然後選用了百度的echarts，不小心花了一天的時間把它的源代碼讀了一遍，它裡邊引用的zrender庫，裡邊有段代碼是你需要的，可以學習下，zrender/area.js at master · ecomfe/zrender · GitHub，這種東西沒有必須要在這裡問，如果你想玩圖形學這個領域的東西，把這個領域的知識啃了，多看些相關項目的源代碼，多寫寫自然就知道了。

過pt點畫一條直線，這個直線與圖形的第一個交點和第二個交點之間的區域在圖形內。

Let me bing that for you

題目描述既然是頂點已知了，以下答案作廢，我說的方法是頂點未知的情況。

反對排名第一的答案，這個問題我曾經研究過。排名第一的答案是上個世紀的古老解法（教科書解法），他只適用於理想的不含水平邊的多邊形。什麼是理想的多邊形？就是多邊形的邊只有一個點寬，多邊形的頂點就只有一個點。但放到計算機里，大家都知道圖都是不那麼理想的，邊可能是兩個像素點寬，頂點處放大了可能是2個點甚至3個點，碰到這些不確定情況奇偶法就完全沒用了。（以上討論都是基於頂點位置不確定情況的，如果頂點都知道了，其實都不用編程了，直接當數學問題解就是了）

這個問題在圖形界裡面其實有一個專門的學術分支，名字叫「區域填充（region filling）」，他針對的範圍也不僅僅是多邊形，甚至是任意形狀、任意粗細的封閉圖形，目標就是用顏色準確填滿這個封閉圖形內部。判斷內點外點也是這些演算法的一個應用。

目前學術上速度最快同時適用於任何形狀粗細圖形的演算法來自這篇論文：

A new and fast contour-filling algorithm。谷歌學術上可以搜到。

不知題主解決這個問題沒有，我今天也碰到了這個問題。如果你成功的話，幫我測試下如下4邊形和若干待檢驗點的位置關係。

x y

1 1

4 1

5 3

2 3 檢驗點為1.5 2 ，1.1 2， 4.5 2

我使用Inclusion of a Point in a Polygon上的wn法，寫了一下，發現判斷失誤，不知道哪裡出問題了，特地請教一下。

topcoder上的一篇文章，非常全面詳細。

http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=geometry3#pointinpolygon

請問樓主是怎麼解決的呢？

這方法使用任意複雜的多邊形嗎