判定點是否在不規則多邊形内部的問題

問題如下：

<a href="http://my.oschina.net/tinyframework/blog/170935#">?</a>

1

2

3

4

<code>話說在平面内有一個任意的不規則的封閉多邊形，另外在這個平面内還有一個點，問題：如何高效的判定這個點是在這個多邊形内部還是外部？</code>

<code>補充：</code>

<code>什麼是任意的呢？也就是說想讓他是啥樣就啥樣，隻要是封閉的多邊形就好。為了簡化題目，明确這個點不在多邊形的線上。</code>

當然，熟悉谷歌和度娘的同學已經搜到了各種正确的不正确的、國内的國外的解法。當然有些參加過acm比賽的同學在學習、訓練或者比賽中，可能也碰到了這個問題。

偶對自己不加思考就直接搜尋的表示遺憾，因為你失去了一次自我提升的機會。

正如一位回答者所述，“弄一個蚊香的你給算算看？”，因為題目，本身就說了是任意的，是以，弄成蚊香形狀也是符合題意的。

此題本要碰到時，想了若幹種方案，有些與答案相同，有的不相同。現在拿一個不太相同的出來與大家分享，個人感覺效率應該是非常高的，大家拍磚輕點，呵呵。

偶把任意形狀的多邊形，比做用釘子卡住的橡皮筋，想怎麼改變形狀，隻要增加更多的橡皮筋即可。但是偶一個一個的拔掉釘子，到釘子數變成3個的時候，它就是個三角形，然後結果就轉變成點是不是在三角形内部的問題。

當然，在拔釘子的時候，要注意一件事情，就是如果這個點剛好在拔掉釘子與邊上兩個釘子構成的三角形當中，就先不拔這個釘子，因為其影響結果的正确。

還有就是，如果在拔釘子的時候，導緻相臨的3個點，變成一條直線了，就把中間一個點去掉，這可以避免最後形成的是三點一線，而不是一個三角形。

ok，算法的思路就算出來了，可以做一個遞歸，每次做一圈，去掉可以去掉的釘子，直到還有3個釘子。

設有n個釘子，最後總是去掉n-3個釘子，就可以判定出結果了。是以時間複雜度是o(n)。