[發明專利]一種適用于任意兩多邊形之間的內靠接臨界多邊形的計算方法

在審

• 申請號: 201710236536.7
• 申請日: 2017-04-12
• 公開（公告）號: CN107146249A
• 公開（公告）日: 2017-09-08
• 發明（設計）人: 劉海明;吳忻生;徐將將
• 申請（專利權）人: 華南理工大學
• 主分類號: G06T7/62
• 分類號: G06T7/62
• 代理公司: 廣州市華學知識產權代理有限公司44245
• 代理人: 李斌

1.一種適用于任意兩多邊形之間的內靠接臨界多邊形的計算方法，其特征在于，對于給定的任意形狀的兩個多邊形A、B，計算多邊形B相對多邊形A的內靠接臨界多邊形，計算方法具體包括如下步驟：

S1、將多邊形A的表示方向進行反向處理；

S2、判斷一個多邊形B的各個角頂點與另一個多邊形A各個矢量邊的接觸情況，并且判斷一個多邊形B的各個矢量邊與另一個多邊形A的各個角頂點的接觸情況，生成兩個多邊形的各個角頂點與各條矢量邊之間能接觸的所有“角頂點-矢量邊”組合；

S3、多邊形B的參考點選取，多邊形B輪廓邊上的任意一個點，包括其角頂點和矢量邊上的點，均可選為參考點；

S4、計算產生初始的矢量線段集合，利用步驟S2得到的能接觸的“角頂點-矢量邊”組合以及步驟S3選取的參考點，讓多邊形B的各個角頂點在A的能接觸的矢量邊上移動，并且讓多邊形B的各個矢量邊在A的能接觸的角頂點上移動，以上參考點的移動將產生矢量線段；產生的所有矢量線段構成初始的矢量線段集合，兩個多邊形之間的內靠接臨界多邊形必定包含在上述方式產生的矢量線段之中；

S5、矢量線段的分割處理，此步驟對在步驟S4中計算產生初始的矢量線段進行分割處理；

S6、濾除矢量線段集合中無效的矢量線段，得到后面合成內靠接臨界多邊形時所需的矢量線段集合；

S7、通過篩選矢量線段合成內靠接臨界多邊形；

S8、計算內靠接臨界多邊形可能存在的退化情形，包括退化點和退化線兩種情形。

2.根據權利要求1所述的一種適用于任意兩多邊形之間的內靠接臨界多邊形的計算方法，其特征在于步驟S2中判定一個多邊形的各個角頂點與另一個多邊形各個矢量邊是否接觸的方法為：

若角頂點的出邊相對于其入邊逆時針轉過的角度大于180度，則判斷角頂點和矢量邊不可能接觸；若不大于180度，且該矢量邊位于角頂點的入邊與出邊反向延長線所構成的逆時針方向夾角區域內，則判斷為兩者能接觸；通過此步驟，可計算獲得兩個多邊形的各個角頂點與各條矢量邊之間能接觸的所有“角頂點-矢量邊”組合。

3.根據權利要求1所述的一種適用于任意兩多邊形之間的內靠接臨界多邊形的計算方法，其特征在于步驟S4中產生初始的矢量線段集合的獲取包括兩個部分：

(1)、針對多邊形B的角頂點與多邊形A的矢量邊的每個能接觸“角頂點-矢量邊”組合，先平移多邊形B使其在組合中的角頂點與A中對應矢量邊的起點重合，然后沿矢量邊方向平移多邊形B，直到該角頂點到達該矢量邊的終點位置，且多邊形B在平移過程中始終保持其角頂點與該矢量邊相接觸，此過程中多邊形B的參考點的移動將產生一條矢量線段，通過這一計算，可產生一組基于多邊形B角頂點和多邊形A矢量邊的能接觸“角頂點-矢量邊”組合的矢量線段；

(2)、針對多邊形A的角頂點與多邊形B的矢量邊的每個能接觸“角頂點-矢量邊”組合，先平移多邊形B使其在該組合中的矢量邊的起點與A中對應的角頂點重合，然后沿該矢量邊的反方向平移多邊形B，直到該矢量邊的終點到達角頂點位置，且多邊形B在平移過程中始終保持其矢量邊與該角頂點相接觸，此過程中多邊形B的參考點的移動也將產生一條矢量線段，通過這一計算，可產生一組基于多邊形A角頂點和多邊形B矢量邊的能接觸“角頂點-矢量邊”組合的矢量線段；

其中上述兩部分計算得到的兩組矢量線段構成本算法所需的初始的矢量線段集合。

4.根據權利要求1所述的一種適用于任意兩多邊形之間的內靠接臨界多邊形的計算方法，其特征在于步驟S5的矢量線段分割處理包括兩種情形：

①若矢量線段之間存在相交，其中兩線段重合或部分重合，以及一線段的端點與另一線段的端點重合不在此范疇內，則計算出它們的交點，并用交點分割該交點所在的矢量線段，每個交點都將其所在的矢量線段分割成兩條矢量線段；

②若某些矢量線段出現重合，其中長度相同的矢量線段完全重合的情形不在此范疇內，則用矢量線段位于重合部分的端點來分割矢量線段；

上述兩種情形的分割處理僅針對初始矢量線段集合中滿足所述兩種情形條件的矢量線段，分割得到的新矢量線段將加入矢量線段集合，而被分割的矢量線段則從集合中剔除；那些無需分割的矢量線段仍保留在集合中。