[發(fā)明專利]一種圖形連通區(qū)域的快速追蹤方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010396904.6
• 申請(qǐng)日: 2020-05-12
• 公開（公告）號(hào): CN111553124B
• 公開（公告）日: 2022-06-17
• 發(fā)明（設(shè)計(jì)）人: 李相啟;謝林君;陸濤濤;劉偉平
• 申請(qǐng)（專利權(quán)）人: 北京華大九天科技股份有限公司
• 主分類號(hào): G06F30/392
• 分類號(hào): G06F30/392
• 代理公司: 北京德崇智捷知識(shí)產(chǎn)權(quán)代理有限公司 11467
• 代理人: 王金雙

一種圖形連通區(qū)域快速追蹤方法，其特征在于，包括以下步驟：1）對(duì)每層金屬和通孔圖形進(jìn)行id標(biāo)記，建立k?d樹；2）創(chuàng)建不相交集維護(hù)圖形之間的連接關(guān)系；3）針對(duì)每層金屬圖形，以其邊框在本層k?d樹內(nèi)查詢或去相連接的通孔層做查詢；4）針對(duì)每層通孔圖形，以及其連接的每一層金屬，以該通孔去金屬層k?d樹做查詢；5）通過(guò)不相交集獲取所有連通區(qū)域的圖形。本發(fā)明的圖形連通區(qū)域快速追蹤方法，減少了金屬層是否與通孔相交的檢查次數(shù)，通孔層需要做查詢的通孔數(shù)量也會(huì)減少，從而極大的改進(jìn)追蹤的性能；根據(jù)原始輸入圖形的特征，有效減少判斷圖形之間連接性的次數(shù)，從而大幅度改進(jìn)追蹤性能。

技術(shù)領(lǐng)域

本發(fā)明涉及半導(dǎo)體集成電路自動(dòng)化設(shè)計(jì)技術(shù)領(lǐng)域，特別是涉及后端版圖設(shè)計(jì)、電阻、電容提取方法。

背景技術(shù)

在平板顯示設(shè)計(jì)中，針對(duì)超大規(guī)模版圖，為了改進(jìn)提取性能以及提取精度，會(huì)針對(duì)一些圖形做切割，切割后會(huì)針對(duì)不同性質(zhì)的區(qū)域做不同的提取方式，而切割后的一些區(qū)域的連接關(guān)系需要重新構(gòu)建，但構(gòu)建后的圖形連接關(guān)系復(fù)雜，降低了追蹤（trace）的性能。

發(fā)明內(nèi)容

為了解決現(xiàn)有技術(shù)存在的不足，本發(fā)明的目的在于提供一種圖形連通區(qū)域的快速追蹤方法，根據(jù)原始輸入圖形的特征，有效減少判斷圖形之間連接性的次數(shù)，從而大幅度改進(jìn)追蹤性能。

為實(shí)現(xiàn)上述目的，本發(fā)明提供的圖形連通區(qū)域快速追蹤方法，其特征在于，包括以下步驟：

1）對(duì)每層金屬和通孔圖形進(jìn)行id標(biāo)記，建立k-d樹；

2）創(chuàng)建不相交集維護(hù)圖形之間的連接關(guān)系；

3）針對(duì)每層金屬圖形，以其邊框在本層k-d樹內(nèi)查詢或去相連接的通孔層做查詢；

4）針對(duì)每層通孔圖形，以及其連接的每一層金屬，以該通孔去金屬層k-d樹做查詢；

5）通過(guò)不相交集獲取所有連通區(qū)域的圖形。

進(jìn)一步地，步驟3）所述針對(duì)每層金屬圖形，以其邊框在本層k-d樹內(nèi)查詢的步驟，進(jìn)一步包括，

如果查詢到區(qū)域內(nèi)存在其他圖形，對(duì)圖形做梯形化，每一個(gè)梯形圖形的id都標(biāo)記為原始圖形的id，以該梯形的邊框在本層做查詢。

進(jìn)一步地，進(jìn)一步包括以下步驟：

如果查詢到大于一個(gè)的圖形，不做處理；否則以梯形化后圖形的邊框去相連接的通孔層做查詢，對(duì)查詢到的圖形不用檢查是否相交，直接標(biāo)記金屬圖形與通孔連通，以及查詢到的通孔圖形在金屬層上被查詢到的信息。

進(jìn)一步地，步驟3）所述針對(duì)每層金屬圖形，以其邊框去相連接的通孔層做查詢的步驟，進(jìn)一步包括，

以金屬圖形的邊框去相連接的通孔層做查詢，對(duì)查詢到的通孔圖形標(biāo)記：金屬圖形與通孔連通、其在金屬層上被查詢到的信息。

更進(jìn)一步地，所述步驟4）進(jìn)一步包括：

如果通孔圖形已經(jīng)標(biāo)記被查詢到過(guò)，則忽略該通孔；

以該通孔去金屬層k-d樹做查詢，如果查詢到的通孔是矩形，則標(biāo)記通孔圖形與金屬圖形連接，否則檢查通孔是否與金屬圖形連通。

為實(shí)現(xiàn)上述目的，本發(fā)明還提供一種計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)，其上存儲(chǔ)有計(jì)算機(jī)程序，所述計(jì)算機(jī)程序運(yùn)行時(shí)執(zhí)行如上文所述的圖形連通區(qū)域快速追蹤方法的步驟。

為實(shí)現(xiàn)上述目的，本發(fā)明還提供一種圖形連通區(qū)域快速追蹤設(shè)備，包括存儲(chǔ)器和處理器，所述存儲(chǔ)器上儲(chǔ)存有在所述處理器上運(yùn)行的計(jì)算機(jī)程序，所述處理器運(yùn)行所述計(jì)算機(jī)程序時(shí)執(zhí)行如上文所述的圖形連通區(qū)域快速追蹤方法的步驟。

本發(fā)明的圖形連通區(qū)域快速追蹤，具有以下有益效果：