(57)【特許請求の範囲】
【請求項１】
プロセッサと、メモリと、ディスプレイと、インプット装置を含むディスプレイ制御システムにおいて、ノードリンクダイヤグラムにおけるノードの移動に応じて任意形状のリンクを曲線変換するための方法であって、前記ノードリンクダイヤグラムはリンクを介して第二ノードにリンクされた第一ノードを有し、前記リンクは前記第一ノードに第一アタッチポイントで接触し及び前記第二ノードに第二アタッチポイントで接触し、前記方法が、
ａ）前記プロセッサがリンクセグメント情報を含むリンク形状情報を前記メモリに格納するステップを含み、
ｂ）前記プロセッサが前記インプット装置による前記第二ノードの移動を検出するステップを含み、
ｃ）前記プロセッサが前記移動した第二ノードの目的地で前記第二ノードのための第三アタッチポイントを識別するステップを含み、前記第三アタッチポイントは前記第二ノード上の前記第二アタッチポイントと同じ位置にあり、
ｄ）前記プロセッサが前記格納されたリンク形状情報に基づいて前記リンクのためのリンクの置き換えデータを生成するステップを含み、
ｅ）前記プロセッサが前記リンクの各セグメントを変換して前記リンクを曲線変換するステップを含み、各セグメントの前記変換が、
ｅ１）前記セグメントのためのアークの長さを決定するサブステップを含み、
ｅ２）前記セグメントの長さ及び前記セグメントの前記アークの長さに基づいて変換ファクタを決定するサブステップを含み、
ｅ３）前記変換ファクタ、リンク置き換えデータ及び元のセグメントの終点位置に基づいて変換されたセグメントの位置及び長さを決定するサブステップを含み、及び、
ｅ４）前記変換されたセグメントの終点位置と先に変換されたセグメントの終点との間の前記変換されたセグメントをディスプレイするサブステップを含む、
任意形状のリンクの曲線変換方法
【請求項２】
プロセッサと、メモリと、ディスプレイと、インプット装置を含むディスプレイ制御システムにおいて、ノードが移動するときにノードリンクダイヤグラムのトポロジを維持するための方法であって、前記ノードリンクダイヤグラムがリンクを介して第二ノードにリンクされる第一ノードを有し、前記リンクが第一アタッチポイントで前記第一ノードに接触し及び第二アタッチポイントで前記第二ノードと接触し、前記方法が、
ａ）前記プロセッサが前記インプット装置によってユーザが前記ノードリンクダヤグラムにおいて前記第二ノードを移動したことを検出するステップを含み、
ｂ）前記プロセッサが前記リンクを再整形するための座標系の原点として前記第一アタッチポイントを定めるステップを含み、
ｃ）前記プロセッサが前記移動した第二ノードに基づいて第三アタッチポイントを決定するステップを含み、
ｄ）前記プロセッサが前記第二アタッチポイント及び前記第三アタッチポイントのための象限を決定するためのステップを含み、
ｅ）前記第二アタッチポイント及び前記第三アタッチポイントのための象限が同じである場合、前記プロセッサが元のリンクの形状特性に基づいて前記第二ノードを移動するのに応じて前記リンクを曲線変換するステップを含み、
ｆ）前記第二アタッチポイント及び前記第三アタッチポイントのための象限が異なる場合、前記プロセッサが前記リンクを再整形するステップを含み、前記再整形ステップが、
ｆ１）前記リンクを前記第三アタッチポイントの前記象限に反転するサブステップを含み、
ｆ２）前記反転されたリンクの形状特性に基づいて前記リンクを曲線変換するステップを含む、
ノードリンクダイヤグラムのトポロジを維持するための方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はグラフィックベースのコンピュータシステムにおけるオペレーティング分野に関し、更に詳細にはノードが移動するときのノードリンク構造のトポロジを維持することに関する。
【０００２】
【従来の技術】
ペンベースのシステム及び”電子ホワイトボード”（例えばゼロックス社の部門LiveWorks から入手可能なLiveBoard （商標名））等のコンピュータベースのシステムは、ペン、スタイラス、又はカーソル制御装置などの入力装置の使用に基づいてグラフィカルユーザインターフェースを提供する。このようなシステムにおいて、”ディスプレイ”はデータを表す手段として及び入力媒体としての両方の機能を果たす。グラフィックオブジェクトは入力装置を用いて生成されたペンストロークを介してディスプレイ上に描かれる。グラフィックオブジェクトは単語、図、又はディスプレイされ得るあらゆるものを表すことができる。従って、ジェスチュアとして公知である入力技術を用いてグラフィックオブジェクト上に様々な操作を行うことができる。ジェスチュアそれ自体は単なるペンストローク（pen stroke）であり、これがインストラクションとして解釈される。しばしば、このようなシステムはペンストロークが持続（persistent）グラフィックオブジェクトを生成するとき又はペンストロークがジェスチュアとして扱われるときを区別するために、描画モード及びジェスチュアモードを有する。
【０００３】
システムの使用の１つは、ノードリンクダイヤグラムの生成及び操作である。例えば、様々なプロジェクトマネージメント、フローチャート作成及び描画プログラムは、ノードが移動するときにノードリンク構造のトポロジ（位相）の維持を可能にする。公知のプログラムは一般的に、公知の事前表示（pre-declared）タイプのノード及びリンクを用いて動作する。しかし、ダイヤグラムが自由形状、即ちノード及びリンクが任意の形を有するときに問題が生じる。
【０００４】
自由形状ノードリンク構造のこのような操作はＥＰ０６６７５６７Ａ２（題名”Apparatus and Method For Supporting the Implicit Structure Of Freeform Lists, Outlines, Text, and Diagrams In A Gesture-Based Input System and Editing System"）に記載されている（当該特許は本発明の出願人に譲渡されている）。ＥＰ０６６７５６７Ａ２には、ノードが移動するときに形状の特徴を維持する持続性リンクを有するダイヤグラム、即ちノードリンク構造について記載がなされている。リンクは直線的幾何学変換を用いて再整形され、これによってその特徴的形状を保ちながら”拡張（stretching）”によってリンクをそのリンクが連結しているノードの新しい位置にフィットさせることができる。リンクのエンドポイントはノードの移動によって必要となれば移動してもよい。
【０００５】
【発明が解決しようとする課題】
自由形状のグラフィック入力をサポートすることができるコンピュータ制御ディスプレイシステムにおいて、ノードが移動するときにノードリンク構造のトポロジを維持するための技術が開示される。リンクはそれがリンクされているノードに関してノードが移動する場所に基づいて再整形される。リンク及びノードはどちも任意の形である。簡単なケースにおいて、リンクが直線であり且つ移動方向がそのラインに沿っている場合、リンクは拡張又は収縮する。しかし、リンク及びノードの移動方向は直線に限定されない。従って、ノードが移動するときにノードリンク構造のトポロジを維持するための様々な方法が必要となる。一般的に、リンクの再整形はノードが移動するときに自動的に起こる。”自動”リンク再整形に関する目的は、リンクの基本的形状の特徴を維持してノードの移動時に望ましくないアーチファクト（例えばリンクがノードに交差する）が起こるのを避けることである。リンクの再整形は曲線変換、リンクのフリッピング、リンクのアタッチポイントのフリッピング及びリンクの打切りを組み合わせて行われる。
【０００６】
リンクの曲線変換は簡単なスケーリングよりも大変である。つまり、リンクは複数のセグメントからなり、ノード移動操作からの移動は（各セグメントに基づいた特定の変換ファクタに従って）分割されて、セグメントに追加される。リンクの形状のフリッピングは、形状の特徴を維持しながらノードが固定ノードに関して作業表面上のどこでも移動することができるので、このフリッピングは望ましい。リンクがノードに”接触する”ポイントはアタッチポイントと呼ばれる。リンクが静止ノードに接触するアタッチポイントは、リンクの再整形を行うための局所座標系の原点を決定するために使用される。ノードが移動する場所に基づいて、リンク形状はこの座標系の軸の１つ又は両方の周りでフリップしてもよく、このフリップしたリンク画像は再整形のために使用される。
【０００７】
望ましくないアーチファクト（即ちリンクがノードを交差する）を避けるには、ノード上のリンクのアタッチポイントをフリッピングするか、又はリンクをルート変更する。アタッチポイントのフリッピングは、ノードがアタッチポイントのフリッピングを許可する場合にのみ行われる。アタッチポイントのフリッピングによって交差リンクが修正されないとき、リンクがノードと交差するポイントでリンクが切捨てられてもよい。
【０００８】
アタッチポイントのフリッピングが許されなければ、リンクのルート変更が起こる。リンクのルート変更において、リンクは固定ノード及び移動ノードのアウトラインに沿ってそのアウトラインが元の交差リンクの固定された部分によって接続される場所に接続される。
【０００９】
最後に、交差リンクはユーザがノードのアタッチポイントを選択してノード上の新しい非交差位置に手動で移動させることによって修正されてもよい。
【００１０】
【課題を解決するための手段】
本発明の第一の態様は、ノードリンクダイヤグラムにおけるノードの移動に応じて任意形状のリンクを曲線変換するための方法であって、前記ノードリンクダイヤグラムはリンクを介して第二ノードにリンクされた第一ノードを有し、前記リンクは前記第一ノードに第一アタッチポイントで接触し及び前記第二ノードに第二アタッチポイントに接触し、前記方法が、ａ）リンクセグメント情報を含むリンク形状情報を格納するステップを含み、ｂ）前記第二ノードが移動したことを検出するステップを含み、ｃ）前記移動した第二ノードの目的地で前記第二ノードのための第三アタッチポイントを識別するステップを含み、前記第三アタッチポイントは前記第二ノード上の前記第二アタッチポイントと同じ位置にあり、ｄ）前記格納されたリンク形状情報に基づいて前記リンクのためのリンクの置き換えデータを生成するステップを含み、ｅ）前記リンクの各セグメントを変換して前記リンクを曲線変換するステップを含み、各セグメントの前記変換が、ｅ１）前記セグメントのためのアークの長さを決定するサブステップを含み、ｅ２）前記セグメントの長さ及び前記セグメントの前記アークの長さも基づいて変換ファクタを決定するサブステップを含み、ｅ３）前記変換ファクタ、リンク置き換えデータ及び元のセグメントの終点位置に基づいて変換されたセグメントの位置及び長さを決定するサブステップを含み、及び、ｅ４）前記変換されたセグメントの終点位置と先に変換されたセグメントの終点との間の前記変換されたセグメントをディスプレイするサブステップを含む。
【００１１】
本発明の第二の態様は、ノードが移動するときにノードリンクダイヤグラムのトポロジを維持するための方法であって、前記ノードリンクダイヤグラムがリンクを介して第二ノードにリンクされる第一ノードを有し、前記リンクが第一アタッチポイントで前記第一ノードに接触し及び第二アタッチポイントで前記第二ノードと接触し、前記方法は、ａ）ユーザが前記ノードリンクダヤグラムにおいて前記第二ノードを移動したことを検出するステップを含み、ｂ）前記第一アタッチポイントを前記リンクを再整形するための座標系の原点として定めるステップを含み、ｃ）前記移動した第二ノードに基づいて第三アタッチポイントを決定するステップを含み、ｄ）前記第二アタッチポイント及び前記第三アタッチポイントのための象限を決定するためのステップを含み、ｅ）前記第二アタッチポイント及び前記第三アタッチポイントのための象限が同じである場合、元のリンクの形状特性に基づいて前記第二ノードを移動するのに応じて前記リンクを曲線変換するステップを含み、ｆ）前記第二アタッチポイント及び前記第三アタッチポイントのための象限が異なる場合、前記リンクを再整形するステップを含み、前記再整形ステップが、ｆ１）前記リンクを前記第三アタッチポイントの前記象限にフリップするサブステップを含み、ｆ２）前記フリップされたリンクの形状特性に基づいて前記リンクを曲線変換するステップを含む。
【００１２】
【発明の実施の形態】
本発明は、ノードリンクダイヤグラムの操作が可能な自由形状グラフィックスベースのコンピュータシステムにおいて作業するときの問題に関する。ノードリンクダイヤグラムはフローチャート、組織チャート、状態図、プロジェクトマネージメントチャート等を含む。ノードリンクダイヤグラムにおいて、しばしばノードをぐるりと移動させながらリンクを保持することが望ましい。また、ノード及びリンクが任意の形をとるようにノードリンクダイヤグラムが自由形状で生成されることができる場合、リンクがそれらの元の形状特性を保持することが望ましいことが分かった。従って、本発明はリンクの変更に関わる必要なくユーザがノードの移動を介してノードリンクダイヤグラムを修正することを可能にする。
【００１３】
本明細書中の表記に使用される以下の用語の意味は以下の通りである。
グラフィックオブジェクト：２Ｄ空間においてディスプレイされたあらゆるオブジェクト
曲線：ユーザによって手動で（例えばペンストロークで）生成された、又はジェスチュア等の他の手段によって作成された（例えばセレクションジェスチュアより生じたセレクション矩形）１次元のグラフィックオブジェクト
ペンストローク：インクストローク又はジェスチュアとなるペンを用いた動作
インクストローク：持続性のある曲線
ジェスチュア：ペンストロークで作成された一時的で動作として解釈される曲線
セレクション：選択されたものとして識別されるグラフィックオブジェクトのセット
ノード：ある境界領域内のグラフィックオブジェクト又はグラフィックオブジェクトのグループ。このような境界領域は一般に可視境界を有する。
リンク：１つ又は２つのノードに接触する（即ちこれらを結ぶ）インクストローク。ノードがノード自体にリンクすることもある。
【００１４】
本発明に使用されるようなコンピュータベースのシステムは、図１を参照して表される。図１を参照すると、コンピュータベースのシステムはバス１０１を介して結合した複数の構成要素からなる。ここに図示されているバス１０１は本発明が曖昧にならないように簡略化されている。バス１０１は複数の平行バス（例えばアドレス、データ及び状態バス）及びバスの階層（例えばプロセッサバス、ローカルバス及び入出力バス）からなる。コンピュータシステムは更に、バス１０１を介して内部メモリ１０３から供給されるインストラクションを実行するためのプロセッサ１０２を含む（内部メモリ１０３は典型的にはランダムアクセスメモリ又は読み出し専用メモリの組み合わせであることに注意されたい）。操作において、本発明の様々な機能要素を実行するためのプログラムインストラクションは、内部メモリ１０３内に格納される。プロセッサ１０２及び内部メモリ１０３は、別々の構成要素であっても単一の一体型装置であってもよい。プロセッサ１０２及び内部メモリ１０３は本明細書中に記載される様々な処理機能を実行するための回路を含む。また、バス１０１には外部格納装置１０７も結合している。外部格納装置１０７は一般的には磁気若しくは光学ディスク格納装置等の高容量格納媒体である。
【００１５】
また、バス１０１にはディスプレイ１０４及びポインティング装置１０５も接続されている。この好適な実施の形態において、ポインティング装置１０５はペンタッチ感知パネルであり、これはディスプレイ１０４にタッチスクリーン画面として統合されている。このようなタッチスクリーン画面は当技術においてはよく知られており、ペンペースのシステム等のこのようなシステムにおいてや、電子ホワイトボードシステムで使用される。しかし、ポインティング装置１０５がスタイラス、マウス、トラックボール又は他のカーソル制御装置であってもよいように、ポインティング装置１０５とディスプレイ１０４は統合される必要はない。。
【００１６】
図２は、本発明に使用されるようなグラフィックユーザインターフェースの特定の実施を表している。図２を参照すると、グラフィックユーザインターフェースはディスプレイ１０４上にディスプレイされ、タッチパネル１０５を介して情報交換される。グラフィックユーザインターフェースは作業表面を使用し、及び図に示されたような複数のアクセス可能機能２０１を用いてもよい。作業表面２０２はユーザが様々な曲線を描いたり他のグラフィックオブジェクトがディスプレイされたりする場所である。アクセス可能機能２０１はディスプレイの底部領域２０３に位置する。この機能２０１はグラフィクオブジェクトを編集（作成、削除、移動、収縮等）したり、タッチパネル１０３の操作モードを変えたり（描画及びジェスチュアモードからの切り換え等）するための操作を含んでもよい。
【００１７】
または、これらの機能はウィンドウズ（Windows ）仕様のアプリケーションに一般的にみられるプルダウンメニューによってアクセスされてもよい。しかしこれらの機能は指定においてオプショナルであり、これらの主な目的は該システムの操作に本質的な操作を決定することである。これらの機能はジェスチュアによって起こる機能と同じ機能を果たす。
【００１８】
本発明のこの好適な実施の形態は、グラフィックユーザインターフェース（ＧＵＩ）を有するペンベースのシステムで実施される。このようなＧＵＩは一般的にグラフィックオブジェクトを選択／選択解除するための”タップ”やタップされたグラフィックオブジェクトに関連し得る操作を呼び出す”ダブルタップ”等の操作をサポートする。オブジェクトが選択されるとそのオブジェクトはドラッグされて作業領域内の所望の位置にドロップされる。以下に詳細に述べるように、このようなタップジェスチュアは選択されたグラフィックオブジェクトのアウトライン上（例えばノードリンクダイヤグラムのノード）に行われ、視覚的に識別出来るようにアウトラインが引かれてディスプレイされる。このアウトライン化によってユーザにグラフィックオブジェクトが選択されたフィードバックが提供される。
【００１９】
この好適な実施の形態の作業領域は”フリーハンド”で描かれたグラフィックオブジェクトを可能にする。従ってノード及びリンクは任意の形状を持ちうる。これはホワイトボードの使用のされる方法に一致する。
【００２０】
本発明のこの好適な実施の形態は、適切なホワイトボードエミュレーションプログラムの制御のもとに操作する、LiveBoard 等のペンベースのシステムで使用されるＣ＋＋プログラミング言語のソフトウェアプログラムとして実施されてきた。このようなソフトウェアプログラムは磁気ディスケットやＣＤ−ＲＯＭ等の適切な格納媒体に格納されてもよい。
【００２１】
ノードリンクダイヤグラムには多くの使用方法がある。これらのダイヤグラムは処理フローを記述したり、グループ化したアイテム間の関係を表したりするために使用されてもよい。ノード／リンク間の構成及び関係は、ノードリンクダイヤグラムの”トポロジ”と呼ばれる。ノードの空間的位置を操作するときにトポロジが保持されることが望ましい。
【００２２】
ノードリンクダイヤグラムにおけるノードは任意の形状であり、関連するグラフィックオブジェクトのグループを表す。これらのグラフィックオブジェクトは一般には文字、単語、又は記号を表す他の情報を表す。ノードはグラフィックオブジェクトをインクストローク又は他のグループ化手段で囲むことによって表される。ノードは可視境界を有し、この境界はノードの空間的限界を示す。ノードは他のノードへの複数のリンクを有してもよい。ノードのセレクションによってもそのリンクのセレクションが行われる。
【００２３】
リンクは１つ以上のノード間の視覚的繋がりを提供するために使用されるインクストロークである。リンクもまた任意の形状を有してもよい。ノード間のリンクを提供することは、特にノードを再配置するときに有効である。ノードが移動するときでもノード間の視覚的関連性を維持することができることによって、グラフィックベースシステムの使用の煩わしさが減少される。
【００２４】
リンクは、少なくとも１つのノードに”接触”する曲線を単に描くことによって作成される。ノードに接触するということは、そのリンクのエンドポイントはノードの境界から所定の距離内にあることを意味する。リンクがノードに”接触”するポイントは”アタッチポイント”と呼ばれる。リンクは少なくとも１つのノード（即ち一端の）及び最高２つのノードに関連している。
【００２５】
この好適な実施の形態は、複数のノード及びリンクを操作することができるが、リンクから生じる基本的な問題が図３に表されたノードリンクダイヤグラムから生じる。図３を参照すると、単一のリンクＬ１  ３０１が各端にノード（静止ノードＮ３０２及びノードＮ１  ３０３）を有し、ユーザがノードＮ１  ３０３をＮ２  ３０４の位置まで手動で移動するところが表されている。この移動によってリンクＬ１  ３０１は形を変えてＬ２  ３０５で表されたようなリンクになる。ノードへのリンクのアタッチポイントはＡ３０６，Ａ１  ３０７及びＡ２３０８で表されている。
【００２６】
図４は、本発明のこの好適な実施の形態において実行されるリンクの再整形を概説するフローチャートを表す。図４を参照すると、先ずユーザはノードリンクダイヤグラムの中のノードを移動する（ステップ４０１）。これは単にドラッグ及びドロップ操作によって、又は見えないグラフィックユーザインターフェースによってサポートされたあらゆる操作によって実行することができる。ノードの再整形における第一ステップは、ステップ４０２の目的地象限を識別することである。目的地象限が同じかどうかが決定される（ステップ４０３）。目的地象限の決定は、元のリンクのフリッピングが必要かどうかを示す。目的地象限が同じであれば、元のリンクに対してリンクは曲線変換する（ステップ４０４）。目的地象限が同じでない場合、元のリンクはそれぞれの軸を横切って目的地象限へフリップする。次にフリップしたリンクに対してリンクの曲線変換が実行される（ステップ４０６）。
【００２７】
リンクを再整形したあと、再整形したリンクがいずれかのノードに交差するかどうかが決定される（ステップ４０７）。ノードに交差するリンクが無ければ、リンクの再整形は完了する（ステップ４１３）。リンクがノードに交差する場合、ノードのアタッチポイントが移動してよいかどうかが決定される（ステップ４０８）。移動できなければ、リンクのルート変更が行われる（ステップ４１０）。そうでない場合は、ノードへのアタッチポイントのフリップが行われる（ステップ４０９）。次に、交差が未だ存在するかどうかがチェックされる（ステップ４１１）。アタッチポイントがフリップした後にノードが交差されていなければ、リンクの再整形は完了する（ステップ４１３）。ノードにリンクが交差したままである場合、リンクはノードに交差するポイントで切り捨てられる（ステップ４１２）。切捨てが完了すると、リンクの再整形は完了する（ステップ４１３）。
【００２８】
この好適な実施の形態において、アタッチポイントはユーザが選択し及び移動してもよいことに注意されたい。これはユーザがノード間の関係を変更したいと欲することもあるため、必要である。更に、ユーザが自動リンク変更の結果に不満であるときに変更を行いたいと欲することもある。
【００２９】
先に述べたように、リンクは曲線のインスタンスである。曲線変換は、概念的にはリンクがその形状特性を維持するようなリンクの拡張又は収縮と考えられることができる。曲線変換では、リンクは図５に表されたように孤立して考えられる。リンクＬ１  ３０１はＡ３０６からＡ１  ３０７までつながっている。Ａ３０６からＡ２  ３０８までのリンクＬ２  ３０５はＬ１  ３０１の形状特性と同じ特性を有することが望ましい。この表示において、固定ノードのアタッチポイントＡ３０６は２次元座標系の原点に位置することに注意されたい。従って、アタッチポイントＡ１  ３０７は座標（ｘ１  ５０１，  ｙ１  ５０２）であり、アタッチポイントＡ２  ３０８は座標（ｘ２  ５０３，  ｙ２  ５０４）である。目的は、Ｌ１  ３０１の形状特性が維持されるように曲線の残りを変換することである。
【００３０】
変換を行う１つの方法は、単純な幾何学変換（例えばスケーリング）である。しかし、これはある状況において望ましくない結果を生じることが分かっている。このような例は図６及び図７に表されている。図６を参照すると、正弦曲線の単一周期の形をしたリンク６０１は、ノード６０２及び６０３に接触している。単純な幾何学変換は一般的に以下のように行われる：元のアタッチポイントのｘｙ座標は（ｘ１，ｘ２）であり、移動するときのアタッチポイントは（ｘ２，ｙ２）である。リンクを変換するために、リンク上の全てのポイントＰ（ｘ，ｙ）はＰ’（ｘ’，ｙ’）に移動する。ここでｘ’＝ｘ×ｘ２／ｘ１及びｙ’＝ｙ×ｙ２／ｙ１である。幾つかの状況において、分母が小さい或いはゼロである場合もあることに注意されたい。その結果は図７に表わされている。図７を参照すると、ノード６０３を移動した結果、曲線の”ハンプ”７０２及び７０３が大きく拡張されるようにリンク７０１が変換されている。これは分母が小さな分数である結果である。従って、本発明はリンクを再整形するために異なるアプローチを用いる。
【００３１】
どのように曲線変換が起こるかをより理解するためには、曲線がどのように表されるかを理解することが必要である。曲線を表す最も簡単な方法は、その曲線のサンプル点のセットによって表すことである。これらのポイントは入力の順番によって自然に順番が決まる。幾つかのシステムは、ビットマップ、即ちサンプル点全体に曲線（スプライン）を当てはめることによって生成されたビットマップによって直接曲線を表す。この好適な実施の形態において、曲線はその開始ポイント及びそのセグメントのセットによって表され、ここでセグメントは２つの連続的なサンプル点によって決定されたベクトル（ｄｘ，ｄｙ）である。これは図８に表されている。図８を参照すると、曲線８０１は作業表面上に現れる。曲線８０１はポイント８１０〜８２０で起こるサンプリングによって検出される。サンプル点間の距離はセグメントと呼ばれる。例えば、セグメント８３１はサンプル点８１０と８１１との間で画定され、ここでサンプル点８１１は終点のサンプル点である。便宜上、固定アタッチポイントが曲線の開始ポイントとなり、移動アタッチポイントが曲線の終了ポイントとなるように、曲線は傾斜によって標準化されている。
【００３２】
この好適な実施の形態の曲線変換テクニックは、前後のアタッチポイント間の差を取り、及びこの差を曲線のセグメントに分配する。換言すると、リンクを形成するポイントは、元のリンクの形状が維持されるように新しい位置に変換される。このテクニックは図９のフローチャート及び図３に表された座標点に則して説明される。図９を参照すると、第一ステップはトータルのＸ及びＹの変更を演算するステップである（ステップ９０１）。（ｘ１，ｙ１）及び（ｘ２，ｙ２）をリンクのアタッチポイントの移動の前後の位置とする。すると、
【００３３】
【数１】
0004028031.tif 000002
【００３４】
となる。次に、残りのステップがリンクのセグメントのそれぞれに実行される。ｉ番目のセグメント（ｄｘ[ ｉ ]，ｄｙ[ ｉ ]）では、この変換はステップ９０２〜９０４に表されたように演算され、新しいｉ番目のセグメント（Ｔｄｘ[ ｉ ]，Ｔｄｙ[ ｉ ]）になる。これは以下の演算によって行われる。
【００３５】
先ずＸ及びｙの曲線のアークの長さ（arclength ）が演算される（ステップ９０２）。
【００３６】
【数２】
0004028031.tif 000003
【００３７】
ここで｜ｘ｜はｘの長さ、即ち絶対値を示す。
【００３８】
次に、変換ファクタｃｘ [ｉ] 及びｃｙ [ｉ] がｉ番目のセグメントのｘ及びｙの長さに基づいて演算される（ステップ９０３）。
【００３９】
【数３】
0004028031.tif 000004
【００４０】
これでｉ番目のセグメントに加えられるべき変更の寄与は、ｃｘ [ｉ] ×ｘＤｉｓｐ及びｃｙ [ｉ] ×ｙＤｉｓｐで表される。従って新しいｉ番目のセグメントは以下の式で演算される（ステップ９０４）
【００４１】
【数４】
0004028031.tif 000005
【００４２】
図３及び図５の例において、アタッチポイントＡ１及びＡ２はアタッチポイントＡを原点とした座標系の同じ象限内にある。この好適な実施の形態において、再整形されるうえに、Ａ２がＡ１と異なる象限内にある場合、リンクの形状はｘ軸若しくはｙ軸又は両軸の周りをフリップ（ミラー反転（mirror-reveresed））する。このフリッピングはユーザが本来望むものであるので、望ましい視覚特性である。図１０はフリッピングの３つのケースを表す。Ａ１が象限１００１から象限１００２に移動した場合、結果はＡ４  １００７になる。フリッピングはｙ軸１００６の周りで起こる。Ａ１が象限１００１から象限１００３に移動した場合、結果はＡ５  １００８である。フリッピングはｙ軸１００６及びｘ軸１００５の周りで起こる。最後に、Ａ１が象限１００４に移動した場合、結果はＡ３１００９である。フリッピングはｘ軸１００５の周りで起こる。
【００４３】
一般に、象限の移動が起こるとき、最初に起こるのは目的地象限へのリンクのフリッピングである。リンク形状のフリッピングは、所望の象限への単純な幾何学変換によって行われる。これに続いて、フリップされたリンクに対して上記のようなリンクの再整形が行われる。
【００４４】
リンクの形状を変換したあと、図３に表された簡単なケースにおいて行われる必要のあるのはこれだけである。しかし１１及び図１２は、再整形及びフリッピングが望ましくない結果を生じたケースを表している。図１１を参照すると、アタッチポイントＡ１  １１０２を有するノードＮ１  １１０１はアタッチポイントＡ２  １１０４を有するＮ２  １１０３で示された位置に移動する。固定ノードＮ  １１０５はアタッチポイントＡ１１０６を有する。リンクＬ１  １１０７はノードＮ１１０５をノードＮ１  １１０１にリンクする。リンクの再整形及びフリッピングの後のこの結果は図１２に表されている。リンクＬ１  １１０７はリンクＬ２  １２０１に再整形され、Ｌ２  １２０１はノードＮ１１０５及びノードＮ２  １１０３の両方に交差する。これは明らかにユーザが欲するものではない。従って、満足できる結果を得るようにアタッチポイントを調節するテクニックが必要である。
【００４５】
ノードの交差を修正する第一ステップは、リンクのアタッチポイントを単にフリップすることである。フリッピングには２つのケースがある。即ちノードを横切る場合とエッジに沿った場合である。ノードを横切るアタッチポイントをフリッピングする際、ノードの反対側へのフリッピングが起こる。図１１及び図１２の例にこのテクニックを適用した結果は図１３に図示されており、図１２のアタッチポイントＡ及びＡ２はＡ’Ａ１３０１及びＡ２’１３０２に移動している。トポグラフィ（topography）及び視覚的な結果を維持する点に関して言えば、これは非常に満足のいく結果を提供する。しかし幾つかの例において、ノードの形状はリンクが接触している場所によってノード間の関係が異なって解釈されるような意味を有することが分かっている。例えば、片側のアタッチメントは入力を示し、その反対側のアタッチメントは出力を示す。従って、内部ノード表示は幾つかの標識（例えばフラッグやノードタイプ）を含み、この標識はアタッチポイントのフリッピングが許されるかどうかを示すために使用される。
【００４６】
アタッチポイントのフリッピングは、ノードの形状がフリップ軸の周りでほぼ対称である場合には直線的である。従って非対称の場合について考察する。垂直軸の周りを左右にフリップする場合のみを考察する（それ以外の場合は類似している）。非対称ケースは図１４に表されている。図１４を参照すると、非対称形ノード１４０５が図示されている。ポイントＡ１  １４０１を右から左へ水平方向にフリップするためにＡ１’１４０３でノードと交差するまでＡ１  １４０１からノード１４０５の反対側へとひっぱり、ここが新しいアタッチポイントとなる。非対称ケースにおいて、フリップされたポイントは完全に異なり得ることに注意されたい。例えば、Ａ１  １４０１及びＡ２  １４０２は両方ともノードのかなり右側にあり、フリップしたポイントＡ２’１４０４はノード１４０５のかなり左側にあるが、フリップしたポイントＡ１’１４０３はノード１４０５の真ん中にある。
【００４７】
考察する他のケースは、水平ラインが３ヵ所以上でノードの囲いに交差する場合である。従ってフリップする対応ポイントを拾うことが重要である。このケースは図１５に表されている。図１５を参照すると、ポイントＡ１  １５０１及びＡ１’１５０２はフリップポイントとして対応し、ポイントＡ２  １５０３及びＡ２’１５０４はフリップポイントとして対応する。対応するフリップポイントを識別するために、左から右まで交差ポイントに番号を付ける。現在のアタッチポイントの番号をＩとする（即ちアタッチポイントは左からＩ番目である）。ここから右から左へとポイントに番号をふる。対応するポイントは右からＩ番目のポイントである。
【００４８】
ノードのエッジに沿ったアタッチポイントのフリップは、アタッチメントを有するノードのエッジに平行してノードが移動したときに起こる。更に、ノードの開始／終了位置はオーバーラップがないようでなければならない。ノードのエッジを横切ってアタッチポイントをフリップする様は図１６及び図１７に図示されている。エッジを横切るアタッチポイントのフリップが一方のノード上で起こる際に、ノードを横切るフリップがもう一方のノードを横切る場合がある。図１６を参照すると、ノード１６０１及び１６０２はリンク１６０３及び１６０４を介してリンクされている。リンク１６０３はアタッチポイント１６０５でノード１６０１に、及びアタッチポイント１６０６でノード１６０２につながっている。リンク１６０４はアタッチポイント１６０７でノード１６０１に、及びアタッチポイント１６０８でノード１６０２につながっている。ここで図１７を参照すると、ノード１６０１は新しい位置に移動し、アタッチポイント１６０６及び１６０７がノード１６０２及び１６０１を横切ってそれぞれアタッチポイント１６０６’及び１６０７’にフリップして移動している。一方、アタッチポイント１６０５及び１６０８はこれらの各ノード１６０１及び１６０２のエッジを横切ってアタッチポイント１６０５’及び１６０８’にフリップしている。リンク１６０３及び１６０４はリンク１６０３’及び１６０４’に再整形され、且つその基本的形状特性を保持している。
【００４９】
エッジに沿ったアタッチポイントのフリップは、エッジの中心点を見つけ、この中心点とアタッチポイントとの間の距離Ｘを見つけ、及びこのアタッチポイントを中心点の反対側の距離Ｘの位置にフリップすることによって行われる。
【００５０】
これらのテクニックが駆使されてもなお、リンクがノードを交差することがある。これは図１８、図１９に表されている。図１８を参照すると、ノード１８０１はリンク１８０３を介してノード１８０２につながっている。リンク１８０３はアタッチポイント１８０４でノード１８０１に、及びアタッチポイント１８０５でノード１８０２につながっている。図１９はノード１８０２が移動した結果を表している。図１９を参照すると、リンク１８０３は再整形されており、リンク１８０３’で図示されている。リンク１８０３’はポイント１９０１でノード１８０２に交差することに注意されたい。ポイント１８０５’はアタッチポイント１８０５がフリップする場所を示す。しかし、ノードのフリッピングによっても交差リンクが修正されないことが明らかである（アタッチポイントのフリッピングの効果を示す破線１９０２によって表されている）。従って、更なる”交差の解除”テクニックが必要となる。
【００５１】
ノードからリンクを打切るためには、リンクがノードと交差する場所を見つけてそのアタッチポイントを作ればよい。リンクが打ち切られたとき、この打ち切られた部分は切捨てられるので、リンクの全体的な形は変わる。この好適な実施の形態において、リンク１８０３’は交差ポイント１９０１で打ち切られ、交差ポイント１９０１からアタッチポイント１８０５までのリンクのセグメントを削除する。この結果は図２０に表されており、ここで再整形されたリンクはリンク２００１で表されている。
【００５２】
ノード上にリンクの複数の交差ポイントがある場合、固定ノードのアタッチポイントに一番近い交差ポイントが選択されることに注意されたい。更に、リンクを打ち切る代わりに、そのリンクがノードに交差するポイントでリンクを曲線変換してもよいことに注意されたい。
【００５３】
リンクのルート変更は、アタッチポイントが移動（フリップ）されずにノードの交差が起こるときに行われる。リンクのルート変更の例は、図２１に表されている。図２１は図１２のノードの交差リンクを修正するために使用されることができるリンクのルート変更を表す。図２１を参照すると、ルート変更されたリンク２１０１は、ノードと交差するのを避けるためにルート変更されている。点線２１０２は、リンクが再整形後に元にあったところを示す。ルート変更されたリンク２１０１はアタッチポイント１１０６からポイント２１０３までノード１１０５の形状に沿い、このポイント２１０３でこのリンク２１０１は交差リンク２１０２にぶつかる。次にルート変更はリンク２１０２の形状に沿ってノード１１０４に交差するところ（すなわちポイント２１０４）まで続く。ここからこのルートはノード１１０３の形状に沿ってアタッチポイント１１０４まで続く。
【００５４】
図２２はリンクをルート変更するための簡単なテクニックのステップを表すフローチャートである。交差リンクが生成されたと仮定する。先ず、ノードのそれぞれのアウトラインが生成される（ステップ２２０１）。ノードのアウトラインが生成される方法は、図２７〜図３０に則して以下に記載される。いずれにせよ、これは図２３に表されており、ノード１１０３及び１１０５それぞれのアウトライン２３０１及び２３０２が図示されている。また、図２３には交差リンク２３０３も表されている。
【００５５】
次に、固定ノードのアタッチポイントから始まって、アウトラインに沿った且つ交差リンクに一番近いルートが選ばれる（ステップ２２０２）。これは図２４に表されている。アウトライン２３０２及び交差リンク２３０３の使用された部分は切捨てられていることに注意されたい。
【００５６】
次にこのルートは移動したノードのアウトラインが交差するポイントに達するまで交差リンクをたどり、交差リンクの残りは切り捨てられる（ステップ２２０３）。これは図２５に図示されており、ノード１１０３に交差するリンク２３０３の部分は切捨てられる。
【００５７】
このポイントで、ルートは移動したノードのアタッチポイントが一番近い距離に達するような方向に、この移動したノードの形をたどる（ステップ２２０４）。これは図２６に表されており、アウトライン２３０１の使用されていない部分は切捨てられる。
【００５８】
任意形状のノードの境界のアウトラインを見つけることは容易なことではない。境界を表す任意の形状の閉鎖曲線の場合、ポイントが曲線の内側にあるか外側にあるかを決定するのは難しい。アウトラインを見つけだすためのテクニックは、図２７のフローチャートによって記載される。図２７を参照すると、第一アウトラインは境界の片側上の開始ポイントから始まり、第二アウトラインは境界の反対側上の開始地点から始まる（ステップ２７０１）。曲線がどこから始まるのかが簡単には分からないので”内側”のアウトラインなのか”外側”のアウトラインなのかがハッキリしないため、境界の両側にアウトラインを引くことが必要である。いずれにせよ、アウトラインのそれぞれは境界から同じ所定距離のところに引かれる。これは図２８に図示されており、外側のアウトライン２８０１及び内側のアウトライン２８０２が表されている。実際にはノード境界の内側及び外側上にアウトラインが引かれることに注意されたい。
【００５９】
次に、各アウトラインは簡単な閉鎖曲線に変換される（ステップ２７０２）。これは、結果的な曲線の端部で小片をトリミングすることによって各アウトライン毎に行われる。このような小さな曲線は図２８に、アウトライン２８０１の曲線２８０３及びアウトライン２８０２の曲線２８０４によって描かれている。これらの曲線はアウトライン処理から生じる。これらの小さな曲線の切捨ては図２９にアウトライン２８０１’及び２８０２’で表されている。
【００６０】
最後に、アウトラインの長い方がノードのためのアウトラインとして選択される（ステップ２７０３）。２つのアウトラインの様々なセグメントの距離を単に合計してこの合計を比較することによって、アウトラインの長い方が決定される。アウトラインの長い方がノードの”外側”のアウトラインであることは明らかである。これは図３０に表されている。
【００６１】
先に述べたアウトライン化プロセスはリンクのルート変更以外にも使用されることに注意されたい。この好適な実施の形態において、同じアウトライン化プロセスはノードの選択を示すために使用される。これはアウトライン曲線を強調したり色付けしたりして、アウトラインに囲まれたノードを選択するという視覚的なフィードバックをユーザに提供する。
【図面の簡単な説明】
【図１】本発明のこの好適な実施の形態において使用されるコンピュータベースシステムのブロック図である。
【図２】図１のディスプレイ上にディスプレイされ且つタッチ感知パネルを通してインターフェースされるような基本的なグラフィカルユーザインターフェースを表した図である。
【図３】本発明のこの好適な実施の形態において実施されるような移動されたノード及び対応する再整形されたリンクを表す図である。
【図４】本発明のこの好適な実施の形態において実施されるようなリンクの再整形をまとめたフローチャートを表す図である。
【図５】本発明のこの好適な実施の形態において実施されるようなリンク再整形の空間座標を表す図である。
【図６】リンクのインスタンスの単純な幾何学的スケーリングの望ましくない結果を表した図である。
【図７】リンクのインスタンスの単純な幾何学的スケーリングの望ましくない結果を表した図である。
【図８】本発明のこの好適な実施の形態における曲線の表示に見られるような曲線のサンプル点及びセグメントを表す図である。
【図９】本発明のこの好適な実施の形態において実施されるような曲線変換のためのステップを表した流図である。
【図１０】本発明のこの好適な実施の形態において実施されるような、元の象限の外にノードが移動するときに行われるような様々な軸を横切ってフリップするときの図３のリンクを表した図である。
【図１１】再整形されたリンクがノードに交差するようなノードの移動を表した図である。
【図１２】再整形されたリンクがノードに交差するようなノードの移動を表した図である。
【図１３】本発明のこの好適な実施の形態において実施されるような、図１１のノードを移動した後のノード上のアタッチポイントのフリッピングを表す図である。
【図１４】本発明のこの好適な実施の形態において実施されるような、非対称形ノード上の様々なポイントでのフリップされたアタッチポイントの選択を表す図である。
【図１５】本発明のこの好適な実施の形態において実施されるような、ノードが複数のポイントで交差するときのフリップされたアタッチポイントの選択を表した図である。
【図１６】本発明のこの好適な実施の形態において実施されるような、ノードのエッジを横切ってアタッチポイントを移動することによってアタッチポイントをフリップするところを表した図である。
【図１７】本発明のこの好適な実施の形態において実施されるような、ノードのエッジを横切ってアタッチポイントを移動することによってアタッチポイントをフリップするところを表した図である。
【図１８】リンクをノードに交差させ、アタッチポイントのフリッピングによってノードの交差が修正されないノードの移動を表す図である。
【図１９】リンクをノードに交差させ、アタッチポイントのフリッピングによってノードの交差が修正されないノードの移動を表す図である。
【図２０】本発明のこの好適な実施の形態において実施されるようなリンクの切捨てを表した図である。
【図２１】本発明のこの好適な実施の形態において実施されるような、交差ノードを修正するためのリンクのルート変更を表す図である。
【図２２】本発明のこの好適な実施の形態において実施されるような、リンクのルート変更のためのステップを表す流図である。
【図２３】図２２のリンクのルート変更で行われるステップを表す図である。
【図２４】図２２のリンクのルート変更で行われるステップを表す図である。
【図２５】図２２のリンクのルート変更で行われるステップを表す図である。
【図２６】図２２のリンクのルート変更で行われるステップを表す図である。
【図２７】本発明のこの好適な実施の形態において実施されるような、ノード境界のアウトラインを生成するためのステップを表す流図である。
【図２８】ノード境界のアウトラインを生成するための図２３の様々なステップのパフォーマンスを表す図である。
【図２９】ノード境界のアウトラインを生成するための図２３の様々なステップのパフォーマンスを表す図である。
【図３０】ノード境界のアウトラインを生成するための図２３の様々なステップのパフォーマンスを表す図である。
【符号の説明】
Ａ      アタッチポイント
Ｌ      リンク
Ｎ      ノード
【図１】
0004028031.tif 000006
【図２】
0004028031.tif 000007
【図３】
0004028031.tif 000008
【図４】
0004028031.tif 000009
【図５】
0004028031.tif 000010
【図６】
0004028031.tif 000011
【図７】
0004028031.tif 000012
【図８】
0004028031.tif 000013
【図９】
0004028031.tif 000014
【図１０】
0004028031.tif 000015
【図１１】
0004028031.tif 000016
【図１２】
0004028031.tif 000017
【図１３】
0004028031.tif 000018
【図１４】
0004028031.tif 000019
【図１５】
0004028031.tif 000020
【図１６】
0004028031.tif 000021
【図１７】
0004028031.tif 000022
【図１８】
0004028031.tif 000023
【図１９】
0004028031.tif 000024
【図２０】
0004028031.tif 000025
【図２１】
0004028031.tif 000026
【図２２】
0004028031.tif 000027
【図２３】
0004028031.tif 000028
【図２４】
0004028031.tif 000029
【図２５】
0004028031.tif 000030
【図２６】
0004028031.tif 000031
【図２７】
0004028031.tif 000032
【図２８】
0004028031.tif 000033
【図２９】
0004028031.tif 000034
【図３０】
0004028031.tif 000035