[發明專利]生成軌跡線頂點序列的方法和裝置

有效

• 申請號: 201510240856.0
• 申請日: 2015-05-12
• 公開（公告）號: CN104801044B
• 公開（公告）日: 2017-12-12
• 發明（設計）人: 謝思遠
• 申請（專利權）人: 深圳市騰訊計算機系統有限公司
• 主分類號: A63F13/56
• 分類號: A63F13/56;A63F13/573
• 代理公司: 廣州華進聯合專利商標代理有限公司44224
• 代理人: 何平,鄧云鵬

1.一種生成軌跡線頂點序列的方法，包括以下步驟：

獲取軌跡網格頂點集；

根據所述軌跡網格頂點集中頂點生成中點路徑頂點集，所述中點路徑頂點集中包括中點；

將所述中點路徑頂點集中頂點進行排序，得到軌跡線頂點序列。

2.根據權利要求1所述的方法，其特征在于，根據所述軌跡網格頂點集中頂點生成中點路徑頂點集的步驟包括：

初始化空的第一集合；

從所述軌跡網格頂點集中依次取出頂點；

判斷在所述第一集合中是否存在頂點與所述取出的頂點之間距離小于設定的間距值，若是，則將所述第一集合中的所述頂點替換為所述第一集合中的所述頂點與所述取出的頂點的中點，若否，則將所述取出的頂點加入所述第一集合中；

遍歷完所述軌跡網格頂點集中頂點，將得到的第一集合作為中點路徑頂點集。

3.根據權利要求2所述的方法，其特征在于，在從所述軌跡網格頂點集中依次取出頂點的步驟之前，所述方法還包括：

判斷所述軌跡網格頂點集是否為空，若是，則結束，若否，則從所述軌跡網格頂點集中依次取出頂點，并移除所述取出的頂點；

在將所述第一集合中的所述頂點替換為所述第一集合中的所述頂點與所述取出的頂點的中點之后，或者在將所述取出的頂點加入所述第一集合中之后，再執行所述判斷所述軌跡網格頂點集是否為空的步驟。

4.根據權利要求1至3中任一項所述的方法，其特征在于，將所述中點路徑頂點集中頂點進行排序，得到軌跡線頂點序列的步驟包括：

從所述中點路徑頂點集中選取軌跡線的起點；

遍歷所述中點路徑頂點集，查找與所述起點距離最近的頂點，將與所述起點距離最近的頂點作為所述起點的相鄰的下一個頂點；

更新所述距離最近的頂點為新的起點；

遍歷完所述中點路徑頂點集中頂點，形成軌跡線頂點序列。

5.根據權利要求4所述的方法，其特征在于，從所述中點路徑頂點集中選取軌跡線的起點步驟包括：

從所述中點路徑頂點集中選取三維坐標中Z坐標最小的頂點作為軌跡線的起點。

6.根據權利要求4所述的方法，其特征在于，從所述中點路徑頂點集中選取軌跡線的起點的步驟之后，所述方法還包括：

判斷所述中點路徑頂點集是否為空，若是，則結束，若否，則遍歷所述中點路徑頂點集，查找與所述起點距離最近的頂點，將與所述起點距離最近的頂點作為所述起點的相鄰的下一個頂點，并從所述中點路徑頂點集中移除所述距離最近的頂點。

7.一種生成軌跡線頂點序列的裝置，其特征在于，包括：

獲取模塊，用于獲取軌跡網格頂點集；

生成模塊，用于根據所述軌跡網格頂點集中頂點生成中點路徑頂點集，所述中點路徑頂點集中包括中點；

排序模塊，用于將所述中點路徑頂點集中頂點進行排序，得到軌跡線頂點序列。

8.根據權利要求7所述的裝置，其特征在于，所述生成模塊包括：初始化單元，用于初始化空的第一集合；

取出單元，用于從所述軌跡網格頂點集中依次取出頂點；

第一判斷單元，用于判斷在所述第一集合中是否存在頂點與所述取出的頂點之間距離小于設定的間距值；

更新單元，用于在判斷出在所述第一集合中存在頂點與所述取出的頂點之間距離小于設定的間距值，將所述第一集合中的所述頂點替換為所述第一集合中的所述頂點與所述取出的頂點的中點，以及在判斷出在所述第一集合中不存在頂點與所述取出的頂點之間距離小于設定的間距值時，將所述取出的頂點加入所述第一集合中；

遍歷單元，用于遍歷完所述軌跡網格頂點集中頂點，將得到的第一集合作為中點路徑頂點集。

9.根據權利要求8所述的裝置，其特征在于，所述第一判斷單元還用于在從所述軌跡網格頂點集中依次取出頂點之前，判斷所述軌跡網格頂點集是否為空，若是，則結束，若否，則所述取出單元從所述軌跡網格頂點集中依次取出頂點，并移除所述取出的頂點；

在將所述第一集合中的所述頂點替換為所述第一集合中的所述頂點與所述取出的頂點的中點之后，或者在將所述取出的頂點加入所述第一集合中之后，再由所述第一判斷單元執行所述判斷所述軌跡網格頂點集是否為空。