複合長方形領域の内点と外点を分類するためのアルゴリズム―実装設計への応用―

佐藤　政生  橘　昌良  鳥居　司郎  大附　辰夫  

誌名
電子情報通信学会論文誌 D   Vol.J66-D    No.2    pp.214-219
発行日: 1983/02/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(386.4KB)>>
論文を購入


あらまし: 
本論文では，座標がディジタル化された平面上において，縦方向または横方向の線分で囲まれた閉領域（複合長方形領域と呼ぶ）と点の集合が与えられたとき，これらの点を，対象とする閉領域の内部にあるものと外部にあるものとに分類するためのアルゴリズムを提案する．次に，本アルゴリズムの計算時間が，閉領域の辺（境界を構成する線分）をm，与えられた点の数をnとしたときO（（m＋n）log m）となることを示す．本アルゴリズムは，計算機による図形処理の基本算法として有用であると考えられるが，具体的な応用例として，プリント基板の内層電源の設計結果の自動検証およびLSIマスクのデザインルールチェックについて考察する．