[發明專利]一種帶弧復雜多邊形快速合并的方法

在審

• 申請號: 202110902252.3
• 申請日: 2021-08-06
• 公開（公告）號: CN115705627A
• 公開（公告）日: 2023-02-17
• 發明（設計）人: 江復興;劉驍;陳金池;黃秀琪;康淑玲
• 申請（專利權）人: 廈門智慧圖信息科技有限公司
• 主分類號: G06T5/50
• 分類號: G06T5/50
• 代理公司: 合肥上博知識產權代理事務所(特殊普通合伙) 34188
• 代理人: 張果果

本發明揭示了一種帶弧復雜多邊形快速合并的方法，包括如下步驟：首先獲取兩個多邊形，使得點集順序為順時針；然后在第一多邊形外或第二多邊形外找點A；接著找不到點A則以第一多邊形或第二多邊形作為合并結果，找到點A則開始順時針遍歷第一多邊形和第二多邊形中的所有線段或弧段，在兩者之間找交點；接著對交點進行標注進點、出點及中性點；最后從出點開始獲取節點，回到出點則實現兩個多邊形的合并。本發明通過對進出點的標記，實現了多邊形合并的完整性和準確性。

技術領域

本發明涉及地理信息技術領域，尤其是涉及一種帶弧復雜多邊形快速合并的方法。

背景技術

空間地理數據是指與地理位置相關的或包含地理信息的數據。在地理信息領域，用矢量數據(坐標和其他數據組合的數據結構)抽象表達真實世界中的點、線、面狀地理要素。

地理空間分析的基礎是地理幾何圖形間的運算，運算的方法直接影響分析的結果及效率，傳統多邊形合并算法僅支持普通多邊形相交情形的合并，對有重疊特別是內部重疊的情況并不能很好的支持，對帶有弧的多邊形的支持也有限。

因此需在現有的基礎上提供一種帶弧復雜多邊形快速合并的方法，支持對帶弧及任意復雜多邊形間的合并的實現與合并效率提升。

發明內容

本發明的目的在于克服現有技術的缺陷，提供一種帶弧復雜多邊形快速合并的方法，通過對進出點的標記，以實現多邊形合并的完整性和準確性。

為實現上述目的，本發明提出如下技術方案：一種帶弧復雜多邊形快速合并的方法，其包括如下步驟：

S1，獲取第一多邊形和第二多邊形的點集為順時針排序，若為逆時針則修改為順時針；

S2，在第一多邊形的點集中尋找在第二多邊形外部點A或尋找第一多邊形所有線段的中點或弧的中點在第二多邊形外部點A，若找到點A則進行S5，若找不到則進行S3；

S3，若第一多邊形不帶弧，則以第二多邊形作為合并結果，若第一多邊形帶弧，則在第二多邊形內以S2的步驟找點A，若找到點A則進行S5，若找不到進行S4；

S4，若第二多邊形不帶弧，則以第一多邊形作為合并結果，若第二多邊形帶弧，則循環第二多邊形中的弧段R以及第一多邊形中所有直線線段L，若R與L相交且有兩個交點，取這個R在這兩個交點中間的點作為點A，則進行S5；若找不到R與L兩個交點，即找不到點A，則以第一多邊形作為合并結果；

S5，若點A在第二多邊形內找到，則將第一多邊形和第二多邊形進行對調，確保點A在第一多邊形內，同時將第一多邊形的所有點集進行重新排序，使得點A為第一多邊形點集中的第一個；

S6，從點A開始順時針遍歷第一多邊形中所有線段或弧段H，將H與第二多邊形的所有線段或弧段相交，若有交點，則將此交點添加到第一多邊形的點集中，若有多個交點，則按與H的起點距離從小到大排序添加，若有重疊點則剔除；

S7，添加交點時同時標注所有的進點、出點和中性點；

S8，順時針循環第一多邊形，遇到出點繼續順時針獲取第一多邊形的節點，遇到進點則進入第二多邊形的順時針獲取節點，遇到中性點繼續順時針獲取第一多邊形或第二多邊形的節點，最終完成多邊形的合并。

優選地，在所述S6中，在添加點的同時，標記交點在第二多邊形中的線段索引，若為弧則記錄弧的信息。

優選地，在所述S6中，在交點小于2的情況下，第二多邊形有一點在第一多邊形里面，則第二多邊形完全在第一多邊形內，則以第一多邊形作為合并結果；若第二多邊形有一點在第一多邊形外面，則第一多邊形和第二多邊形無法合并。

優選地，在所述S7中，所述中性點為除了進點和出點還在第二多邊形內或邊上的點。