スペースモデルによる二次元図形処理システムの試作 : 注目,局所集合演算,運動図形の衝突検出

概要

論文の詳細を見る
スペース.モデリングは図形空間をポインタで表現し,局所処理により図形処理を効率化する,二次元・三次元一貫した新しい図形データ構造のコンセプトである.スペースモデルの応用範囲は広いが,今回の試作は基本原理・性能の確認を目的とし,二次元多角形に関するデータ構造生成,注目,隣接空間検索,図形集合演算,運動図形の衝突検出,表示に範囲を限定した.実験結果は原理どおり,局所処理により良好な対話性能を得ることができた.必要な図形への注目時間はCPU時間で4〜5ms(CPU68020,演算コプロセッサ付き),隣接空間検索は200μs,注目した多角形と他の多角形との集合演算は1ms以下,衝突検出は運動経路長に比例するが短距離ならば1秒以下と高速である.これらは原理的に全体図形数によらずO(1)の処理である.また大最図形の一括データ構造生成時間は一頂点(交点を含む)あたり4ms以下となり,これも原理どおり全体でO(N)(Nは交点を含む総頂点数)であることがデータで裏づけられた.その他,表示すべき重なり図形を後から塗消さないため,本モデルの包含図形検索機能を使って,常に外側図形から表示するよう高速に表示順序を決める方式もテストした.
一般社団法人情報処理学会の論文
1988-10-15