[發明專利]面向平面點集構建凸包的方法、裝置、電子設備及介質

在審

• 申請號: 202110996712.3
• 申請日: 2021-08-27
• 公開（公告）號: CN113689524A
• 公開（公告）日: 2021-11-23
• 發明（設計）人: 章森;查文中
• 申請（專利權）人: 中國電子科技集團公司信息科學研究院
• 主分類號: G06T11/20
• 分類號: G06T11/20
• 代理公司: 北京辰權知識產權代理有限公司 11619
• 代理人: 李小朋

本申請公開了一種面向平面點集構建凸包的方法、裝置、電子設備及介質。其中，本申請中，在若確定平面點集中包含的坐標點數量為至少三個，獲取平面點集中任意三個第一坐標點；根據三個第一坐標點，構建初始凸包；若檢測到存在新加入平面點集的第二坐標點，確定第二坐標點未形成在初始凸包內部；根據第二坐標點以及初始凸包，構建目標凸包。通過應用本申請的技術方案，可以實現在建立初始凸包的基礎上，運用較少的計算和存儲資源，能夠快速準確的構建出平面點集的凸包，而且在迭代過程中，由于大部分坐標點僅處理一次因此可以避免相關技術中出現的構建凸包繁瑣的問題。

技術領域

本申請中涉及數據處理技術，尤其是一種面向平面點集構建凸包的方法、裝置、電子設備及介質。

背景技術

凸包(Convex Hull)是計算機圖形學中的一個基本對象。在二維平面上，凸包是包含平面上給定的若干個點的最小凸多邊形。基于二維平面上的若干點，構建這些點的凸包是計算機圖形學中的一個關鍵技術，在地理信息系統、機器視覺、電子電路設計與生產、智能目標識別等領域有著廣泛的應用。

進一步的，如果平面上的若干點是動態流式數據，隨著時間流失數據源源不斷到來。每到來一個或一批數據，就要構建已有數據的凸包。相關技術中在構建凸包的過程中，會出現執行多次重復計算，消耗許多計算和存儲資源的問題。從而導致業務處理效率較低。

發明內容

本申請實施例提供一種面向平面點集構建凸包的方法、裝置、電子設備及介質，其中，根據本申請實施例的一個方面，提供的一種面向平面點集構建凸包的方法，包括：

若確定平面點集中包含的坐標點數量為至少三個，獲取所述平面點集中任意三個第一坐標點；

根據所述三個第一坐標點，構建初始凸包；

若檢測到存在新加入所述平面點集的第二坐標點，確定所述第二坐標點未形成在所述初始凸包內部；

根據所述第二坐標點以及所述初始凸包，構建目標凸包，并利用所述目標凸包確定線路規劃。

可選地，在基于本申請上述方法的另一個實施例中，所述根據所述第二坐標點以及所述初始凸包，構建目標凸包，包括：

若所述第二坐標點形成在所述初始凸包的外邊上，則將所述第二坐標點作為所述初始凸包的頂點；

以所述第二坐標點作為頂點，以及，以所述初始凸包對應的三個第一坐標點為頂點，構建所述目標凸包。

可選地，在基于本申請上述方法的另一個實施例中，所述根據所述第二坐標點以及所述初始凸包，構建目標凸包，包括：

若所述第二坐標點形成在所述初始凸包的外部，將所述初始凸包對應的三個第一坐標點以預設順序連接成邊，形成初始凸包對應的邊集合；

將所述第二坐標點與每個所述第一坐標點進行連接，得到對應的多個目標線段；

檢測每個所述目標線段與所述邊集合中每個邊是否相交，如均不相交，采集所述初始凸包中存在的，由不相交目標線段所組成的坐標點，形成特征點構成集合；

基于所述特征點構成集合，構建所述目標凸包。

可選地，在基于本申請上述方法的另一個實施例中，所述基于所述特征點構成集合，構建所述目標凸包，包括：

若確定所述特征點構成集合中特征點的數量為兩個，將所述第二坐標點作為頂點，將所述第二坐標點插入到所述初始凸包中，生成所述目標凸包；

或，

若確定所述特征點構成集合中特征點的數量超過兩個，確定所述特征點構成集合中的兩個關鍵特征點，并刪除所述特征點構成集合中，除所述關鍵特征點之外的特征點；