JPH0785301A - 情報処理装置 - Google Patents

Abstract

(57)【要約】 【目的】 線上判定処理の対象を少なくすることで、図
形の特定を高速で行うことが可能な情報処理装置を提供
する。 【構成】 入力手段１から指定点が入力されると、三角
形領域算出手段２がその指定点と４つの制御点からなる
２つの三角形領域を算出し、この三角形領域に指定点が
含まれるか否かを第１判断手段３で判断する。指定点が
三角形領域に含まれる場合、第２判断手段４が指定点と
セグメントと所定距離内に存在するか否かを判断し、存
在すれば、ベジェ曲線特定手段５がそのセグメントを含
むベジェ曲線を特定する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、情報処理装置に係
り、詳細には、ベジェ曲線の描画機能を備えた情報処理
装置に関する。

【０００２】

【従来の技術】パーソナルコンピュータやオフィスコン
ピュータ、ワークテーション、電子出版システム、ワー
ドプロセッサその他各種の情報処理装置が、オフィス、
工場、設計事務所、家庭等に普及し、広く使用されてい
る。このような情報処理装置において、道路地図や建築
図面等の各種図面を作成する場合、任意形状の曲線を描
画することが必要となり、そのための方法として、ベジ
ェ関数によるベジェ曲線を使用する場合がある。ベジェ
曲線は、４つの制御点により描画するもので、始点、終
点上を通過し、両者間に指定される２つのコントロール
ポイントの内側を通過する曲線である。

【０００３】一方、このような各種の図形処理機能を備
えた情報処理装置では、既に作成した所定の図形を特定
する処理が必要になる。例えば、既に作成した図形の削
除、移動、複写、変形等の各種処理を行う場合に、以下
に説明する図形の特定処理が行われる。まず、操作者が
ディスプレイに表示された複数のベジェ曲線のうち特定
したいベジェ曲線上にカーソルを移動して指定点を入力
する。そして、情報処理装置がこの指定点上のベジェ曲
線を認識する。認識は、ベジェ曲線を含む所定領域内に
指定点が有るか否かを判断する領域内判定を行い、領域
内に含む場合には、更にベジェ曲線上に指定点があるか
否かを判断する線上判定を行う。ここで、線上判定は、
セグメント（入力されたアンカーポイント間の最小単位
のベジェ曲線）の分割を繰り返し、各アンカーポイント
を結ぶ直線で近似し、各直線に対してその直線を含む矩
形領域内に指定点が含まれるか否かを判断する。指定点
が含まれる場合、指定点と直線との距離を計算し、許容
範囲内であれば、そのベジェ曲線上に指定点があるもの
と判定している。

【０００４】

【発明が解決しようとする課題】ところで、ベジェ曲線
の特定処理における線上判定は、時間を要する。これ
は、ベジェ曲線の分割によるセグメントの直線近似に時
間を要すると共に、近似した各直線を含む矩形領域内外
の判定と距離の計算にも時間を必要とし、これらの各処
理をセグメントに対して分割した直線の数だけ処理を行
う必要があるためである。この線上判定処理は、領域内
判定において指定点が領域内にあると判定される全ての
ベジェ曲線に対して行われる。ところが、従来の領域内
判定処理は、指定点が存在するか否かの判定をベジェ曲
線を含む矩形領域に対して行っているため、線上判定処
理の対象が増加することが多かった。

【０００５】図１４は、従来の線上判定の対象となるベ
ジェ曲線を決定する領域判定処理を説明するためのもの
である。この図１４は、多くの図形を重ねて各図形の内
部を少しづつ色を変えながら塗りつぶすことにより立体
感を表現するような場合の例である。このような図にお
いて、例えば、指定点８９（図面上、×で示す。）が図
示の位置に指定されたとする。この場合、図１４（ｂ）
に示すように、各ベジェ曲線９０ａ〜９４ａを含む矩形
領域９０ｂ〜９４ｂに対して領域内判定を行うと、全て
の矩形領域に対して指定点８９が含まれることとなる。
このため、全てのベジェ曲線９０ａ〜９４ａに対して、
長時間を要する線上判定処理を行う必要があり、全体と
して更に処理時間が掛かっていた。このように、従来の
図形特定処理における、領域内判定は、矩形領域によっ
て行われていたために、領域内と判定される場合が増
え、その結果時間の掛かる線上判定処理の対象も増加
し、結果として高速処理を行うことができなかった。

【０００６】そこで、本発明は、線上判定処理の対象を
少なくすることで、図形の特定を高速で行うことが可能
な情報処理装置を提供することを目的とする。

【０００７】

【課題を解決するための手段】請求項１記載の発明で
は、図１に原理的に示すように、曲線が通過する２つの
アンカーポイントと、通過しない２つのコントールポイ
ントの４つの制御点からベジェ曲線を描画する情報処理
装置において、描画されたベジェ曲線を特定するための
指定点を入力する入力手段１と、ベジェ曲線のセグメン
ト上の所定点を算出し、この所定点、始点、一方のコン
トールポイントからなる三角形領域、および、前記所定
点、終点、他方のコントールポイントからなる三角形領
域を算出する三角形領域算出手段２と、この三角形領域
算出手段２で算出された２つの三角形領域に前記入力手
段１から入力された指定点が含まれるか否かを判断する
第１判断手段３と、この第１判断手段３で２つの三角形
領域に指定点が含まれると判断されたセグメントに対し
て、所定距離内に前記指定点が存在するか否かを判断す
る第２判断手段４と、この第２判断手段４で指定点が所
定距離内に存在すると判断されたセグメントを含むベジ
ェ曲線を特定するベジェ曲線特定手段５とを、情報処理
装置に具備させて前記目的を達成する。

【０００８】請求項２記載の発明では、図２に原理的に
示すように、請求項１記載の情報処理装置において、セ
グメントの４つの制御点を含む矩形領域を算出する矩形
領域算出手段６と、この矩形領域算出手段６で算出され
た矩形領域に前記入力手段１から入力された指定点が含
まれるか否かを判断する第３判断手段７とを備え、前記
三角形領域算出手段２は、前記矩形領域に指定点が含ま
れると前記第３判断手段７で判断されたセグメントに対
して三角形領域を算出する。

【０００９】

【作用】請求項１記載の情報処理装置では、入力手段１
から指定点が入力されると、三角形領域算出手段２がそ
の指定点と４つの制御点からなる２つの三角形領域を算
出し、この三角形領域に指定点が含まれるか否かを第１
判断手段３で判断する。指定点が三角形領域に含まれる
場合、第２判断手段４が指定点とセグメントと所定距離
内に存在するか否かを判断し、存在すれば、ベジェ曲線
特定手段５がそのセグメントを含むベジェ曲線を特定す
る。

【００１０】請求項２記載の情報処理装置では、セグメ
ントの４つの制御点を含む矩形領域を矩形領域算出手段
６で算出し、その矩形領域に入力手段１から入力された
指定点が含まれると第３判断手段７で判断された場合
に、前記三角形領域算出手段２が三角形領域を算出す
る。

【００１１】

【実施例】以下、本発明の情報処理装置における一実施
例を図３ないし図１３を参照して詳細に説明する。図３
は第１〜第３の実施例における情報処理装置のハード構
成を表したものである。この図１に示すように、情報処
理装置は、本実施例によるベジェ曲線描画処理等の各種
処理動作を行うＣＰＵ（中央処理装置）１１を備えてい
る。このＣＰＵ１１には、データバス等のバスライン１
３を介して、ＲＯＭ１５、ＲＡＭ１７、画像メモリ１
９、入力装置２１、スキャナ２３、プリンタ２５、ディ
スプレイ２７、通信制御部２９の各部が接続されてい
る。

【００１２】ＲＯＭ１５は、装置全体をＣＰＵ１１で制
御するための各種プログラムや、各種データが格納され
たリード・オンリ・メモリである。このＲＯＭ１３に
は、本実施例によるベジェ曲線の特定処理プログラム等
の図形処理プログラムや、ベジェ関数、その他各種デー
タ等が格納されている。ＲＡＭ１７は、ＣＰＵ１１で行
われる各種処理動作において使用されるワーキングメモ
リとして使用され、また各種データの保存に使用される
ランダム・アクセス・メモリである。このＲＡＭ１７に
は、図形処理により描画される、直線や各種図形に対す
る座標値や図形の種類を特定する図形描画データが格納
される。また、本実施例によるベジェ曲線描画処理で自
動設定されたコントールポイントと、入力されたアンカ
ーポイントもベジェ曲線描画データとしてＲＡＭ１７に
格納されるようになっている。なお、本実施例による各
種動作を行うためのプログラムやデータは、フロッピー
ディスク等の他の記憶媒体からＲＡＭ１７にインストー
ルし、ＲＡＭ１７からプログラム等を読みだして動作す
るようにしてもよい。

【００１３】画像メモリ１９は、画像データを記憶する
ものであり、ＲＡＭ１７に格納されている図形描画デー
タで描画される図形が格納され、この画像メモリ１９に
格納されるデータが、プリンタ２５やディスプレイ２７
に出力されるようになっている。入力装置２１は、ポイ
ンティングデバイスとしてのマウス２１１やキーボード
２１３等の各種入力装置を備えている。また、入力装置
２１には、図示しないタブレットやデジタイザ等の各種
入力装置も接続が可能になっている。スキャナ２３は、
画像データを読み込む入力装置で、読み込まれた画像デ
ータは、画像メモリ１９に格納されるようになってい
る。プリンタ２５およびディスプレイ２７は、図形描画
データに従って画像メモリ１９に展開された図形データ
を出力する装置である。プリンタ２５としては、ドット
プリンタ、レーザプリンタ、ＸＹプロッタ等の各種装置
が使用される。また、ディスプレイ２７としては、ＣＲ
Ｔディスプレイや、液晶ディスプレイ等の各種ディスプ
レイが使用される。

【００１４】通信制御部２９は、ＬＡＮ（ローカル・エ
リア・ネットワーク）、ファクシミリ通信網、ＩＳＤＮ
（サービス総合ディジタル網）等の各種通信網を介し
て、パーソナルコンピュータやオフィスコンピュータ、
ワークテーション、電子出版システム、ワードプロセッ
サその他各種の情報処理装置や、異機種装置と接続され
ている。この通信制御部２９を介して他の情報処理装置
間において、図形描画データ等の各種データの通信が行
われるようになっている。

【００１５】次に、このように構成された実施例の動作
について説明する。 〔ベジェ曲線描画処理の原理〕図４はベジェ曲線による
曲線の描画状態を表したものである。この図４に示すよ
うに、４つの制御点を構成するアンカーポイントＰ０、
Ｐ３、コントールポイントＰ１、Ｐ２のうち、始点Ｐ
０、終点Ｐ３を通り、２つのコントールポイントＰ１、
Ｐ２の方向と距離によって決定されるベジェ曲線Ｌ０が
描画されることとなる。このベジェ曲線Ｌ０は、次の３
次ベジェ関数Ｂ（ｔ）によって演算される。 Ｂ（ｔ）＝（１−ｔ）³ ・Ｐ０ ＋３（１−ｔ）² ・ｔ・Ｐ１ ＋３（１−ｔ）・ｔ² ・Ｐ２＋ｔ³ ・Ｐ３ ここで、０≦ｔ≦１である。

【００１６】次にベジェ曲線の特定処理動作について説
明する。 〔動作の概要〕本実施例によるベジェ曲線の特定処理
は、操作者によってマウス２１１から指定点８９が入力
されると、その指定点８９上のベジェ曲線を特定する。
本実施例では、この入力された指定点８９の領域内判定
を、ベジェ曲線を描画するアンカーポイントＰ０、Ｐ
３、コントールポイントＰ１、Ｐ２および、そのベジェ
曲線のｔ＝０．５の点Ｐ４からなる、２つの三角形領域
に対して領域内判定を行う。

【００１７】図５から図１２は、ベジェ曲線の特定処理
動作を説明するためのものである。図５に示すように、
３本の曲線Ｌ１、Ｌ２、Ｌ３が既に描画され、ディスプ
レイ２７に表示されているものとする。そして、これら
の各曲線のうち、操作者が曲線Ｌ２を特定すべくマウス
２１１等の操作によって指定点８９を入力した場合の、
情報処理装置による曲線Ｌ２の特定処理動作について説
明する。ＣＰＵ１１は、指定点８９が入力されたか否か
を監視しており、図１２に示すように、指定点８９が入
力されると（ステップ１；Ｙ）、パラメータｎ、ｍをそ
れぞれ１に設定する（ステップ２）。そして、図６に示
すように、ディスプレイ２７に表示されている各曲線Ｌ
１、Ｌ２、Ｌ３を含む最小の矩形領域Ｑ１、Ｑ２、Ｑ３
を計算し、ＲＡＭ１７に格納しておく（ステップ３）。
なお、これら各矩形領域は、曲線の描画時に予め計算し
ておき、その図形を示すデータと共に矩形領域を示すデ
ータをＲＡＭ１７に格納しておくようにしてもよい。こ
の場合、ＣＰＵ１１は、ＲＡＭ１７から、各曲線を含む
最小の矩形領域を計算しておく。

【００１８】そして、ＣＰＵ１１は、ＲＡＭ１７に格納
した矩形領域Ｑｎを読み出し、その矩形領域Ｑｎ内に指
定点８９があるか否かを順次判断する（ステップ４）。
矩形領域Ｑｎに指定点８９が含まれる場合（ステップ
４；Ｙ）、図７に示すように、そのベジェ曲線Ｌｎのセ
グメントＬｎｍを構成する４つの制御点、すなわち、２
つのアンカーポイント（始点、終点）と２つのコントー
ルポイントを含む最小の矩形領域Ｒｎｍを算出する（ス
テップ５）。ＣＰＵ１１は、算出した矩形領域Ｒｎｍに
指定点８９が含まれるか否かを判断する（ステップ
６）。指定点８９が含まれる場合（ステップ６；Ｙ）、
そのベジェ曲線Ｌｎｍをｔ＝０．５で分割する点ｔｎｍ
を計算する（ステップ７）。

【００１９】図８はベジェ曲線Ｌ０をｔ＝０．５で分割
する点ｔｎｍを表したものである。例えば、図８に示す
４つの制御点Ｐ０、Ｐ１、Ｐ２、Ｐ３で定義される３次
ベジェ曲線Ｌ０は形状を変えることなく２つの３次ベジ
ェ曲線に分割することができる。すなわち、ベジェ曲線
Ｌ０は、４点Ｐ０、Ｐ４、Ｐ７、Ｐ９で定義される３次
ベジェ曲線Ｌ１および４点Ｐ９、Ｐ８、Ｐ６、Ｐ３で定
義される３次ベジェ曲線Ｌ２に分割できる。ここで点ｔ
ｎｍは、制御点Ｐ９が該当する。ここで、 Ｐ４＝（Ｐ０＋Ｐ１）／２ Ｐ５＝（Ｐ１＋Ｐ２）／２ Ｐ６＝（Ｐ２＋Ｐ３）／２ Ｐ７＝（Ｐ４＋Ｐ５）／２＝（Ｐ０＋２Ｐ１＋Ｐ２）／
４ Ｐ８＝（Ｐ５＋Ｐ６）／２＝（Ｐ１＋２Ｐ２＋Ｐ３）／
４ Ｐ９＝（Ｐ７＋Ｐ８）／２＝〔Ｐ０＋３（Ｐ１＋Ｐ２）
＋Ｐ３〕／４ である。このように３次ベジェ曲線は、分割を繰り返し
再帰的に適用することで、際限なく細分することができ
るという性質をもっている。

【００２０】ＣＰＵ１１は、点ｔｎｍを算出すると、図
９に示すように、２つの三角形領域Ｐ０、Ｐ１、ｔｎｍ
と、ｔｎｍ、Ｐ２、Ｐ３の２つの三角形領域Ｓｎｍを算
出し、その三角形領域Ｓｎｍ内に指定点８９があるか否
かを判断する（ステップ８）。指定点８９が三角形領域
Ｓｎｍ内にある場合（ステップ８；Ｙ）、そのセグメン
トＬｎｍ（図９では、セグメントＬ２２）について、従
来と同様に、線上判定処理を行う（ステップ９）。な
お、本実施例における線上判定処理では、セグメントＬ
ｎｍを２５６分割したアンカーポイントを直線で結ぶこ
とにより近似する。ＣＰＵ１１は、線上判定処理によ
り、近似した直線と指定点との距離が所定の許容値内に
有るか否かを判断し、許容値内であれば（ステップ１
０）、そのセグメントＬｎｍを含む曲線Ｌｎを、特定す
ると共に、ディスプレイ２７に所定の表示をして（ステ
ップ１１）、特定処理を終了する。

【００２１】ステップ６、ステップ８、および、ステッ
プ１０における判断がＮの場合、ＣＰＵ１１は、ｍが最
終値か否かを判断する（ステップ１２）。ｍが最終値で
ない場合（ステップ１２；Ｎ）、ｍに１を加えて（ステ
ップ１３）、ステップ５以降の処理を次のセグメントＬ
ｎｍについて行う。ここで、ステップ６の判断がＮの場
合は、矩形領域Ｒｎｍに指定点８９が含まれない場合で
あり、例えば、図１０に示す矩形領域Ｒ１１や矩形領域
Ｒ１３が該当する。また、ステップ８の判断がＮの場合
は、矩形領域Ｒｎｍに指定点８９が含まれるが、三角形
領域Ｓｎｍ内に指定点８９が含まれない場合であり、例
えば、図１０に示す矩形領域Ｒ１２に対する三角形領域
Ｓ１２（図１１参照）が該当する。

【００２２】そして、ＣＰＵ１１は、ステップ１２およ
びステップ４の判断において、ｍが最終値である場合
（ステップ１２；Ｎ）、および、矩形領域Ｑｎ内に指定
点８９がない場合（ステップ４；Ｎ）、ｎが最終値か否
かを判断する（ステップ１４）。ｎが最終値でない場合
（ステップ１４；Ｎ）、ｎに１を加えて（ステップ１
５）、ステップ４以降の処理を、次の曲線Ｌｎの矩形領
域Ｑｎについて行う。ｎが最終値である場合、指定点８
９で指定された位置に該当する曲線が存在しない旨をデ
ィスプレイ２７に表示して（ステップ１６）、特定処理
を終了する。

【００２３】図１３は、本実施例の線上判定処理（ステ
ップ９）の対象となるセグメントＬｎｍを説明するため
のものである。この図１３は、図１４（ｂ）に対応して
示されている。この図１３に示すように、本実施例で
は、三角形領域Ｓｎｍ内に指定点８９が含まれるか否か
を判断している（ステップ８）ため、線上判定処理の対
象となるセグメントＬｎｍとしては、９０ａのみであ
る。このように、従来の特定処理では、図１４（ｂ）に
示すように、全てのベジェ曲線９０ａ〜９４ａに対し
て、長時間を要する線上判定処理を行う必要があるのに
対して、本実施例では、線上判定処理の対象となるセグ
メントが少ないため、図形を高速で特定することができ
る。

【００２４】

【発明の効果】以上説明したように、本発明の情報処理
装置によれば、線上判定処理の対象が少なくなるので、
図形の特定を高速で行うことができる。

【図面の簡単な説明】

【図１】請求項１の発明における情報処理装置の原理を
示す原理図である。

【図２】請求項２の発明における情報処理装置の原理を
示す原理図である。

【図３】本発明の情報処理装置における一実施例のハー
ド構成を表したものである。

【図４】ベジェ曲線による曲線の描画状態の説明図であ
る。

【図５】ベジェ曲線の特定処理動作の対象となるベジェ
曲線を例示した説明図である。

【図６】ベジェ曲線の特定処理動作における、各曲線を
含む最小の矩形領域Ｑｎの説明図である。

【図７】ベジェ曲線特定処理動作における、セグメント
の４つの制御点を含む最小の矩形領域Ｒｎｍの説明図で
ある。

【図８】ベジェ曲線特定処理動作における、ベジェ曲線
Ｌ０をｔ＝０．５で分割する点ｔｎｍの説明図である。

【図９】ベジェ曲線特定処理動作における、２つの三角
形領域の説明図である。

【図１０】ベジェ曲線特定処理動作における、矩形領域
Ｒｎｍに指定点を含む場合と含まない場合の説明図であ
る。

【図１１】ベジェ曲線特定処理動作における、三角形領
域Ｓｎｍ内に指定点が含まれない場合の説明図である。

【図１２】ベジェ曲線特定処理動作を示すフローチャー
トである。

【図１３】実施例における線上判定処理の対象となるセ
グメントＬｎｍの説明図である。

【図１４】従来の線上判定の対象となるベジェ曲線を決
定する領域判定処理の説明図である。

【符号の説明】

１ 入力手段 ２ 三角形領域算出手段 ３ 第１判断手段 ４ 第２判断手段 ５ ベジェ曲線特定手段 ６ 矩形領域算出手段 ７ 第３判断手段 １１ ＣＰＵ １３ バスライン １５ ＲＯＭ １７ ＲＡＭ １９ 画像メモリ ２１ 入力装置 ２１１ マウス ２１３ キーボード ２３ スキャナ ２５ プリンタ ２７ ディスプレイ ２９ 通信制御部

Claims (2)

【特許請求の範囲】
1. 【請求項１】 曲線が通過する２つのアンカーポイント
   と、通過しない２つのコントールポイントの４つの制御
   点からベジェ曲線を描画する情報処理装置において、 描画されたベジェ曲線を特定するための指定点を入力す
   る入力手段と、 ベジェ曲線のセグメント上の所定点を算出し、この所定
   点、始点、一方のコントールポイントからなる三角形領
   域、および、前記所定点、終点、他方のコントールポイ
   ントからなる三角形領域を算出する三角形領域算出手段
   と、 この三角形領域算出手段で算出された２つの三角形領域
   に前記入力手段から入力された指定点が含まれるか否か
   を判断する第１判断手段と、 この第１判断手段で２つの三角形領域に指定点が含まれ
   ると判断されたセグメントに対して、所定距離内に前記
   指定点が存在するか否かを判断する第２判断手段と、 この第２判断手段で指定点が所定距離内に存在すると判
   断されたセグメントを含むベジェ曲線を特定するベジェ
   曲線特定手段とを具備することを特徴とする情報処理装
   置。
2. 【請求項２】 セグメントの４つの制御点を含む矩形領
   域を算出する矩形領域算出手段と、 この矩形領域算出手段で算出された矩形領域に前記入力
   手段から入力された指定点が含まれるか否かを判断する
   第３判断手段とを備え、 前記三角形領域算出手段は、前記第３判断手段で、前記
   矩形領域に指定点が含まれると判断されたセグメントに
   対して三角形領域を算出することを特徴とする請求項１
   記載の情報処理装置。