JPH08255259A - コンピュータ化された作図方法 - Google Patents

Abstract

(57)【要約】 （修正有） 【課題】 製図インジケータが描く精密な基準に欠ける
作図パス（経路）から、正確な基準を満足する作図パス
を作成する。 【解決手段】 所定の精密基準に欠けたパス内のインジ
ケータの移動位置を表すインジケータ情報要素のグルー
プを発生する工程、インジケータ情報要素に応答して位
置を表す変換された情報要素のグループを発生する工
程、ニューラルネットを用いて情報要素の変換されたグ
ループに演算を加え、この演算に応答して変換されたグ
ループを分類する工程、分類に応答してインジケータ情
報要素のグループの特徴を発生する工程並びに精密基準
に欠けていない変更されたパスの位置を表す情報要素の
変更されたグループを定める工程とを備える。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、コンピュータを使った
製図方法に関し、特に製図インジケータが描く精密な基
準に欠ける作図パス（経路）から、正確な基準を満足す
る作図パスを作成することを行う方法に関する。

【０００２】

【従来技術】製図およびデザインをするためにコンピュ
ータを使用すること、およびコンピュータを使った方法
は、しだいに一般的なこととなりつつある。

【０００３】コンピュータ支援設計（ＣＡＤ）の目標
は、デザインを表し、デザインのための作図を分析し、
デザインを変更し、開発プロセス中のすべての段階にお
ける製図のコピーを記憶できる能力をデザイナーに与え
ることである。ある意味におけるＣＡＤシステムおよび
その方法の進歩は、デザイナーに提供されるフレキシビ
リティおよび可能なデザインおよび作図の複雑さによっ
て測ることができる。

【０００４】代表的なＣＡＤ方法では、ユーザーすなわ
ちデザイナーが点、ラインまたは円のような幾何学的要
素を指定し、次に適用可能な場合にその要素の大きさの
特徴を指定しなければならない。例えばユーザーすなわ
ちデザイナーは、円を指定し、次にその中心にカーソル
を位置させることにより円の中心を定め、次に円の所望
の半径に等しい距離だけその中心からカーソルを移動す
ることにより、その大きさを指定する。次にシステムは
かかる円の作図を実行し、これをユーザーにディスプレ
イする。システムおよびディスプレイ内の情報は（シス
テムの限界および許容度内で）正確な円を表す。次に同
様な、すなわち類似する操作を行えば、この作図に他の
正確な幾何学的形状を加えることができる。

【０００５】

【発明が解決しようとする課題】当然ながらこのような
ユーザーとの相互対話を行う方法は、人が作図を行う場
合の自然な方法に従うものではない。人の自然な方法で
はユーザーの手により製図器具を移動させる。更に、多
くのデザイナーはデザインの正式な製図に適用されるよ
うな基準に欠ける、スケッチのような製図をする際に、
最も創造的となる。

【０００６】ニュートン（Newton）の商標で、アップル
コンピュータ社から販売されているデバイスは、非ＣＡ
Ｄ環境でノートブック能力と称されているある種のスケ
ッチ能力を提供している。このデバイスは、ユーザーに
よるスケッチからより正確に見える単一要素のパス、例
えば円および楕円や、より正確に見えるマルチ要素のパ
ス、例えば一連の直線を作成するようになっている。更
にこのデバイスは、付随する幾何学的な拘束条件、例え
ば隣接するライン要素の一致する端部の点を一致させる
ようにもなっている。

【０００７】

【課題を解決するための手段】本発明は、ＣＡＤ環境と
一貫性があり、このＣＡＤ環境に組み込まれるようなス
ケッチタイプの作図（描画）能力を提供するものであ
る。本発明はＣＡＤ環境で重要である作図パーツと要素
との間の種々の幾何学的拘束条件を含む。これら幾何学
的作図パーツまたは要素としては、ポイント、直線、オ
ープンな円弧、円および楕円がある。

【０００８】これら要素のうちの１つの、スケッチされ
たインジケータパスを解釈する能力と共に、削除および
ベタ塗り（areafill）シンボルを区別したり認識したり
する能力もある。

【０００９】更にこのデバイスは、比較的複雑なマルチ
要素のストロークを区別したり、解釈できる能力も提供
するものである。このデバイスはストロークに沿う要素
の折れ点位置を決定し、精度の基準を満たすストローク
を再構成する前に、これら要素を認識することにより、
このような能力を実行する。

【００１０】作図パーツすなわち要素スケッチ、認識お
よび画定に関する本発明の特徴によれば、所定の精密基
準に欠けた作図パスを表示する情報を発生し、この情報
をかかる精密基準に欠けていない作図パスを表示する方
法に変換するための、コンピュータ化された方法が提供
される。所定の精密基準に欠けたパス内のインジケータ
の移動位置を表示するインジケータ情報要素のグループ
を発生する。次にこれらインジケータ情報要素に応答し
て位置を表示する変換された情報要素のグループを発生
する。ニューラルネットを用いて変換されたグループに
演算を行い、これに応答して分類する。次にこの分類に
応答してインジケータ情報要素のグループの特徴を発生
し、精密基準に欠けていない変更されたパスの位置を表
示する情報要素の変更グループを定める。

【００１１】例えば情報要素の変更されたグループは、
オープンな円弧を表示できる。ニューラルネットは円、
楕円、複数の円弧および削除シンボルを表示できる出力
分類を表示できる。

【００１２】情報要素の変換されたグループの発生は、
所定のグリッド内の、回転されスケール化され、変換さ
れ、マップ化された位置のグループを表示する情報要素
のグループに、インジケータ情報要素のグループを変換
することを含むことができる。この情報要素グループ
（所定のグリッド内の位置を表示し、これら位置が次に
クローズドパスを表示する場合）は更に変換されたクロ
ーズドパスを表示する、所定グリッド内の位置を表示す
るグループに更に変換できる。同様に、一方向にオープ
ンな円弧を表示する所定グリッド内の位置を情報要素の
基準グループが表示している場合、このグループは更に
反対方向にオープンな円弧を表示する、所定グリッド内
の位置を表示するグループに変換できる。

【００１３】更にコンピュータ支援設計に適した情報要
素の変更グループに関連した情報、例えば表示された大
きさを決定するための情報を発生できる。

【００１４】更に、分類目的のため一致しているかどう
か最初に述べたような情報要素の変換されたグループ
を、ラインおよび４５度の円弧を表示するパターンを含
む情報要素の認識されたパターンに対してテストするこ
ともできる。

【００１５】作図ストロークをパーツすなわち要素に分
割することに関する本発明の特徴によれば、所定の精密
基準に欠けた作図パスを表示する方法を発生し、作図パ
スのセグメントの折れ点を表示する折れ点情報を選択す
るためのコンピュータ化された方法が提供される。所定
の精密基準に欠けたパス内のインジケータの移動位置を
表示するインジケータ情報要素を発生する。次に分類基
準に応答して情報要素をカテゴリー内に分類する。次に
分類および折れ点選択基準に応答して折れ点情報要素を
選択する。折れ点情報要素は情報要素のセグメントの限
界を区切るためのものである。

【００１６】情報要素の分類の実行に当たり、情報要素
の角度変化、曲率および傾き変化を表示する機能を計算
し、この計算に応答して情報要素をカテゴリー化する。
次に隣接する情報要素に対するカテゴリー化に応答し
て、カテゴリー化された情報要素を再カテゴリー化し、
情報要素のための初期の基準分類を達成する。

【００１７】折れ点情報要素の選択に対し、最初に述べ
た分類および潜在的折れ点情報基準に応答して潜在的折
れ点情報要素を最初に選択し、次に潜在的折れ点情報要
素に隣接する情報要素をニューラルネットにより演算
し、次にニューラルネットに応答して潜在的折れ点要素
を除くことができる。

【００１８】情報要素のセグメントはカーブしたオープ
ンセグメントおよびカーブしたクローズドセグメントを
含むパスまたは直線セグメントおよびカーブしたオープ
ンセグメントを含むパスを表示する位置を表示すること
ができる。

【００１９】上記特徴および別の幾何学的拘束条件の特
徴の双方に関する本発明の更に別の特徴によれば、所定
の精密基準に欠けた作図パスを表示する情報を発生し、
かかる精密基準に欠けていない作図パスを表示するディ
スプレイに前記情報を変換するためのコンピュータ化さ
れた方法が提供される。所定の精密基準に欠けたパス内
のインジケータの移動位置を表示するインジケータ情報
要素を発生する。この発生に応答して情報要素のセグメ
ントに対する限界を区切る折れ点情報要素が定められ
る。次に精密基準に欠けていない変更されたパスのセグ
メントを表示する情報要素の変更されたグループが定め
られる。情報要素の変更されたグループのうちの幾何学
的拘束条件が発生され、この幾何学的拘束条件の発生に
応答して幾何学的に拘束されたセグメントを表示する情
報要素の拘束されたグループが定められる。次に精密基
準に欠けていないパスを表示すると共に、情報要素の拘
束されたグループを含む、情報要素によって表示された
ディスプレイがなされる。

【００２０】幾何学的拘束条件は、例えば一致条件、平
行条件、接線条件および再限定条件を含むことができ
る。

【００２１】更に、表示された大きさを決定するための
情報を含む、コンピュータ支援設計のための情報要素の
拘束されたグループに関連した情報も発生できる。

【００２２】添付図面において、本発明の種々の目的お
よび特徴を実証する実施例を次のように示す。

【００２３】本明細書には、図示するように本発明の詳
細な実施例が開示されている。しかしながらこれら実施
例は、種々の形態で提供でき、そのうちのいくつかは開
示した実施例とかなり異なる可能性がある。従ってここ
に開示した特定の細部は、代表的なものにすぎず、この
点に関し、開示目的のための最良の実施例を示し、かつ
本発明の範囲を定める特許請求の範囲の根拠となるもの
とみなされる。

【００２４】図１にはコンピュータ支援設計（ＣＡＤ）
のためのワークステーション３０が示されている。この
ワークステーションの構成部品のうちには、ワークステ
ーションの入力デバイスとして、ユーザーにより移動さ
れ、その他の方法で操作できる標準的マウス３２と、キ
ーボード３４と、ディスプレイスクリーン３８を有する
デスプレイ３６がある。当然ながらワークステーション
３０は従来のワークステーションと同じ物理的な外観と
なっている。しかしながら内部の動作、ユーザーおよび
マウスとの相互対話、コンピュータ支援設計および製図
を行う結果、並びにかかる設計および製図に関連したコ
ンピュータ化された情報は、本発明に従い、かつ本発明
を実施するものである。

【００２５】図６は、ライン４０によって示されるよう
な作図パスに沿って移動されるようなマウス３２を示
す。個人のフリーハンドの移動から生じる代表的な作図
パスのように、作図路４０は正式な製図、特に製品や部
品の設計の際に使用される製図に通常関連する規格や精
密さの基準に欠けている。従ってユーザーは恐らく直線
状の傾斜したラインのパスを描くことを望んでいても、
実際に描かれるパスはこの基準から大きくはずれること
になる。一般にユーザーがマウスのボタンを押し、描き
たいパスの開始点を表示することにより、パスの開始点
をワークステーションに表示できる。描きたいパスの終
了点は、そのボタンを離すか、またはボタンを離した後
に同じボタンを再び押すか、または最初にボタンを離し
た後に別のボタンを押すことにより表示できる。次に製
図を行う個人による鉛筆またはペンのストロークに類似
した方法で、開始点から終了点までのパスをパスストロ
ークとみなす。

【００２６】図６のディスプレイスクリーン３８上に示
された一連のクロス表示４２は、図示した例ではマウス
３２を用いたユーザーの操作によって生じたディスプレ
イスクリーン上の一連のカーソル位置を表示する。同様
に、ディスプレイスクリーン上の一連の光った位置４４
は、一連のカーソル位置に対応している。かかる光った
位置は当然ながらディスプレイスクリーン上の代表的な
主要点であり、これら点を接続すればディスプレイスク
リーンに沿った連続的なパスが表示される。更にワーク
ステーション３０およびディスプレイスクリーン３８
（図１）を有するディスプレイ３６が、十分に微細な解
像度を有するとみなせば、一連の光った点は一般にユー
ザーにとっては接続されたパスのように見える。従って
点または位置４４の光ったシリーズは、ディスプレイス
クリーン３８上の作図パスを表示し、このパスはマウス
３２の作図パス４０に対応する。点または位置のシリー
ズおよびこれらが示すディスプレイ上のパスは同様に正
式な製図に関連する基準に欠けている。

【００２７】図６において、表示Ｉ₁ （Ｘ₁ ，Ｙ₁ ）は
一連の光った点の第１点４２すなわち位置を表示するワ
ークステーションのコンピュータ装置によって内部的に
得られる情報要素を示している。情報要素のＸ₁ および
Ｙ₁ 成分は、位置自体、例えばデカルト座標系における
座標を示すようになっている。当然ながらこの座標の代
わりの座標として、極座標系における角度と径がある。

【００２８】また、当然ながらＩ₁ （Ｘ₁ ，Ｙ₁ ）から
Ｉ_n （Ｘ_n ，Ｙ_n ）、すなわち一連の点４４における最
終点のためにコンピュータ装置によって得られる内部情
報要素を示す表示までの、点線によって示されるよう
な、点の各々に対してかかる内部情報要素がある。ま
た、これらの表示はＣＡＤシステムにおいて一般に使用
されるようなタイプの情報要素を示すにすぎない。

【００２９】図６を参照し続ける。この図の右側には一
連の光った位置、すなわち上記方法の結果として、入力
すなわちインジケータの一連のディスプレイ点の変更を
同じように示すディスプレイ点４６が示されている。こ
れらディスプレイ点は、先に述べた規格または精密基準
が欠如していない直線状の傾斜ライン、すなわち正式な
設計製図の規格および基準に従った直線ラインに合致す
るように変更されたディスプレイパスを示している。こ
れら点が示す変更されたディスプレイパスは、ユーザー
がマウス４２を移動させたパス４０の、固定された変形
例を示す。出力表示Ｏ₁ （Ｘ₁ ，Ｙ₁ ）からＯ
_m （Ｘ_m ，Ｙ_m ）は、コンピュータ装置において決定さ
れた、変更された一連の点または位置のための位置を示
す、コンピュータ装置によって内部で得られる情報要素
を示す。

【００３０】標準的ＣＡＤシステムおよび方法は、デザ
インをしたり、詳細なデザイン、製図および検査の実行
および関連づけを行う能力を提供するものである。いく
つかの例のように、これらは関連する図の変更を自動的
に設計したり、次元的情報を維持し、表示するいくつか
の能力を含む。図６におけるＯ₁ （Ｘ₁ ，Ｙ₁ ）からＯ
_m （Ｘ_m ，Ｙ_m ）に関連する表示Ｄ₁ からＤ_m は、かか
る標準的ＣＡＤ機能を実行するためのコンピュータシス
テムにおける情報要素の存在を単に表示するものであ
る。情報要素Ｏ₁ （Ｘ₁ ，Ｙ₁ ）からＯ_m （Ｘ_m ，
Ｙ_m ）によって示される直線ラインパスの長さを示すデ
ィスプレイの一部としての端部引出線の間の矢印内にあ
るＬ ｉｎなる次元的表示は、かかる標準的な次元に関
連した能力を示すにすぎない。

【００３１】図７を参照すると、本発明に係わるワーク
ステーション３０は、単一点、直線ライン、オープン円
弧、円または楕円を表示する位置または点を示す情報要
素を発生でき、これら幾何学的要素は正式なデザインま
たはデザイン製図の精密基準または規格に欠けている
が、かかる精密基準または規格を満たす幾何学的要素
（またはセグメント）をそれぞれ示す要素の、変更され
たグループを定めている。かかる結果生じるセグメント
は図７に示されるような精密な点５０、直線ライン５
２、円５４および楕円５６として示される。

【００３２】図１０において、直線を意図しているが、
精密基準に欠如するマウス３２による作図パス６０が左
に示されている。これと異なり、このパスはマウスまた
はインジケータのパスすなわちディスプレイされている
ようなパスに対応するよう、ワークステーションのコン
ピュータ装置で発生されるインジケータ情報要素によっ
て示されるようなパスを示しているとみなすことができ
る。右側には、ワークステーション３０で得られる、変
更された情報要素によって表示される作図パス６２が示
されている。当然ながらこのパスは、所望の精密基準を
満たす直線ラインの外観となっている。これと同様に、
精密基準に欠如する、意図する円弧６４、意図する円６
６および意図する楕円７０のパスが、それぞれ図１１、
１２および１３の左に示されているが、一方、精密な基
準を満たす円弧、円および楕円の作図パスがそれぞれ図
１１、１２および１３の右側に示されている。

【００３３】図１０〜１３のパスはそれぞれ単一セグメ
ント（すなわち単一要素）のストロークとなっている。
従ってワークステーションは、単一の定義された幾何学
的セグメントまたは要素として、直線ラインセグメン
ト、円弧、円および楕円を認識し、分類し、演算を行う
ことができる。当然ながらこれは点についても当てはま
る。

【００３４】図１４および１５には、マルチセグメント
ストロークのパスが示されている。図１４の左には、図
１０〜１３の左のパスに類似するが、コーナーの折れ点
で一致する２つの直線ラインセグメントとなるようなス
トロークのパス７８が示されている。このケースでは、
ワークステーション３０は、小さな円８０で表示される
意図するコーナーの折れ点を認識する。この認識は、折
れ位置または折れ点を表示する情報要素を、コンピュー
タで識別することにより実行される。次にこの折れ点で
区切られた接続点を有するストローク内の２つのセグメ
ントを、直線ラインとして別々に認識し、共通折れ点を
除き、別々に処理できる。この結果、所望の精度でコー
ナー折れ点８４で接続した２つの直線ラインセグメント
を含むパス８２が得られる。

【００３５】図１５の左側には、小さい円９０および９
２により表示されるような２つの折れ点を含むと認識さ
れるストロークパス８６がある。ここで、これら折れ位
置または点を示す２つの情報要素を識別する。パスをフ
ィレット形状に円弧で接続された２本の直線ラインを含
む３セグメントパスとして認識する。これら３つのセグ
メントは、一旦折れ点を識別すれば別々に認識して処理
し、次に図１５の右に示すような折れ点９６および９８
を有する３セグメントパス９４を示す情報要素セグメン
トを定めることができる。

【００３６】図８の左側には、ベタ塗りコマンドシンボ
ルのための代表的なマウスパス１００が示されている。
このパスはパスインジケータとしてのマウスの移動によ
り発生される表示情報要素によって表示されるパス、す
なわちディスプレイされているようなパスとみなすこと
もできる。右側には、削除コマンドシンボルのためのパ
ス１０１の同様な状況が示されている。表示されるよう
に、これらシンボルを作成すべき幾何学的パスにおける
成分として使用する場合、これらシンボルはマルチセグ
メント（または要素）ストロークとみなされる。しかし
ながら、これらの特徴的な性質、および認識されかつ認
められる幾何学的パスの成分の性質に起因して、これら
のコマンドストロークは、最終的にはベタ塗りおよび削
除コマンドの認識および使用に関連する１つの完全セグ
メントまたは要素として取り扱われる。

【００３７】図９の左側には、精度を高めた正方形のた
めのディスプレイスクリーンパス１０２およびマウス３
２のベタ塗り移動に対応するベタ塗りシンボルのための
ディスプレイパス１０３が示されている。この結果であ
るベタ塗りシンボルの一般的角度の正方形内の領域のク
ロスハッチングの表示がされたフィル部分１０４が、右
側に示されている。

【００３８】図１６の左側には、正方形を意図したマウ
スの作図パスに対応するディスプレイ作図パス１１０が
示されている。パスに沿う矢印は、単一ストロークパス
の移動方向を表示している。表示するように、パスの両
辺は正しく平行となっていない。更に、パスの開始点お
よび終了点において、真のコーナー位置を越えるような
延長部がある。当然ながらこのパスはマウスのパス自体
を表示するとみなすこともできる。更に、このマウスパ
スから得られる、ＣＡＤワークステーション３０（図
１）内で発生されるインジケータ情報要素は、このディ
スプレイ作図パスを示している。当然ながら右側のパス
１１１は折れ点を位置させ、意図する直線ラインを認識
し、更にかかるラインのための変更された情報要素を発
生できることを示している。しかしながらこのパスは更
に対向する辺の対の間の意図する平行性の条件を表し、
更に再限定拘束条件も表す、限定された情報要素を提供
できる。図１６の右には、下方の左側でコーナーを形成
するように、各々の延長を限定するようにパスの開始点
と終了点で一致する正方形の辺を再限定する際に、再限
定拘束条件が表されている。このパス１１１は、拘束条
件またはディスプレイされているようなかかるパスを含
む参考とした特徴のすべてを含むコンピュータシステム
で得られる情報要素で表示されるパスとして、見ること
ができる。

【００３９】図１７では、かかる平行性および再限定拘
束条件のみならず、接線拘束条件も示されている。図の
第１フレーム、第３フレームおよび第５フレームにおい
て、矢印付きパスによりマウスパスから生じたディスプ
レイパス（マウスパス自体としても見ることができるパ
ス）が示されている。矢印の付いていないディスプレイ
パスは、必要に応じ折れ認識、セグメント認識および処
理ならびに折れ点認識および処理能力を表している。当
然ながらこれらパスは対応する特徴を得るため、変更ま
たは変換を受けた情報要素によって示されるパスとして
もみなすことができる。

【００４０】従って図１７の第１パネルでは、単一スト
ロークの作図パス１１２が示されている。第２パネルで
はこのパスはパス１１４に変換され、多少９０度よりも
大きい角度で、コーナーにて接続された２本の直線ライ
ンセグメントを表している。第３パネルではマウスの移
動の結果として、別のパス１１６が追加されている。こ
の追加パスは、２つのストロークで正方形を描きたいと
いうユーザーの意図を示している。対向する辺に関連す
る平行線の拘束条件およびストロークを交差させる場所
に関連する再限定拘束条件が認識され、これら拘束条件
はこの図面の第４パネルの正方形パス１１８で示され
る。当然ながらこのパスは、第３パネルで加えられた新
しい作図パスが、コーナーの折れ点で合流する２本の直
線ラインとして認識されたことを表している。第５パネ
ルでは、マウスの追加運動が単一ストロークパス１２０
を加え、このパス１２０は正方形の４つの辺の各々に内
接する円となるように意図したものである。このような
結果を得るにあたり、第６パネルでは意図する円として
新しいパスを認識し、円と正方形の４つの辺の各々との
接線拘束条件を認識し、これを表示している。

【００４１】図１８〜２０も、幾何学的拘束条件を示し
ている。直線ラインを意図するストロークおよびそれに
続く円を意図するストロークが、図１８の左に示すよう
に、接線拘束条件を受けることなく、それぞれ直線ライ
ンパス１２２および交差しない円１２４として表示でき
る。しかしながら接線拘束条件により、意図する接線関
係が認識される。この結果、直線ラインパス１２６と円
形パス１３０とが、互いに接する。これと同様に、一致
拘束条件を受けることなく、図１９の左に示すように、
点１３２と直線ライン１３４とを分離するような結果も
可能である。一致拘束条件を受けると、この結果、点１
３６と直線ライン１３８とが一致する。

【００４２】図２０には、円とこの円から延びる接線ラ
インを描こうとする単一ストロークのディスプレイパス
のための接線拘束条件が示されている。円が精密な基準
を満たさず、直線ラインも精密規格を満たさず、更に全
く接線が存在していないディスプレイパス１４０が左側
に示されており、右側には円と接線方向に延びるライン
を含む変更されたディスプレイパス１４２が示されてい
る。

【００４３】図２および３のフローチャートは、１スト
ロークのためのセグメントを区切るよう、折れ点を決定
するための方法に関し、図４のフローチャートは、かか
る基準を満たさないセグメントから所望の精密な基準を
満たすセグメントを作成することに関する。図５のフロ
ーチャートは図２、３および４の特徴のみならず、幾何
学的拘束条件を含む、より包括的な方法に関するもので
ある。

【００４４】マウス３２の移動（図１および図６）に応
答して、コンピュータ装置で発生されたインジケータ要
素に対し、マルチセグメントストロークでセグメントを
区切るよう、折れ目を認識することについて説明する
と、当然ながら各セグメントは位置すなわち点の表示を
含む。記憶されたインジケータ要素により、コンピュー
タにこの位置または点ストリームを記憶すると、このス
トリームのうちの点に適用される幾何学的特徴の計算お
よび点ストリームのフィルタリングに向けられると述べ
ることができる演算により、この折れ目位置認識（折れ
点認識）をスタートできる。

【００４５】これを実行するにあたり、インジケータ情
報要素によって示されるような１ストロークに対する点
ストリーム内の点の対の間の相対的距離および（角度変
化を意味する）角度を計算する。従って、例えばかかる
ストロークに対する第２、第３および第４点に関して、
第２点と第１点の間の距離を計算し、第３点と第２点の
間の距離を計算し、次に第４点と第３点の間の距離を計
算する。同様に、第３点と第２点とを結ぶラインと、第
２点と第１点とを結ぶラインとの角度差を計算し、第２
点に適用できる角度差として適用する。第３点と第２点
とを結ぶラインからの、第４点と第３点を結ぶラインの
角度変化を計算し、第３点に適用できる角度変化として
適用する。これは容易に明らかなように、第１点および
最終点に適用できる角度変化がなく、更に第１点前また
は最終点後に適用できる距離がない場合を除き、ストロ
ークにおけるインジケータ要素で表示される点のすべて
に対してこれを実行する。これは図２のフローチャート
のスタート点（ブロック１４４）に示されているような
ものである。

【００４６】コンピュータ装置内で発生される１つのイ
ンジケータ要素から次のインジケータ要素までの、ワー
クステーション３０自体の部品内での通常の伝送遅れか
ら生じるかかる期間を越える、最小の距離移動および最
小の時間間隔を必要とするようにセッティングを行うこ
とができるが、かかる最小インターバルを不要とし、ワ
ークステーションが行うことができる頻度で一般にマウ
スの位置をサンプリングできるようすることが有利であ
ることが判っている。この結果、コンピュータ装置内の
インジケータ情報要素により表示される、重複インジケ
ータ点が生じ得る。重複点は余分な情報とみなすことが
できる。一般に当然ながらその他の余分な情報、すなわ
ちノイズも存在する。

【００４７】従って、インジケータ情報要素によって表
示されるような連続する重複点（これは当然許容差内に
ある）をワークステーション内に記憶されていたストロ
ークから除く（ブロック１４６）。次にノイズ除去特性
として、許容度内で連続する点に適用できる２つおよび
３つの連続角の組み合わせをテストし、これらが相殺さ
れ、マウスを使用する際のユーザーによるマウスの無意
識のゆれを多少表すように、０にセットできるかどうか
を見る（ブロック１５０）。 例えば５、１０、−１
５、２０、５、５、１０、−１０、０の、点に適用でき
る一連の角度変化を、０、０、０、２０、５、５、０、
０、０の角度変化に変える（しかしながら当然、このこ
とはこれを考慮するため、これら点の情報要素を変更す
ることを意味するものではない。一般にこれら角度変化
の単位は、度で表示できる。当然ながら、これら演算は
上記幾何学的特性の計算および折れ点認識のためのフィ
ルタリングの一部となっている。

【００４８】このプロセスの連続として、開始点および
終了点で明らかとなる理由を除き、ストロークに対する
点に適用できる曲率半径を点に対して作成された円に基
づいて計算する（ブロック１５２）。表示するように、
このような計算は重複点を除いた後に行われるが、当然
ながら角度変化の相殺は実際の下方の点に影響を与える
ものではない。曲率半径のこの計算に関し、この計算を
適用できない開始点および終了点を除き、その点（１つ
は６つの点の前に位置し、１つは６つの点の後に位置す
る）を用いて構成された円に基づいて、各点に対する曲
率半径を計算する。従って、例えば点ｐ₁ 、ｐ₂ 、
ｐ₃ ．．．ｐ_n が与えられた場合、これら点ｐ₁ 、ｐ₇
およびｐ₁₃を通る円を構成することにより、点ｐ₇ に適
用できる曲率半径を決定できる。次に点ｐ₂ 、ｐ₈ およ
びｐ₁₄を通る円を構成することにより、点ｐ₈ に適用で
きる曲率半径を決定する（この曲率半径の情報は、この
点にてコンピュータシステムに表示されているディスプ
レイに適用できる特定のスケールを変更するよう、ユー
ザーによって入力できたスケールファクタを除くように
正規化される）。

【００４９】その後、見つけられた曲率円に対する中心
点の連続する対に対して、これら中心点の間の距離を計
算する（ブロック１５４）（この距離は特定のディスプ
レイ内でユーザーに対して課せられているスケールファ
クタ（倍率）を除くように正規化される）。次にその後
最初の３つおよび最後の３つの各点に対して適用される
平均化された傾きを計算し、ストロークに対する点を適
用する（１５６）。この計算は、評価点の３つ前の位置
の点および３つ後の位置の点により定められるラインの
傾きを探すことによって行われる。例えば点ｐ₁ 、
ｐ₂ 、ｐ₃ ．．．ｐ _n が与えられると、ｐ₄ に対する傾
きが点ｐ₁ およびｐ₇ を通るラインを構成することによ
り決定される。点ｐ₅ に対する傾きは、点ｐ₂ およびｐ
₈ を通るラインを作成することにより、点ｐ₅ に対する
傾きが決定される。

【００５０】次に、（ブロック１５８で）平均化された
傾きが使用されるが、この平均化された傾きは点に対し
て適用できる平均化された傾きの変化を計算する際に、
点に対して計算される。点の計算された平均傾きと、先
の点の計算された平均化された傾きとの差を決定するこ
とにより、１つの点に適用できる平均化された傾きの変
化を計算する。当然ながらこの計算では、３つの開始点
と３つの終了点は除かれる。

【００５１】このことは、どれを幾何学的特性の計算お
よびフィルタリングに向けられる折れ目認識プロセスの
部分として考えることができるかを結論する。

【００５２】次の操作の組は、ストロークの領域を分類
することに向けられる特徴とみなすことが好ましい。

【００５３】これを行う際（ブロック１６０）、この点
に適用できる角度変化の絶対値の各々、この点に適用で
きる曲率、およびこの点に適用できる傾き変化の絶対値
に対する点にカテゴリーを適用する。これらカテゴリー
は、表示された変数に基づいて点が発生する領域を分類
する試みとみなすと好ましい。これらカテゴリーは、次
のようにみなす。

【００５４】 １．実線 − ごく直線状のラインを表示する ２．混合ライン又はゆるやかなライン − ゆるやかな
直線状のラインを表示する ３．混合カーブまたはゆるやかなカーブ − ゆるやか
な曲線を表示する ４．完全なカーブ − 極めて湾曲したラインを表示す
る ５．シャープな転回部 − 極端な曲がりを示す

【００５５】このようなカテゴリー化を続けると、次の
記述的表示としてみなすことができる要素の限界値とし
て、次の値をきめることができる。

【００５６】

【表１】

【００５７】ここで、傾きの値は度で示されており、曲
率の値はインチで示されている。（またここではスケー
ルファクタ（倍率）により影響されるこれら値のうちの
１つにすぎない曲率は正規化され、かかるスケールファ
クタ（倍率）は除かれる。）

【００５８】次に、実線、混合カーブまたは完全カーブ
として、点に適用できる角度変化に基づき、点を分類す
るための、上記の値に基づく基準がある。特に、角度変
化の絶対値がわずかな傾き未満であれば、カテゴリーは
実線となる。角度変化の絶対値がわずかな傾き以上で、
かつ小さな傾き以下であれば、混合カーブとなる。点に
適用できる角度変化の絶対値が小さな傾きより大であれ
ば、角度変化に基づくこの点のカテゴリーは完全カーブ
となる。

【００５９】同様に、点に適用できる曲率半径の絶対値
が大きな曲率以上であれば、曲率に基づく点に適用され
るカテゴリーは実線となる。他方、曲率半径の絶対値が
大きな曲率未満であれば、カテゴリーは完全カーブとな
る。

【００６０】次に点に適用できる傾き変化の絶対値につ
いて説明すると、傾き変化の絶対値が直線状の傾き以下
であれば、傾き変化に基づき、この点に適用できるカテ
ゴリーは実線となる。傾き変化の絶対値が直線状の傾き
より大で、かつ小さい傾き以下であれば、カテゴリーは
混合カーブとなる。傾き変化の絶対値が小さい傾きより
大で大きな傾き以下であれば、カテゴリーは完全カーブ
となる。傾き変化の絶対値が大きな傾きより大であれ
ば、カテゴリーはシャープな転回部となる。

【００６１】表示され、コンピュータ装置に記憶される
このような情報から、これらの決定を行う点に対して複
合カテゴリーを適用できる（ブロック１６４）。これら
の複合カテゴリーは、決定された角度変化、曲率および
傾き変化に対するカテゴリーに基づき、ライン、カーブ
またはシャープな転回部とみなす。種々の可能性に対す
る複合分類は次のとおりである。

【００６２】

【表２】

【００６３】従ってこのチャートは、角度変化、曲率お
よび傾き変化変数に対する点に適用できるカテゴリーか
ら、点に適用できる複合カテゴリーをどのように決定す
るかを示している。このチャートおよび図２に関連して
（ブロック１６４）、異なるライン分類に対するサブカ
テゴリーは、それにも係わらずライン分類となることに
留意すべきである。同様にそれにも係わらず、異なるカ
ーブ分類に対するサブ分類は、すべてカーブ分類とな
る。

【００６４】一連の点内の明らかな異常点である範囲外
に点がある場合、ストロークの領域を分類するこの形態
の一部として、これら点を再カテゴリー化することが好
ましい（ブロック１６６）。これはリニア点に対する再
カテゴリー化により、極めてリニアな点の長いストリー
ム内に見いだされる単一カーブ点に適用する。同様に、
隣接点に基づいて中間点をカテゴリー化することが好ま
しい（既に述べたように、これは開始点での多数の点お
よび終了点での多数の点を含むことになる。）。

【００６５】このような分類の特徴を実行した後、折れ
点候補点の識別に向けられた（図２におけるブロック１
７０における）形態が生じ得る。このような形態は、折
れ点識別のための点カテゴリー化の固定化、コーナーの
折れ点候補点の発見およびフィレット状折れ点候補点の
発見に向けられた形態を含む。これらについては、図３
を参照して、後により詳細に処理する。しかしながら
（ブロック１７２において）図２を参照し続けると、セ
グメント分析を用いた折れ点候補点のテストおよび除去
に向けられる演算もある。

【００６６】この演算は図４の演算に従って処理および
認識するために、仮定的に２つのセグメントに分割する
ポイントのストリームの一部を、除かれた折れ点候補点
として識別された点との演算による潜在的な単一セグメ
ントとして、どのようにテストするかと関連している。
当然ながらこのことは、ここのセグメントの処理に関す
る図４に示された演算の説明を参照すればより詳細に理
解できよう。

【００６７】次に図２（ブロック１７４）を再度参照す
ると、潜在的折れ点候補点を除いた後に、真の折れ点が
残る。（除かれた折れ点候補点である点の除去および重
複点の除去とは別に）折れ点の識別と関連させて説明し
た変化または変更のいずれもなく、（点または位置を表
示するインジケータ情報要素としての）マウスの移動の
結果としてコンピュータ装置内に最初に記憶された点ま
たは位置へ戻り、最終の選択された折れ点によって点の
ストリーム内のその結果生じるセグメントを区切り、
（インジケータ情報要素としての）点のこれらセグメン
トストリームを構成し、ストロークに対してその結果生
じたセグメントとして記憶する。

【００６８】図３を参照すると、点のカテゴリー化の固
定化、コーナー折れ点候補点の発見および一般に上記の
ようにしか称されていないフィレット状折れ点候補点の
発見を行うと、折れ点候補点の識別のための多数の点の
再カテゴリー化により、かかる固定化が行われる（ブロ
ック１７６）。

【００６９】まずストリーム内のすべての点に対する複
合カテゴリー化がカーブであれば、かかる再カテゴリー
化も折れ点、コーナーまたはフィレットの発見は全く不
要である。この点に関し、このような特定の目的に対し
ては、シャープな転回部の複合分類は、カーブ分類とみ
なすことを覚えておくべきである。よって、この目的の
ためのこれら２つの分類の間の区別は重要ではない。更
に、特に記さない限り、削除シンボルを単一セグメント
ストロークとする条件も実行することも記憶すべきであ
る。

【００７０】よって、点のすべてがカーブしていないと
仮定すれば、再カテゴリー化に向けられた演算（図３に
おけるブロック１７６）を行う。潜在的再カテゴリー化
のある種の形態は、シャープな転回部領域に関係してい
る。かかる領域の一例としては、次のような一連の点に
対する一連の複合分類となる。すなわちライン、ライ
ン、カーブ、カーブ、カーブ、シャープな転回部、シャ
ープな転回部、シャープな転回部、カーブ、カーブ、カ
ーブ、ライン、ラインである。

【００７１】一般にこのような状況では、シャープな転
回部領域の範囲を確定するカーブ点は、実際にはカーブ
していない。あるライン領域から別のライン領域への移
行部にグレイ領域があるにすぎない。従ってこのような
状況では、これら点の分類はライン分類に変換される。
よって、ライン、ライン、ライン、ライン、ライン、シ
ャープな転回部、シャープな転回部、シャープな転回
部、ライン、ライン、ライン、ライン、ラインのような
シリーズとなる。

【００７２】しかしながらこのような状況では、カーブ
領域を単なるグレイエリアとしないことも可能である
（すなわちユーザーはラインを引き、その後このライン
に対して鋭角で円弧を描く）。これに合わせるには、シ
ャープな転回部領域のいずれかの側で、限られた数の点
分類しか変換しない。９個の限度が便利で有効であるこ
とが判っている。

【００７３】特定の実施例では、シャープな転回部であ
る３つの連続する点があるが、単一のシャープな転回部
の点のいずれかで、カーブ点の再カテゴリー化を移動し
ながらセットするには、１つのシャープな転回部の点で
十分である。

【００７４】かなりの数の連続点が、ある最小絶対値、
例えば０.０１度よりも小さい角度変化を有している場
合、別の再カテゴリー化演算（ブロック１７６）が行わ
れる。このような状況では、領域内のかかる点のすべて
をラインに再カテゴリー化する。上記のような複合分類
結果のチャートにより、極めて小さな角度変化を備えた
点がカーブの複合分類となる可能性があることを示して
いる。表示された再カテゴリー化は、これら分類が一般
にノイズであり、訂正すべきであることを認識するにす
ぎない。再カテゴリー化を行うには、かかる連続点は最
小９つとすると便利で、かつ有効であることが判ってい
る。

【００７５】再カテゴリー化（ブロック１７６）に焦点
を合わせると、複合カーブ（ゆるやかなカーブ）の複合
カテゴリー化のみならず、極めて小さな角度変化を有す
る点は、ラインの複合分類に変換される。同じ０.０１
度のカットオフは、これに対し便利で、かつ有効である
ことが判っている。かかる再カテゴリー化の後に、シャ
ープな転回部領域の発見と共に、折れ点候補点の実際の
選択を開始できる（図３のブロック１７８）。一般に、
再び少なくとも短いシリーズの連続するシャープな転回
部の複合分類があるが、１つしか必要でない。

【００７６】シャープな転回部領域を識別した後に、い
ずれかの側でこの領域の範囲を確定する２つの点（これ
らの点はシャープな転回部の点ではない）と共に、その
領域内の点を一緒のものとみなし、最も大きな角度変化
の絶対値を有する点を、これらの中から発見する。次に
その点をコーナーの折れ点候補点としてセットアップす
る（ブロック１８０）。当然ながらこれはシャープな転
回部領域毎に行う。

【００７７】コーナー状よりもむしろカーブ状の転回部
に関連した折れ点であるフィレット状の折れ点の候補点
の識別について話題を変えると、フィレット状の折れ点
を発見しようとする際に、カーブ領域を識別し、使用す
る。図３のこの特徴について述べると（ブロック１８
２）、カーブ領域を発見し、その領域内の点をカウント
することに関連する演算が行われる。カウント数が十分
であり（図中の好ましく有効な数は少なくとも１０のカ
ウントである）、かつその領域に対するブラケット点が
ラインとして分類されている場合、その領域の各端部に
対するエッジカーブ点でフィレット状折れ点候補点を選
択する（ブロック１８４）。（明らかな代替方法はエッ
ジライン点を選択することである。）カーブ領域内の点
の数が不十分（例えば１０未満）であり、かつコーナー
の折れ点の候補点に対する点が十分（例えば図に示すよ
うに、少なくとも２つ）であれば、その代わりにかかる
コーナー折れ点を発生する潜在性がある（ブロック１８
６）。このような状況では、角度変化の最大値が最大の
カーブ領域内で、この点が見つかる。この値は所定の最
小値（例えば図に示すような２３度）より大きければ、
この位置でコーナー折れ候補点が発生される（ブロック
１８６）。

【００７８】当然ながら、図３を参照して説明し、図示
した（例えば図１５参照）ことから、隣接ライン点を有
するエッジではフィレットタイプの領域に対するフィレ
ット折れ点候補点からしか発生されないことが明白とな
るはずである。従って、かかる領域に対して１つまたは
２つの候補点を発生できる。

【００７９】既に図３を参照して折れ点候補点の識別
（図２におけるブロック１７０）についてより詳細に説
明してあるので、折れ点候補点のテストおよび移動（図
２におけるブロック１７２）について、更に説明する。

【００８０】最初は、折れ点候補点によりストリームが
候補セグメントに区切られている場所に接続部が達して
いる。しかしながら図４を参照してより詳細に説明する
セグメント分類方法を、折れ点識別および選択方法の一
部として用い、折れ点候補点によって区切られた種々の
候補セグメントを分類するのに用いることができる。こ
れら候補セグメントはマウス３２の移動により発生され
る初期インジケータ要素または点に基づいており、この
結果、この分類により、あるラインが別のラインと一致
することを示されている場合、ストローク部分が存在し
得る。同様に、ラインが円弧または円となったり、円弧
または円がラインとなったりすることを示す結果も得ら
れる場合がある。また、円弧または円が別の円弧または
円となる可能性もある。

【００８１】簡単に説明すれば、折れ点候補点を除くた
めのテスト（図２のブロック１７２）を行うには、除か
れた２つのセグメントの交点に対する折れ点と共に、同
じセグメント分類方法（図４）に従って所定の評価と共
に、上記タイプの隣接するセグメントのテストを行う。
これはセグメント分類方法や存在する折れ点を用いるこ
となく、有効な単一セグメント分類を発生するかどうか
を判断するように行われる。そうであれば折れ候補点は
そのインジケータ要素と共にすべての目的に対して除か
れ、２セグメント領域の代わりに単一セグメント領域を
提供するだけである。

【００８２】従って折れ点が除かれた状態で、単一ライ
ンとして、ラインとラインの間の領域を分類できる場
合、その折れ点は実際に除かれる。プリ評価基準を備え
た、円弧または円となるラインとして、またはラインと
なる円弧または円として識別された領域を、折れ点を除
いた状態で単一の円弧または単一の円として分類できる
場合、その折れ点は除かれる。プリ評価とは、この折れ
点の除去を検討できるように、ライン領域の長さに対す
る円弧または円領域の径の比が、所定の最小値以上とな
るようにすべきことである。この理由は、円弧または円
となったり、またはならなかったりする、ある程度の比
較的短いラインを許可したり、排除してはならないから
である。かかる最小値３が好ましく有効であることが判
っている。円弧または円セグメントと他の円弧または円
セグメントとの結合点における折れ候補点に関し、この
折れ点を除いた状態で単一セグメントのためのセグメン
ト分類方法が、単一円弧または単一円を発生した場合、
その折れ候補点を除く。

【００８３】次に、図４のフローチャートを参照する
と、ストロークを分割した個々のセグメントの認識、ま
たは分割しない場合の単一セグメントの認識、更に発生
したものに基づく点、直線、円弧または楕円の発生に対
し演算を行う。

【００８４】この初期の特徴を、ｘｙ座標のストリーム
の変換／正規化と便宜的に称すことができる。既に述べ
たように、既に解決した折れ点決定方法に関連し、点ス
トリームについて、あるクリーンアップ変更を行うこと
ができたが、点ストリームは、ユーザーによるマウスの
移動の即座の結果として、コンピュータ内で発生された
初期のインジケータ要素によって表示された位置のスト
リームとなる（例えば図６参照）。例外は、ちょうど説
明したとおりの除かれた折れ候補点である点およびそれ
らのインジケータ要素の排除である。更に折れ点認識の
際のように、ここでは重複点を除く。

【００８５】技術的な事項として、コンピュータ装置で
表示される指定された位置の細かさ、すなわち精度は、
実際にはワークステーション３０（図１）の特性によっ
て制限されることに留意されたい。これに関し、（図１
におけるディスプレイ３６のような）ディスプレイおよ
びそのインターフェース化部品は、入力情報を受け、計
算を行い、その結果を記憶するワークステーションの部
品の解像度よりも小さい細かさ、すなわち解像能力とな
り得る。従って、情報要素における位置情報は、一般
に、ディスプレイスクリーンまたは他のタイプのディス
プレイ、例えばプリントアウトでディスプレイされる解
像度よりも解像度が高くなり得る。

【００８６】図４を参照すると、セグメントに関連した
初期変換／正規化の組の演算の説明から明らかとなるよ
うに、この組の演算は一般に、プロセス中に点としての
セグメントのプリ分類に達しながら、当該セグメントに
対する点（インジケータ要素によって表示された位置）
の回転、スケーリングおよび変換を行う（図４のブロッ
ク１８６）。

【００８７】始めはセグメントがクローズドセグメント
（例えば円または楕円）またはオープンセグメント（例
えば円弧または直線）のいずれに判断されたかを記憶す
るのに用いられるクローズドフラグを、フォールス
（偽）とセットする。次に点の組を演算して開始点およ
び終了点によって定義されるべきベクトルが（０度で）
Ｘ軸に沿うように、ストリームを回転させる。次にこの
結果生じたセグメントのＸ方向（ｄｘ）およびＹ方向
（ｄｙ）への大きさを決定する。更に、開始点と終了点
との間の距離も計算する。

【００８８】ボックスの両辺がＸ軸およびＹ軸に平行な
状態の回転されたセグメントの最小−最大ボックス（ｍ
ｉｎ−ｍａｘ ｂｏｘ）の対角線に対するこのボックス
の比をテストする。当然ながらこの対角線は（（ｄｘ）
² ＋（ｄｙ）² ）の平方根である。このテストした比が
所定のスレッショルド値よりも低ければ、追加演算を行
う。このスレッショルド値に関しては、ユーザーがこれ
を選択するある程度の自由度を有するようにできると有
利であることが判っている。比較的正確な製図を行う専
門家とみなされるユーザーが使用できるスレッショルド
を０.１とし、中間レベルとみなされるユーザーに対す
るスレッショルドは０.２とし、初心者とみなされるユ
ーザーに対するスレッショルドを０.３とすると、好ま
しく、かつ効率的であることが判っている。

【００８９】上記比がスレッショルドよりも小さけれ
ば、セグメントのうちのすべての点に対する最小二乗適
合ラインを計算し、このラインが０度となるように点の
ストリームを回転し、この点においてセグメントが閉じ
たと判断されたことを表示するように、クローズドフラ
グを真にセットする。当然ながら最小二乗適合ラインと
は、セグメントの所定の関連する点とライン間の二乗さ
れた距離の合計の平方根を最小とするラインのことであ
る。回帰解析により、かかる最小二乗適合ラインおよび
その決定は、種々の数学的に行われる演算および研究分
野で共通に用いられるものである。

【００９０】比が表示されたスレッショルドよりも低い
かどうか、また、これら比に依存する演算を行うかどう
かとは独立して、開始点および終了点によって決まるベ
クトルが、Ｘ軸（０度）に従うよう、または最小二乗適
合ラインがＸ軸に沿うように、点ストリームの回転がな
される。いずれの場合にせよ、次に回転されたセグメン
トをスケール化し、原点（０、０）にある＋Ｘ、＋Ｙ象
限内の所定の大きさのエリア内に入るように変換する。
例えば１インチ×１インチの格子サイズが好ましく、効
率的であることが判っている。

【００９１】これまで述べたことに関する評価に際し、
（ｄｘ、ｄｙ）によって表示されるセグメントの大きさ
が十分小さい場合、すなわち言い換えれば、セグメント
が適合するｍｉｎ−ｍａｘ ｂｏｘが十分小さい場合、
点としてセグメントをあらかじめ分類でき（ブロック１
８６）、多くの演算（ブロック１８６の一部およびブロ
ック１９０、１９２、１９４、１９６および２００）を
避けることができる。当然ながらこの領域内にはかなり
の数のインジケータ情報要素が生じることがある。すな
わち、ユーザーは点を表示するのにマウスを多少移動で
きたが、ユーザーが行ったものは点と解釈されるような
判断がなされた。

【００９２】実際には、予想されるように、最初にフル
ストロークを点としてあらかじめ分類できる場合に限
り、点の分類ができるようにすることが、好ましく、か
つ効率的であることが判っている。従って、図２および
図３において説明したように、折れ点認識前では、（折
れ点認識操作の場合と同じような重複点の排除を含む）
上記のようにセグメントのプリ分類のためのストローク
を点としてテストすることが好ましく、かつ効率的であ
る。これによれば、点のプリ分類および図４の操作の下
記のような点の発生および関連する方法（発生された点
の除去）は、折れ点認識前のセグメント分類操作のみに
おけるマルチセグメントストロークのためのセグメント
認識のために行う必要はない。折れ点認識前にかかる点
のプリ分類が為される場合に、折れ点認識をすることな
く下記のようにその時間に点セグメントを発生する。

【００９３】次の組の演算は、パターン認識および／ま
たはニューラルネットのためのセグメント用入力パター
ンの発生と便宜的に称することができる。

【００９４】分類目的のためのセグメントに関する情報
をテストするため、セグメントを構成する位置（点）の
回転され、スケール化され、変換されたストリームの位
置を１００個の位置、１０個の位置×１０個の位置のグ
リッドにマップ化する（ブロック１９０）。当然、この
マップ化は、セブメントの分類のための入力情報を比較
的扱いやすいサイズに限定することである。従って入力
情報は１００個の位置の各々がこのセグメントに対しヒ
ットしているか、またはミスしているかどうかに関する
情報に減縮される。

【００９５】この１０×１０マトリックスのためのヒッ
トパターンの類似性を少なくするには、所定のパターン
を意識的に変え、これらパターンを他のタイプのパター
ンとより区別できるようにすると有利である。

【００９６】これによれば、セグメントがクローズドセ
グメントとして記録されている場合、ヒットのパターン
はグリッドの頂部に変換される（ブロック１９２）。こ
のような例としては、ｘで表示された１０×１０のグリ
ッドにおけるヒットによる下記の変換がある。

【００９７】

【００９８】ここに表示するように、この変換はヒット
がグリッドの頂部の行に達するまで、ヒットパターンを
上方に変換する。

【００９９】セグメントの異なる分類間の区別をする方
法を簡単にするための、かかる別の変更とは、笑った顔
つきの円弧を示すセグメントパターンのためのヒットパ
ターンをフリップ操作して、怒った顔つきの円弧に変え
ることである。この目標は、すべての怒った顔つきの円
弧パターンにして、それらの認識を容易にすることであ
る。上記変換例に類似するこの例は、次のように示され
る。

【０１００】

【０１０１】従って、セグメントのためのヒットパター
ンの開始点および終了点が、グリッドの同じ行上にあ
り、開始−終了行が第１行上にあり、更にその開始−終
了行の上にヒットがなければ、このパターンをフリップ
操作する。より技術的に説明すれば、この方法ではパタ
ーンをＹ方向に分割する水平線を横断する鏡像となるよ
うに、パターンを変える。（これについては図４のブロ
ック１９２に示されている。）

【０１０２】これを行った場合、ライン、４５度の円弧
として、またはパターン認識演算を利用したベタ塗りシ
ンボルとして、グリッドパターンによるセグメントの別
のプリ分類を行う試みが可能である（ブロック１９
４）。この理由は、これらセグメント分類のためのグリ
ッドパターンは検査によって容易に認識できるからであ
る。より詳細に説明すれば、直線として分類すべきパタ
ーンは、第１のグリッドの行のみに沿うヒットを有して
いなければならず、４５度の円弧として分類すべきセグ
メントは、グリッドの最初に２行のみにヒットを有して
いなけれならず、ベタ塗りセグメントはグリッドパター
ンの最上部の行のみに沿うヒットを有していなければな
らない。かかるパターンは下記のように表示される。

【０１０３】

【０１０４】ベタ塗りに関し、かかるベタ塗りシンボル
はクローズドセグメントとして分類するために、表示さ
れた最上部の行に変換されていなければならないことに
留意すべきである。上記のようなベタ塗りと直線との差
異は異なるセグメントの分類を容易に区別するのを補助
するよう、変換とパターンのフリッピングがどのように
働くかを表示している。

【０１０５】点のプリ分類の場合と多少同様に、ベタ塗
りシンボルは実際はマルチセグメントストロークとして
認められない。これらの理由およびその他の効率上の理
由から、折れ点の認識前のポイントのプリ分類のための
テストで、点のプリ分類が行われない場合、ライン、４
５度の円弧またはベタ塗りとしてのプリ分類となる、図
４のパーツにおける操作、かかるプリ分類に基づくライ
ン、円弧またはベタ塗りの発生および関連する方法（発
生したセグメントの除去）も、折れ点認識操作前に実行
される。これらのいずれも、シングルセグメントのベタ
塗りシンボルとしてのストロークのテストを可能にし、
他のフォームのプリ分類の場合の効率を高めることがで
きる。しかしながら、ストロークのためのマルチセグメ
ント認識における点としてのプリ分類のための状況と逆
に、これらプリ分類、ラインおよび４５度の円弧のため
の関連する方法も、折れ点認識後のマルチセグメントス
トロークのために実施される。しかしながら、上記のよ
うなストロークのためのマルチセグメントスト認識で
は、かかるプリ分類およびベタ塗りシンボルのための関
連方法は実行されない。

【０１０６】この接続点では、点、直線、４５度円弧ま
たはベタ塗りシンボルとして分類すべきセグメントのた
めのプリ分類が行われていなければならない（点および
ベタ塗り方法だけが折れ点認識前の完全ストロークのた
めに試みられるセグメント認識に適用可能である）。し
かしながら、かかるプリ分類がなされない場合、図２お
よび３に従って折れ点認識後にセグメントを処理するこ
ととなり、セグメントを円弧、円、楕円または削除シン
ボルと分類すべきかどうかの問題が残る。このような分
類方法を実行するには、入力ノードとしてグリッドのう
ちの１００ポイントを用いるニューラルネットを利用す
る（ブロック１９６）。

【０１０７】このニューラルネットは、規格に従って開
発されたものであり、これまで何年もの間使用されてき
た周知の技術である。このニューラルネットは、表示し
たように、１２個の隠されたノードと、６個の出力ノー
ドを有する１００個の入力ノードとして１００個のグリ
ッド位置を有するバックプロパゲーション形ニューラル
ネットである。この出力ノードは、９０度円弧、１８０
度円弧、２７０度円弧、円、楕円または削除シンボルに
対する可能性と、グリッドパターンの他の５つの可能性
とを比較することにより、相対的近似性に換算して信頼
レベルを、特定ノードにおける出力の強さに従って表示
する。出力ノードに対する別の円弧サイズの選択を参照
すれば、これらの代替案は、円、楕円または削除シンボ
ルからの円弧の区別がなかったとしたら、異なる大きさ
の円弧を１つのセグメントに対して最終的に区別しない
という考えで選択される。ニューラルネットのノードに
おける出力レベルで表示できる出力％の例としては、次
のものがある。９０度の円弧−９２％、１８０度の円弧
−２０％、２７０度の円弧−１％、円−０％、楕円−２
％、削除シンボル−８％である。

【０１０８】ニューラルネットのテスト結果が存在する
場合（決定を行い、セグメントのための分類を行えない
と表示する状況に反し）、分類を行うには、所定の基準
を満たさなければならない。一般的な基準として、２つ
の上部分類候補は５０％以上の組み合わされた％のレベ
ルを有するはずである。次の分類基準が９０度の円弧分
類に適用できる。 １．クローズドフラグはフォールス（偽）でなければな
らない。（クローズドまたはオープンインジケータは、
従ってオープンセグメントを示す。） ２．９０度円弧にたいして表示された％は８０％以上で
あるか、またはランナーアップは１８０度の円弧でなけ
ればならない

【０１０９】次に、１８０度円弧として分類に適用でき
る基準は次のとおりである。 １．クローズドフラグはフォールス（偽）でなければな
らない。 ２．％レベルは８０％以上であるか、またはランナーア
ップは９０度または２７０度の円弧でなければならな
い。

【０１１０】２７０度の円弧分類に対して付加的基準は
次のとおりである。 １．％レベルは８０％以上であるか、またはランナーア
ップは１８０度円弧または円でなければならない。 ２．％レベルが８０％未満で、ランナーアップが１８０
度円弧である場合、クローズドフラグはフォールスでな
ければならない。

【０１１１】円に対する分類基準は次のとおりである。 １．％レベルは８０％以上、またはランナーアップは２
７０度の円弧または楕円でなければならない。

【０１１２】楕円に適用できる分類基準は次のとおりで
ある。 １．クローズドフラグは真でなければならない。 ２．％レベルは８０％以上またはランナーアップは円で
なければならない。

【０１１３】最後に、削除シンボルに適用できる分類基
準は次のとおりである。 １．クローズドフラグはフォールスでなければならな
い。 ２．％レベルは８０％以上でなければならない。 ３．（重なった点が除かれた状態で）削除ストローク内
に少なくとも１５個の点が存在していなければならな
い。

【０１１４】ニューラルネットを使う分類に適用できる
付加的演算によりセグメントのアスペクト比が分類の変
更を行うべきことを示している場合、円から楕円、また
は楕円から円への、上記のような分類の変更が可能とな
っている（ブロック２００）。特にアスペクト比を示す
判断が所定の限度を越えるとみなせば、円分類を楕円分
類に変える。これとは異なり、判断により限度よりも少
ないと判断されれば、楕円分類は円分類に変えられる。
ユーザーが製図の初心者であると考えられれば、ユーザ
ーにこの限度を２.５にセットさせ、中級者と考えられ
れば２.０にセットさせ、熟練者であると考えられれば
１.５にセットすると好ましく、かつ効率的であること
が判っている。この計算は、上記のように回転する際の
セグメントのＸまたはＹの値の大きいほうの差を、Ｘま
たはＹの値の小さいほうの差で割った比、すなわちｄｘ
およびｄｙのうちの大きいほうを小さいほうで割った比
とすることができる。上記のように、この回転は円また
は楕円のための最小二乗適合ラインに基づくものである
ことが予想される。当然ながら１０×１０のグリッド上
で表示されるようなセグメントのｄｘおよびｄｙの値に
基づくようなアスペクト比を表示するストロークの他の
変形例に基づく計算を、これとは別に用いることができ
る。

【０１１５】次に、当該セグメントが点の分類、一種の
プリ分類（ブロック１８６）、パターン認識により直
線、４５度の円弧またはベタ塗りシンボルの分類、別の
タイプのプリ分類（ブロック１９４）、またはニューラ
ルネットの使用を含むこの種類の分類方法を用いて、９
０度の円弧、１８０度の円弧、２７０度の円弧、円、楕
円または削除シンボル（ブロック１９６および２００）
に分類されている。かかるセグメントが極端に大きいか
または小さい形状、または原点から極めて離れた形状と
なっていることが判れば、このセグメントを除くことが
できるという評価と共に（ブロック２０４）、コンピュ
ータ装置内のセグメントを実際に発生または画定するた
めの情報を、この点から保証できる（ブロック２０
２）。上記のように、折れ点認識前のストロークに対
し、点としてのプリ分類に基づきこのことが生じ得る。
折れ点認識前、または折れ点認識後のセグメント認識中
のストロークに対するラインまたは４５度の円弧でも、
このことが生じ得る。他の円弧、楕円または円に対して
も、折れ点認識後にこのことが生じる。

【０１１６】これを参照する場合に、まず円弧について
述べるのが好ましい。この点に関し、本方法は単一円、
すなわち単一の中心と径とを有する円の一部にそれぞれ
限定される円弧を発生する。分類が円弧と決まれば、完
了している度と大きさに関する分類は、もはや直接的な
問題ではない。重なった点が除かれ、除かれた折れ候補
点も存在していない状態で、コンピュータ装置に記憶さ
れた初期インジケータ情報要素を、次に使用する。詳細
に述べれば、最初の、かかる記憶されたインジケータ情
報要素の位置情報を、円弧を発生させるのに使用される
円を構成する第１サンプル点として用い、最後のかかる
記憶された要素の位置情報を、第２サンプル点として用
い、数のカウントが第１点と最終点との間の中間（すな
わち約半分）にある情報要素の位置情報を、第３サンプ
ル点として用いる。より詳細に説明すれば、これら３点
は、円の中心および径を決める。円弧の幅は第１点位置
と最終点位置によって決まる（ブロック２０２）。

【０１１７】円弧の発生のための前提条件は、３つのサ
ンプル位置が同一直線上になく、３つのうちの２つが一
致していないことである。更に、後の条件は、発生され
た円弧が３３０度以上である場合、この円弧は完全な円
となるように閉じられるだけである（ブロック２０
２）。

【０１１８】発生された円弧の除去に関し（ブロック２
０４）、原点よりも過度に離れた形状に基づく取り除き
条件がある。より詳細には１つのモデル単位が１インチ
（ディスプレイ上で）に等しいか、または２５.４のモ
デル単位がかかる１インチ（１インチが約２５.４ｍｍ
であるという意味において）に等しくなるように、ユー
ザーがモデル単位のスケールを特定できるようにする
と、便利で、かつ効率的であることが判っている。ユー
ザーが一旦このようなスケールを決め、発生された円弧
の中心点を、１５０００×１５０００のモデル単位の領
域外に決定するれば、この発生された円弧を維持せず、
これを除き、これを単なるエラー条件とすることが好ま
しく、かつ効率的であることが判っている。

【０１１９】円弧に対するかかる追加的エラー条件は、
距離許容度と称すことができるものに関連している。よ
り詳細に説明すれば、円弧の終了点の間の距離または円
弧の径が距離許容度未満、すなわち過度に小さければ、
同様にエラー条件が存在するとみなされる（ブロック２
０４）。ユーザーが製図の初心者、中級者または熟練者
のいずれかに応じて、この距離許容度をユーザーが特定
できるようにすると便利で、かつ効率的である。０.
１、０.２および０.３のモデル単位の距離許容度は、そ
れぞれ熟練者のレベル、中級者のレベルおよび初心者の
レベルに対して、便利で、かつ効率的であることが判っ
ている。

【０１２０】本例における直線の発生について説明する
と、（重複点が除かれ、除かれた折れ候補点が存在して
いない状態で）第１および最終インジケータ情報要素
は、直線ラインを発生するためのサンプル点となる。し
かしながらこれら２つの位置は、かかる発生の前提条件
として一致することができない。仮に一致した場合、エ
ラー条件が存在すると判断する。後の条件（ブロック２
０４）として、いずれかの位置が２００００×２０００
０のモデル単位領域外にあれば、エラー条件が存在し、
その結果生じるラインの長さが、距離許容度未満、すな
わち過度に短い場合もエラー条件が存在する。

【０１２１】セグメントとしての円の発生を説明する。
まず、上記タイプのｍｉｎ−ｍａｘｂｏｘ（ブロック２
０２）を決定する。（ボックスの辺の分割線に基づく）
ボックスの中心点を円の中心として選択する。ボックス
の幅および長さの平均を円の直径として選択する。極端
に大きな形状または極端に小さな形状、または原点から
極めて遠い形状に基づく発生された円の除去に関し（ブ
ロック２０４）、径を距離許容度以上とし、５０００モ
デル単位未満でなければならないとすると、便利で、か
つ効率的であることが判っている。同様に、中心を２０
０００×２００００のモデルユニットの領域内になけれ
ばならないとすると有利であることが判っている。

【０１２２】セグメントとしてのポイントの発生につい
て説明する。（折れ点認識時のように重複点が除かれた
状態で、）初期インジケータ情報要素により特定された
位置を発生された点の位置として選択する。先に述べた
ように、一般にストロークの最小の大きさに基づく点判
断による最初の判断の後に、多くの情報要素が生じる。
選択された点が２００００×２００００個のモデル単位
の領域外にあれば、１つの点に対し発生された点の除去
が行われ、エラー条件が存在する（ブロック２０４）。

【０１２３】楕円を発生するには（ブロック２０２）、
長軸および短軸の長さおよび中心点を決定する際に上記
タイプのｍｉｎ−ｍａｘ ｂｏｘを使用する。楕円の中
心点が対抗する辺を２分割する線の交点により決定され
たこのボックスの中心点となり、短軸および長軸の長さ
はボックスの長さおよび幅によって決定される。楕円の
角度を決定するため、上記タイプの最小二乗適合ライン
を使用する。発生された楕円の除去条件を採用しないこ
とは、好ましく、かつ効率的であることが判っている
（ブロック２０４）。

【０１２４】上記のように、点、削除およびベタ塗り
は、単一要素のストロークである。ベタ塗りはクローズ
ド領域に関連している（図９）。ベタ塗りから生じるク
ロスハッチングの角度は、このシンボルの最小二乗適合
ラインに対する角度によって決定できる。次のグループ
のうちから、最小二乗適合ラインの角度に最も近い角度
を選択すると、便利で、かつ効率的であることが判って
いる。すなわち０°、３０°、４５°、６０°、９０
°、１２０°、１３５°、１５０°、１８０°、２１０
°、２２５°、２４０°、２７０°、３００°、３１５
°、３３０°である。このベタ塗りを、選択したクロー
ズド領域に関連させるための明らかな選択案は、ベタ塗
りシンボル内の（折れ点認識の際のように重複点を除い
た状態で）第１インジケータ要素の位置をクローズド領
域に接近させることである。

【０１２５】削除シンボルに対し、明らかな代替案は、
非ポイント前で点を削除すべきとする評価により、ユー
ザーによって加えられた先の最終セグメント（またはス
トローク）を削除することである。別の代替案は、接近
度、すなわち削除シンボルのための（折れ点認識におけ
るような重複点が除かれた状態の）第１インジケータ要
素への接近度を用いること、または最初の接近度および
先の最後のセグメントをフォールバックとしてのみ使用
することである。

【０１２６】図５において、ストロークをセグメントに
分割するためのストロークの折れ点の決定、セグメント
の認識および発生および拘束条件の問題に関する方法
を、広義のコンピュータ支援設計（ＣＡＤ）に関連づけ
られている。当然ながら、図に向けられる初期演算は、
下記を含むこれまで詳細に述べたものに従って行われ
る。すなわちストローク内で移動されるインジケータを
使ったユーザーによるストロークの描画（ブロック２０
６）、折れ位置（点）の選択、個々のセグメント領域へ
のマルチセグメントストロークの分割（ブロック２１
０）、ストロークにおけるマルチセグメントの認識（す
なわちシングルセグメントストロークにおけるセグメン
トの認識）（ブロック２１２）、およびマルチセグメン
ト（または単一セグメント）の発生（ブロック２１４）
を含む。

【０１２７】（これらセグメントを画定する情報の）こ
れらセグメントが発生する場合、ワークステーションで
発生されたＣＡＤモデルにセグメント（情報）を加える
ことができる（ブロック２１４）。ＣＡＤ分野で標準的
なかかるモデルは、当該デザインまたは作品を構成する
情報を含む。

【０１２８】図１６および２０、ならびにかかる図に関
連した説明は、ストロークのうちのセグメント内の拘束
条件の発見を示している。図１７、１８および１９なら
びにこれらに関連した説明は、異なるストロークのセグ
メント、すなわち新しく発生されたストロークの説明
と、先のストロークのセグメントとの間の拘束条件の発
見および検討を示している。当然ながらかかる演算は、
ストロークの発生されたセグメント内、かかるセグメン
トと先のストロークのセグメントの間の拘束条件、例え
ば一致条件、平行条件、接線条件および再限定条件を発
見し（ブロック２１６）、更にＣＡＤシステムのための
拘束条件管理システムへの発見された拘束条件および発
生されたセグメントの追加を行う（ブロック２１８）。
ＣＡＤ関係におけるかかる幾何学的拘束条件を発見し、
決定するための演算および技術は、エドワード・Ｔ・コ
ーンにより米国特許庁に同時に提出された、本願出願人
を譲受人とする米国特許出願の要旨となっている。参考
例としてここに援用するこの米国出願の発明の名称は、
「コンピュータで発生された製図の要素間の幾何学的関
係の自動的識別」［ロビンス、バーリナー及びカールソ
ン（Robbins,Berliner& Carson）の米国出願：整理番号
５９０８−１０２に掲載。］である。上記幾何学的拘束
条件に関連する演算および技術の外に、本願は共通直線
性、垂直性および同一サイズにも関係している。

【０１２９】以下に上記幾何学的拘束条件を発見し、決
定するため演算および技術について説明を加える。この
演算および技術の総合目的は、コンピュータ化されたモ
デルにおける要素間の幾何学的拘束条件の可能な識別を
行うための有効なコンピュータ化された方法及びこれに
関連する装置を提供することである。この演算および技
術は、特に、該モデルにおける要素が適当に拘束された
モデルの対応する理論値から所定の許容誤差範囲内では
ずれている場合に有効である。さらに、この演算および
技術の、より特徴的な目的は、上記拘束条件を識別する
ために計算の回数を減らすようにデータを組織化し、イ
ンデックス化することである。さらに、別のより特徴的
な目的は、個々の計算の複雑さを減らすようにデータを
組織化し、インデックス化することである。

【０１３０】この演算および技術は、次の構成を含むも
のである。即ち、２次元像を描くための、複数の成分
（点、線分、円、円弧等）から構成されるモデルを使用
し且つ前記成分の各々が１つあるいはそれ以上の関連す
る点要素（隔離された点、端点、中心点等）及び／又は
線形要素（ライン、接線等）を含み、各々はｎ＞２の変
数によって定義される、コンピュータ支援システムにお
いて、２つあるいはそれ以上の前記要素の間の幾何学的
拘束条件（一致、共線、平行、垂直、再限定、ポイント
オン、同心性、接線性等）を自動的に識別するコンピュ
ータ化された方法であって、以下の工程を含む方法であ
る。

【０１３１】前記モデルにおける各点要素に関連するｎ
の変数（Ｘ，Ｙ）を使用して、第１のｎ−トリー（Ｔ
Ｒ）において点要素をインデックス化する工程 前記モデル内の前記要素の第１のシーケンスを使用し
て、第１のシーケンスの各々の要素で、所定の許容範囲
内の所定の幾何学的拘束条件を満足する点要素を含む可
能性のあるノードに対して第１のトリーを検索する工程 前記モデル中の線形要素のシーケンスのうちの各々に関
連するｎ変数を使用して、第２のｎ−トリーにおいて線
形要素をインデックス化する工程 及び前記モデル内の前記要素の第２のシーケンスを使用
して、第２の所定の許容範囲内で第２の所定の幾何学的
拘束条件を満足する線形要素を含む可能性のあるノード
に対して第２のトリーを検索する工程 この自動的識別方法は、上記構成に加えてさらに次の工
程を含むことが好ましい。 このようにして見つけ出された他の要素のいずれかをテ
ストして、それら要素が、現実に、前記許容範囲の各々
の範囲内において前記所定の幾何学的拘束条件の各々を
満足するか否かを決定する工程 さらに、この自動的識別方法は、上記構成において、前
記モデルが２次元モデル即ち、ｎ＝２であり、前記第１
のトリーがカーテシアンクオドトリーであり、且つ前記
第１の要素のシーケンスが第１のトリー内の点と一致す
る可能性をテストされた点及び第１のトリー内の点とポ
イントオン関係にある可能性をテストされたラインを含
むことが好ましい。

【０１３２】さらに、この自動的識別方法は、上記構成
において、前記第２のトリーが極クオドトリーであり、
且つ前記第２のシーケンスが該極クオドトリー内の他の
ラインと一致する可能性をテストされたライン及び該極
クオドトリー内のラインと接する可能性をテストされた
円を含むことが好ましい。さらに、この自動的識別方法
は、上記構成において、前記第２のトリーが前記極クオ
ドトリー内の各個別の角度θの値の単なる整列されたリ
ストを含むことが好ましい。さらに、この自動的識別方
法は、上記構成において、所定の許容範囲内で異なる近
似する角度が前記リストから除かれていることが好まし
い。さらに、この自動的識別方法は、上記構成におい
て、前記所定の許容範囲が０より大きく、且つ前記トリ
ーの各々の各点に向けられた検索が前記所定の許容範囲
によってテスト点から分割された候補点を位置づけする
ことができ、たとえ該候補点が特別のテスト点に関連す
るノードに隣接するノード内であっても位置づけできる
ことが好ましい。さらに、この自動的識別方法は、上記
構成において、前記第１のトリーの各ラインに向けられ
た検索が所定の許容範囲で分割された少なくとも２つの
検索パスを含むことが好ましい。

【０１３３】さらに、この自動的識別方法は、上記構成
において、さらに次の工程を含むことが好ましい。 前記第１のトリーのラインに向けられたいずれかの検索
のうちのいずれかの要素をテストして、これら要素が前
記所定の許容範囲の各々の内で前記所定の幾何学的拘束
条件の各々を現実に満足するか否かを決定する工程 上記演算および技術によれば、基礎モデルにおいて定義
される、点と線との間の正確な幾何学的拘束条件を自動
的に識別するコンピュータ化された新規な作図システム
により、前記諸目的が達成される。

【０１３４】より詳細には、この演算および技術は、識
別操作を簡単にし、例えばクオドトリー（ｑｕａｄｔｒ
ｅｅ）等の多次元インデックススキームで基礎データを
インデックス化することにより処理される変数の数を減
らす。これにより、多次元空間内の特定の位置に配置さ
れたあらゆる要素を識別することが容易になる。より詳
細には、２つのｎ−トリーインデックスが使用される。
この演算および技術には、カーテシアン座標で表される
点（円の中心点並びに線分及び円弧の端点を含む）に関
連するカーテシアンｎ−トリー、極座標で表されるライ
ン（円弧の端点における接線を含む）に関連する極ｎ−
トリーが含まれる。カーテシアンｎ−トリーは、特定の
位置（例えば、２つの円の間の同心の関係あるいはライ
ンの端点と円の中心との間の再限定の関係）の近傍にお
ける点又は特定のパス（例えば、二番目の線に交差する
１つのラインの端点の間の再限定の関係）の所定の許容
範囲内の点を見つけるために使用される。極ｎ−トリー
は、他のラインと同一直線上にあるライン（例えば、特
定の円弧の一端と接する関係）、所定の傾きを有するラ
イン（例えば、特定のラインに平行あるいは垂直なライ
ン）及び特定の円上の任意の点に接する（例えば接触関
係）ライン（他の円弧の端点で接するベクトルを含む）
を見つけるために使用される。

【０１３５】正確な操作、例えば特定の円上の任意の点
で接するすべてのラインを識別するために、極トリーに
存在する角度θの異なる値のリストをこの極トリーに追
加することにより計算時間を大幅に削減してもよい。こ
の角度のリストは極クオドトリーにおける各“個別の”
角度θの値の単純に整列されたリストでもよい。このク
オドトリーからは、所定の許容範囲内で異なる近似する
角度が除去されている。別のこの演算および技術の特徴
によれば、点はテスト点の与えられた許容範囲内であっ
てもよいが、このテスト点に対応する特別のノードに隣
接したノード内でもよいので、隣接するノード間で正確
な要素を識別するための設備も作られる。

【０１３６】さらに別の特徴によれば、テスト点及び識
別点は、必然的に同じノード内でインデックス化される
ことなく、トリーを構成する許容範囲内で同時に発生す
る１つのプライオリ（ｐｒｉｏｒｉ）として知られるの
で、特別の許容範囲内で、事実識別要素が特別の抑制を
塩化する（ｓａｌｉｆｙ）か否かを評価するための該識
別要素をテストするための設備も作られる。以下に、上
記演算および技術における好適な態様について、図２１
乃至２３を参考にして説明する。

【０１３７】型どおりのカーテシアンクオドトリーは図
２１によりドラマティカリーに表現される。このクオド
トリーは、トリー（Ｔ）、このトリー（Ｔ）内のノード
（Ｎ）及びこのノード（Ｎ）内の要素（Ｅ）で表現され
るデータ構造のリンクされた階層として与えられる。こ
のトリーは、ルートノード（ＲＮｏ，ｏ）に対するポイ
ンターを含む、各ノードは各ノードの位置（例えばその
中心）及びサイズ（例えば端部間の長さ）、並びにあら
ゆる関連づけられた要素のリスト（リーフノードをＬＮ
と仮定する）又はその４つのクオドノード（内部ノード
をＩＮと仮定する）に対するポインターを含む。例え
ば、ルートノード（ＲＮ）の右上のクオドラント（ｑｕ
ａｄｒａｎｔ）は、８の長さを有し且つカーテシアンク
オドトリー（ＴＲ）を構築するために使用される許容範
囲Ｔ＝２よりも少ない垂直方向距離（Ｔ−Δ₁ ）で離れ
ている２点Ｅ₁ ，Ｅ₂ を含むリーフノード（Ｌ
Ｎ_+4,+4 ）である。ルートノード（ＲＮ）の右下のクオ
ドラントは内部ノード（ＩＮ_-4,-4 ）であり、これは各
々４の長さを有する４つのクオドラントに分割され、そ
の分割されたうちの低レベルの内部ノードＩＮ_-2,-2 を
含む右上のクオドラントを伴っている。このクオドラン
トは、順に各長さ２の４つのリーフノードを含んでい
る。リーフノードＬＮ_+3,-3 がある左上のクオドラント
は、点Ｅ₂ から垂直方向距離Ｔ−Δ₂ で離れている点Ｅ
₃ を有する。

【０１３８】いくつかのリーフノード（例えば、ＬＮ
_+4,+4 ）は、１以上の要素を含んでおり、一方、他のリ
ーフノード（例えば、ＬＮ_+6,-6 ）は、全く要素を含ま
ないこと（この場合、親の内部ノードにおけるノードポ
インターは領域を確保するためにＮＵＬＬに設定され
る。）に注目すべきである。また、２点（例えば要素Ｅ
₂ 及びＥ₃ ）が、クオドトリーを構築するために使用さ
れるＴ＝２の許容範囲以下により水平及び垂直方向に分
割されることができ、それでもなお、両者は同じリーフ
ノード内に存在しないことになる。その上、要素Ｅ₁ 及
びＥ₂ によって示されるように、１つの要素とその要素
のリーフノードの中心との間の距離は、クオドトリーを
構築するために使用されるＴ＝２の許容範囲よりもかな
り大きなものとすることができる。

【０１３９】従って、特点の点（時々、テストポイント
として言及される）に対する所定の許容範囲内に位置づ
けられるトリー内のすべての点を見つけるために、一度
リーフノード（例えば図１におけるノード（Ｌ
Ｎ_+4,+4 ））がテスト点（例えば要素Ｅ₂ ）を含むこと
を見つけると、点検索ルーチンは、そのノード内のすべ
てのデータ点（例えば要素Ｅ₁ ）をテストしてテスト点
の所定の許容範囲内に現実にそれらデータ点が位置づけ
られているか否かを決定するだけでなく、テスト点があ
らゆる隣接ノードから水平あるいは垂直方向に±Ｔの許
容範囲内に存在するか否かをも決定し、この場合その隣
接ノード内の点（例えばノード（ＬＮ_+3,-1 及びＬＮ
_-2,+2 ））が試験される。同様に、すべての検索が、オ
リジナルテスト点のみならず、垂直及び／又は水平にオ
リジナルテスト点から±Ｔで置き換えられた８つの補足
テスト点も使用することにより、行うことができる。

【０１４０】要素リストは、好ましくは、要素の位置
（その要素のＸ及びＹ座標、仮にその要素が点でトリー
がカーテシアンクオドトリーである場合）、例えばコン
ピュータで援助された作図プログラム内の幾何学的イメ
ージを定義する基礎モデル等の分割データ構造内の対応
する要素に対するポインター、及び（もしあるなら）次
の関連する要素に対するポインターを含む。

【０１４１】クオドトリーは、トリー及び関連するデー
タ構造を作成し、削除し、維持するための簡単なハラス
キーピングルーチンを使用して維持される。このような
ハラスキーピングルーチンは、平均的職人の技能範囲内
で適切である。型どおりの作図及び表示ルーチンもまた
欠陥を直す目的で便利である。

【０１４２】計算によれば、θ（０＝２π）の円属性及
びρの反対の符号はρにπを加えた場合に相当するとい
う事実を除いて、図２２の極クオドトリー（ＴＰ）はカ
ーテシアンクオドトリー（ＴＲ）に類似しており、同じ
データ構造とハラスキーピングルーチンを使用すること
ができる。特に点（ρ，θ）は、角度θの無限長さのラ
インで表現され、原点から直線距離ρに位置する。しか
し、正確な操作のために、演算時間は、トリー内に存在
する角度θの異なる値のリストを追加することによりか
なり減縮される。この角度のリストは、極クオドトリー
における各々別個の角度θの値の簡単な配列リストであ
る。この角度リストから所定の許容範囲内で異なる、近
似する角度が除去される。図２２において注目すべきこ
とは、線Ｌ₁ 及びＬ₂ が近値する傾きを有しており、そ
れ由にトリーを構築するために使用される所定の許容範
囲内で平行である。しかし、これら線は原点からの垂直
距離でかなり異なっているので、これら線は、共線関係
ではないし、現実に異なるリーフノード内に存在する。 以下の検索ルーチンが提供される：

【０１４３】ＱＴＦＰＮＴ 前記した点検索ルーチンである。カーテシアン座標にお
ける点は極座標におけるラインに相当するので、このル
ーチンもまた、ρ及びθの特定の値を有するラインを
（ρとθについての所定の許容範囲内で）見つけるため
に極クオドトリーの検索に使用される。

【０１４４】ＱＴＦＰＬＮ Ｘ軸やＹ軸に切片を有する（又はこれらに平行する）特
定の横断線（例えば図１のラインＰ）上の（与えられた
許容範囲を含む）カーテシアンクオドトリーにおける点
を見つける。前述したように、２点（又は１点と１本の
ライン）はクオドトリーを構築するために使用される許
容範囲以内で分割されることができる。それにもかかわ
らず、２点は、隣接するノード内にインデックス化され
ることになる。従って、２つのテスト線が追加される。
即ち、一方のライン（図２１のＰ′）は、特定のライン
（例えば前記Ｐ）のＴだけ上方に及びＴだけ左に置換さ
れたものであり、もう一方のライン（図２１のＰ″）は
特定の直線をＴだけ下方に及びＴだけ右方に置換された
ものである。３本の直線は、各々、クオドトリーの隣接
するリーフノードを通じてそれぞれのテストパスをトレ
ースするために使用される（例えば、図２１では直線
Ｐ′とリーフノード（ＬＮ_+4,+4 、ＬＮ_-2,+2、ＬＮ
_-5,+1 及びＬＮ_-7,+1 ））。さらに、これら隣接するリ
ーフノードの各々にインデックス化された要素（例え
ば、点Ｅ₁ ，Ｅ₂ 及びＥ₅ ）は可能な拘束関係で検査さ
れる（例えば、これら点は直線Ｐ上に存在する）。カー
テシアン座標における点は極座標におけるラインに相当
するので、同じ傾きθを有するすべてのラインによって
定義される点はρ軸に対して平行な直線上に存在するこ
とになる。このルーチンもまた、特定の傾きを有するラ
インを見つけるために極トリーにおいて使用される。

【０１４５】ＱＴＦＰＣＲ 特定の中心と特定の半径を有する円上（与えられた許容
範囲内で）のカーテシアンクオドトリー内の点を見つけ
る。このルーチンは、テストパスが同心円であることを
除き、ＱＴＦＰＬＮと同様である。

【０１４６】ＱＴＦＣＴＮ 特定の中心と特定の半径を有する円に接する、極クオド
トリー内のラインを見つける。角度リスト内の各角度θ
は特定の円に接する２つのテストライン（ρ₁，θ）、
（ρ₂ ，θ）を発生するのに使用する。次いで、各テス
ト接線は、ρ及びθについて同じ値（±Ｔ）を有するラ
インに対し極クオドトリーを検索するためにＱＴＦＰＮ
Ｔによって使用される。

【０１４７】余分な幾何学的関係を見つけるために、基
礎モデルにおける要素は、該モデル中の他の点と一致す
る点をチェックすること、同様に他のラインと平行なラ
インをチェックすること等の必要を避けることによって
かなり有利な効果を奏するようにして初めにインデック
ス化される。特に、クオドトリーインデックスの使用
は、テストされている要素のすぐ近傍（このインデック
スを構築するために使用される所定の許容範囲によって
確立されるものとしての近傍）に存在する要素に対して
要素検索を制限する。あるモデルにおけるすべての幾何
学的関係を見つけるための時間内の結果として得られる
性能は、単純検索の（Ｎ² ＋Ｎ）／２と比較すると、Ｎ
・ｌｏｇ₄ （Ｎ）に近似している。この演算および技術
によれば、２つの異なるクオドトリーが使用される。一
方は、直交（カーテシアン）座標において、一致点ある
いは同一線上の点を見つけるためのものである。もう一
方は、極座標において平行、同一線あるいは直交するラ
インを見つけたり、円の接線を見つけるためのものであ
る。

【０１４８】この演算および技術の好適な態様において
は、以下の幾何学的要素が重要事項である。 要素 インデックス 記述 点．点 直交 点 ライン．ライン 極 無限長ライン ライン．端点 直交 ある線分の２つの端点の内の一方の端点 円．円 Ｎ／Ａ 完全円（その中心点のみがインデックス化 される） 円．中心 直交 円の中心点 円．端点 直交 ある円の円弧の２つの端点の内の一方の端 点 円．ベクトル 極 円弧の２つの端点の内の一方の端点で、該 円弧に接する直線

【０１４９】さらに、次の関係が重要事項である。 関係 記述 関連事項 ＳＴＣＯＩＮ 一致 点．点−点．点 円．中心−円．中心 ＳＴＣＬＩＮ 共線 ライン．ライン−ライン．ライン ＳＴＣＣＥＮ 同心円 点．点−円．中心 円．中心−円．中心 ＳＴＰＡＲＡ 平行 ライン．ライン−ライン．ライン ＳＴＰＥＲＰ 垂直 ライン．ライン−ライン．ライン ＳＴＲＥＬＭ 再限定 ライン．ライン−ライン．端点 ライン．ライン−円．端点 円．円−ライン．端点 円．円−円．端点 ＳＴＴＡＮＧ 接線 ライン．ライン−円．ベクトル ライン．ライン−円．円 円．ベクトル−円．ベクトル 円．円−円．ベクトル ＳＴＲＬＣＮ 中心へ再限定 ライン．端点−円．中心 円．端点−円．中心 ＳＴＰＴＯＮ ポイントオン 点．点−ライン．ライン 円．中心−ライン．端点 円．中心−ライン．ライン 点．点−円．円 ＳＴＥＮＤＰ 端点 ライン．端点−点．点 円．端点−点．点 ＳＴＭＲＬＭ 相互再限定 ライン．端点−ライン．端点 ライン．端点−円．端点 円．端点−円．端点

【０１５０】ＳＴＰＴＯＮ，ＳＴＲＥＬＭ及びＳＴＲＬ
ＣＮを除き、すべては再帰的である。モデルにおけるす
べての点に合わせたデータ（点．点、ライン．端点、
円．端点、円．中心）は、直交座標トリーを検索するた
めにルーチンＱＴＦＰＮＴに対する入力として使用され
る。さらに、結果としての出力はいずれも次の例のよう
にテストされる（参考要素は図２３に示す）： ・点の一致性（ＳＴＣＯＩＮ、点．点、点．点） ・点とラインの端点との間の端点関係（ＳＴＥＮＤＰ、
点．点、ライン．端点） ・点と円弧の端点との間の端点関係（ＳＴＥＮＤＰ、
点．点、円．端点） ・２つのラインの隣接した端点間の相互再限定関係（Ｓ
ＴＭＲＬＭ、ライン．端点、ライン．端点）。ラインＬ
７及びラインＬ５を見よ。 ・ラインと円弧の隣接する端点間の相互再限定関係（Ｓ
ＴＭＲＬＭ、ライン．端点、円．端点）。 円の弦を横切るラインの場合のように、ラインは、１回
以上円に再限定されることに注目すべきである。ライン
Ｌ２と円Ｃ１を見よ。 ・２つの円弧の隣接する端点間の相互再限定関係（ＳＴ
ＭＲＬＭ、円．端点、円．端点）。円Ｃ４及び円Ｃ５を
見よ。 ・ラインの端点と円の中心との間の中心関係に対する再
限定（ＳＴＲＬＣＮ、ライン．端点、円．中心）。ライ
ンＬ９及び円Ｃ４を見よ。 ・点と円との間の同心性（ＳＴＣＣＥＮ、点．点、円．
中心） ・円と他の円との間の同心性（ＳＴＣＣＥＮ、円．中
心、円．中心） ・円と他の円との間の一致性（ＳＴＣＯＩＮ、円．中
心、円．中心）、但し、これらが等しい半径を有する場
合（円Ｃ５及び円Ｃ４を見よ。） ・端点と円中心との中心関係に対する再限定（ＳＴＲＬ
ＣＮ、円．端点、円．中心）。円６及び円７を見よ。 ・円の中心と端点を含む円との間のポイントオン関係
（ＳＴＰＴＯＮ、円．中心、円．端点）。円Ｃ６及び円
Ｃ７を見よ。 ・円の中心とラインとの間のポイントオン関係（ＳＴＰ
ＴＯＮ、円．中心、ライン．端点）。ラインＬ９及び円
Ｃ４を見よ。

【０１５１】注目すべきは、様々な要素のタイプの分
布、及び特定の関係にあることを見つけた要素をテスト
するために要する時間に対するトリーを検索するのに要
する時間に依存して、第１要素を見つけるための関係に
おいて第２要素を使用することがより効果的となるだろ
う。

【０１５２】モデル中の各線は極座標トリーを検索する
ためにルーチンＱＴＦＰＮＴに対する入力として使用さ
れる。次いで、出力は、次の例のようにテストされる： ・ラインと他のラインとの間の共線関係（ＳＴＣＬＩ
Ｎ、ライン．ライン、ライン．ライン） モデル中の各線（ライン．ライン）は、直交座標トリー
を検索するためにルーチンＱＴＦＰＮＴに対する入力と
して使用される。次いで、出力は、次の例のようにテス
トされる： ・点とラインとの間のポイントオン関係（ＳＴＰＴＯ
Ｎ、点．点、ライン．ライン） ・円中心とラインとの間のポイントオン関係（ＳＴＰＴ
ＯＮ、ライン．ライン、円．中心）。ラインＬ９及び円
Ｃ４を見よ。 ・ラインと他のラインの端点との間の再限定関係（ＳＴ
ＲＥＬＭ、ライン．端点、ライン．ライン）。ラインＬ
８及びラインＬ１を見よ。 ・ラインと円弧の端点との間の再限定関係（ＳＴＲＥＬ
Ｍ、円．端点、ライン．ライン）。注目すべきは、円弧
は、円の弦の場合のように１回以上同一ラインに対して
再限定されることである。ラインＬ３及び円Ｃ４を見
よ。

【０１５３】注目すべきは、モデル中の各点をチェック
することによりあるライン上の点を見つけようと努力す
るよりも、むしろ、該ラインをそのライン上に存在しそ
うな点に対して検索を限定するために使用することであ
る。

【０１５４】モデル中の各線の傾きに相当するライン
は、極座標トリーを検索するためにルーチンＱＴＦＰＬ
Ｎに対する入力として使用される。次いで、出力は次の
例のようにテストされる： ・ラインと他のラインとの間の平行関係（ＳＴＰＡＲ
Ａ、ライン．ライン、ライン．ライン）、（ＳＴＣＬＩ
Ｎでない）又は（ＳＴＣＬＩＮがオフ）の場合。ライン
Ｌ６及びラインＬ２を見よ。 モデル中の各ラインの傾きに相当するラインプラスπ／
２は、極座標トリーを検索するためにルーチンＱＴＦＰ
ＬＮに対する入力として使用される。次いで、出力は次
の例のようにしてテストされる： ・ラインと他のラインとの間の垂直関係（ＳＴＰＥＲ
Ｐ、ライン．ライン、ライン．ライン）。ラインＬ３及
びラインＬ１を見よ。 モデル中の円弧の各端点で各接線ベクトルは、極座標ト
リーを検索するためにルーチンＱＴＦＰＮＴに対する入
力として使用される。次いで、その出力は、次の例のよ
うにテストされる： ・円弧の端点とラインとの間の接触（ＳＴＴＡＮＧ、ラ
イン．ライン、円．ベクトル）。ラインＬ１及び円Ｃ１
を見よ。 ・円弧の端点と他の円弧の端点との間の接触（ＳＴＴＡ
ＮＧ、円．ベクトル、円．ベクトル）、２つの端点が直
交座標において同じ場合。円Ｃ５及び円Ｃ４を見よ。 モデル中の各円は、直交座標トリーを検索するためにル
ーチンＱＴＦＰＣＲに対する入力として使用される。次
いで、その出力は次の例のようにテストされる： ・ある点と上記円との間のポイントオン関係（ＳＴＰＴ
ＯＮ、点．点、円．円） ・他の円の中心と上記円との間のポイントオン関係（Ｓ
ＴＰＴＯＮ、円．中心、円．円） ・あるラインの端点と上記円との間の再限定関係（ＳＴ
ＲＥＬＭ、ライン．端点、円．円）。注目すべきは、ラ
インは、弦の場合のように、１回以上円に対して再限定
されてもよいことである。直線Ｌ２及び円Ｃ１を見よ。 ・円弧の端点と上記円との間の再限定関係（ＳＴＲＥＬ
Ｍ、円．端点、円．円）円Ｃ６及び円Ｃ７を見よ。

【０１５５】モデル中の各円は、極座標トリーを検索す
るためにルーチンＱＴＦＣＴＮに対する入力として使用
される。次いで、その出力は、次の例のようにテストさ
れる。 ・あるラインと上記円との間の接触（ＳＴＴＡＮＧ、ラ
イン．ライン、円．円）。ラインＬ８及び円Ｃ７を見
よ。 ・他の円弧の端点と上記円との間の接触（ＳＴＴＡＮ
Ｇ、円．ベクトル、円．円）、しかし問題の端点が上記
円上にある場合に限る。円Ｃ５及び円Ｃ４を見よ。 過剰に拘束されたモデルを構築するのを避け、且つ拘束
条件の数及び当該モデルに変化をもたらすために要求さ
れる計算の複雑さを減らすことを目的として、以下のガ
イドラインが、発見された拘束条件が当該モデルに加え
られる前に適用されるべきである： １ もし既に現在構築中のタイプの要素間に或る関係が
存在するならば、次に、別のタイプを構築しないこと ２ もし拘束条件のタイプが無効であるならば、次に、
拘束条件を構築しないこと ３ もし２つの要素が同じであるならば、関係を構築し
ないこと ４ 要素の端点が関係に含まれる場合のいずれにおいて
も、その端点の数は、拘束条件の拡張されたデータ領域
に保存されるだろう。 ５ 余分な拘束条件を除くことを目的として、同じタイ
プの関連する要素の各集合ごとに先導要素を識別するこ
と ６ 特に、大幅な許容範囲が含まれている場合は、矛盾
する拘束条件をチェックし、最も正確なものを選択する
こと

【０１５６】以下の特別規則が好適な態様において行わ
れている。 １ 関係が端点条件に依存してもよい場合は、その端点
をチェックすること ２ 異なるクラスの余分な再限定拘束条件を避けること
（相互及び標準の再限定）。 ３ もし端点が一致しているならば、共線関係のライン
についてのみ再限定（相互に再限定）を許すこと ４ もし相互に再限定する拘束条件が２つの要素間に既
に存在するならば、端点ごとに１つの拘束条件のみを構
築すること ５ ある円が同心又は一致の集合内の先導要素である場
合、又はいずれの種類の集合にも属さない場合、当該円
とあるラインとの間にポイントオン拘束条件を構築する
のみとすること ６ 共線の拘束条件が存在し、それが無効でない場合
は、平行の拘束条件を構築しないこと ７ 一致の拘束条件が存在し、それが無効でない場合
は、接線の拘束条件を構築しないこと ８ 円が一致しない場合、同じサイズの円の拘束条件を
加えること ９ 各ラインが各々の平行の集合の先導要素であるか、
又はいずれの平行の集合に存在しない場合にのみ、垂直
の拘束条件を加えること １０ 同じラインの両方の端点で相互に矛盾する再限定
の拘束条件が存在し得る場合は、より近い端点でのみ拘
束条件を構築すること １１ あるラインとある円の中心及び外側との間で矛盾
するポイントオン及び接線の拘束条件が存在し得る場合
は、より近い要素でのみ拘束条件を構築すること １２ 与えられた１つのラインに対しては、１つの垂直
関係を構築するのみとすること １３ 平行の集合内で先導要素となっていない与えられ
たラインに対しては１つの平行関係を構築するのみとす
ること 上記のリストは、消耗するものと考えてはならないし、
余分な、競合する及び／又は矛盾する拘束条件を除去す
るための他の同様な特別規則が、疑いなく、当業者に対
して明らかとなるだろう。

【０１５７】同じノード内の２以上の要素がクオドトリ
ーを構築するために使用される許容範囲内で共に位置づ
けられ、一般規則として、それら要素は一致するものと
考えられる。しかし、特別の用途では、クオドトリーを
構築するためにより粗末な許容範囲を使用すること（こ
のようにしてノードの数と検索時間を減らす）、及び見
つけられた要素が検索要素に一致しているか否か又はそ
うではなく、検索要素によって拘束されるか否かを決定
するため、よりよい許容範囲を使用することは有利とな
るだろう。例えば、極クオドトリーは、一致条件とし
て、２つのラインを同じ傾きと原点からの垂直距離を有
するものとして考える。たとえ、これら２つのラインの
隣接する点の間の実際の距離が垂直ベクトルからこれら
の点までの距離によって拡大されるとしてもこのように
考える。同様にして、接線と円との間のあらゆるスペー
スが、その円とそのラインの垂直ベクトルとの間の距離
によって拡大される。その上、特に許容範囲は付加的な
ので、拘束条件は必ずしも移行的とならない。２つより
も多くの相互に拘束された要素（例えば、多数の平行線
から形成される格子）を、共通の先導要素に対する共通
の拘束条件によってリンクされた要素のリストとして組
織することが好ましい。

【０１５８】いくつかの用途では、例えば同じ長さを有
する複数のライン又は同じ半径を有する複数の円等のよ
うに寸法の拘束条件を識別することも有効である。寸法
は、単一の値からなる変数なので、このような寸法の拘
束条件は、型どおりの線形インデックスの方法により簡
単に識別される。

【０１５９】多少の規則的幾何学的構造を有する物体を
描くことによる、１つあるいはそれ以上のフリーハンド
の線形像を２次元の機械的作図に加工する方法にふさわ
しい本演算および技術の好適な態様において、相対的に
大きな許容範囲が、角度に対する拘束条件に使用され、
可能な拘束条件の検索が現在表示されている像の中に現
れている要素に限定される。新たに入力された線形像の
各々は、各基本ストロークの要素と、実時間で、比較さ
れ且つインデックス化される。この基本ストロークは、
該ストロークに関係する可能な拘束条件に対して、ウイ
ンドウ内に前に加工された要素のインデックスにアクセ
スしたりアップデートしたりするために使用される各線
形像を形成する。すべての基本ストロークが加工された
後、モデルは、新たに見つけ出された拘束条件を使用し
て再構築され、フリーハンドの像は、新たに見つけ出さ
れた拘束条件で修正されたモデルを描いた、コンピュー
タ作図によって置換される。上記幾何学的拘束条件を発
見し、決定するための自動的識別方法により得られた拘
束条件は、拘束条件管理システムへと追加される。

【０１６０】拘束条件管理システムは、拘束条件と一致
性があるのはどのセグメントであるかを解くことができ
る（ブロック２２０）。当然ながらこのシステムはかか
る一貫性を含むよう発生されたセグメントを多少変更
し、更に同じ理由で先のセグメントを変更することを一
般に行う。拘束条件が一旦決定されれば、かかる拘束条
件と一致するセグメントを解くことは、より標準的なタ
イプの演算である。ＤＣＭの名称でディーキューブドリ
ミテッド（Ｄ−Ｃｕｂｅｄ Ｌｔｄ．）によって販売さ
れている製品は、かかる演算を実行するようになってい
るワークステーション用のプログラムソフトウェアを示
している。

【０１６１】一旦、幾何学的拘束条件と一致してセグメ
ントと解くと、ＣＡＤモデルに記憶されていたようなセ
グメント情報は、セグメントに対して更新できる（ブロ
ック２２２）。このモデルは更新されたモデルのディス
プレイを含む通常のデザインまたはディスプレイ機能の
いずれかに対してアップツーデートである（ブロック２
２４）。

【０１６２】先の情報要素からの情報要素に適用できる
構成された曲率円のための中心からの距離（またはそれ
によって表示される位置または点）は先の説明で計算さ
れるように表示される（ブロック１５４）。先に述べた
折れ点方法では実行されないが、これら中心距離を使用
し、コーナーおよびフィレット状折れ点の外に、変曲折
れ点を使用するような変更を実施できる。これを行うた
め、変曲折れ点のための候補点として、この適用可能な
中心距離の比較的大きな値を有する位置を発見できる。
前提条件としてのこれら位置は、両側が比較的長い一連
のカーブした複合分類によって囲まれた、比較的小さい
一連の複合ライン分類内になければならない。この例と
しては次のものがある。

【０１６３】

【表３】

【０１６４】本例では、変曲折れ点または変曲折れ候補
点は、一般に値１００の中心距離が生じる位置に生じ
る。

【０１６５】同じようなラインに沿って、図３に関連し
てアウトラインを述べたような折れ候補点を識別するた
めのステップの変形は、所定の点で有利であると考える
ことができる。この代替例を説明し、折れ点の識別を回
避したこの接続部で（先に述べたように）すべての点が
カーブしていないと仮定すると、この代替例のもとで再
カテゴリー化操作を開始できる。再びある種の潜在的再
カテゴリー化はシャープな転回部領域と関連している。
先の例を繰り返すと、かかる領域の一例は、つぎのよう
な一連の点に対する一連の複合分類となる。すなわちラ
イン、ライン、カーブ、カーブ、カーブ、シャープな転
回部、シャープな転回部、シャープな転回部、カーブ、
カーブ、カーブ、ライン、ラインである。しかしながら
この場合、シャープな転回点の分類はカーブ分類に変換
されるので、このシリーズはライン、ライン、カーブ、
カーブ、カーブ、カーブ、カーブ、カーブ、カーブ、カ
ーブ、カーブ、ライン、ラインとなる。

【０１６６】また、特定の例において、シャープな転回
部である３つの連続する点があるが、シャープな転回部
の再カテゴリー化を動きでセットするには、１つのシャ
ープな転回部点で十分である。

【０１６７】次に、ある最小値よりも小さい角度変化を
有するかなりの数の連続点を、ラインに再カテゴリー化
し、また小さい角度変化を有する混合カーブ点をライン
に再カテゴリー化することを実行する。

【０１６８】上記のように変換された前者の各シャープ
な転回部に対し、現在はカーブ点である点を共に考え、
最大の角度変化の絶対値を有する点のうちの点を発見す
る。次にこの点をコーナー折れ点候補点としてセットア
ップする。

【０１６９】次にフィレット状折れ点候補点に対し十分
なカーブ点カウントを有し、（再カテゴリー化された転
回部の点を有する領域を含む）ブラケットライン点を有
するカーブ領域に基づくこれらの選択は、先に述べたと
おりである。更にカーブ領域における点の数が不十分で
あり、かつコーナーの折れ点に対しては十分である場合
の、付加的コーナー折れ点の潜在的選択は、先に述べた
とおりである。

【０１７０】このことは他の方法と対照的に、コーナー
の折れ点と共に、ある種の潜在的なフィレット状折れ候
補点をウォッシュアウトする傾向はない。しかしながら
この方法は一般に最終折れ点を決定するのに、先に述べ
たように取り除かれるより多数の折れ候補点を発生し得
る。

【０１７１】ユーザーが先に述べた相互対話、特にユー
ザーが制御するパスを表示するのに使用する便利なデバ
イスとして、マウス３２を図示し、説明したが、他の従
来の種々の別の装置も容易に利用できる。当然ながらこ
れら装置のうちの１つとして、デジタイザタブレット装
置の一部であるパックがある。

【０１７２】上記に含まれる多くの細部およびこれらの
実施方法は、アメリカコーポレーションのデソルトシス
テムのうちのＣＡＤシステムに組み込むのに特に適して
おり、このシステムは、特にモデル名ＲＳ６０００でＩ
ＢＭ社により、ユニックスワークステーション用に商標
「PROFESSIONAL CADAM」で販売されている、またはモデ
ル番号７００でヒューレットパッカード社により販売さ
れている。更に、その作動はＣ＋＋言語またはＣ言語お
よびフォートラン言語と組み合わせたＣ＋＋言語による
実行に特に適している。

【０１７３】後に明らかとなるように、本明細書に詳細
に説明したような種々の特徴は例示であり、特定の用
途、コンテクストおよび要件に応じて、異なる選択なら
びに変更または変形を受けるものである。従って本発明
の範囲または精神から逸脱することなく、多くの変形お
よび変更が可能である。

【図面の簡単な説明】

【図１】 本発明に係わる方法を実行するのに使用する
コンピュータワークステーションを示す。

【図２】 １つのストロークを複数のセグメントに分解
するための工程を示すフローチャートである。

【図３】 図２のブロック１７０をより詳細に示すフロ
ーチャートである。

【図４】 点、直線、円弧、円または楕円であるセグメ
ントを発生する際のステップを示すフローチャートであ
る。

【図５】 図２〜４により詳細に示された特徴を含み、
更に中間ストロークのセグメント内の幾何学的拘束条件
条件および中間ストロークの外からの他の幾何学的拘束
条件条件を課すことを含む、（ストローク内のインジケ
ータを移動する）ストロークを描くユーザーから生じた
セグメントをディスプレイする際のステップを示すフロ
ーチャートである。

【図６】 作図ストロークにおけるマウスの移動、ディ
スプレイカーソルのその結果生じる移動、および図１の
ワークステーション上での直線セグメントのその結果生
じるディスプレイを、多少略図として示す図である。

【図７】 本発明によって得られる幾何学的セグメント
（または要素）を示す。

【図８】 ベタ塗りコマンドストロークおよび削除コマ
ンドストロークを示す。

【図９】 ベタ塗りストロークおよびこれが適用される
クローズド領域、およびストロークに応答して発生する
領域内のクロスハッチパターンを示す。

【図１０】 ユーザーのフリーハンドの運動に関連した
所定の精密さの基準に欠けたユーザーの手の移動の幾何
学的セグメント（要素）、および本発明によって生じ
た、かかる基準を満たした対応するセグメントを多少略
図として示す図である。

【図１１】 ユーザーのフリーハンドの運動に関連した
所定の精密さの基準に欠けたユーザーの手の移動の幾何
学的セグメント（要素）、および本発明によって生じ
た、かかる基準を満たした対応するセグメントを多少略
図として示す図である。

【図１２】 ユーザーのフリーハンドの運動に関連した
所定の精密さの基準に欠けたユーザーの手の移動の幾何
学的セグメント（要素）、および本発明によって生じ
た、かかる基準を満たした対応するセグメントを多少略
図として示す図である。

【図１３】 ユーザーのフリーハンドの運動に関連した
所定の精密さの基準に欠けたユーザーの手の移動の幾何
学的セグメント（要素）、および本発明によって生じ
た、かかる基準を満たした対応するセグメントを多少略
図として示す図である。

【図１４】 コーナーの折れ点において合流する２本の
直線から成るストロークを右側に多少略図で示し、この
ストロークによって生じるユーザーの手の運動のストロ
ークを左側に多少略図で示す図である。

【図１５】 ２本の直線ラインセグメント、１つの円弧
セグメントおよび２つの折れ点を有するストロークを右
側に多少略図で示し、このストロークによって生じるユ
ーザーの手の運動のストロークを左側に多少略図で示す
図である。

【図１６】 ユーザーによって発生され、平行性および
再限定幾何学的拘束条件に欠けたストロークが、どのよ
うに本発明に従い、かかる拘束条件を含む正方形となる
かを、多少略図で示す。

【図１７】 ２つのストロークでユーザーによって入力
された正方形の同じような状況を、最初の４つの部分が
示し、最後の２つの部分は正方形に接する拘束条件を含
む円形ストロークを意図するものを加えたこと、かつ、
かかる拘束条件を課した結果を示す。

【図１８】 ラインと円との接線拘束条件を課すことを
多少略図で示す。

【図１９】 ラインと点との一致拘束条件を多少略図で
示す。

【図２０】 最初２つのセグメントを有する単一ストロ
ークとして形成された円とラインとの間の接線拘束条件
を多少略図で示す。

【図２１】 テスト点、線形テストパス及び円形テスト
パスと同様な多くのデータ点を含むカーテシアンクオド
トリーの図である。

【図２２】 所定の傾きを有する直線に相当する線形テ
ストパスと同様な多くのラインを含む極クオドトリーの
図である。

【図２３】 様々な幾何学的拘束条件によって関連づけ
られる要素を有する基礎モデルを表す２次元図である。

【符号の説明】

３０ ワークステーション ３２ 標準的マウス ３４ キーボード ３６ ディスプレイ ３８ ディスプレイスクリーン １１２ 単一ストロークの作図パス １１４ ２本の直線を表すパス １１６ 別のパス １１８ 正方形パス １２０ 内接円としたい単一ストロークパス

フロントページの続き (72)発明者 エドワード ティ．コーン アメリカ合衆国、カリフォルニア州 91504−3341、バーバンク、エヌ．ブエナ ビスタ ストリート 1935、ダスソール ト システムズ オブ アメリカ 内

Claims (19)

【特許請求の範囲】
1. 【請求項１】 所定の精密基準に欠けた作図パスを表す
   情報を発生し、次にこの情報をかかる精密基準に欠けて
   いない作図パスを表す情報に変換するためのコンピュー
   タ化された方法であって、 所定の精密基準に欠けたパス内のインジケータの移動位
   置を表すインジケータ情報要素のグループを発生する工
   程と、 前記インジケータ情報要素に応答して位置を表す変換さ
   れた情報要素のグループを発生する工程と、 ニューラルネットを用いて情報要素の前記変換されたグ
   ループに演算を加え、この演算に応答して前記変換され
   たグループを分類する工程と、 前記分類に応答してインジケータ情報要素の前記グルー
   プの特徴を発生する工程と、 前記精密基準に欠けていない変更されたパスの位置を表
   す情報要素の変更されたグループを定める工程とを備え
   た、コンピュータ化された方法。
2. 【請求項２】 情報要素の前記変更されたグループは、
   オープンな円弧を表示する、請求項１記載のコンピュー
   タ化された方法。
3. 【請求項３】 変換された情報要素のグループを発生す
   る前記工程は、更に、インジケータ情報要素の前記グル
   ープを、所定のグリッド内の回転され、スケール化さ
   れ、変換され、マップ化された位置のグループを表す情
   報要素のグループに変換することを含む、請求項１記載
   のコンピュータ化された方法。
4. 【請求項４】 変換された情報要素のグループを発生す
   る前記工程は、更に、クローズドパスを表示する所定グ
   リッド内の位置を表す前記情報方法のグループを、変換
   されたクローズドパスを表示する、前記所定のグリッド
   内の位置を表す情報要素のグループに変換することを含
   む、請求項３記載のコンピュータ化された方法。
5. 【請求項５】 変換された情報要素のグループを発生す
   る前記工程は、更に、一方向にオープンな円弧を表示す
   る、所定グリッド内の位置を表す前記情報要素のグルー
   プを、反対方向にオープンな円弧を表示する、前記所定
   のグリッド内の位置を表示する情報要素のグループに変
   換することを含む、請求項３記載のコンピュータ化され
   た方法。
6. 【請求項６】 前記ニューラルネットは、円、楕円、複
   数の円弧および削除シンボルを表示する出力分類を含
   む、請求項１記載のコンピュータ化された方法。
7. 【請求項７】 示された大きさを決定するための情報を
   含む、コンピュータ支援設計のための、情報要素の前記
   変更されたグループに関連した情報を発生する工程を更
   に含む、請求項１記載のコンピュータ化された方法。
8. 【請求項８】 情報要素の前記変換されたグループを分
   類するため、一致しているかどうか、この変換されたグ
   ループと情報要素の認識されたパターンとをテストする
   工程を更に含む、請求項１記載のコンピュータ化された
   方法。
9. 【請求項９】 前記テスト工程の前記認識されたパター
   ンは、ラインおよび４５度の円弧を表示するパターンを
   含む、請求項８記載のコンピュータ化された方法。
10. 【請求項１０】 所定の精密基準に欠けた作図パスを表
    示する情報を発生し、前記作図パスのセグメントの折れ
    点を表示する折れ点情報を選択するコンピュータ化され
    た方法であって、 所定の精密基準に欠けたパス内のインジケータの移動位
    置を表示するインジケータ情報要素を発生する工程と、 分類基準に応答して情報要素をカテゴリーに分類する工
    程と、 前記分類および情報要素のセグメントのための限界を区
    切るための折れ点選択基準に応答して、折れ点情報要素
    を選択する方法とを備えた、コンピュータ化された方
    法。
11. 【請求項１１】 前記分類工程は、 情報要素の角度変化、曲率および傾き変化を表示する関
    数を計算し、この計算に応答して情報要素をカテゴリー
    化する工程を含む、請求項１０記載のコンピュータ化方
    法。
12. 【請求項１２】 前記分類工程は、 情報要素の複数の幾何学的基準を表示する関数を計算
    し、この計算に応答して情報要素をカテゴリー化する工
    程と、 隣接する情報要素に対する前記カテゴリー化に応答して
    情報要素を再カテゴリー化する工程を含む、請求項１０
    記載のコンピュータ化された方法。
13. 【請求項１３】 前記選択工程は、 前記分類および潜在的折れ点選択基準に応答して、潜在
    的折れ点情報要素を選択する工程と、 ニューラルネットを用いて潜在的折れ点情報要素に隣接
    する情報要素のグループに演算を加え、前記ニューラル
    ネットに応答して潜在的折れ点情報要素を除く工程を含
    む、請求項１０記載のコンピュータ化された方法。
14. 【請求項１４】 情報要素の前記セグメントはカーブし
    たオープンセグメントおよびクローズドセグメントを含
    むパスを表示する位置を表示するためのものである、請
    求項１０記載のコンピュータ化された方法。
15. 【請求項１５】 情報要素の前記セグメントは直線状の
    セグメントおよびカーブしたオープンセグメントを含む
    パスを表示する位置を表示するためのものである、請求
    項１０記載のコンピュータ化された方法。
16. 【請求項１６】 所定の精密基準に欠けた作図パスを表
    示する情報を発生し、かかる精密基準に欠けていない作
    図パスを表示するディスプレイに前記情報を変換するた
    めのコンピュータ化された方法であって、 所定の精密基準に欠けたパス内のインジケータの移動位
    置を表示するインジケータ情報要素を発生する工程と、 情報要素のセグメントの限界を区切るよう、前記情報の
    発生に応答して折れ点情報要素を定める工程と、 前記精密基準に欠けていない変更されたパスのセグメン
    トを表示する情報要素の変更されたグループを定める工
    程と、 前記情報要素の変更されたグループのうちの、幾何学的
    拘束条件を発生し、この幾何学的拘束条件の発生に応答
    して幾何学的に拘束されたセグメントを表示する情報要
    素の拘束されたグループを定める工程と、 前記精密基準に欠けておらず、情報要素の前記拘束され
    たグループを含む、情報要素によって表示されたパスを
    表示するディスプレイを供給する工程とを備えた、コン
    ピュータ化された方法。
17. 【請求項１７】 前記幾何学的拘束条件は一致条件を含
    む、請求項１６記載のコンピュータ化された方法。
18. 【請求項１８】 前記幾何学的拘束条件は一致条件、平
    行条件、接線条件を含む、請求項１６記載のコンピュー
    タ化された方法。
19. 【請求項１９】 更に表示された大きさを決定するため
    の情報を含む、コンピュータ支援設計のための、情報要
    素の前記拘束されたグループに関連した情報を発生する
    工程を含む、請求項１６記載のコンピュータ化された方
    法。