[發明專利]一種基于拓撲不變性的圈地方法

有效

• 申請號: 201810488317.2
• 申請日: 2018-05-21
• 公開（公告）號: CN108711170B
• 公開（公告）日: 2022-04-08
• 發明（設計）人: 賈聰;姜福泉;張志超
• 申請（專利權）人: 武漢山驍科技有限公司
• 主分類號: G06T7/62
• 分類號: G06T7/62
• 代理公司: 武漢天領眾智專利代理事務所(普通合伙) 42300
• 代理人: 高蘭

本發明涉及一種基于拓撲不變性的圈地方法，本發明通過將平面結構轉化成為一個不變的拓撲結構，利用圈地算法，可以精確的計算出所包圍元素的詳細數據，解決了在平面內經過一段時間自由運動回到領地后，所圈到領地的詳細數據(包括面積和坐標等)計算不準確的問題。

技術領域

本發明涉及計算機圖形處理技術領域，具體的說是一種基于拓撲不變性的圈地方法。

背景技術

在圈地游戲中(二維平面)，從一個點出發隨意運動，當回到出發點后，需要把運動路徑和領地包圍的區域，設置為自己領地并求出領地的面積，現有技術中，在二維平面內構建一個直角坐標系，在坐標系算出領地和路徑的具體的坐標，再把滿足條件(大于某個值、小于某個值)的坐標點設置成自己的領地；通過路徑點的坐標，自動量取，計算方程，然后用微積分計算出面積。但會存在以下的缺陷：

1、在直角坐標系中，運動的路徑是隨機的，根據約束坐標滿足相應的條件，無法滿足極端特殊的情況，很難通過統一的坐標約束算法來算出領地，如圖1所示，O1為起點，在規則的路徑下，坐標系中隨意一個點，當同時滿足xminX、xmaxX、yminY、ymaxY(minX、maxX、minY、maxY四個點為當前坐標(x,y)下的路徑的最大最小值)四個條件，就可以得到該點在路徑范圍內，也就是說這個點將是自己的領地，但這種算法無法滿足如圖2所示的路徑，O2為起點，(x，y)滿足條件xminX、xmaxY、yminY、ymaxY，但點(x，y)不屬于領地；

2、通過微積分計算面積，首先需要計算出路徑的公式，因為運動的路徑完全隨機，求導出來的路徑的公式也只是一個近似值，這樣求得的面積就會存在誤差，圖1與圖2的路徑都是隨機的，無法求得精確的路徑公式，所以根據微積分也無法求得準確的面積。

故針對上述技術中存在的缺點及局限性，本發明提出了一種提高準確性的基于拓撲不變性的圈地方法。

發明內容

為了解決上述現有技術中存在的問題，本發明提供一種提高準確性的基于拓撲不變性的圈地方法。

本發明解決其技術問題所采用的技術方案是：

一種基于拓撲不變性的圈地方法，包括以下步驟：

步驟一、將工作區域按網格劃分，所述網格由多個六邊形按順序拼接而成，得到所述工作區域拓撲不變的結構，并將每一個網格定義為一個map結構體；

步驟二、對步驟一中的工作區域內一個閉合路徑，以一個網格為單位，生成一個最小的包圍盒；

步驟三、對步驟二中的閉合路徑作出如下定義，閉合路徑所占區域為占領地，其余區域為空地，記占領地的狀態為1，空地的狀態為0，將狀態為0的網格放入集合list中；

步驟四、對步驟三中得到的集合list中的點進行循環遍歷，若該點周圍的點存在于集合list中，則從集合list中移除，添加到棧stack中，得到新的集合list，即為閉合路徑的圈地區域的點；

步驟五、對步驟四中得到的新的集合list中的點的狀態設置為1，得到圈地區域的詳細數據。

進一步地，所述步驟一中的map結構體的屬性包括拓撲關系對應的坐標(x，y)、狀態以及實際坐標(worldX，worldY)。

進一步地，所述步驟三中得到集合list的具體過程為，遍歷最小包圍盒內所有的map結構體，若為占領地，則記狀態為1，若為空地，則記狀態為0，并把這個map結構放入到集合list中。

進一步地，所述步驟四中集合list中的點進行循環遍歷具體過程為：

S1、選取包圍盒中左下角的點加入到棧Stack中，并記該點為(x_min，y_min)，進入步驟S2中執行；