把旅行記憶裝進App，我的國家公園打卡App開發故事：怎麼辦？我不小心亂立了一個Flag！

前情提要，上次提到國家公園打卡App的核心功能之一，是透過使用者GPS座標辨認使用者是否在國家公園內。其實這是屬於經典計算幾何學問題Point in Polygon / PIP（多邊形內的點），我介紹了圓心法、對角法和射線投射法等不同的解決方法，然而，還一種叫做「卷繞數」（Winding number）的算法，理論上比較準確，但是太複雜，沒有在上一篇文章裡說明。

結果我亂立Flag說破百讚解鎖「卷繞數」，沒想到就破百讚了，早知道門檻設高一點，多賺一點愛心。感謝大家支持啦！發現給自己出了一個難題⋯

首先，先來講一下為什麼需要「卷繞數」算法，上篇文章比較簡化了射線投射法的規則，這裡我們更加仔細看看射線法的缺點。

射線法（Ray Casting）是從使用者的座標向東畫出一條無限長的射線，並計算這條線與公園邊界的交會點的數量。

1. 若無交點，則使用者不在公園內。

2. 交會點若是奇數，也就是1, 3, 5…個交點，則在公園內。

3. 交會點若是偶數，也就是2, 4, 6…個交點，則不在公園內。

但是，如果這條線剛好經過多邊形的頂點或是邊線，代表使用者不在公園內。

沒錯，就是這個「但是」造成了射線投射法的不穩定性！

越是靠近邊界，就越難以計算真正交會的點的數量，也無法辨認是不是經過邊或是角。

如果是遊戲、打卡APP，也不需要如此精準，如果需要超級精準就需要卷繞數（Winding Number)！卷繞數這個名詞聽起來很數學，但不要被它嚇跑了。在判定一個人是不是在一個國家公園的界線內這方面，其實相對來說很單純。

簡單地說，如果一個人在原地轉一圈，如果他的視野都能夠看到國家公園的邊界，就代表著他在國家公園的界線內。如果有時能看到，有時候看不到邊界，那代表著他在國家公園之外。

在概念上這是簡單的，但實際上要計算的時候，還是比較麻煩：

1. 以使用者的位置為中心，向公園的每一個邊界劃出一條直線。
2. 計算每條線之間的夾角。注意角度必須按照線條的次序計算，而且有方向性，這裡要用逆時針方向來計算角度。如果是順時針方向，那麼角度就會被記為負值。
3. 將所有的角度加起來，如果總和為360，就表示這個點在國家公園內部。
   

除了傳統用角度相加的算法，還有複雜度更低的Dan Sunday’s winding number algorithm，這裡就不做解釋了。今天真的太燒腦。

實務點說，有更簡單的解決靠近邊界的方法。例如：設立誤差值、或是直接顯示訊息：「無法判定，走幾步再試」。不要忘記，軟體開發大多是用來解決某種問題，當遇到困難的時候，不仿回到問題本身，看看實際使用情境，去思考看看有沒有更容易的解法，有時候簡單的方法才是最合適的！