JPH08129649A - ノードリンク構造レイアウト方法及びマシン動作方法 - Google Patents

Abstract

(57)【要約】 【課題】 ノードリンク構造を密度のばらつきなくレイ
アウトする。 【解決手段】 本発明は、指数関数的に増大するブラン
チを有するノードリンク構造20を容易に均一にレイアウ
トするために、負の曲率を有するレイアウト空間32では
円の面積がその半径の指数関数に比例するという特徴を
利用する。まず、ノードリンク構造20の親ノードの位置
及び子ノードの位置に対するレイアウト空間内位置を示
すレイアウトデータ30が得られる。この子位置42、44、
46は、下位レベルノード数と共にゆっくりと増大する関
数を近似する半径を有する円48に沿って隣接するため、
子位置同士の間の離間は全てブランチ内で略均一であ
る。レイアウトデータが用いられて、第１の表現が表示
される。ユーザからの位置変更信号があれば、第１の表
現の変更された継続として知覚されることができる第２
の表現が表示されることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ノードリンク構造
のレイアウトに関する。

【０００２】

【従来の技術及び発明が解決しようとする課題】ギンド
ン，アール．エドワード（Guindon, R., Ed., ）の「人
間とコンピュータの対話のための認識科学とその応用
（Congnitive Science and its Application for Human
Computer Interaction ）」［ニュージャージー州ヒル
ズデイルのローレンスアールバウム（Lawrence Erlbau
m）、１９８８年］のＰ２０１〜Ｐ２３３におけるフェ
アチャイルド，ケイ．エム．（Fairchild, K.M. ）、ポ
ルトロック，エス．イー．（Poltrock, S.E.）、ファー
ナス，ジー．ダブリュ．（Furnas, G.W.）の「セムネッ
ト（ＳｅｍＮｅｔ）：大規模知識ベースの３次元グラフ
ィック表示（Three-Dimensional Graphic Representati
ons of Large KnowledgeBases）」は、セムネット即ち
３次元グラフィカルインタフェースについて述べてい
る。

【０００３】図１−１に関して示され且つ述べられてい
るように、セムネットは、知識ベースを３次元空間にお
いて有向グラフとして表し、該有向グラフは、線又は弧
で連結されてラベル付けされた矩形として表された知識
エレメントを有する。

【０００４】本発明の一態様は、ノードリンク構造のレ
イアウトにおける基本的な問題を軽減する。ノードリン
ク構造中の情報は、構造を横断するにつれて指数関数的
に増大する傾向がある。例えば、ノードリンク構造が、
ルートノードと、ルートノードより低いレベルのノード
とを有するツリー又は他の階層（hierarchy ）的構造で
ある場合には、ノード数と、それ故にツリーにおける情
報量とは、ルートから下位レベルになるにつれて、指数
関数的に増大する傾向がある。ノードリンク構造の表現
をディスプレイする場合等いくつかのアプリケーション
では、各ノードが他のノードから十分に離間された独自
の位置を有するように、１つの空間にノードリンク構造
をレイアウトすることが有益である。ノード数及びツリ
ーにおける情報量が指数関数的に増大することにより、
１つの空間にノードリンク構造をレイアウトすることは
困難である。

【０００５】いくつかの従来技術は、２次元、３次元、
又はそれ以外のｎ次元のユークリッド空間においてノー
ドリンク構造をレイアウトする。例えば、上述のフェア
チャイルド他の技術はノードを３次元空間に配置する
が、それは一部には、ノードを平面に配置すると弧が交
わってしまうからである。ロバートソン（Robertson ）
他の米国特許第５，２９５，２４３号は、回転するサブ
構造を有する階層的構造を３次元空間に配置する技術に
ついて述べている。

【０００６】ユークリッド空間におけるレイアウトは例
えば、ルートノードから始まり、空間に各ノードを配置
しながら構造を横断する。ユークリッド空間におけるレ
イアウトは、指数関数的な増大のために、密度において
大きなばらつきを含みがちである。ブランチにおけるノ
ードは、ルートに近いノードよりもずっと密度が高い傾
向がある。密度に大きなばらつきがあると、このような
レイアウトに基づいて走査検索を使用するユーザが、密
度の異なる領域におけるノード同士の関係を理解するこ
とが困難であるため、レイアウトの使用において問題が
生じる。

【０００７】

【課題を解決するための手段】本発明の技術は、指数関
数的に増大するブランチを有するノードリンク構造が、
負の曲率を有する空間では密度の大きなばらつきを有す
ることなくレイアウトされることができるという発見に
基づくものである。空間は、平行な線が発散する場合に
負の曲率を有する。本発明の実施の形態は、ｎ次元の双
曲的空間（２次元の双曲的空間は「双曲面」と呼ばれ
る）を含む。双曲面では、例えば、円の面積はその半径
の指数関数に比例するので、指数関数的に増大するブラ
ンチを有するノードリンク構造の均一なレイアウトを得
ることが容易である。負の曲率を有するレイアウト空間
は、レイアウト空間における位置が限られた精度で特定
される場合に、双曲面又は負の曲率を有する他の連続的
空間に対する「ディスクリート（離散的）な近似」と呼
ばれ、レイアウト空間における全ての位置は、双曲面又
は負の曲率を有する他の連続的空間における位置にマッ
ピング（写像）されるが、逆は成り立たない。

【０００８】各技術は、負の曲率を有するレイアウト空
間においてノードリンク構造の部分の位置を示すレイア
ウトデータを使用する。レイアウトデータは例えば、レ
イアウト空間における位置を示す座標を含む。レイアウ
トデータは、ブランチを形成するノードの集合の中の各
ノードに対するレイアウト空間における位置を示す。親
ノードの集合の中の各々に関して言えば、親ノードを共
有する下位レベルのノードは、空間における円又は円の
弧に略沿った形で存在し、親ノードはその円の略中心に
位置される。ここで使用するように、「円に沿って」と
は、円の弧に沿った配列も含まれる。各円に沿って隣接
する下位レベルのノードの位置は、おおよそ基底スペー
シング（間隔）だけ離間される。集合中の全親ノードの
円の半径は共に半径方向離間関数を近似し、該関数は、
半径と円に沿って隣接する下位レベルのノード同士間の
離間とが全てブランチ内で略均一となるように、下位レ
ベルのノード数と共にゆっくりと増大する。

【０００９】ブランチの略均一なレイアウトは非常に有
益である。例えば、ブランチを含むノードリンク構造の
表現をディスプレイすることにおいて、さらなるレイア
ウトが必要でなくなる、即ち、レイアウト空間において
厳密な変換を実行して変換された位置を得ることによ
り、そして、この変換位置から、ディスプレイ上に表さ
れることのできる平坦なユークリッド領域（円形、ディ
スク形状領域、若しくは任意の他の適切な形状の領域
等）へとマッピングすることにより、表現が得られるこ
とができる。

【００１０】レイアウト空間は、例えば双曲面のディス
クリートな近似であることが可能であり、レイアウトデ
ータは、双曲面における位置を一体となって示す２つの
座標を各ノードに対して示すことができる。ノードリン
ク構造は、ツリー等の非循環グラフであることが可能で
ある。

【００１１】本発明の一態様は、ノードリンク構造の表
現のディスプレイに関する。この技術では、レイアウト
データを使用して、ノードリンク構造の第１の表現をデ
ィスプレイ上に表示する。第１のディスプレイ位置から
第２のディスプレイ位置への変更を示すユーザからの信
号に応答して、この技術は次に、第１の表現の移動され
た継続として認知される第２の表現を示す。第１の表現
は、第１のディスプレイ位置付近に、ノードリンク構造
の第１の部分を表す第１の特徴を含み、また第２の表現
は、前記第１の部分を示すものの第２のディスプレイ位
置付近にある第２の特徴を含む。

【００１２】本発明の別の態様は、上述のレイアウトデ
ータを得るための技術を提供する。この技術は、上述の
レイアウトデータを得るためにノードリンク構造を規定
するノードリンクデータを使用する。この技術は次に、
レイアウトデータを使用して、２つ以上の異なるマッピ
ングを実行する。各マッピングにより得られたマッピン
グデータは、ノード集合の部分集合に対する位置を示
す。例えば位置は、ディスプレイ位置、又は別の適切な
空間における位置であることが可能である。

【００１３】本発明のまた別の態様は、レイアウトデー
タが双曲面のディスクリートな近似における位置を示す
場合に、上述の変換データを得る技術を実行する際に生
じる問題の認識に基づく。変換が純粋な平行移動（tran
slation ）である場合には、回転に関する問題が生じ
る。双曲面において直線に対して平行移動を実行する
と、その直線上にない点がその直線上の点に対して回転
されるので、直覚的にわからなくなるおそれがある。さ
らに、閉ループを形成する一連の平行移動は、その各々
が、平行移動のその直線に沿ってオリエンテーション
（配向）を保持するので、この場合もまた反直覚的な回
転を生じる。

【００１４】本発明のこの態様は、回転の問題を軽減す
る技術を提供する。各技術は、回転成分を含む変換を提
供する。この技術は、より大きなスペーシングの領域に
おける子ノードが、例えば常にその親ノードの右にとい
うように、正規のオリエンテーションで表されるように
回転作用する。別の技術は、ノードリンク構造のルート
ノードのオリエンテーションを保持するように回転作用
する。

【００１５】上述の技術は、指数関数的に増大するノー
ドリンク構造が、負の曲率を有する面において均一にレ
イアウトされることができるため、有利である。例え
ば、一旦ノードリンク構造が双曲面にレイアウトされる
と、そのノードリンク構造を再度レイアウトする必要が
ない、即ち、同一のレイアウトを変換して、他の望まし
い表現を生成することができる。双曲面は、ディスク等
のディスプレイ領域にマッピングされて、或る部分はよ
り詳細に示し、他の部分は詳細に示さないことができる
ので、詳細に示された部分の内容を見ることができる。
さらに、２つの表現同士間の任意の変換が同じ時間量で
なされることができるので、高品質のアニメーションを
用いたナビゲーションが可能となる。アニメーション速
度で表される一続きの画像は、構造の複数の部分の位置
を変えながら、継続したものとして知覚されることがで
きる。従ってユーザは、或る部分の位置の変更を指示す
ることができ、マシンは、指示された通りにその部分が
移動された画像を自動的に表すことができる。このこと
は、ユーザが構造の任意の部分に変更の的を当てること
ができることを示している。

【００１６】本発明の請求項１の態様は、ノードリンク
構造レイアウト方法であって：レイアウトデータを得る
ステップを有し；該レイアウトデータは、ノードリンク
構造部分に対するレイアウト空間内位置を示し；前記レ
イアウト空間は負の曲率を有する空間であり；前記ノー
ドリンク構造は、ノード及びリンクを含み、各リンクは
ノードの中の少なくとも２つに関連し；前記レイアウト
データは、ノード集合に対するレイアウト空間内位置を
示し；前記ノード集合は、最上位レベルと少なくとも１
つの下位レベルとを含む２つ以上のノードレベルを有す
るブランチを形成し、該最上位レベルが最上位レベルノ
ードを含み、該下位レベルが下位レベルノードを含み、
各下位レベルにおける各ノードが、次に高いレベルに親
ノードを有すると共にこの親ノードに１つのリンクを介
して関連づけられ；２つ以上の親ノードの集合中の各々
に対して、前記レイアウトデータが、親ノードに対する
レイアウト空間における親位置を示し、また前記レイア
ウトデータが、親ノードを共有する多数の下位レベルの
ノードに対するレイアウト空間における円に略沿った形
で存在する子位置を示し、前記親位置が前記円の略中心
にあり、前記下位レベルノード数が２つ以上であり、円
に沿って隣接する子位置が略基底スペーシングだけ離間
され；前記円が、下位レベルノード数と共にゆっくりと
増大する関数を近似する半径を有し、よって該半径と、
円に沿って隣接する子位置同士間のスペーシングとが全
て前記ブランチ内で略均一であり；前記方法がさらに、
前記レイアウトデータを用いてノードリンク構造の第１
の表現をディスプレイ上に表示するステップを有し；ユ
ーザからの信号を受け取るステップを有し；該信号が第
１のディスプレイ位置から第２のディスプレイ位置への
変更を示し；前記第１の表現が第１のディスプレイ位置
付近に第１の特徴を含み、該第１の特徴がノードリンク
構造の第１の部分を表し；前記信号に応答して、ノード
リンク構造の第２の表現をディスプレイに表示するステ
ップを有し；該第２の表現がノードリンク構造の第１の
部分を表す第２の特徴を含み、該第２の特徴が第２のデ
ィスプレイ位置付近に表示され；前記第２の表現が前記
第１の表現の変更された継続として知覚されることがで
きる；ことを特徴とする。

【００１７】本発明の請求項２の態様は、マシンを動作
する方法であって、該マシンが、メモリと、該メモリに
格納されたデータをアクセスするように接続されるプロ
セッサと、該メモリに格納されるノードリンクデータ
と、を含み、該ノードリンクデータがノードリンク構造
を規定し、該ノードリンク構造がノード及びリンクを含
み、各リンクが少なくとも２つのノードに関連する。前
記マシン動作方法は、プロセッサを操作してノードリン
クデータを用いてレイアウトデータを得るステップを有
し；前記レイアウトデータが、ノードリンク構造部分に
対するレイアウト空間内位置を示し、該レイアウト空間
が負の曲率を有する空間であり；前記ノードリンク構造
がノード及びリンクを含み、各リンクがノードの中の少
なくとも２つに関連し；前記レイアウトデータが、ノー
ド集合に対するレイアウト空間内位置を示し；前記ノー
ド集合が、最上位レベルと少なくとも１つの下位レベル
とを含む２つ以上のノードレベルを有するブランチを形
成し、各下位レベルにおける各ノードが、次に高いレベ
ルに親ノードを有し、ノードが親ノードに対して１つの
リンクを介して関連づけられ；２つ以上の親ノードの集
合中の各々に対して、前記レイアウトデータが、親ノー
ドに対するレイアウト空間における親位置を含み、前記
レイアウトデータが、前記親ノードを共有する多数の下
位レベルのノードに対するレイアウト空間における円に
略沿った形で存在する子位置を含み、前記親位置が円の
略中心にあり、下位レベルノード数が２つ以上であり、
前記円に沿って隣接する子位置が、略基底スペーシング
だけ離間され、前記円が、下位レベルノード数と共にゆ
っくりと増大する関数を近似する半径を有し、よって半
径と、円に沿って隣接する子位置同士間のスペーシング
とが全てブランチ内において略均一であり、前記マシン
動作方法がさらに、前記プロセッサを動作して、レイア
ウトデータを用いて２つ以上の異なるマッピングを実行
するステップを有し；各マッピングによりマッピングデ
ータが得られ；各マッピングにより得られたマッピング
データがノード集合の部分集合の位置を示すことを特徴
とする。

【００１８】

【発明の実施の形態】「グラフ」は、各リンクが２つの
ノードに関連するノードリンク構造である。「非循環グ
ラフ」は、リンクがグラフ中の任意の２つのノード同士
間に１つの経路のみを提供するグラフである。「有向グ
ラフ」は、各リンクが、そのリンクの関連するノード同
士間に、１つのノードがリンクのソースであり他のノー
ドが目的地であるというように方向を示すグラフであ
る。ツリーは、必ず１つのルートノードを有する非循環
有向グラフであり、ツリー中のあらゆる他のノードは、
ルートノードから始まり示された方向にある各リンクに
従う唯一の経路により到達されることができる。

【００１９】ノードリンク構造の「ブランチ（分岐）」
は、リンクが、関連するノードペアとして且つ方向を示
すものとして取り扱われる場合に、ノードリンク構造内
にツリーを形成するノード集合である。従ってブランチ
は、２つ以上のレベルを含み、「最上位レベルノード」
は、ツリーのルートノードであるノードであり、「下位
レベルノード」は、最上位レベルノードよりも１つ以上
下のツリーレベルのノードである。各下位レベルノード
は、そのすぐ上のレベルに「親ノード」を有し、下位レ
ベルノードは、１つのリンクを介して親ノードに関連づ
けられる。親ノードは、そのすぐ下のレベルに「子ノー
ド」の集合を有し、親ノードは１つのリンクを介して各
子ノードに関連づけられる。１つの親ノードの複数の子
ノードは、その親ノードを共有する。親ノードはまた、
「子孫ノード」の集合を有し、該「子孫ノード」は、親
ノードの子ノードとそれら子ノードの子ノードの全て等
を包含する。

【００２０】ノードリンク構造の「指数関数的に増大す
るブランチ」は、下位レベルにいくにつれて、ノード数
がおおよそ、下位レベルのノードをブランチの最上位レ
ベルノードに関連づけるリンク数ｍの指数関数で増大す
るブランチである。例えば、ブランチ内の親ノードが平
均して３つの子ノード有する場合、ｍ番目の下位レベル
におけるノード数はおおよそ３^m 個である。

【００２１】「有界ノード特徴」は、知覚できる境界を
有するノード特徴である。有界ノード特徴の「範囲の中
心」は、ノード特徴の境界内の領域範囲の中心である。
従って有界ノード特徴の範囲の中心は、ノード特徴の境
界から演算されたり、表現を見て評価されたりできる。

【００２２】１つの表現における第１の有界ノード特徴
に「最も近い他のノード特徴」は、第１のノード特徴の
範囲の中心から任意の他の有界ノード特徴の範囲の中心
までのスペーシングを越えない距離だけ、第１のノード
特徴の中心から離間された中心を有する第２の有界ノー
ド特徴である。ここではこの距離をノード特徴の「最も
近いノードスペーシング」と呼ぶ。有界ノード特徴は、
最も近い他のノード特徴を１つより多く有することもあ
り、その全ては、最も近いノードスペーシングだけ離れ
た所に範囲の中心を有する。

【００２３】第１の領域における最も近いノードスペー
シングが第２の領域におけるそれよりも概して大きいと
観察者が認めることができる場合には、第１の領域にお
ける有界ノード特徴は、第２の領域における有界ノード
特徴よりも「概して知覚的に大きい」最も近いノードス
ペーシングを有する。有界ノード特徴が、１つの表現の
中の他の領域における最も近いノードスペーシングより
も概して知覚的に大きい「最も近いノードスペーシン
グ」を有する領域は、「より大きいスペーシングの領
域」と呼ばれることが可能である。

【００２４】ノードリンク構造の表現においては、親ノ
ード特徴及び子ノード特徴のディスプレイ位置と、それ
らのディスプレイ位置が得られた方法がわかっていて、
子の子孫が領域の外周から最小スペーシングより遠くに
位置する可能性が小さければ、親ノード特徴のディスプ
レイ位置と子ノード特徴のディスプレイ位置との間の関
係は、「子孫ノードのいずれもが領域の外周から最小ス
ペーシングより遠くにある可能性は小さい」ということ
になる。例えば、以下に述べる実行では、２つのディス
プレイ位置の関係が、子ノード特徴のディスプレイ位置
が親ノード特徴のディスプレイ位置と同じ位外周に近接
しているような関係であるかどうかの可能性を検査す
る。

【００２５】「負の曲率を有する空間」は、平行な線が
発散する空間である。従って、所与の直線上にない負の
曲率を有する空間における任意の位置を介すれば、所与
の直線に平行な他の直線が複数ある。負の曲率を有する
空間の一例は、双曲的なｎ次元空間である。「双曲面」
は、双曲的な２次元空間である。

【００２６】連続空間の「ディスクリートな（離散的）
近似」は、空間内の各位置が連続空間に対する連続した
範囲の数の部分集合により一義的に特定されることがで
きる空間であり、該部分集合は、ディスクリートな近似
での位置が、連続空間と比較した場合に限られた精度で
特定されることのみが可能である。例えば、連続空間に
おける位置が実数により特定されることができる場合に
は、ディスクリートな近似での位置は、整数又はｎビッ
ト数等によってのみ特定されることが可能である。

【００２７】各位置が複数の位置のうち隣接する位置に
対してよりも弧に対しての方がより近接しているという
ように、楕円や円の弧がレイアウト空間内に存在するこ
とができる場合には、データ項目は「円に略沿った」位
置又は「弧に略沿った」位置を示す。円に略沿った隣接
位置同士は、レイアウト空間における隣接位置同士間の
距離が、基底スペーシングの大きさの水準内にある場合
には、略基底スペーシングだけ離間される。

【００２８】位置が円に対してよりも円の中心に対して
の方がより近接する場合には、データ項目は、レイアウ
ト空間において「円の略中心」にある位置を示す。

【００２９】２つ以上の親ノードを含み、その各々に対
してデータ項目が、円に略沿って親ノードを共有する子
ノードの位置と該円の略中心にある親ノードの位置とを
示すブランチ内において、円の半径と、円に沿って隣接
する子の位置との間のスペーシングとの最大及び最小の
ものが、互いの大きさの水準内にある場合には、その半
径及びスペーシングは、「ブランチ内で全て略均一」で
ある。円は半径を有し、各数の子ノードを有する円の半
径の平均長が、単調な正のスロープを有すると共にその
スロープが子の数の増加と共に減少する関数を近似する
曲線を形成する場合に、該半径は「下位レベルノードの
数と共にゆっくりと増大する関数を近似する」。

【００３０】図１〜図５は、本発明の概括的な特徴を示
す。図１は、ノードリンク構造を規定するノードリンク
データを用いて、負の曲率を有するレイアウト空間にお
ける位置を示すレイアウトデータを得、それにより２つ
以上の異なるマッピングが行われることのできる方法を
示す。図２は、ノードリンクデータを用いて、図１のよ
うにレイアウトデータを得てマッピングを達成すること
における概括的な動作を示す。図３は、第１及び第２の
表現を以下のように表すことのできる方法を示す；第２
の表現は、第１の表現での第１のディスプレイ位置から
第２のディスプレイ位置への変更を示すユーザからの信
号に応答して、自動的に示されることができる。図４
は、第１及び第２の表現を図３のように表すことにおけ
る概括的な動作を示す。図５は、図１で示されるように
レイアウトデータを得ることができると共に、それを使
用してマッピングを達成することができ、図３で示され
るように第１及び第２の表現を表すことのできるマシン
の概括的な構成要素を示す。

【００３１】図１において、ノードリンクデータ１０
は、ノードリンク構造（一部が図示される）を規定す
る。示されるように、ノードリンク構造２０は、ノード
と、ノードに関連するリンクとを含む。図１は、ノード
リンク構造２０の指数関数的に増えるブランチを示し、
最上位レベルノード２２は、１つのリンクを介して下位
レベルノード２４、２６、及び２８に関連づけられてい
る。破線で示されるように、下位レベルノード２４、２
６、及び２８のそれぞれは、その次に下位レベルの３つ
のノードに関連づけられる。この増加率が続けば、指数
関数的に増加するブランチの下位レベルにおけるノード
数は略３^m 個であり、ここでｍは、そのレベルにおける
ノードを最上位レベルノード２２に関連づけるリンク数
である。図１で示されるように、２次元のユークリッド
平面において指数関数的に増加するブランチをレイアウ
トすることは困難である。

【００３２】しかしながらレイアウトデータ３０は、ノ
ードリンク構造２０の指数関数的に増加するブランチに
おけるノードの、負の曲率を有する空間３２における位
置を示す。空間３２は、レイ３６とレイ３８の間で頂点
から延びるウェッジの該頂点に最上位レベルノード２２
の位置３４を有するように、概括的に図示される。この
最上位レベルウェッジは、最上位レベル２２に割り当て
られたものである。下位レベルノード２４、２６、及び
２８は、円４８に略沿った位置４２、４４、及び４６を
有することができ、空間３２における円４８の中心はお
およそ、最上位レベルウェッジの頂点である位置３４に
ある。

【００３３】位置４２、４４、及び４６は全て、最上位
レベルウェッジ内にあり、より下位レベルにある、最上
位レベルノード２２の全ての子孫もまた、最上位レベル
ウェッジ内に位置することができる。例えば、指数関数
的に増加するブランチの、次に下位レベルにあるノード
も同様に、空間３２におけるその中心がほぼ、位置４
２、４４、及び４６にあるそれぞれの円に沿って、位置
されることができる。空間３２は負の曲率でカーブして
いるので、下位レベルノード２４、２６、及び２８の各
々は、たとえ下位レベルウェッジが互いにオーバーラッ
プしなくても、レイ３６及び３８が位置３４から発散す
るのと略同じ角度でウェッジの頂点から分岐するレイ同
士の間に下位レベルウェッジを割り当てられることがで
きると共に、その全ては最上位レベルウェッジ内に含ま
れる。

【００３４】円４８上で隣接する子位置４２及び４４
は、距離ｄ₁ だけ離間されており、隣接する子位置４４
及び４６は、距離ｄ₂ だけ離間されている。距離ｄ₁ 又
はｄ₂の各々は基底スペーシングに略等しく、円４８の
半径ｄ₀ とブランチ内の他の円の半径は共に、半径と、
円に沿って隣接する子位置同士間のスペーシングとが全
てブランチ内で略均一であるように、下位レベルノード
の数と共にゆっくりと増大する関数を近似する。

【００３５】図１で示されるように、レイアウトデータ
３０は、２つ以上の異なるマッピングを実行するように
使用されることができる。０番目にマッピングされたデ
ータ５０とＮ番目にマッピングされたデータ５２で示さ
れるように、マッピング毎にマッピングデータが得られ
る。各マッピングにより得られたマッピングデータは、
ノードリンク構造２０におけるノードの部分集合の位置
を示す。例えば位置は、ディスプレイ位置、又はレイア
ウト空間とは別の空間における位置であることが可能で
ある。

【００３６】図２において、ボックス６０における動作
は、ノードリンク構造を規定するノードリンクデータを
得ることにより開始する。ノードリンク構造は、ノード
及びリンクを含み、各リンクは少なくとも２つのノード
に関連づけられる。

【００３７】ボックス６２の動作は、ボックス６０で得
られたノードリンクデータを使用して、負の曲率を有す
るレイアウト空間における、ブランチ中のノードの位置
を示すレイアウトデータを得る。親ノード集合中の各々
に対しては、親ノードを共有する子の位置は、ほぼ親ノ
ードの位置にその中心をおく円にほぼ沿っており、隣接
する子ノード同士は、略基底スペーシングだけ離間され
る。ブランチ内の複数の円の半径は共に、親を共有する
子ノードの数と共にゆっくりと増加する関数を近似する
ので、半径と、円に沿って隣接する子位置同士間のスペ
ーシングとは全て、ブランチ内で略均一である。

【００３８】ボックス６４における動作は次に、ボック
ス６２からのレイアウトデータを使用して、少なくとも
２つの異なるマッピングに対してマッピングデータを得
る。各マッピングに対して得られたマッピングデータ
は、ノードの部分集合の位置を示す。

【００３９】図３において、レイアウトデータ７０は、
ノードリンク構造の部分（複数）の、負の曲率を有する
レイアウト空間における位置を示す。レイアウトデータ
７０は、ノードリンク構造の第１の表現７４を有する画
像７２を表すように用いられる。画像７２は、マウスや
他のポインタ制御デバイスにより制御されてディスプレ
イ位置を示す信号を提供することのできるポインタ７６
を含むように図示される。

【００４０】図３の破線で示されるように、第１のディ
スプレイ位置から第２のディスプレイ位置への変更を示
す信号７８をユーザが提供する前に、不特定の時間が経
過する。第１の表現７４は、第１のディスプレイ位置付
近にノードリンク構造の第１の部分を表す第１の特徴を
有する。例えば、ノード特徴８０、８２、及び８４のう
ちの１つが、第１のディスプレイ位置付近にあることが
可能である。

【００４１】信号７８に応答して、画像８６は、ノード
リンク構造の第２の表現８８を有するように示される。
第２の表現８８は、第１の表現７４の変更された継続と
して知覚される。

【００４２】第２の表現８８では、ノードリンク構造の
第１の部分を表す第２の特徴は、第２のディスプレイ位
置付近にある。例えば、第１の表現７４におけるノード
特徴８０が第１のディスプレイ位置付近にあったとし
て、ノード特徴９０が同一ノードを示すとすれば、第２
のディスプレイ位置は、ノード特徴８０の位置からノー
ド特徴９０の位置へのドラッギング信号により指示され
たということができる。同様に、ノード特徴９２及び９
４がそれぞれ、ノード特徴８２及び８４と同一のノード
を示すとすれば、第２のディスプレイ位置は、ノード特
徴８２又はノード特徴８４の位置からそれぞれ、ノード
特徴９２又はノード特徴９４の位置へのドラッギング信
号により指示されることができたといえる。また、ノー
ド特徴８２からノード特徴９２へとサイズが増している
ことにより示される通り、より大きいスペーシングの領
域の中心に第２の位置を示すように、第１の表現７４の
ノード特徴８２上でクリックすることにより、第２のデ
ィスプレイ位置が指示されることができたといえる。

【００４３】図４は、図３で示されたオペレーションを
実行する概括的な動作を示す。ボックス１２０の動作で
は、負の曲率を有するレイアウト空間におけるノードリ
ンク構造の部分の位置を示すレイアウトデータが得られ
る。

【００４４】ボックス１２２の動作は、ボックス１２０
からのレイアウトデータを用いて、ノードリンク構造の
第１の表現を表示する。第１の表現は、ノードリンク構
造の第１の部分を示す第１の特徴を含み、該第１の特徴
は第１のディスプレイ位置付近にある。

【００４５】破線で示されるように不特定の時間経過
後、ボックス１２４の動作は、第１のディスプレイ位置
から第２のディスプレイ位置への変更を示す、ユーザか
らの信号を受け取る。

【００４６】ボックス１２６の動作は、ノードリンク構
造の第２の表現を表すことにより、ボックス１２４の信
号に応答する。第２の表現は、ノードリンク構造の第１
の部分を示す第２の特徴を含む。この第２の特徴は、第
２のディスプレイ位置付近にある。

【００４７】図５のマシン１５０は、ユーザ入力回路１
５４からユーザのアクションを示すデータを受け取るよ
うに、そして画像を規定するデータをディスプレイ１５
６に提供するように接続されるプロセッサ１５２を含
む。プロセッサ１５２はまた、ノードリンクデータ１５
８をアクセスするようにも接続され、該ノードリンクデ
ータは、図２に関して上述したようにノードリンク構造
を規定する。プロセッサ１５２は、命令入力回路１６２
を介して命令を指示する命令データ１６０を受け取るよ
うにも接続され、この命令入力回路１６２は、この図で
は、メモリ１６４、記憶媒体アクセスデバイス１６６、
又はネットワーク１６８への接続から受け取られた命令
を提供することができる。

【００４８】命令データ１６０により示された命令を実
行する際、プロセッサ１５２はノードリンクデータ１５
８を用いて、図２のボックス６２と図４のボックス１２
０で示されたように、負の曲率を有するレイアウト空間
におけるノードリンク構造の部分の位置を示すレイアウ
トデータを得る。次にプロセッサ１５２は、レイアウト
データを用いて、図４のボックス１２２で示されたよう
に、ディスプレイ１５６上にノードリンク構造の第１の
表現を表示するが、これは、図２のボックス６４で示さ
れたように、ディスプレイの１つの領域に対してノード
の部分集合の第１のマッピングを行うことにより、実行
されることができる。プロセッサ１５２がユーザ入力デ
バイス１５４からユーザ信号を示すデータを受け取り、
その信号が、図４のボックス１２４のように第１のディ
スプレイ位置から第２のディスプレイ位置への変更を示
すものである場合には、プロセッサ１５２は、ノードリ
ンク構造の第２の表現を自動的にディスプレイ１５６上
に表示することができ、この場合、第１のディスプレイ
位置付近にあった特徴の位置は、図４のボックス１２６
で示されるように、第２のディスプレイ位置に変更され
ることとなる。第２の表現は、図２のボックス６４で示
されたように、第２のマッピングを実行することにより
表示されることができる。

【００４９】上述のように、図５は、命令入力回路１６
２が、命令を示すデータを受け取ることのできる３つの
可能なソース、即ちメモリ１６４、記憶媒体アクセスデ
バイス１６６、及びネットワーク１６８を示している。

【００５０】メモリ１６４は、ランダムアクセスメモリ
（ＲＡＭ）や読出し専用記憶素子（ＲＯＭ）を含むマシ
ン１５０内の任意の従来のメモリ、又は任意の種類の周
辺若しくは遠隔メモリであることが可能である。

【００５１】記憶媒体アクセスデバイス１６６は、記憶
媒体１７０をアクセスするドライブ又は他の適切なデバ
イスであることが可能である。記憶媒体１７０は例え
ば、１つ以上のテープ、ディスケット、若しくはフロッ
ピーディスク等の磁気媒体；１つ以上のＣＤ−ＲＯＭの
セットのような光媒体；又はデータを記憶するための他
の任意の適切な媒体；であることが可能である。記憶媒
体１７０は、マシン１５０の一部；サーバ又は他の周辺
若しくは遠隔メモリデバイスの一部；又はソフトウェア
製品の一部；であることが可能である。これら全ケース
において、記憶媒体１７０は、マシン１５０で使用され
ることのできる工業製品である。データユニットが記憶
媒体１７０上に位置づけられることができるので、記憶
媒体アクセスデバイス１６６は、データユニットをアク
セスすることができると共に、命令入力回路１６２を介
してプロセッサ１５２にそれらを連続して提供すること
ができる。連続して提供されると、データユニットは、
命令データ１６０を形成し、示されるような命令を指示
する。

【００５２】ネットワーク１６８は、マシン１８０から
受け取られた命令データ１６０を提供することができ
る。マシン１８０におけるプロセッサ１８２は、ネット
ワーク接続回路１８４を介してネットワーク１６８を経
て、命令入力回路１６２との接続を確立することができ
る。どちらのプロセッサも、接続を開始することが可能
であり、接続は、任意の適切なプロトコルにより確立さ
れることができる。プロセッサ１８２は、メモリ１８６
に格納された命令データをアクセスし、この命令データ
をネットワーク１６８を経てプロセッサ１５２に伝送す
ることができ、その結果プロセッサ１５２が、ネットワ
ーク１６８から命令データを受け取ることができる。命
令データ１６０は、プロセッサ１５２によりメモリ１６
４若しくは他の場所に格納されることができると共に、
実行されることができる。

【００５３】上述の概括的な特徴は、種々のマシンにお
いて多数の方法で実行され、負の曲率を有するレイアウ
ト空間におけるノードリンク構造の部分の位置を示すレ
イアウトデータが得られ且つ使用されることができる。
以下に述べる実行は、ＵＮＩＸ／Ｘオペレーティングシ
ステムを実行するＳｕｎＳＰＡＲＣＳｔａｔｉｏｎにお
いて実行した。それとは別に、アップルマッキントッシ
ュ（Apple Macintosh）のパーソナルコンピュータにお
いても実行した。ＵＮＩＸでの実行では、コモンＬＩＳ
Ｐインタフェースマネージャ（ＣＬＩＭ）を付けて拡張
されたコモンＬＩＳＰプログラミング環境において書か
れた命令を実行する。コモンＬＩＰＳ環境及びＣＬＩＭ
拡張は、ルシッド・インコーポレイテッド（Lucid In
c.）及びフランツ・インコーポレイテッド（Franz In
c.）から購入することができる。

【００５４】図６は、本発明を実行したシステムの構成
要素を示す。

【００５５】図６のマシン２００は、中央処理ユニット
（ＣＰＵ）２０２、マイクロプロセッサ、又は適切なプ
ロセッサを含む。ＣＰＵ２００は、キーボード２０４及
びマウス２０６を含むように図示されるユーザ入力デバ
イスから、ユーザ信号を示すデータを受け取るように、
接続される。ＣＰＵ２０２はまた、ディスプレイ２０８
上に画像を表示させるデータを提供するように、接続さ
れる。ディスプレイ２０８に表示される画像は、マウス
２０６や別のポインタ制御デバイスにより制御されるポ
インタ２１０を含むことができる。

【００５６】ＣＰＵ２０２は、メモリ環境２２０を共に
提供する１つ以上のメモリ構成要素に接続される。メモ
リ構成要素は従来的に、ＣＰＵ２０２に直接接続される
常駐ＲＡＭ、内部バスを介してＣＰＵ２０２に接続され
る１つ以上の内部ディスクドライブ若しくは他の記憶媒
体アクセスデバイス、そして、記憶媒体アクセスデバイ
スを含むと共に、マシン２００の外部接続を介してＣＰ
Ｕ２０２に接続される周辺デバイス若しくは遠隔サーバ
等の１つ以上の外部メモリ構成要素、を包含する。ＣＰ
Ｕ２０２は従来的に、アドレスを提供することにより、
メモリ環境２２０中の任意のメモリ構成要素に格納され
たデータをアクセスする。

【００５７】図６は、メモリ環境２２０に格納されるプ
ログラム構成要素とデータ構成要素を示す。プログラム
構成要素とデータ構成要素は別々に図示されているが、
所与のメモリ構成要素内に別々に格納される必要はな
い。プログラム構成要素は、ＣＰＵ２０２が実行するこ
とのできる命令を示すデータを含むとともに、目的コー
ドフォーム又はソースコードフォームで格納されること
ができる。適切であれば、プログラム構成要素は、ソー
スコードフォームで格納されたプログラム構成要素から
命令を得るのに必要な、任意のコンパイラ及びインタプ
リタを含むことも可能である。プログラム構成要素によ
り示された命令を実行する際、ＣＰＵ２０２はデータ構
成要素をアクセスして使用する。

【００５８】オペレーティングシステムプログラム２３
０により示された命令を実行する際、ＣＰＵ２０２は、
ＣＰＵ２０２とマシン２００の他の構成要素との間でデ
ータを伝送するオペレーションを実行する。このような
オペレーションには、例えば、ＣＰＵ２０２のメモリス
ペース中の論理アドレスを物理アドレスにマッピングし
て、メモリ環境２２０中のメモリ構成要素をアクセスす
ること等が含まれる。

【００５９】ＣＬＩＭライブラリ及びユーザインタフェ
ース拡張を含むコモンＬＩＰＳ環境プログラム２３２に
より示された命令を実行する際、ＣＰＵ２０２は、フラ
ンツ・インコーポレイテッド（Franz Inc.）から入手可
能なＣＬＩＭ２．０仕様において規定される標準ＣＬＩ
Ｍインタフェースを提供する。その結果、ＣＰＵ２０２
が、ＣＬＩＭソースコードを実行することができるの
で、走査検索（browser）インタフェースプログラム２
３４及び双曲ジオメタリプログラム２３６は、ＣＬＩＭ
を付けて拡張されたコモンＬＩＳＰで実行されることが
できる。

【００６０】走査検索インタフェースプログラム２３４
により指示された命令を実行する際、ＣＰＵ２０２はま
ず、マシン２００を初期化する。ＣＰＵ２０２は、ノー
ドリンク構造を規定するノードリンクデータ２４０を用
いて、双曲面におけるノードリンク構造の部分の位置を
示すレイアウトデータ２４２を得る。ＣＰＵ２０２は、
レイアウトデータ２４２を用いて、ノードリンク構造の
初期表現に対するマッピングデータ２４４を得る。ＣＰ
Ｕ２０２がディスプレイ２０８にデータを提供すると、
ディスプレイに初期表現が表示される。

【００６１】走査検索インタフェースプログラム２３４
により示された命令を実行する際、ＣＰＵ２０２はま
た、キーボード２０４及びマウス２０６から、ユーザ信
号のイベントを示すデータを受け取る。ＣＰＵ２０２
は、イベント待ち行列データ２４６をアクセスすること
により、イベントに応答するステップの待ち行列をセッ
トアップし、維持し、そしてハンドルする（処理す
る）。ユーザ信号イベントに応答するステップが完了す
ると、ＣＰＵ２０２は次のイベントに応答するステップ
をセットアップすることができる。

【００６２】走査検索インタフェースプログラム２３４
により示された命令を実行する際、ＣＰＵ２０２はま
た、アニメーションパラメータデータ２４８をアクセス
することにより、アニメーションパラメータを修正する
ことができる。あるいはＣＰＵ２０２は、レイアウトデ
ータ２４２を用いて、ノードリンク構造の変更された表
現に対するマッピングデータ２４４を得ることができ、
ディスプレイ２０８にデータを提供して、変更された表
現をディスプレイに表示させる。

【００６３】ＣＰＵ２０２は、レイアウトデータ２４２
を得るため、マッピングデータ２４４を得るため、ポイ
ンタ２１０の位置からノードリンク構造の一部分にマッ
ピングするため等、多様な目的のために、双曲的ジオメ
トリプログラム２３６により示された命令を実行するこ
とができる。図６で示されるように、表現は、その上に
フィギュア２５２が示される背景２５０を含むことがで
き、フィギュア２５２内でポインタ２１０の位置は、例
えば最も近いノードにマッピングされることができる。

【００６４】上述したＣＰＵ２０２のオペレーションを
多くの方法で実行して、負の曲率を有する空間において
レイアウトされたノードリンク構造に対して走査検索
（browser ）を提供することが可能である。図７は、図
６のマシンが如何にして、エッジに近すぎないノードの
位置を変換することにより走査検索を提供することがで
きるかを示す。図８は、図６のマシンが如何にして、全
ノードのレイアウトデータを連続的に変換することによ
り走査検索を提供することができるかを示す。

【００６５】図７及び図８の概括的なアプローチは、ノ
ードの位置がレイアウト空間において変換され、次にレ
イアウト空間からディスプレイ位置へのマッピングによ
り表現が表示されることができる、ということである。
上述のように、レイアウト空間は、双曲面又は負の曲率
を有する別の適切な空間であることが可能である。双曲
面とディスプレイ領域の間のマッピングを容易にするた
めに、ディスプレイ位置は、円形のディスプレイ領域内
の位置であることが可能である。

【００６６】図７のボックス２６０の動作は、ノードリ
ンク構造中の各ノードに対するレイアウト空間における
位置を示すレイアウトデータを得る。レイアウト空間
は、例えば双曲面であることが可能である。ボックス２
６０の動作はまた、レイアウトデータにおいて実行され
ることのできる現行変換を初期設定して、変換位置を得
る。初期現行変換は例えば、レイアウト空間におけるノ
ードの位置を変更しないヌル変換であることが可能であ
る。

【００６７】ボックス２６２の動作は次に、ボックス２
６０からのレイアウトデータに現行変換を実行し、レイ
アウト空間における位置がエッジに非常に近いノード以
外の各ノードの変換位置を示す変換データを得る。エッ
ジは、ノードリンク構造の表現がディスプレイされた時
に表示されるレイアウト空間の部分の境界となる。

【００６８】次にボックス２６４の動作は、ボックス２
６２から得られた変換位置をマッピングして、エッジに
近すぎない各ノードに対するディスプレイ上の位置を得
る。ボックス２６４の動作は次に、ディスプレイに表現
を表示する。エッジにそれほど近くない各ノードの表現
は、ノードのディスプレイ位置にノードの特徴を含む。

【００６９】図７の破線により示されるように、ボック
ス２７０の動作は、不特定の時間の経過後、ボックス２
６４の動作に続くことができ、この動作は、位置の変更
に対する要求をユーザから受け取る。この要求は、ディ
スプレイ上での少なくとも１つの位置の指示を含む。

【００７０】ボックス２７２の動作は、ボックス２７０
において指示されたディスプレイ位置（単数又は複数）
をレイアウト空間に再びマッピングして、レイアウト空
間における開始位置及び終了位置を得る。例えば、マウ
スクリック等によりディスプレイ位置が１つのみ示され
る場合には、クリックの発生した時のポインタの位置を
用いて開始位置を得ることができ、また終了位置は、レ
イアウト空間におけるその表現の中心の位置であること
が可能である。あるいは、例えばボタンを押してその後
放すことによるドラッギング動作の間に、２つのディス
プレイ位置が示される場合には、ボタンを押した時のポ
インタの位置を用いて開始位置を得、またボタンから手
を放した時のポインタの位置を用いて、終了位置を得る
ことができる。

【００７１】ボックス２７４の動作は、開始位置を終了
位置に移動するレイアウト空間の変換を得る。ボックス
２７６の動作は、現行変換とボックス２７４からの新た
な変換とを結合して、結合された変換を得る。ボックス
２６２及び２６４の動作が実行されて別の表現が表示さ
れる時には、この結合された変換が現行変換となる。

【００７２】以下に述べるように、図７の技術を実行し
て、ただ１つの表現ではなく、クリックに応答して一連
の表現を表示した。このように変更することにより、開
始位置から終了位置への連続した動作の知覚を提供する
ことができる。

【００７３】図８の技術は、例えばボックス２８０の動
作が図７のボックス２６０の動作と同じであるといった
ように、図７の技術と類似する。しかしながら、重要な
違いは、ボックス２８２の動作が、ボックス２６２でエ
ッジ付近のノードとして取り扱われたものも含めて、ノ
ードリンク構造中の各ノードの変更された位置を得ると
いうことである。よって図８の技術は、大型のノードリ
ンク構造に対しては、図７の技術ほど有効でない。

【００７４】ボックス２８４の動作は、図７のボックス
２６４の動作と同じように、ボックス２８２からの変換
された位置をディスプレイ位置にマッピングし、このデ
ィスプレイ位置を用いて、ボックス２６４と同じように
表現を表示する。

【００７５】ボックス２９０の動作は、ボックス２７０
と同じように要求を受け取る。ボックス２９２の動作
は、ボックス２８０からのレイアウトデータではなく、
ボックス２８２からの変換されたデータであるようにレ
イアウトデータを先ず更新することにより、応答する。
次にボックス２９２の動作は、ボックス２９０で示され
たディスプレイ位置（単数又は複数）から変換されたレ
イアウト空間へとマッピングを行って、開始位置及び終
了位置を得る。ボックス２９４の動作は、開始位置を終
了位置に移動する新たな変換を得、ボックス２８２及び
ボックス２８４の動作が実行されて別の表現が表示され
る前に、現行変換を更新して、新変換とする。

【００７６】上述の通り、図７の技術は、大型のノード
リンク構造を図８の技術以上により良くハンドルする
が、その理由は、エッジに非常に近いノードに対しては
ボックス２６２の動作が実行されないからである。図８
の技術は、大型の構造に対しては実用的でないというこ
とが判った。さらに、図８の技術では変換を得る際に情
報がいくらか失われるため、図７の技術の方がより正確
である；それはなぜなら、図７の技術はボックス２６０
からの元々のレイアウトデータを使用し続けるからであ
る。

【００７７】以下に述べるＣＰＵ２０２のオペレーショ
ンの実行は、図７の走査検索技術に続くものであるが、
以下に述べる基本的なオペレーションを使用して、図８
の走査検索技術を実行することもできる。

【００７８】以下に述べる実行は、一様な方法でノード
リンク構造を双曲面にレイアウトし、この面を円形のデ
ィスプレイ領域にマッピングする。双曲面は、平行な線
が互いに離れるように発散する数学上の構築物である。
これは、円の円周がその半径と共に指数関数的に増大す
るという便利な特性につながり、このことは、距離が増
すとともに指数関数的により多くの空間を利用できると
いうことを意味する。従って、指数関数的に増大するノ
ードリンク構造を双曲的空間において一様な方法でレイ
アウトすることができれば、親、子、及び同胞の間の距
離は、階層中のどの場所でも略同じである。

【００７９】双曲面は数学上の物体であるが、双曲面
は、単位円上へ自然な方法でマッピングされることがで
き、単位円は、２次元（ユークリッド）ディスプレイ上
にそれをディスプレイする方法を提供する。このマッピ
ングは、双曲面の起点付近の部分を他の部分よりも多く
のディスプレイ空間を用いてディスプレイする。双曲面
の起点から非常に遠隔の部分は、ディスプレイのエッジ
付近に極小さい空間を取る。従って単位円への投影は、
ノードリンク構造の一部を構造全体の構成の中に埋め込
みながら、該一部により多くの空間を割り当てる固有の
メカニズムを提供する。

【００８０】双曲面上での構造の平行移動は、構造全体
を見ているという錯覚を弱めることなく、構造のどの部
分が最も大きい空間を得るのかを調整するメカニズムを
提供する。構造はまず、そのルートをより大きいスペー
シングの領域の中心にディスプレイされるが、実行は、
ポインタクリックや対話式ドラッギングを用いてフォー
カスを操作すると共に、かかる操作を織りまぜて移り変
わり（transition）をスムーズにアニメート（動画化）
する有効な手続きを包含する。構造の構成は常に、親、
同胞、及び子といったいくつかの世代を含んでおり、ユ
ーザは、迷うことなく構造を探索することが容易にな
る。

【００８１】以下に述べる走査検索は、従来の階層的視
覚よりもずっと大きな構造との効果的な対話を支持する
と共に、ロバートソン（Robertson ）他の米国特許第
５，２９５，２４３号において述べられたもの等の他の
新しい走査検索に比べて優れている。６００×６００ピ
クセルのウィンドウでは、標準的な２次元階層走査検索
は、各々が３文字列を有する１００個のノードをディス
プレイできるのが、典型的である。以下に述べる走査検
索は、１０００個のノードをディスプレイすることがで
き、そのうちフォーカスに最も近い５０個は、３〜１２
個の文字列を示すことができる。従って、１０倍に及ぶ
数のノードがディスプレイされることが可能であると共
に、ノードリンク構造にわたって一層有効なナビゲーシ
ョンが提供されることができる。構造の部分の対象とす
るレベルが変化するに従って、構造を動的に歪ませてデ
ィスプレイすることにより、スケーリングの利点が得ら
れる。

【００８２】図９及び図１０は、レイアウトオペレーシ
ョンにおける動作を示す。図９は、ＣＰＵ２０２が双曲
面にノードリンク構造をレイアウトする方法を示す。図
９の技術は、図７のボックス２６０の動作と図８のボッ
クス２８０の動作を実行するように用いられることがで
きる。図１０は、ノードの子までの距離、子の位置、ウ
ェッジ、及びルーム（空間）の境界と、ノードの半径が
図９において如何に得られることができるかを示す。

【００８３】図９のレイアウト技術は、局所情報に基づ
いてノードリンク構造中の各ノードを再帰的にレイアウ
トする。ノードは、それ自体から外方向に向かう双曲面
のウェッジを割り当てられ、該ウェッジの中にそのノー
ドの子孫が配置されることができる。ノードの子の全て
は、そのノードのウェッジの弧に沿って（即ちノードか
ら等しい距離をおいて）配置されると共に、互いに或る
最小の距離だけ離間されるに足りるだけ親ノードから離
れた所に配置される。各子は、その子孫に対するサブウ
ェッジを有する。

【００８４】双曲的ジオメトリでは平行な線同士が発散
するということにより、各子は典型的に、その親のウェ
ッジと略同じ角度で広がるウェッジを有する。不均一な
構造に対してよりコンパクトなレイアウトを得るため
に、それ自体が多くの子孫を有する同胞は子孫を有さな
い同胞よりも大きいルーム（空間）を得るように、この
構造を変更する。この変更は、孫を祖父母から同じ距離
でより近くに置く傾向がある。

【００８５】図９の技術はまた、ルートノードの子の占
める角度を変えることによって変更されることができ
る。ルートノードの子は、３６０°の円いっぱいに広げ
られるか、あるいは全てが円の片側に置かれることがで
きる。いくつかのケースでは、後者の方が良い。

【００８６】図９のボックス３５０の動作は、ノードリ
ンクデータ中のルートノードのハンドル、双曲面の起点
の座標、該ルートノードの子孫に対して利用可能な双曲
面のウェッジ、及びルームの境界を用いてレイアウトオ
ペレーションを実行するための呼出しを受け取ることに
より、開始する。図９のレイアウトオペレーションは、
ノードリンクデータのハンドルがルートノードのハンド
ルでもあるように、非循環型の階層的ノードリンク構造
を規定するノードリンクデータを用いて、使用されるこ
とができる。双曲面のウェッジは、ウェッジの角度と方
向により規定されることができる。オリエンテーション
が放射状である場合には、ウェッジ角度は３６０°であ
ることが可能であるので、その方向は重要でないが、例
えばオリエンテーションが右方向である場合には、ウェ
ッジ角度はより小さく（例えば１２０°）、方向がオリ
エンテーションを決定する。ルームの境界は、ルートノ
ードに対して０．９に初期設定されることが可能であ
る。

【００８７】ボックス３５２の動作は、現在ハンドルさ
れているノードが子を有するかどうかを調べる。子を有
しておれば、ボックス３５４の動作は、以下に述べるよ
うに、双曲面において子までの距離を得る。次にボック
ス３６０の動作は、現行ノードの子の各々をハンドルす
る繰り返しループを開始する。

【００８８】ボックス３６２の動作は、次の子ノードに
対して、以下に述べるように双曲面における位置、ウェ
ッジ、及びルーム境界を得ることによって、各ループを
開始する。ボックス３６４の動作は次に、次の子のハン
ドルと、ボックス３６２からのその位置、ウェッジ、及
びルーム境界を用いてレイアウトオペレーションに対す
る再帰的な呼出しを行う。ボックス３６６の動作は、再
帰的呼出しからリターンし、次いでボックス３６８の動
作は、現行ノードの子ノードのリストに、その子のハン
ドルを加える。

【００８９】現行ノードの子の全てがハンドルされた
ら、ボックス３７０の動作は、ボックス３５０又はボッ
クス３６４の呼出しにおいて受け取られたルーム境界
か、あるいはボックス３５４からの、現行ノードの子ま
での距離の半分か、のいずれかを取ることにより、現行
ノードの半径を得る。現行ノードが子を有さない場合に
は、ボックス３７０の動作は、ボックス３５０からのル
ーム境界を半径とする。

【００９０】次にボックス３７２の動作は、現行ノード
のデータ構造を形成する。現行ノードのデータ構造は、
その位置とボックス３７０からのその半径を含み、現行
ノードが子を有する場合には、そのノードのデータ構造
はまた、ハンドル又はボックス３６８からのその子のリ
ストに対する他のリンクを含む。データ構造はまた、他
の関連する情報を含むことも可能である。次にボックス
３７４の動作は、現行ノードのデータ構造のハンドルを
戻すことにより、終了する。

【００９１】図１０は、図９のボックス３５４、３６
２、及び３７０の動作が如何に実行されることができる
かを示す。

【００９２】以下の記述において、１対の点同士の間の
距離は、起点に１つの点を置くポアンカレモデルにおけ
る点同士の間の距離として、符号化される。この距離
は、双曲的空間における点同士間の距離の逆双曲線正接
である。

【００９３】ボックス３９０の動作は、全ノードに対し
て同一である基底スペーシングＳを用いて、必要とされ
るスペースの値を得ることによってノードの子までの距
離を得ることにより、開始する。必要なスペースは、子
孫が均一に離間された場合に、ノードの各子の子孫によ
り占められることになる角度に依存する。このような角
度をここでは「重み」と呼称する。各子の重みの値は、
１．０とｌｎ（１．０＋Grandchildren ）の大きい方を
取ることにより得られることができ、ここで変数Grandc
hildren は、ノードの子の子であるノードの孫の全てに
対して、１．０とｌｎ( １．０＋（子の数))の大きい方
を合計したものに等しい。

【００９４】必要なスペースの値を得るために、ボック
ス３９０の動作はまた、利用できる全角度を、現行ノー
ドの全ての子に対する重みの合計で割ることによって、
角度小片を得る。角度小片に重みの中で最小のものを乗
算して角度単位αが得られる。よって必要なスペース
は、((ssin² ＋１．０）^1/2 −ssin) に等しく、ここで
ssin＝((( １．０−Ｓ²)／２Ｓ)( sinα))である。

【００９５】ボックス３９２の動作は、ボックス３９０
からの必要なスペースが、２Ｓ/(１＋Ｓ²)として計算さ
れる最小スペース（最小スペースは、基底スペーシング
Ｓとそれ自体の双曲的合計である）より大きいかどうか
を決定する。大きければ、ボックス３９４の動作は、子
までの距離を必要なスペースに設定し、大きくない場合
には、ボックス３９６の動作は、子までの距離を最小ス
ペースに設定する。

【００９６】次にボックス３９８の動作は、幅Ｗ₀ の値
を０に初期設定する；下位ルームの値は、ボックス３９
４又はボックス３９６からの距離Ｄの双曲的な半値に初
期設定されることができ、Ｄ/(１．０＋ (１．０−Ｄ²)
^1/2)として計算される；方向を示す値は、現行ノードの
ウェッジの角度幅Ｗを示す値と、単位円上の一点のｘ及
びｙ座標である（Θx ，Θy ）の形態で現行ノードのウ
ェッジの方向を示す値とを用いて初期設定されることが
できる。第１の子の方向を計算するための開始方向（Θ
x ，Θy ）は、((( Θx (cos( −Ｗ))) − (Θy (sin(
−Ｗ))))という計算値を有することができる。

【００９７】ボックス３６０の動作は、図９に関して上
述したように、繰り返しループを開始する。繰り返しル
ープの役割は、ボックス４００、４０２、４０４、及び
４０６で示される。

【００９８】ボックス４００の動作は、次の子ノードの
ウェッジの初期幅と方向を得、次いでこの初期幅を用い
て最終幅を更新する。ボックス４００の動作はまた、利
用できる次の子ノードの位置、ウェッジ、及びルームを
得る。

【００９９】ボックス４００の動作は、子の重みと角度
小片（両方共にボックス３９０で得られる）の積として
初期幅Ｗ_n を得ることができる。ボックス４００の動作
は、ボックス３９８又は前ループのいずれかからの（Θ
x ，Θy ）及び幅角Ｗ₀ を用いて、((( Θx (cos( Ｗ₀
＋Ｗ_n ))) −( Θy (sin( Ｗ₀ ＋Ｗ_n ))))、((Θy (cos
( Ｗ₀ ＋Ｗ_n ))) ＋( Θx (sin( Ｗ₀ ＋Ｗ_n ))))) に等
しい座標値を有する子の方向（Θx ，Θy ）を計算する
ことができる。ボックス４００の動作は次に、初期幅Ｗ
_n の値を有するように幅Ｗ₀ を更新する。

【０１００】ボックス４００の動作は、親ノードがルー
トノードである場合にはボックス３５０からの、あるい
は親ノードに対して実行される場合にはボックス３６４
からの親ノードの位置（ｘ，ｙ）を用いて；子の方向
（Θx ，Θy ）を用いて；そしてボックス３９４若しく
は３９６からの距離Ｄを用いて；次の子ノードの位置を
得ることができる。位置は、変換を用いて計算された値
（ｘ，ｙ，Θx ，Θy ）を含む。

【０１０１】ポアンカレモデルにより表される双曲面の
厳密な変換は、点ｐ及び角度αにより決定される（ｐは
変換前に起点であった点の最終位置を示し、αは回転を
示す）。点（ｘ，ｙ）の変換は、((Θ_z ＋Ｐ)/( Ｐ^* Θ
_z ＋１))であり、ここで、ｚは、実部ｘと虚部ｙを有す
る複素数；Ｐは、ｐを表す複素数；Θは、角度α分の回
転を表す大きさ１の複素数；Ｐ^* はＰの複素共役；であ
る。得られた値の実部及び虚部はそれぞれ、ポアンカレ
モデルにおいて変換された点ｐのｘ座標及びｙ座標であ
る。

【０１０２】共に４つの座標（ｘ，ｙ，Θx ，Θy ）に
より表される角度αのコサイン及びサインと点ｐを規定
する値が得られたら、実部ｘと虚部ｙを有する複素数と
してのＰと、実部Θx 及び虚部Θy を有する複素数とし
てのΘを得ることにより、変換を得ることができる。

【０１０３】従って、起点から点（ｘ，ｙ）への変換を
得るには、点及び方向（ｘ，ｙ，１．０，０．０）から
変換が得られることができ、ここで、座標１．０及び
０．０は、右方向、即ちそれから他の方向が測定される
基準方向を示す。この変換を、ここでは「起点からのト
ランスレータ」と呼ぶ。反対に、点（ｘ，ｙ）から起点
への変換を得るには、点及び方向（−ｘ，−ｙ，１．
０，０．０）から変換が得られることができる。この変
換を、ここでは「起点へのトランスレータ」と呼ぶ。

【０１０４】ボックス４００の動作は、起点から親ノー
ドの位置への第１のトランスレータ（translator）を得
て、次いでこの第１のトランスレータを距離Ｄのｘ及び
ｙ成分即ち（ＤΘx ，ＤΘy ）に適用することにより新
たなｘ及びｙ座標を得ることができる（ここで（Θx ，
Θy ）は、上述した子の方向である）。ボックス４００
の動作は次に、新たなｘ及びｙ座標に対する起点への第
２のトランスレータを得、そして子の方向（Θx ，Θy
）に第１のトランスレータを適用して得られたものに
第２のトランスレータを適用し、（Θx ，Θy ）の新た
な値を得る。

【０１０５】（Θx ，Θy ）の新たな値は、子ノードの
ウェッジの方向を示す。ボックス４００の動作は、ボッ
クス３９４又はボックス３９６からの初期幅Ｗ_n 及び距
離Ｄを用いることによって、次の子ノードのウェッジの
角度を得ることができる。ボックス４００の動作は、座
標（Ｄ，０．０）に対する起点へのトランスレータを
得、次いでこのトランスレータを cosＷ_n 及び sinＷ_n
に適用して、比Ｒを有する値を得ることができる。

【０１０６】最後に、ボックス４００の動作は、ボック
ス３６４の再帰的呼出しにおいて渡されるべきルーム境
界を得る際に使用されることのできるルームを得ること
ができる。利用可能なルームは、ボックス３９４又はボ
ックス３９６からの距離Ｄと初期幅Ｗ_n を用いて計算さ
れることができる。利用可能なルームは次いで、((ｓ ²
＋１．０）^1/2 −ｓ）と計算されることができ、ここで
ｓ＝((( １．０−Ｄ²)/２Ｄ)/(sinＷ_n ))である。

【０１０７】ボックス４０２の動作は次に、ボックス４
００からの利用可能なルームが、ボックス３９８からの
下位ルームより大きいかどうかに基づいて分岐する。大
きい場合には、ボックス４０４の動作はルーム境界を、
利用可能なルームの値に設定する。大きくない場合に
は、ボックス４０６の動作は、ルーム境界を下位ルーム
の値に設定する。

【０１０８】次に、現行ノードの全ての子が繰り返しル
ープによりハンドルされる（処理される）と、ボックス
４１０の動作は、ボックス３５０で受け取られたルーム
境界がボックス３９８からの下位ルームより大きいかど
うかに基づいて分岐する。大きい場合には、ボックス４
１２の動作は、ノードの半径をルーム境界の値に設定す
る。大きくない場合には、ボックス４１４の動作は、ノ
ードの半径を下位ルームの値に設定する。

【０１０９】図１０のオペレーションの結果、ブランチ
内のノードは略均一なスペーシングで離間される。それ
はなぜなら、基底スペーシングＳは、それより小さいス
ペーシングが発生しない最小値であるからであると共
に、他のスペーシングは、ノードの子の数と共にゆっく
りとしか増加しないために、Ｓと比べてたいして大きく
ないということがわかるからである。

【０１１０】図１１〜図１３は、双曲面からディスプレ
イ領域へのマッピングオペレーションを示す。図１１
は、レイアウト空間からディスプレイ位置へのマッピン
グが如何に実行されることができるかを示す。図１１の
技術を用いて、図７のボックス２６２及び２６４の動作
を実行することができ、同じ技術を用いて、図８のボッ
クス２８２及びボックス２８４の動作を実行することも
できる。図１２は、単位円においてノードのマッピング
位置が如何にして得られることができるかを示すと共
に、リンク特徴を表示することにおける関連オペレーシ
ョンを示す。図１３は、ノード特徴を表示することにお
けるオペレーションを示す。

【０１１１】図１１の技術は、上述の双曲面レイアウト
空間から単位円へ、そして単位円から円形のディスプレ
イ領域へとマッピングを行う。双曲面を単位円にマッピ
ングするには２つの標準的な方法がある。両方の方法に
おいて、双曲面における１つの近傍は円中心のフォーカ
スにレイアウトされ、一方双曲面の残りの部分は、円の
周囲方向に遠近法的な状態で消えていく。投影（projec
tive）マッピング即ちクレインモデル（Klein model ）
は、双曲面における線を単位円における線にするが、角
度を歪ませる。等角（conformal ）マッピング即ちポワ
ンカレモデルは、角度はそのまま保持するが、双曲面に
おける線を、単位円で弧となるように歪ませる。

【０１１２】ｒ_k ＝((２ｒ_p ) ／( １＋ｒ_p ²)) に従っ
て起点からの距離を再計算することにより、２つのマッ
ピング間で変換を行うことは容易であり、これら両方
を、走査検索の実行における使用に関して、実験により
テストした。ポアンカレモデルは、ノードにおいて扇の
広がった形状を保持すると共に、スクリーンの実面積
（screen real-estate）を用いることに関してより優れ
た仕事を行うので、ポアンカレモデルの機能の方が、よ
り良い。加えて、ディスプレイにおける弧は、ディスプ
レイにマッピングする際に生じている歪みの種類を暗示
する。従って、図１１の技術は、ポアンカレモデルを使
用する。ポアンカレモデルの下での双曲面の厳密な変換
は、単位円をそれ自体に送る複素平面での線形的部分変
換（linear fractional transformation）に対応する。
アールフォース，エル．ブイ．（Ahlfors, L.V. ）の
「複素分析（Complex Analysis）」（McGraw-Hill, 196
6 ）の７６〜８９頁には、線形部分変換の理論が述べら
れている。

【０１１３】ポアンカレ投影は、マッピングされた円が
起点から遠くなるにつれてその大きさが縮んでいくもの
の、双曲面上の円をユークリッド単位円上の円にマッピ
ングする。図１１の技術は、他のどのノードの円とも交
わらないように保証された、各ノードの回りの双曲面に
おける円を計算することにより、この特性を発揮する。
そのような円が単位円にマッピングされると、円は、ノ
ードの図式的又は組織的な表現がディスプレイされるこ
とになる円形のディスプレイ領域を各ノードに対して提
供する。これは、ノードが受け取る実際のスペースの量
に依存してノードの異なる表現を用いるという便宜と組
み合わせられることができる。

【０１１４】図１１において、ボックス５００の動作
は、図９のボックス３５０の動作と同じく、ノードリン
ク構造のルートノードのハンドルと共にマッピングに関
する呼出しを受け取る。ボックス５００の動作はまた、
現行トランスレータと呼ばれる変換；リンク機能と呼ば
れる、リンク特徴を表すための機能；ノード機能と呼ば
れる、ノード特徴を表す機能；ノード特徴を表す際にノ
ードがエッジに近すぎないかどうかを決定するために使
用される限界値；を受け取る。例えば、呼出しがアニメ
ートされる画像のシーケンス中に行われれば、限界値は
０．０７であることが可能であり、そうでない場合に
は、マッピングが実行されている円形のディスプレイ領
域の半径の逆数を得ることにより計算して、限界値はピ
クセルの大きさであることが可能である。満足できるア
ニメーションが必要な場合には、限界値は、表現をレン
ダリング（render）するのに必要な時間を減少するよう
に調整されることができる。

【０１１５】ボックス５０２の動作は、前のノード特徴
の位置を示す変数や、単位円の外周からの、上記前の位
置の半径方向のギャップを示す変数を含めて、複数の変
数を初期設定することにより、マッピングを開始する。
ボックス５０２の動作は以下に述べるように、限界値等
の、アニメートされる表現のシーケンス内で使用される
べき値を、予め計算することができる。

【０１１６】ボックス５０４の動作は、以下に述べる技
術を用いて、単位円における現行ノードのマッピング位
置（ｘ，ｙ）を得ることにより、図１１においてＤｏＮ
ｏｄｅと呼称される再帰的オペレーションを開始する。
マッピング位置は、レイアウト空間における現行ノード
の逆像である。ボックス５０６の動作は次いで、現行変
換を用いて、ボックス５０４からの位置を前ノード特徴
の位置に連結する線として実行されたリンク特徴を表示
する。

【０１１７】ボックス５１０の動作は、ボックス５０４
からの位置によりノード特徴が表されることができるか
どうかを決定する。これは、ボックス５０４からの位置
の半径方向ギャップを計算し、次にそれをボックス５０
２からの予め計算された限界値と比較して、それが単位
円の外周に近すぎる位置でないかどうかを決定すること
により実行される。ＤｏＮｏｄｅ内での計算を減少する
ために、半径方向ギャップを（１．０−（ｘ² ＋
ｙ² ））と計算する；それはなぜなら、（ｘ² ＋ｙ²）
の値は別の目的のためにも計算されなければならないか
らである。ボックス５０２の動作は、ボックス５００か
らの限界値を用いて、予め計算される限界値（１．０−
（１．０−限界値）² ）を得ることができる。半径方向
ギャップが予め計算された限界値より小さい場合には、
ボックス５０４からの位置は、単位円の外周に近すぎる
ということになる。

【０１１８】ボックス５０４からの位置が外周に近すぎ
る場合には、ボックス５１０の動作は、半径方向ギャッ
プを前位置の半径方向ギャップの９５％と比較して、そ
の子が現在の位置よりも単位円の外周から遠くにあり得
る状態で、その親からの方向に存在するかどうかを決定
する。ボックス５１０の動作が、位置及び方向が両方共
によくないことを見い出せば、ＤｏＮｏｄｅは終了す
る。しかし、現在の位置が単位円の外周に近すぎない場
合や、その子が現位置よりも外周から遠くにあり得るよ
うな場合には、現行ノードを表すノード特徴が表示され
得るので、ボックス５１２の動作は、その子の各々をハ
ンドルする（処理する）繰り返しループを開始する。

【０１１９】ＤｏＮｏｄｅに対して再帰的呼出しを繰り
返し行う際、ボックス５１４の動作は、前ノード特徴の
位置をボックス５０４からの位置にセットすることによ
り、そして前位置の半径方向ギャップをボックス５１０
で計算された半径方向ギャップにセットすることによ
り、各ループを開始する。これらの値は、ループ内で局
所的にセットされる。次にボックス５１６の動作は、次
の子に対してＤｏＮｏｄｅを子のハンドルとボックス５
０４からの親の位置と共に呼び出す。ボックス５１８の
動作は、ＤｏＮｏｄｅからリターンする。

【０１２０】全ての子がハンドルされて各々が単位円に
おけるマッピング位置を有すると、ボックス５２０の動
作は、ＤｏＮｏｄｅが終了する前に現行ノードのノード
特徴を表示する。従ってノード特徴は、ボックス５０６
で表されたリンク特徴の上に描かれる。ノード特徴は、
レイアウト空間におけるノードの位置と半径を用いて配
置され、ディスプレイ面においてマッピング領域を得る
ことができ、このマッピング領域は、後述するように中
心及び半径により規定される。ウェーハ変数がある場合
には、ノード特徴は、その中心に中心を置くテキストと
半径を有する円を含むが、テキスト変数がある場合に
は、ノード特徴は、その中心に中心を置くテキスト及び
矩形を含む。

【０１２１】ボックス５０６及びボックス５２０の動作
はそれぞれ、ディスプレイ２０８上に特徴を表示するこ
とを含む。これらの動作は、従来のディスプレイドライ
バ技術を用いて、使用されている指定ディスプレイシス
テムに適切なように実行されることができる。一般に、
これらの動作は、単位円位置からディスプレイ位置への
一定の変換を行う。

【０１２２】図１２は、ボックス５０４及びボックス５
０６の動作が実行されることのできる方法を示す。

【０１２３】ボックス５４０の動作は、ＤｏＮｏｄｅ呼
出しをノードのハンドルと親の変換位置と共に受け取
る。ノードがルートノードである場合には、親の変換位
置は、それ自身の変換位置とされる。そうでない場合に
は、親の変換位置は、以下に述べられるように現行トラ
ンスレータを適用することにより以前に得られたもので
ある。

【０１２４】ボックス５４２の動作は、ノードのハンド
ルを使用して、レイアウト空間におけるその位置を得る
が、該位置は、図９のボックス３７２に関して述べたよ
うにノードのデータ構造から得られることができる。ボ
ックス５４４の動作は次に、ボックス５００からの現行
トランスレータをボックス５４２からのノード位置に適
用して、レイアウト空間における変換位置を得る。トラ
ンスレータは、図１０のボックス４００に関して上述し
たように得られることができる。

【０１２５】ボックス５００からのリンク機能は、ボッ
クス５４０からの親の位置と、ボックス５４４からの変
換位置と共に呼び出されて、図１２における残りの動作
が実行されることができる。リンク機能は、親の変換位
置と現行ノードの変換位置とを用いてマッピング位置を
得ることにより、ボックス５４６において開始する。こ
の実施の形態では、ウィンドウの左上の角から（Ｒ_d ，
Ｒ_d ）に中心を置く半径Ｒ_d の円形のディスプレイ領域
へとマッピングされると、各座標ｃのマッピングは、
（ｃＲ_d ＋Ｒ_d ＋０．５）の下のフロア（floor ）を計
算することにより、得られることができる。このマッピ
ングは、レイアウト空間から単位円へのインプリシット
なマッピングを含み、それは、レイアウト空間における
位置の座標を単位円での位置のｘ座標及びｙ座標として
得ることにより実行される。次いで単位円位置が、上記
計算によりディスプレイ位置にマッピングされる。

【０１２６】リンク機能は、弧であるリンク特徴をディ
スプレイすることが適切であるかどうかを決定すること
により、ボックス５５０で継続する。弧は、例えば、ア
ニメーションシーケンス中には適切であり得ない；それ
はなぜなら、弧が付加的な計算を必要とするからであ
る。あるいは、ボックス５４６からのマッピング位置同
士間の差が小さい場合に弧は適切であり得ないので、弧
はいずれにしても略線として現れるであろう。弧が適切
でない場合には、ボックス５５２の動作は、ボックス５
４６からのマッピング位置を連結する直線を引く。

【０１２７】弧が適切である場合には、ボックス５５４
の動作は、ボックス５４０からの親の位置（ｘ_p ，
ｙ_p ）とボックス５４４からの変換位置（ｘ_t ，ｙ_t ）
とを使用して、ディスプレイ空間における弧の曲率半径
を計算することにより開始する。ボックス５５４の動作
は、２つの点を通ると共に９０度で境界円と交わる弧の
曲率の中心を得ることにより、実行されることができ
る。これは、レイアウト空間における２つの点同士の間
の線からマッピングされた弧である。次に計算により、
曲率半径を得ることができる。

【０１２８】ボックス５５４の動作は、ｄ＝２（ｘ_p ｙ
_t −ｘ_t ｙ_p ）という値をまず得て、次いでａ＝((１＋
ｘ_t ² ＋ｙ_t ² )/ｄ) とｂ＝((１＋ｘ_p ² ＋ｙ_p ² )/
ｄ) という２つの値を得ることができる。曲率の中心
は、ｘ_c ＝ｂｙ_t −ａｙ_p 、ｙ_c＝ａｘ_p −ｂｘ_t であ
るような点（ｘ_c ，ｙ_c ）である。曲率半径は、曲率の
中心から、親の変換位置（ｘ_p ，ｙ_p ）か現行ノードの
変換位置（ｘ_t ，ｙ_t ）のいずれかまでの距離として、
計算されることができる。

【０１２９】ボックス５５６の動作は、ボックス５５４
からの曲率半径が正確なドローイング（drawing ）に対
して大きすぎないかどうかを決定する。大きすぎる場合
には、ボックス５５２の動作は、上述のように直線を引
く。しかしながら、半径が十分に小さい場合には、ボッ
クス５５８の動作は、従来の計算を用いて、ボックス５
５４で計算されたように、ディスプレイ上に弧を描く。

【０１３０】ボックス５５２の動作又はボックス５５８
の動作の後、図１２の技術は図１１のボックス５１０に
戻る。

【０１３１】図１３は、図１１のボックス５２０の動作
が実行されることのできる方法を示す。

【０１３２】図１３のボックス５７０の動作は、ノード
特徴を表示することが適切であるかどうかを検査するこ
とにより開始する。この動作は、ノード特徴がディスプ
レイされるべきことを示すようにパラメータが設定され
るのかどうか、又はアニメーションシーケンスに対して
は、ノード特徴がアニメーションの間にディスプレイさ
れるべきではないことを示すようにパラメータが設定さ
れるのかどうか、を決定することを含む。ノード特徴の
表示が適切でない場合には、ＤｏＮｏｄｅは終了する。

【０１３３】ノード特徴の表示が適切である場合には、
ボックス５７２の動作は、ボックス３７２に関して述べ
られたデータ構造からの現行ノードの位置及び半径を使
用して、単位円における中心位置と単位円内半径を得
る。中心位置のｘ及びｙ座標は、各々に((１．０−ｒ_j
² )/( １．０−( ｘ² ＋ｙ² ) ｒ_j ² ))を乗算すること
により得られることができ、ここで、ｒ_j は現行ノード
の半径であり、例えば０．９より小さい数を乗算される
ことにより、ノード同士間にギャップを付加するように
任意に調整される。ボックス５７２の動作は、半径ｒ_j
に((１．０−( ｘ ² ＋ｙ² ))/(１．０−( ｘ² ＋ｙ² )
ｒ_j ² ))を乗算して、単位円内半径ｒ_u を得ることがで
きる。

【０１３４】次にボックス５７４の動作は、ボックス５
７２からの中心位置と単位円内半径ｒ_u を用いて、ディ
スプレイ上の対応する円を囲む境界ボックスの左上の角
にディスプレイ位置を得るとともに、ディスプレイ上の
対応する円の直径を得る。左上角のｘ及びｙ座標はそれ
ぞれ、座標ｃを用いて、（Ｒ_d （ｃ−ｒ_u ）＋Ｒ_d ＋
０．５）の下のフロアを計算することにより、得られる
ことができる。直径は、値（Ｒ_d ( ｘ＋ｒ_u ）＋Ｒ_d ＋
０．５）の下のフロアと、値（Ｒ_d （ｘ−ｒ_u ）＋Ｒ_d
＋０．５）の下のフロアとの間の差として得られること
ができる。

【０１３５】次にボックス５７６の動作は、ボックス５
７４からの大きさに合うキャラクタの総数を得る。総数
は、サイズにおけるフロアファンクションとキャラクタ
サイズに関して得られることができる。ボックス５８０
の動作は、総数が２より大きいかどうかにより分岐す
る。２より小さければ、ＤｏＮｏｄｅは、意味のあるテ
キストを表現するのにサイズが不十分であるため、終了
する。

【０１３６】総数が２より大きい場合には、ボックス５
８２の動作は、テキストの位置を得る。例えばｘ座標
は、マッピングされたサイズと、そのノードのテキスト
中のキャラクタの数とキャラクタサイズとの積と、の差
の半分とマッピングされたｘ座標との合計であることが
可能である。ｙ座標は、（Ｒ_d ｙ＋Ｒ_d ＋０．５）の下
のフロアであることが可能であり、ここでｙはボックス
５７２からの中心のｙ座標である。

【０１３７】次にボックス５９０の動作は、ウェーハが
表示されるべきか矩形が表示されるべきかに基づいて分
岐する。ウェーハの場合には、ボックス５９２の動作
は、ボックス５７４からのマッピング位置に円を描く。
矩形の場合には、ボックス５９４の動作は、テキストの
回りに合う矩形を、ボックス５８２からの位置に描く。
次に、ボックス５９６の動作は、ＤｏＮｏｄｅが終了す
る前にボックス５８２からの位置にテキストを描く。

【０１３８】以下に述べるように、図１１〜図１３の技
術は、位置の変更に対する要求に応答して使用されるこ
ともできる。

【０１３９】図１４〜図１６は、表現の位置の変更を要
求するユーザからの信号に応答するオペレーションを示
す。図１４は、ＣＰＵ２０２が、レイアウト空間にマッ
ピングすると共に変換を得てそれを適用することによ
り、ユーザからの信号に如何に応答することができるか
を示す。図１４の技術を用いて、図７のボックス２７
２、２７４、及び２７６の動作を実行することができ、
同じ技術を用いて、図８のボックス２９２及び２９４の
動作を実行することができる。図１５は、ルートノード
のオリエンテーションを保持しながら、第１の位置から
第２の位置への変換を得る方法を示す。図１６は、右方
向へ、より大きいスペーシングの領域の中心にノードの
子を方向づけながら、第１の位置から第２の位置への変
換を得る方法を示す。

【０１４０】図１４の技術は、双曲面における構造を平
行移動して、連続的且つ幾何学的なフォーカス移動方法
を提供する。ユーザは、構造全体の視覚的な構成を維持
しながら、構造を容易に走査検索することができる。ユ
ーザは、目に見える任意の点をクリックして、それを中
心にあるフォーカスに持っていくか、あるいは目に見え
る任意の点を任意の他の位置に対話的にドラッギングす
るかのいずれかにより、フォーカスを変更することがで
きる。どちらの場合にも、表現の残りの部分は適切に変
換される。中心に近づく領域は大きくなり、元は中心に
あった領域は、エッジ近くになるにつれて縮んでいく。

【０１４１】２つの変換の合成を計算するために、点
（０，０）が第１の変換の下で変換され、次にその結果
に対して第２の変換が行われることができる。次に、同
様のことが、点（０，１）に対して行われることができ
る。それら２つの点の画像は、合成を識別するのに十分
であり、適切な幾何学的オペレーションは、その情報か
ら直接的に演算されることができる。

【０１４２】図１４のボックス６１０の動作は、表現が
表示されているディスプレイ領域において、第１の位置
と第２の位置を示す位置の変換に対する呼出しを受け取
る。ドラッギングオペレーションでは、第１及び第２の
位置は、明確に示されることができる。クリックオペレ
ーションでは、第１の位置がクリック位置であり、第２
の位置がディスプレイ領域の中心であることが可能であ
る。

【０１４３】ボックス６１２の動作は、ボックス６１０
からの第１及び第２の位置を、双曲的ジオメトリオペレ
ーションが実行されることのできる単位円座標に変換す
ることにより、開始する。この実施の形態では、表現は
ウィンドウ内の半径ｒの円形ディスプレイ領域に表示さ
れるので、ボックス６１２の動作は、各座標をｒで割っ
て１．０を減算することにより、実行されることができ
る。

【０１４４】ボックス６２０の動作は次に、ボックス６
１２からの単位円位置のいずれかが、単位円のエッジに
近すぎないかどうか（例えばエッジの約０．０２５範囲
内にあるかどうか）を検査する。いずれかが近すぎる場
合には、ボックス６２２の動作は、起点からその位置ま
での距離の９７％を各座標に乗算するなどして、エッジ
に近すぎる位置を調整する。このように、エッジに近す
ぎる位置をエッジから遠くなるよう移動させるように、
各座標をわずかに減らす。

【０１４５】ボックス６１２の変換と、必要であればボ
ックス６２２の調整は、第１の位置の逆像と第２の位置
の逆像の両方を、レイアウト空間に生成する。

【０１４６】次にボックス６２４の動作は、第１の位置
の逆像を第２の位置の逆像にする、レイアウト空間にお
ける変換を見い出すことにより、トランスレータを得
る。以下に詳細に述べる技術を用いてトランスレータを
得ることができる。

【０１４７】図１４の技術は、ボックス６３０の動作に
示されるように、アニメーションが実行されているか否
かに依存して、２つの異なる経路をとることができる。
ドラッギングオペレーションでは、アニメーションは連
続性の知覚を生じる必要がないこともあるが、クリック
オペレーションでは、連続性の知覚を生じる、より小さ
いステップのアニメートシーケンスに分割されることが
必要であり得る。

【０１４８】アニメーションが実行されていない場合に
は、ボックス６３２の動作は、ボックス６２４からのト
ランスレータを現行平行移動と合成することにより、新
たな現行平行移動を得る。これは、平行移動（translat
ion ）を用いて、レイアウトデータからディスプレイ表
現を得るという意味である。新たな値Ｐ_n とΘ_n を、Ｐ
_n ＝((Ｐ₁ ＋Ｐ₂ Θ₁ )/( １．０＋Ｐ₁ ^* Ｐ₂ Θ₁ ）
（ここで、Ｐ₁ ^* はＰ₁の複素共役である）、Θ_n ＝
((Θ₂(Θ₁ ＋Ｐ₁ Ｐ₂ ^* ))/(１．０＋Ｐ₁ ^* Ｐ₂ Θ ₁ )
と計算することにより、各々が点Ｐ_i と回転角度Θ
_i （ｉはトランスレータを示す）により規定される、第
１のトランスレータと第２のトランスレータの合成が得
られることができる。合成されると位置の交換が可能で
ないため、トランスレータが合成される順序は、結果と
して得られる平行移動に影響を及ぼす。

【０１４９】ボックス６３４の動作は、ボックス６３２
からの新たな現行平行移動をレイアウトデータに適用し
て、変換位置を得、次いで変換位置をマッピングし、図
１１に関して上述されたように表現を表示する。こうし
て、ボックス６１０の呼出しに対する応答が終了する。

【０１５０】アニメーションが実行されている場合に
は、ボックス６４０の動作は、以下に述べるようにボッ
クス６２４からのトランスレータのｎ番目のルートを得
る。次に、ボックス６４２の動作は、中間的平行移動
を、表現を表示するために用いられる現行平行移動に初
期設定することにより、繰り返しループに備える。ボッ
クス６４４の動作は、ｎ回実行される繰り返しループを
開始して、ｎ個の中間的平行移動を得る。ボックス６４
６の動作は、ボックス６４０からのｎ番目のルートを中
間的トランスレータと合成し、ボックス６３２に関して
述べた合成技術を用いて、新たな中間的平行移動を得
る。次に、ボックス６４８の動作は、ボックス６４６か
らの新たな中間的平行移動を、中間的平行移動の待ち行
列に加える。

【０１５１】ｎ個の中間的平行移動が待ち行列に加えら
れた後、ボックス６５０の動作は、ボックス６２４から
のトランスレータを、表現の表示に用いられる現行平行
移動と合成することにより、最終の平行移動を得る。ボ
ックス６５２の動作は、最終の平行移動を待ち行列に加
え、次いでボックス６５４の動作は待ち行列を通って、
レイアウトデータに各平行移動を適用して変換位置を
得、次いで、変換位置をマッピングすると共に、ボック
ス６３４に関して上述したように表現を表示するが、待
ち行列に加えられた各々の平行移動に対して１つの表現
を有する。こうして、ボックス６１０の呼出しに対する
応答が終了する。

【０１５２】ボックス６４０の動作は、トランスレータ
の点Ｐ_t と回転角度Θ_t を用いて以下のようにｎ番目の
ルートを得ることができる。３つのケースのどれを適用
するかを決定するために、ボックス６４０の動作は、ｄ
＝（４｜Ｐ_t ｜² −｜Θ_t −１｜² ）を得ることができ
る。ボックス６４０の動作はまた、例えばｑ_a ＝（｜Θ
_t −１｜² ／｜Θ_t ＋１｜² ）及びｑ_b ＝（ｄ／｜Θ_t
＋１｜² ）のように、１つより多いケースにおいて使用
可能な値を予め計算することも可能である。

【０１５３】ｄ＞０であれば、ボックス６４０の動作
は、ａ₁ ＝（tanh((atanh(ｑ_b ^1/2))/ｎ）／(
ｑ_b ^1/2)) 、ｔ₁ ＝ａ₁ ²ｑ_a 、及びｒ₁ ＝ａ₁ ((１＋ｑ
_a ）／（１＋ｔ ₁ ))^1/2 を得ることができる。

【０１５４】ｄ＝０であれば、ボックス６４０の動作
は、ｔ₂ ＝（ｑ_a ／ｎ² ）、ｒ₂ ＝((( １＋ｑ_a ）／
（１＋ｔ₂ ))^1/2 ／ｎ）という同様の値を得ることがで
きる。

【０１５５】ｄ＜０である場合には、ボックス６４０の
動作は、ａ₃ ＝((tan((atan(−ｑ_b ^1/2))/ｎ))、ｔ₃ ＝
（ａ₃ ²｜Θ_t −１｜² ／（−ｄ))、及びｒ₃ ＝（４ｔ₃
／((１＋ｔ₃ )(｜Θ_t −１｜² ))^1/2 を得ることができ
る。

【０１５６】次に、ボックス６４０の動作は、実部((１
−ｔ_i ）／（１＋ｔ_i ))と虚部（２ｔ_i ^1/2 / ( １＋ｔ
_i ))（ここで、ｔ_i は上述のように適用可能なケースに
対する値である）を有する複素角度Θ_r をまず得ること
により、ｎ番目のルートトランスレータの回転角度Θ_n
を得ることができ、また複素平方根に対するブランチカ
ットが選択されて、より小さい絶対回転を有する角度が
与えられる。Θ_r は、Θ_n を得るために１という大きさ
を有するように正規化される。

【０１５７】最後に、ボックス６４０の動作は、ｎ番目
のルートトランスレータの点Ｐ_n を、Ｐ_n ＝Ｐ_t ｒ_i (
Θ_n ／Θ_t ）^1/2 （ここで、ｒ_i は上述のように適用可
能なケースに対する値である）として得ることができ
る。

【０１５８】図１５は、第１の位置（ｘ₁ ，ｙ₁ ）から
第２の位置（ｘ₂ ，ｙ₂ ）へのトランスレータを得ると
共に、第３の位置（ｘ₃ ，ｙ₃ ）のオリエンテーション
を保持するために、ボックス６２４の動作が如何に実行
されることができるかを示す。示されるように、図１５
の動作は、図１４のボックス６２０又はボックス６２２
のいずれかの後に続き、この実施の形態では、ドラッギ
ング呼出しに応答しての実行の場合にはボックス６３２
に先行し、クリック呼出しに応答しての実行の場合には
ボックス６４０に先行する。ドラッギング呼出しに応答
して呼び出される場合には、第１の位置はドラッギング
動作の開始位置であり、第２の位置は終了位置である。
クリック呼出しに応答して呼び出される場合には、第１
の位置はクリックの位置であり、第２の位置は単位円の
起点である。どちらの場合にも、第３の位置は、ルート
ノードの現在位置であり、この現在位置は、レイアウト
空間において位置（０，０）に現行平行移動を実行する
ことにより得られる。

【０１５９】ボックス６７０の動作は、第３の位置から
起点への第１のトランスレータを得、図１０のボックス
４００に関して上述したように実行されることができ
る。次にボックス６７２の動作は、第１の位置に第１の
トランスレータを適用し、第１の変換位置を得る。

【０１６０】ボックス６７４の動作は、回転成分を有さ
ないと共に、第１の変換位置（ｘ_a，ｙ_a ）を第２の位
置（ｘ_b ，ｙ_b ）に移す第２のトランスレータを得る。
ボックス６７４の動作は、点Ｐ₂ と回転角度（１．０，
０．０）を有するトランスレータを得ることにより、実
行されることができる。ボックス６７４の動作は、複素
値((Ｂ−Ａ)(１＋( ＡＢ )^* ) / ( １− (｜ＡＢ
｜^* )²）の実部を得ることにより、Ｐ₂ の実部を得るこ
とができる。ボックス６７４の動作は同様に、複素値
((Ｂ−Ａ)(１−( ＡＢ )^* ) /(１− (｜ＡＢ｜^* )²) の
虚部を得ることにより、Ｐ₂ の虚部を得ることができ
る。これらの式において、Ａ＝ｘ_a ＋ｉｙ_a 、Ｂ＝ｘ_b
＋ｉｙ_b である。

【０１６１】ボックス６７６の動作は次に、ボックス６
７４から得られた第２のトランスレータとボックス６７
０から得られた第１のトランスレータとの合成であるト
ランスレータを得る。ボックス６７６から得られたトラ
ンスレータは次に、図１４のボックス６３２の動作にお
いて、又はボックス６４０及びボックス６５０の動作に
おいて、実行されることができる。

【０１６２】図１６は、ノード特徴の子が右方向への方
向付けで、より大きいスペーシングの領域の中心付近に
あるように、第１の位置から起点である第２の位置への
トランスレータを得るために、ボックス６２４の動作が
実行されることのできる方法を示す。示されるように、
図１６の動作は、図１４のボックス６２０又はボックス
６２２のいずれかの後に続くと共に、この実施の形態で
は、クリック呼出しに応答して実行されるだけなので、
図１６の動作はボックス６４０に先行する。第１の位置
はクリック位置である。

【０１６３】ボックス６９０の動作は、第１の位置から
起点への第１のトランスレータを得ると共に、図１０の
ボックス４００に関して上述したように実行されること
ができる。ボックス６９２の動作は、ボックス６９０か
ら得られた第１のトランスレータと、ディスプレイされ
る表現を得るために使用される現行トランスレータとの
合成である第２のトランスレータを得る。

【０１６４】ボックス６９４の動作は、現行変換の反転
を適用して、第１の位置の逆像を得る。点Ｐと回転角度
Θとにより規定される変換は、点（−ＰΘ^* ）と回転角
度Θ ^* とによる変換を得ることにより、反転されること
ができる。ボックス６９４の動作はまた、第１の位置の
逆像を用いて、最も近いノードの親を見い出す。

【０１６５】ボックス７００の動作は、ボックス６９４
からの親ノードの位置にボックス６９２からの第２のト
ランスレータを適用すると共に、その結果が１という大
きさを有するように正規化して、親の方向（Θx ，Θy
）を得る。ボックス７０２の動作は次に、起点を移動
することなくレイアウト空間を親方向に回転する第３の
トランスレータを得る。第３のトランスレータは、
（０，０）という点と（−Θx ，Θy ）を有することが
できる。

【０１６６】次にボックス７０４の動作は、ボックス７
０２から得られた第３のトランスレータをボックス６９
２から得られた第２のトランスレータと合成することに
より、第４のトランスレータを得る。次に、ボックス７
０６の動作は、ボックス７０４からの第４のトランスレ
ータと、現行平行移動の反転とを合成することにより、
トランスレータを得る。ボックス７０６からのトランス
レータは、図１４のボックス６４０及び６５０の動作に
おいて使用されることができる。

【０１６７】上述の実行は、円形のディスプレイ領域に
表現を表示するが、表現は、双曲面からの適切なマッピ
ングを介して、楕円のような任意の他の適切な形状のデ
ィスプレイ領域にも表示されることができる。

【０１６８】上述の実行は、単一のより大きいスペーシ
ングの領域を有するように表現を示すが、表現は、より
多くのノード特徴にフォーカスを当てるために、２つ以
上の、より大きいスペーシング領域を有するように表示
されることができる。特に興味深いのは、ポアンカレマ
ップにおける点（ａ，０）及び点（−ａ，０）がそれぞ
れ、双眼鏡で見た場合のような（２つの）より大きいス
ペーシング領域の中心となる、２重フォーカス表現であ
る。この表現の場合、ポアンカレマップにより表現され
る双曲面における点ｚは、ディスプレイ空間における
((ｚ（１−ａ²) /(１−ａ² ｚ²)) にマッピングされ
る。

【０１６９】上述の実行は、双曲面を使用するが、双曲
的なｎ空間等の負の曲率を有する別の空間を使用するこ
ともできる。

【０１７０】上述の実行は、双曲面において位置を表示
するのに複素数を使用するが、それは一部には、複素数
における連続関数が等角マッピングであるからである。
しかしながら、双曲面における位置は、他のタイプのデ
ータ又は座標を用いて表示されることができる。

【０１７１】上述の実行は、双曲面から単位円へ、そし
て単位円から円形のディスプレイ領域へとマッピングす
るが、レイアウト空間からディスプレイ領域への他のタ
イプのマッピングを使用することもできる。例えば、ポ
アンカレモデルからクラインモデルへのマッピングは実
験段階ではまだ満足がいく程には実行されなかったが、
このようなマッピングも使用することができる。

【０１７２】アニメーションを実行することにおいて、
上述の実行は、ｎ個（ｎは定数）のステップを使用す
る。アニメーションの数は、定数ではなく、アニメート
動作が生じている開始位置と終了位置との間の距離に依
存する変数であることも可能である。

【０１７３】ループ型の走査検索を行うことにおいて本
発明を使用した。

【０１７４】さらに、負の曲率を有する空間においてノ
ードリンク構造を均一にレイアウトすることは、インタ
ラクティブボイスシステムに適用されることができ、ま
た、レイアウト空間からサウンドレンダリングへのマッ
ピングが実行されることが可能である。

【図面の簡単な説明】

【図１】ノードリンクデータを用いて、負の曲率を有す
る空間における位置を示すレイアウトデータを得、それ
により２つ以上の異なるマッピングが達成されることの
できる方法を示す概略的フローチャートである。

【図２】図１のようにレイアウトデータを得ると共にマ
ッピングを達成することにおける概括的な動作を示すフ
ローチャートである。

【図３】ノードリンク構造の第１及び第２の表現が如何
に表示されるかを示す概略的なフローチャートであり、
この第２の表現は、第１の表現における、第１の位置か
ら第２の位置への変更を指示する信号に応答して自動的
に表示される。

【図４】図３のように第１及び第２の表現を表示するこ
とにおける概括的な動作を示すフローチャートである。

【図５】図１のようにレイアウトデータを得てマッピン
グを実行し、また図３のように第１及び第２の表現を表
示するマシンの概括的な構成要素を示す概略図である。

【図６】負の曲率を有するレイアウト空間においてノー
ドリンク構造をレイアウトし、次いでマッピングを行っ
てディスプレイ上にノードリンク構造の表現を表示する
ことのできるシステムの構成要素を示す概略ブロック図
である。

【図７】図６のマシンが、位置の変更に関する要求に応
答して、エッジに近すぎないノードの部分集合の位置を
変換し且つマッピングすることにより、走査検索インタ
フェースを提供することのできる動作を示すフローチャ
ートである。

【図８】図６のマシンが、位置の変更に関する要求に応
答して、全ノードの位置を連続的に変換し且つマッピン
グすることにより、走査検索インタフェースを提供する
ことのできる動作を示すフローチャートである。

【図９】図７の技術を実行する図６のシステムによるレ
イアウトオペレーションにおける動作を示すフローチャ
ートである。

【図１０】ノードの子までの距離、子の位置、ルーム境
界、及びノードの半径を図９において得ることのできる
動作を示すフローチャートである。

【図１１】図７の技術を実行する図６のシステムによる
レイアウト空間からディスプレイ位置へのマッピングに
おける動作を示すフローチャートである。

【図１２】単位円におけるノードのマッピング位置を得
ると共に、リンク特徴を表示することのできる図１１の
動作を示すフローチャートである。

【図１３】図１１におけるノード特徴を表示する動作を
示すフローチャートである。

【図１４】図７の技術を実行する図５のシステムによ
る、位置の変更を要求するシステムに応答する動作を示
すフローチャートである。

【図１５】図１４のルートノードのオリエンテーション
を保持するトランスレータを得ることのできる動作を示
すフローチャートである。

【図１６】より大きいスペーシングを有する領域の中心
にある或るノードの子ノードを起点として右方向に再配
置するトランスレータを得ることのできる、図１４の動
作を示すフローチャートである。

【符号の説明】

１０ ノードリンクデータ ２０ ノードリンク構造 ２２ 最上位レベルノード ２４、２６、２８ 下位レベルノード ３０ レイアウトデータ ３２ 負の曲率を有する空間 １５０ マシン １５２ プロセッサ １５４ ユーザ入力回路 １５６ ディスプレイ １５８ ノードリンクデータ １６０ 命令 １６２ 命令入力回路

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｇ０６Ｆ 17/00 Ｇ０６Ｔ 11/80 9365−5Ｈ Ｇ０６Ｆ 15/62 ３２２ Ｂ (72)発明者 ラマナ ビー．ラオ アメリカ合衆国 カリフォルニア州 94112 サンフランシスコ イナ コート 50

Claims (2)

【特許請求の範囲】
1. 【請求項１】 ノードリンク構造レイアウト方法であっ
   て、 レイアウトデータを得るステップを有し；該レイアウト
   データは、ノードリンク構造部分に対するレイアウト空
   間内位置を示し；前記レイアウト空間は負の曲率を有す
   る空間であり；前記ノードリンク構造は、ノード及びリ
   ンクを含み、各リンクはノードの中の少なくとも２つに
   関連し；前記レイアウトデータは、ノード集合に対する
   レイアウト空間内位置を示し；前記ノード集合は、最上
   位レベルと少なくとも１つの下位レベルとを含む２つ以
   上のノードレベルを有するブランチを形成し、該最上位
   レベルが最上位レベルノードを含み、該下位レベルが下
   位レベルノードを含み、各下位レベルにおける各ノード
   が、次に高いレベルに親ノードを有すると共にこの親ノ
   ードに１つのリンクを介して関連づけられ；２つ以上の
   親ノードの集合中の各々に対して、前記レイアウトデー
   タが、 親ノードに対するレイアウト空間における親位置を示
   し、 親ノードを共有する多数の下位レベルのノードに対する
   レイアウト空間における円に略沿った形で存在する子位
   置を示し、前記親位置が前記円の略中心にあり、前記下
   位レベルノード数が２つ以上であり、円に沿って隣接す
   る子位置が略基底スペーシングだけ離間され；前記円
   が、下位レベルノード数と共にゆっくりと増大する関数
   を近似する半径を有し、よって該半径と、円に沿って隣
   接する子位置同士間のスペーシングとが全て前記ブラン
   チ内で略均一であり；前記方法がさらに、 前記レイアウトデータを用いてノードリンク構造の第１
   の表現をディスプレイ上に表示するステップを有し；ユ
   ーザからの信号を受け取るステップを有し；該信号が第
   １のディスプレイ位置から第２のディスプレイ位置への
   変更を示し；前記第１の表現が第１のディスプレイ位置
   付近に第１の特徴を含み、該第１の特徴がノードリンク
   構造の第１の部分を表し；前記信号に応答して、ノード
   リンク構造の第２の表現をディスプレイに表示するステ
   ップを有し；該第２の表現がノードリンク構造の第１の
   部分を表す第２の特徴を含み、該第２の特徴が第２のデ
   ィスプレイ位置付近に表示され；前記第２の表現が前記
   第１の表現の変更された継続として知覚されることがで
   きる、ことを特徴とするノードリンク構造レイアウト方
   法。
2. 【請求項２】 マシンを動作する方法であって、 該マシンが、メモリと、該メモリに格納されたデータを
   アクセスするように接続されるプロセッサと、該メモリ
   に格納されるノードリンクデータと、を含み、該ノード
   リンクデータがノードリンク構造を規定し、該ノードリ
   ンク構造がノード及びリンクを含み、各リンクが少なく
   とも２つのノードに関連し、 前記マシン動作方法は、 プロセッサを操作してノードリンクデータを用いてレイ
   アウトデータを得るステップを有し；前記レイアウトデ
   ータが、ノードリンク構造部分に対するレイアウト空間
   内位置を示し、該レイアウト空間が負の曲率を有する空
   間であり；前記ノードリンク構造がノード及びリンクを
   含み、各リンクがノードの中の少なくとも２つに関連
   し；前記レイアウトデータが、ノード集合に対するレイ
   アウト空間内位置を示し；前記ノード集合が、最上位レ
   ベルと少なくとも１つの下位レベルとを含む２つ以上の
   ノードレベルを有するブランチを形成し、各下位レベル
   における各ノードが、次に高いレベルに親ノードを有
   し、ノードが親ノードに対して１つのリンクを介して関
   連づけられ；２つ以上の親ノードの集合中の各々に対し
   て、前記レイアウトデータが、 親ノードに対するレイアウト空間における親位置を含
   み、 前記親ノードを共有する多数の下位レベルのノードに対
   するレイアウト空間における円に略沿った形で存在する
   子位置を含み、前記親位置が円の略中心にあり、下位レ
   ベルノード数が２つ以上であり、前記円に沿って隣接す
   る子位置が、略基底スペーシングだけ離間され、 前記円が、下位レベルノード数と共にゆっくりと増大す
   る関数を近似する半径を有し、よって半径と、円に沿っ
   て隣接する子位置同士間のスペーシングとが全てブラン
   チ内において略均一であり、 前記マシン動作方法がさらに、 前記プロセッサを動作して、レイアウトデータを用いて
   ２つ以上の異なるマッピングを実行するステップを有
   し；各マッピングによりマッピングデータが得られ；各
   マッピングにより得られたマッピングデータがノード集
   合の部分集合の位置を示す、 ことを特徴とするマシン動作方法。