設計法則檢驗器是超大型積體電路計算機輔助設計的工具之一，而光罩的布林運算是
建立檢驗器的重要過程。本文旨在提出一簡易、快速的演算法，藉此建立一檢驗器系
統。在現有的演算法中常發生的嚴重缺點，即將非錯誤指為錯誤，所謂假錯。例如「
掃描法」中將原已相接的圖型視為過窄的「接連」假錯。其他方面，如「邊緣法」中
的錯誤重複指示，圖型間頂點對頂點需要額外的處理，「方形法」則需耗費許多時間
去計算圖型間的交點。本文所提出的演算法均能對上列缺點一一解除。所耗的「期望
時間」與「期望空間」則分別為O（nlogn）與O（n1/2），n為垂直或水平線段之一種
的數目。結果顯示比「方形法」和「邊緣法」來得快速、易懂。
|