JPH03194666A - 図面拡大縮小方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、図形拡大縮小方式に関するもので、例えば
、ＬＳＩ（大規模集積回路）のレイアウト検証やアート
ワーク等に用いられる図形拡大縮小アルゴリズムに利用
して特に有効な技術に関するものである。

〔従来の技術〕

ＬＳＩのレイアウト検証やアートワーク等における基本
的な処理として、図形パターンの拡大及び縮小処理が必
要とされる。また、このような拡大及び縮小処理を実現
するための図形拡大縮小アルゴリズムとして、例えば、 （１）　１９８３年２月、■日立製作所発行のｒ中央研
究所研究報告Ｊ第１４６１７号、 （２）　１９８３年１２月、電子通信学会発行のｒ電子
通信学会論文誌Ｊ　Ｖｏｌ、Ｊ６６−Ｃ：ぬ１２、第１
１３２頁〜第１１３９頁、 （３１１９８８年７月、情報処理学会発行の「設計自動
化研究部会資料」第４３−４、 にそれぞれ記載される第１ないし第３の図形拡大縮小方
式が提案されている。

このうち、第１の図形拡大縮小方式では、第６図（ａ）
に例示されるように、拡大又は縮小後の頂点Ａ”〜Ｈ°
の座標を所定のアルゴリズムに従って演算し、これらの
頂点を連結することで、所定の出力図形が得られる。ま
た、第２の図形拡大縮小方式では、入力図形を、まず第
７図（ａ）に例示されるように、Ｘ軸方向に拡大又は縮
小し、次に第７図（ｂ）に例示されるように、Ｙ軸方向
に拡大又は縮小することで、所定の出力図形が得られる
。さらに、第３の図形拡大縮小方式では、入力図形を所
定方向に連結される一連のベクトルにより表現し、これ
らのベクトルを指定された拡大又は縮小幅だけ平行移動
することで、所定の出力図形が得られる。

〔発明が解決しようとする課題〕

ＬＳＩの高集積化が進み、レイアウトパターンが複雑化
されるのにともない、上記に記載される図形拡大縮小方
式にはそれぞれ次のような問題点が生じることが、本願
発明者等によって明らかとなった。すなわち、上記第１
の図形拡大縮小方式では、例えば入力図形の大きさが指
定される縮小幅より小さい場合、第６図（ｂ）に太線で
示されるような不正図形が出力される。また、第２の図
形拡大縮小方式では、入力図形を構成する各辺がＸ軸及
びＹ軸方向に平行又は４５度をなす方向にある場合に限
られるため、複雑なレイアウトパターン等に対処しにく
い、さらに、第３の図形拡大縮小方式では、特に隣接す
るベクトル対がその移動方向の前方において１８０度よ
り小さい角をなす場合において、各ベクトルの移動方向
に平行して想定される矩形の重なり部を排除するための
演算がそれぞれ必要となる。このため、演算処理に供す
べき図形データ量ならびに演算処理時間が増大し、設計
自動化システム等の処理能力が制限されるものである。

この発明の目的は、任意角の辺を有する入力図形に対し
て、不正図形を生じることなくかつ高速に対処しうる図
形拡大縮小方式を提供することにある。この発明の他の
目的は、ＬＳＩのパターン検証やアートワーク等に供さ
れる設計自動化システム等の信頼性及び機能性を高め、
その処理能力を高めることにある。

この発明の萌記ならびにその他の目的と新規な特徴は、
この明細書の記述及び添付図面から明らかになるであろ
う。

（ｔｓａを解決するための手段〕 本願において開示される発明のうち代表的なものの概要
を簡単に説明すれば、下記の通りである。

すなわち、入力図形を、例えば右回りに連結される一連
のベクトルにより表現し、上記一連のベクトルのそれぞ
れを指定される拡大又は縮小幅だけ平行移動した後、上
記一連のベクトルのうち、互いに隣接しその移動方向の
前方において１８０度より小さい角をなしかつ移動後に
交点を有するベクトル対を、上記交点よりその移動方向
の後方で抹消し、移動後交点を有しないベクトル対を、
これらのベクトルの移動前の頂点を経由する二つの連結
ベクトルを介して連結する。また、互いに隣接しその移
動方向の前方において１８０度より大きい角をなすベク
トル対を、新しく頂点を有するまで延長する。そして、
上記方法に従って連結された一連のベクトルに囲まれる
領域のうち、図形の重なり数が１以上となる有効領域を
抽出し、出力図形を得るものである。

〔作　用〕 上記した手段によれば、任意角の辺を有する入力図形に
対し、不正ＷＩ形を生しることなくかつ実質的に無効と
なるベクトルを早期に排除しつつ、拡大及び縮小処理を
高速に施しうる図形拡大縮小方式を実現できる。これに
より、ＬＳＩのパターン検証やアートワーク等に供され
る設計自動化システム等の信頼性及び機能性を高め、そ
の処理能力を高めることができる。

（実り例〕 第１図には、この発明が通用された図形拡大縮小方式の
一実施例の基本処理フロー図が示されている。また、第
２図には、第１図の図形拡大縮小方式による図形拡大処
理の−実り例の演算手順図が示され、第３図には、第２
図の図形拡大処理を説明するための概念図が示されてい
る。さらに、第４図には、第１図の図形拡大縮小方式に
よる図形縮小処理の一実施例の演算手順図が示され、第
５図には、第４図の図形縮小処理を説明するための概念
図が示されている。これらの図をもとに、この実施例の
図形拡大縮小方式の概要とその特徴を説明する。なお、
−この明細書において、図形の拡大とは、入力図形の各
辺を指定された拡大幅だけ均等に広げることを意味し、
縮小とは、入力図形の各辺を指定された縮小幅だけ均等
に縮めることを意味する。したがって、入力図形の各辺
と拡大又は縮小後の出力図形の各辺の長さの比率は、必
ずしも一定とはならない。

この実施例の図形拡大縮小方式は、特に制限されないが
、ＬＳＩのレイアウトパターン設計等に供される設計自
動化システムに、図形拡大縮小アルゴリズムとして折り
込まれる。この図形拡大縮小アルゴリズムにおいて、各
図形はその座標がディジタル化された平面上に表示され
、その拡大及び縮小処理は、第１図の基本処理フロー図
に従って順次進められる。

第１図において、入力図形は、特に制限されないが、右
回り方向に連結される一連のベクトルにより表現され、
その拡大及び縮小処理は、これらのベクトルのそれぞれ
を指定された拡大又は縮小幅だけ平行移動することによ
り開始される。

すなわち、第２図に例示される図形拡大処理の場合、例
えば８個の頂点Ａ−Ｈを有する入力図形は、第２図（ａ
）に示されるように、右回りに連結される８本のベクト
ルにより表現される。このうち、６１ｉ１の頂点Ａ、　
Ｃ，Ｄ、　Ｅ、　Ｇ及びＨをはさんでそれぞれ隣接する
二つのベクトルつまりベクトル対は、拡大時におけるそ
の移動方向の前方においてほぼ２７０度の移動角をなし
、残りの頂点Ｂ及びＦをはさんでそれぞれ隣接するヘク
トル対は、はぼ９０度の移動角をなす、入力図形を構成
する８本のベクトルは、まず第２図（ｂ）に示されるよ
うに、指定された拡大幅Ｗだけそれぞれ平行移動される
。その結果、頂点Ｂをはさんで隣接するベクトル対は、
交差して交点を有し、他の頂点をはさんでそれぞれ隣接
するベクトル対は、それぞれ分離され交点を有しない。

上記により平行移動された各ベクトルは、第１図に示さ
れるように、それぞれの移動角に応じて連結されあるい
は切断される。すなわち、各頂点をはさんで隣接するベ
クトル対が１８０度を超える移動角をなす場合、移動後
のベクトルは当然分離され、交点を有しない、第２図の
実施例の場合、６個の頂点Ａ、　Ｃ，Ｄ、　Ｅ、　Ｇ及
びＨをはさんでそれぞれ隣接するベクトル対は、第２図
（Ｃ）に示されるように、頂点を有するまでそれぞれ延
長され、これによって新しい頂点Ａ’　、Ｃ’　、Ｄ’
Ｅ’　、　Ｇ’及びＨｏが得られる。

一方、各頂点をはさんで隣接するベクトル対が１８０度
に満たない移動角をなす場合、移動後のベクトルは、そ
の両方が指定された拡大幅より長いとき交点を有し、そ
のいずれかが指定された拡大幅より短いとき交点を有し
ないものとなる。第２図の実施例の場合、頂点Ｂをはさ
んで隣接しかつ移動後に交点を有するベクトル対は、第
２図（Ｃ）に示されるように、その交点において切断さ
れ、その移動方向の後方において抹消される。そして、
このベクトル対の交点は、新しい頂点Ｂ゛とされ、これ
らのベクトルの抹消された部分に関する図形データは、
以後の演算処理において必要とされない、ところが、頂
点Ｆをはさんで隣接しかつ移ｉｌＩ後に交点を有しない
ベクトル対は、第２図（Ｃ）に示されるように、その一
方において、上記頂点Ｅ′及びＧｏに向かってそれぞれ
延長され、その他方において、移動前の頂点Ｆを経由す
る二つの連結ベクトルを介して連結される。その結果、
これらのベクトルの接点として、新しい頂点Ｆ゛が得ら
れる。

新しい頂点と移動前の一部の頂点ならびにこれらの頂点
を連結するベクトルにより表現される拡大図形は、第１
図に示されるように、さらにその有効領域のみが抽出さ
れ、所定の出力図形が得られる。すなわら、この実＆例
のＦｙＪ形拡大縮小方式では、図形の重なり数が０以下
となる領域は無効とされ、図形の重なり数が１以上とな
る領域のみが有効領域として抽出される。第２図の実施
例の場合、頂点Ａ゛ないしＨｏ及び頂点Ｆを結ぶ１０本
のベクトルにより囲まれる領域は、図形の重なり数が１
以上となる。このため、これらのベクトルに囲まれるす
べての領域が有効領域となり、第２図（ｄ）に示される
出力図形が得られる。

ところで、入力図形の拡大は、第３図（ｂ）に例示され
るように、指定された拡大幅Ｗを半径としかつ入力図形
の各辺にそって移動する円の外側の軌跡として定義され
る。そして、上記軌跡は、実質的に第３図（ｃ）に示さ
れる１本の曲線の外縁として表現でき、同図における図
形の重なり数が１以上となる部分を選択的に抽出するこ
とで、第３図（ｄ）の拡大図形が得られる。

ここで、図形の重なり数は、周知のように、図形の内側
において１とされ、外側において０とされる。そして、
右回りの曲線又はベクトルに囲まれる部分では、重なる
図形つまりｆＩｉ域の数に応じて加算され、左回りの曲
線又はベクトルに囲まれる部分では、重なる図形つまり
領域の数に応じて減算される。

言うまでもなく、上記第３図（Ｃ）の曲線は、等価的に
第２［（Ｃ）に実線で示される１０本のベクトルと点線
で示される抹消ベクトルとに対応し、第３図（ｄ）の拡
大図形は、第２図（ｄ）の出力図形に対応する。

次に、第４図に示される図形縮小処理の場合、例えば８
個の頂点Ａ−Ｈを有する入力図形は、上記図形拡大処理
の場合と同様に、右回りに連結される８本のベクトルに
よって表現される。このうち、６個の頂点Ａ、Ｃ，Ｄ、
Ｅ、Ｇ及びＨをはさんでそれぞれ隣接するベクトル対は
、縮小時における移動方向の両方においてほぼ９０度の
移動角をなし、残りの頂点Ｂ及びＦをはさんでそれぞれ
隣接するベクトル対は、はぼ２７０度の移動角をなす、
入力図形を構成する８本のベクトルは、まず第４図（ｂ
）に示されるように、指定された縮小幅Ｗだけそれぞれ
平行移動される。その結果、頂点Ａ、　Ｃ，Ｄ、及びＨ
をはさんで隣接するベクトル対は、交差して交点を有し
、他の頂点をはさんでそれぞれ隣接するベクトル対は、
それぞれ分離され交点を有しない。

上記により平行移動された各ベクトルは、前述のように
、それぞれの移動角に応じて連結されあるいは切断され
る。すなわち、各頂点をはさんで隣接するベクトル対が
１８０度を超える移動角をなす場合、移動後のベクトル
は当然分離され、交点を有しない、第４図の実施例の場
合、２個の頂点Ｂ及びＦをはさんでそれぞれ隣接するベ
クトル対は、第４図（Ｃ）に示されるように、頂点を有
するまでそれぞれ延長され、これによって新しい頂点Ｂ
′及びＦｏが得られる。

一方、各頂点をはさんで隣接するベクトル対が１８０度
に満たない移動角をなす場合、移動後のベクトルは、前
述のように、その両方が指定された拡大幅より長いとき
交点を有し、そのいずれかが指定された拡大幅より短い
とき交点を有しないものとなる。第４図の実施例の場合
、頂点Ａ、　Ｃ。

Ｄ及びＨをはさんでそれぞれ隣接しかつ移動後に交点を
有するベクトル対は、第４図（ｃ）に示されるように、
その交点において切断され、その移動方向の後方におい
て抹消される。そして、これらのベクトル対の交点は、
新しい頂点Ａ’　、Ｃ’Ｄ゛及びＨｏとされ、これらの
ベクトルの抹消された部分に関する図形データは、以後
の演算処理において必要とされない、ところが、頂点Ｅ
及びＧをはさんでそれぞれ隣接しかつ移動後に交点を有
しない複数のベクトル対は、第４図（Ｃ）に示されるよ
うに、その一方において、上記頂点Ｆ′に向かってそれ
ぞれ延長され、その他方において、移動前の頂点Ｅ及び
Ｇを経由する二つの連結ベクトルを介して連結される。

その結果、これらのベクトルの交点として、新しい頂点
Ｅ′及びＧｏが得られる。

新しい頂点と移動Ａｊの一部の頂点ならびにこれらの頂
点を連結するベクトルにより表現される縮小図形は、Ａ
ｉ１述のように、さらにその有効領域のみが抽出され、
所定の出力図形が得られる。したがって、第４図の実施
例の場合、新しい頂点Ａ。

ないしＨｏを結ぶベクトルによって囲まれる＠城は、図
形の重なり数が１以上となり、有効領域とされる。しか
し、頂点Ｅ゛から頂点Ｅ、Ｅ’　、Ｆ、Ｇ’　、Ｇ及び
Ｇｏを経由するベクトルによって囲まれる領域は、図形
の墓なり数がＯ以下となり、無効領域とされる。その結
果、第４図（ｄ）に示されるように、新しい頂点Ａ°な
いしＨｏとこれらの頂点を連結する８本のベクトルによ
り表現される所定の出力図形が得られる。

ところで、入力図形の縮小は、第５図（ｂ）に例示され
るように、指定された縮小幅Ｗを半径としかつ入力図形
の各辺にそって移動する円の内側の軌跡として定義され
る。そして、上記軌跡は、実質的に第５図（ｅ）に示さ
れる１本の曲線の内縁として表現でき、同図における図
形の重なり数が１以上となる部分を選択的に抽出するこ
とで、第５図（ｄ）の縮小図形が得られる。

言うまでもなく、上記第５図（Ｃ）の曲線は、等価的に
第３図（ｃ）に実線で示される１２本のベクトルと点線
で示される抹消ベクトルとに対応し、第５図（ｄ）の縮
小図形は、第３図（ｄ）の出力図形に対応する。

最後に、上記図形縮小処理において、入力図形を構成す
る辺のいずれかが指定された縮小幅Ｗより短い場合、第
６図に示される従来の図形拡大縮小方式と同様に、不本
意な虚の図形が生じる。ところが、この虚の図形は、上
記説明から明らかなように、図形の重なり数が０以下と
なるため、結果的に不正図形は残存しない。

以上のように、この実施例の図形拡大縮小方式では、入
力図形が、右回りに連結される一連のベクトルにより表
現され、これらのベクトルが、まず指定された拡大又は
縮小幅だけそれぞれ平行移動される。このうち、互いに
隣接しその移動方向の前方において１８０度より小さい
移動角をなしかつ移動後に交点を有するベクトル対は、
上記交点よりその移動方向の後方で抹消され、移動後に
交点を有しないベクトルは、これらのベクトルの移動ｉ
ｊの頂点を経由する二つの連結ベクトルを介して連結さ
れる。さらに、互いに隣接しその移動方向の前方におい
て１８０度より大きい移動角をなすベクトル対は、新し
く頂点を有するまで延長される。そして、上記方法に従
って連結された一連のベクトルに囲まれる領域のうち、
図形の重なり数が１以上となる領域のみが選択的に抽出
され、これによって所定の出力図形が得られる。その結
果、この実施例の図形拡大縮小方式は、任意角の辺を有
する入力図形に対し、不正図形を生じることなく、高速
に対処することができる。また、上ｔ！図形拡大及び縮
小処理の過程で、実質的に無効となるベクトルは、早期
に切断・抹消される。このため、相応して図形データの
必要量が削減され、図形拡大及び縮小処理に要する演算
処理時間が短縮されるものとなる。

以上の本実施例に示されるように、この発明をＬＳＩの
レイアウト設計自動化システムの図形拡大縮小アルゴリ
ズムに通用することで、次のような作用効果が得られる
。すなわち、 １１）入力図形を、例えば右回りに連結される一連のベ
クトルにより表現し、上記一連のベクトルのそれぞれを
指定される拡大又は縮小幅だけ平行移動した後、上記一
連のベクトルのうち、互いに隣接しその移動方向の前方
において１８０度より小さい角をなしかつ移動後に交点
を有するベクトル対を、上記交点よりその移動方向の後
方で抹消し、移動後交点を有しないベクトル対を、これ
らのベクトルの移動前の頂点を経由する二つの連結ベク
トルを介して連結する。また、互いに隣接しその移動方
向のｉ方において１８０度より大きい角をなすベクトル
対を、新しく頂点を有するまでそれぞれ延長する。そし
て、上記方法に従って連結された一連のベクトルに囲ま
れる領域のうち、図形の重なり数が１以上となる領域を
選択的に抽出し、出力図形を得る。これにより、任意角
の辺を有する入力図形に対し、不正図形を生じることな
く対処しうる図形拡大縮小方式を実現できるという効果
が得られる。

（２）上記（１）項において、実質的に無効となるベク
トルを早期に排除できるため、拡大及び縮小処理に必要
な図形データ量を削減し、演算処理時間を短縮できると
いう効果が得られる。

（３）上記＋１１項及び（２）項により、ＬＳＩのパタ
ーン検証やアートワーク等に供される設計自動化システ
ム等の信頼性及び機能性を高め、その処理能力を高める
ことができるという効果が得られる。

以上本発明者によってなされた発明を実施例に基づき具
体的に説明したが、この発明は上記実施例に塵定される
ものではな（、その要旨を逸脱しない範囲で種々変更可
能であることはいうまでもない０例えば、入力図形を構
成するベクトルは、左回りに連結されるものであっても
よい、また、入力図形は、その内側に穴部すなわち窓部
を持つものであってもよい、この場合、これらの窓部を
構成するベクトルは、図形の外形を構成するベクトルと
逆回りすなわち左回りに連結されることを必要条件とす
る。

以上の説明では主として本発明者によってなされた発明
をその背景となった利用分野であるＬＳＩのレイアウト
設計自動化システムの図形拡大縮小アルゴリズムに通用
した場合について説明したが、それに限定されるもので
はなく、例えば、同様な機能を有する電子線描画装置等
にも通用できる０本発明は、少な（とも図形パターンの
拡大及び紬小義能を有するシステム又はそのアルゴリズ
ムとして広く通用できる。

〔発明の効果〕 本願において開示される発明のうち代表的なものによっ
て得られる効果を簡単に説明すれば、下記のとおりであ
る。すなわち、入力図形を、例えば右回りに連結される
一連のベクトルにより表現し、上記一連のベクトルのそ
れぞれを指定される拡大又は縮小幅だけ平行移動した後
、上記一連のベクトルのうち、互いに隣接しその移動方
向の前方において１８０度より小さい移動角をなしかつ
移動後交点を有するベクトル対を、上記交点よりその移
動方向の後方で抹消し、移動後交点を有しないベクトル
対を、これらのベクトルの移動Ｍｊの頂点を経由する二
つの連結ベクトルを介して連結する。また、互いに隣接
しその移動方向の前方において１８０度より大きい移動
角をなすベクトル対を、頂点を有するまでそれぞれ延長
する。そして、上記方法に従って連結された一連のベク
トルに囲まれる領域のうち、図形の重なり数が１以上と
なる領域を選択的に抽出し、出力図形を得る。

これにより、任意角の辺を有する入力図形に対し、不正
図形を生じることなくかつ実質的に無効となるベクトル
を早期に排除しうる図形拡大縮小方式を実現できる。そ
の結果、ＬＳＩのパターン検証やアートワーク等に供さ
れる設計自動化システム等の信頼性及び機能性を高め、
その処理能力を高めることができる。

【図面の簡単な説明】

第１図は、この発明が適用された図形拡大縮小方式の−
実り例を示す基本処理フロー図、第２図は、第１図の図
形拡大縮小方式による図形拡大処理の−実り例を示す演
算手順図、第３図は、第２図の図形拡大処理を説明する
ための概念図、 第４図は、第１図の図形拡大縮小方式による図形縮小処
理ψ一実施例を示す演算手順図、第５因は、第４図の図
形縮小処理を説明するための概念図、 第６図は、従来の図形拡大縮小方式の一例を示す演算手
順図、 第７図は、従来の図形拡大縮小方式の他の一例を示す演
算手順図である。 第 １ 図 入力図形 出力図形 第 図 第 図 第 図 紀 ５ 図 第 図 第 図

Claims (1)

1. 【特許請求の範囲】 １、入力図形を、所定方向に連結される一連のベクトル
   により表現し、上記一連のベクトルのそれぞれを指定さ
   れる拡大又は縮小幅だけ平行移動した後、上記一連のベ
   クトルのうち、互いに隣接しその移動方向の前方におい
   て１８０度より小さい角をなしかつ移動後に交点を有す
   るベクトル対を、上記交点よりその移動方向の後方にお
   いて抹消して処理することを特徴とする図形拡大縮小方
   式。 ２、上記一連のベクトルは、右回りに連結されるもので
   あって、上記一連のベクトルのうち、互いに隣接しその
   移動方向の前方において１８０度より小さい角をなしか
   つ移動後に交点を有しないベクトル対は、これらのベク
   トルの移動前の頂点を経由する二つの連結ベクトルを介
   して連結され、互いに隣接しその移動方向の前方におい
   て１８０度より大きい角をなすベクトル対は、新しく頂
   点を有するまで延長されることを特徴とする特許請求の
   範囲第１項記載の図形拡大縮小方式。 ３、上記入力図形の拡大又は縮小図形は、上記方法に従
   って連結された一連のベクトルに囲まれる領域のうち、
   図形の重なり数が１以上となる領域を抽出することによ
   って得られるものであることを特徴とする特許請求の範
   囲第１項又は第２項記載の図形拡大縮小方式。