二次元スペース・モデリングの考察 : ポインタ方式空間表現による局所的図形処理

概要

論文の詳細を見る
LSI, 地図, 等大規模図形処理を効率化するためには, 図形の必要部分に注目した局所的処理を行うことが望ましい. 本論文では, これを実現するため図形空間をポインタで表現する新しい図形データ構造を提案し, その原理・応用・生成手法等につき考察する. 本方式によれば図形処理の基本となる隣接空間や重なり図形の検索が, 例外的な場合を除き局所的に可能になり, 処理時間は総図形頂点数N^☆と無関係でO(N^o)のオーダとなる. その結果, 局所的図形論理操作(AND, OR, 等),運動図形の衝突検出, 注目点近傍の探索, さらに図形データベースのメンテナンス, 等が例外的な場合を除きO(N^o)の時間で実現できる. また本方式は, 点, 折れ線から, 凹凸, 斜辺, 穴を含むステンドグラス風多色図形までを取り扱うことができる. これらの機能は, LSIレイアウト図の対話形デザインルール・チェック, 同コンパクション, 地図における道順探索, 等従来困難であったり, 長時間を要するとされていた処理のいくつかを実用的な速度で実現可能にするために役立つと考えられる.
一般社団法人情報処理学会の論文
1986-12-15