[發明專利]大規模集成電路版圖非結構網格偏心中點生成方法和系統

有效

• 申請號: 202010912374.6
• 申請日: 2020-09-03
• 公開（公告）號: CN112052641B
• 公開（公告）日: 2021-03-30
• 發明（設計）人: 唐章宏;鄒軍;黃承清;汲亞飛;王芬
• 申請（專利權）人: 北京智芯仿真科技有限公司
• 主分類號: G06F30/392
• 分類號: G06F30/392
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 李興林

1.一種大規模集成電路版圖非結構網格偏心中點生成方法，其特征在于，包括：

獲取待識別超大規模集成電路版圖中包含多個頂點的多個多邊形；

采用Delaunay三角剖分算法形成以多邊形頂點為網格節點的Delaunay三角形網格；

確定是否存在至少一條多邊形的邊與所述Delaunay三角形網格的邊相交；若存在，則判定與所述三角形的邊相交的所述多邊形的邊為丟失邊；否則，則判定所述多邊形的邊為恢復邊；

采用偏心中點恢復法對所述丟失邊進行恢復；

在恢復丟失邊的過程中確定所述恢復邊的直徑圓是否包含其他Delaunay三角形網格節點，且確定所述恢復邊的左三角形是否為質量差的三角形；若所述恢復邊的直徑圓包含其他Delaunay三角形網格節點，且所述恢復邊的左三角形為質量差的三角形，則判定所述恢復邊為被侵蝕的邊；所述多邊形邊的左三角形為存在這樣一個三角形，該多邊形邊同時為該三角形的邊且該邊的方向與該三角形的邊的方向相同；所述質量差的三角形為該三角形的外接圓的半徑與其最短邊的長度之比大于設定閾值的三角形，或為三角形的最小角小于設定的最小角閾值的三角形；

采用偏心中點消除法消除所述被侵蝕的邊；

返回確定所述是否存在至少一條多邊形的邊與所述Delaunay三角形網格的邊相交的步驟，直至所述多個多邊形中所有的丟失邊被恢復，所有的被侵蝕的邊被消除；

所述采用偏心中點恢復法對所述丟失邊進行恢復，具體包括：

從所述丟失邊的第一頂點A和第二頂點B分別出發，找到與所述丟失邊相交的邊的所有頂點；

確定與所述丟失邊相交的邊的所有頂點中與所述丟失邊的所述第一頂點A或所述第二頂點B距離最近的頂點，作為最近點C；如果交換第一頂點A和所述第二頂點B的位置使得

在所述丟失邊上按設定條件確定偏心中點O；所述設定條件為：所述偏心中點O使得∠COB等于所述設定的最小角閾值θ_threshold；

判斷線段和間的關系，若則將所述丟失邊的中點作為新的偏心中點O，若則所確定的偏心中點O位置不變；

將所述偏心中點O插入到所述丟失邊上，形成新的多邊形邊和同時將偏心中點O采用Delaunay三角剖分算法插入到所述Delaunay三角形網格中，形成第一Delaunay三角形網格；

判斷所述第一Delaunay三角形網格是否存在丟失邊；若存在丟失邊，則返回從所述丟失邊的第一頂點A和第二頂點B分別出發，找到與所述丟失邊相交的邊的所有頂點的步驟，直至所有丟失邊被恢復；

所述采用偏心中點消除法消除所述被侵蝕的邊，具體包括：

確定所述被侵蝕的邊的直徑圓中與所述被侵蝕的邊的第一頂點A′或第二頂點B′距離最近的一頂點C′；如果交換所述第一頂點A′和所述第二頂點B′的位置使得

在被侵蝕的邊上找到偏心中點O′，使得∠A′O′C′＝θ_threshold；其中，θ_threshold為所述設定的最小角閾值；

判斷線段和間的關系；若則將被侵蝕的邊的中點作為新的偏心中點O′，若則所確定的偏心中點O′位置不變；

將所述偏心中點O′插入到所述被侵蝕的邊上，形成新的邊和同時將所述偏心中點O′采用Delaunay三角剖分算法插入到所述Delaunay三角形網格中，形成第二Delaunay三角形網格；

判斷所述第二Delaunay三角形網格是否存在被侵蝕的邊；若存在被侵蝕的邊，則返回確定所述被侵蝕的邊的直徑圓中與所述被侵蝕的邊的第一頂點A′或第二頂點B′距離最近的一頂點C′的步驟，直至所有被侵蝕的邊被消除。

2.根據權利要求1所述的大規模集成電路版圖非結構網格偏心中點生成方法，其特征在于，所述若存在丟失邊，則返回從所述丟失邊的第一頂點A和第二頂點B分別出發，找到與所述丟失邊相交的邊的所有頂點的步驟，直至所有丟失邊被恢復，具體包括：

若存在丟失邊，則將所有所述第一Delaunay三角形網格中的丟失邊添加到丟失邊集合中；

從所述丟失邊集合中調取一丟失邊，并執行從所述丟失邊的第一頂點A和第二頂點B分別出發，找到與所述丟失邊相交的邊的所有頂點的步驟，直至所述丟失邊集合中的所有丟失邊均被恢復。