JPH0271384A

JPH0271384A - ３次ベジェ曲線の折線近似装置

Info

Publication number: JPH0271384A
Application number: JP63222438A
Authority: JP
Inventors: Masayuki Okamoto; 雅之岡本; Mitsuru Yamauchi; 山内　満; Toshiya Mima; 美間　俊哉
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1988-09-07
Filing date: 1988-09-07
Publication date: 1990-03-09
Anticipated expiration: 2012-11-17
Also published as: JP2677273B2

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔概　要〕たとえばコンピュータグラフィック表示装置、図形印刷
装置等に用いられる３次ヘジ、曲線の折線近似装置に関
し、処理時間およびデータ量を増大させることなく曲線を折
線で近似させるごとを目的とし、３次ベジェ曲線の始点
、第１の制御点、第２の制御点、および終点を入力する
３次へジを曲線座標入力手段と、前記始点と前記終点と
を結ぶ線分の中点と、前記第１の制御点と前記第２の制
御点とを結ぶ線分の中点と、の誤差を演算する誤差演算
手段と、該誤差か所定値以上か否かを判別するｔ！′（
差判別手段と、該誤差が所定値未満の場合には当該曲線
の始点および終点を結ぶ線分を前記曲線の折線う一一夕
として発生する折線データ発生手段と、前記誤差が所定
４Ｗ以十の場合ｔこは前記３次ヘソエ曲線を分割し、該
分割さＪ′シた各３次−・シェ曲線に処１シ２て前記誤
差演算手段および前記誤差判別１段の動作を繰り返さ一
已る曲線分割手段とを具備するように構成する。

〔産業上の利用分野〕

本発明はたＬえば二Ｉンピ７．−タグラフイック表示装
；〃、図形印刷装置等ムご用いられる３次ヘジェ曲線の
折線近似装置に関する。

〔従来の技術〕

一般的に、；３次ヘジ工曲線は、第２図に示すように、
始点ＱＩ　＋、終点（、ｌ　、　４．２つの制御点Ｑ、
２Ｑ１．の４つの曲線定着座４ｇ１により、曲線が表さ
れる。この３次・＼ジー１−曲線の曲線トの点は、この
４つの曲線定義座標を用いることにより、節Ｉｐに求め
ることができる（山口富十夫著“二１／ビブ、−タデイ
スプレイによる形状処理Ｔ学（２）　　ｐｉ（１〜１５
、日刊Ｔ業、昭和５７）。ずなわち、ＣＬ、（始点）、
Ｑ、２（制御点）、Ｑｌ：ｌ（制御点）　、Ｑ、、（終
点）Ｑ）　４つの曲線定義座標が与えられたとき、以ト
の手順により曲線を比率ｔｓ　：　］−１３で分割・す
る曲線１の点を求めることができる。

（１）　Ｑ、Ｉ　、　Ｑｌ２間を比率ｔｓ＋］−ｔｓで
内分する点をＱ２□とし、Ｑ、□、Ｑ、、間を比率ｔｓ
：ｌｔｓで内分する点をＱ２２とし、Ｑ、１．Ｑ、、間
を比ｔｊＬｓ：Ｉｔｓで内分する点をＱ２．とする。

（２）さらに、Ｑ２．．０２２間を比率Ｌｓ：１４ｓで
内分する点をＱｌｌとし、Ｑ２．、Ｑ２ｙ間を比率ｉｓ
　：　］ｔｓで内分する点をＱ、２とする。

（３）さらにもう−・度、０．　、　、　、０．　：１
２間を比率Ｌ：、：１−１ｓで内分する点をＱ４．とす
る。

このとき、Ｑ４□は、Ｑｚ　、ＣＬ２．Ｑｌ：１．Ｑｘ
６ごより与えられた曲線を比率ｔｓ：ＩＬｓで分割する
曲線にの点となる。

同時に、Ｑｘ、Ｑ＋□、Ｑｌ３　、　Ｑ１４の４゛っの
曲線定義座標により表されたもとの３次ヘジエ曲線は、
Ｑ、ｌｌ　、　Ｑ２１　、　Ｑ：ｌｌ　、　Ｑ４＋の４
つの曲線定義座標により表される３次ヘジェ曲線と、と
Ｑ４１．Ｑ３□Ｑ２．、Ｑ、、の４つの曲線定義座標に
より表される３次ヘン五曲線の２つの曲線に分割される
。

従来、３次へノ五曲線を直線列で近似する場合には、上
述の方法による分割を予め決められた回数だｉ−１繰り
返し行い、求められた曲線上の点を順番に結んだ直線列
としていた。

［発明が解決しようとずろ課題〕分割の回数と求められる曲ｖＡＪ−１の点の数には、指
数関数に比例する関係があり、従って、曲率が大きい曲
線を折線で高精度で表すためには、上記同数を増加させ
る必要があり、この結果、処理時間およびデータψが増
大する一方、曲率が小さい曲線に対して過剰の精度とな
り、逆の場合には、曲率が大きい曲線の近似された曲線
の品質が低下するという課題かある。

従って、本発明の目的は、処理時間およびデータ量を増
大させることなく３次ヘシエ曲線を折線で高精度に近似
させるごとにある。

〔課題を解決するだめの手段〕

」−述の課題を解決するだめの手段４．４第１図にボさ
れる。すなわち、３次ヘジェ曲線座標入力手段は、３次
ヘジエ曲線の始点Ｑｌい第１の制御点Ｑ、２、第２の制
御点Ｑ１９、および終点０，４を入力し、誤差演算手段
は始点Ｑｌｌと終点Ｑ１４とを結ぶ線分Ｑ、、Ｑ１４の
中点Ｐと、第１の制御点Ｑ、２と第２の制御点ＱＩ３と
を結ぶ線分Ｑ１□ＱＩｆｆの中点Ｒと、の誤差を演算し
、誤差判別手段は誤差が所定埴以」二か否かを判別する
。この結果、誤差か所定値未満の場合には、折線データ
発生手段が当該曲線の始点および終点を結ぶ線分Ｑ、、
Ｑ、、を曲線の折線データとして発生する。他方、誤差
が所定値以１−の場合には、曲線分割手段は、３次ヘジ
ェ曲綿を分割し、これら分割された３次ヘジｙ−＋ｆｂ
　’ｒｒ’Ｒにり、ナして誤差演算手段および誤差判別
手段の動作を繰り返さ−υるものである。

Ｃ作　用〕」−述の手段によれは、第３図に不ずように、誤差とし
Ｃは、近イ以された線分Ｑ、、Ｑ、、と、その区間の実
際の曲線Ｘとの最大距離を用いる。このとき、曲線×と
線分Ｑ　＋　＋　（、ｌ　ｌ　４との距離をｉｉｔ：Ｒ
することは困難であるため、３次ヘジエ曲線の性質であ
る凸閉包（発生される曲線Ｘは１４つの曲線定義座標の
内側に存在する）を利用し、ヘジェ曲線の始点ＱＩＩと
終点Ｑ、を結ぶ線分の中点Ｐと、２つの制御点Ｑ１□、
Ｑ１３間を結ぶ線分中点Ｒとの距離を誤差として用いる
。点Ｐと点０間の距離は、３次ヘジ五曲線の凸閉包より
、線分ＱｌｌＱ１４と曲線Ｘとの最大距離よりも長くな
る。点Ｐと点Ｑとの距離（誤差）が大きい場合には、３
次・＼ジェ曲線は分割される。従って、この分割回数は
曲線Ｘの形状変化に合わせて変化する。この結果、曲率
が大きい曲線に対しては分割回数は増加するが、曲率が
小さい曲線に対しては分割回数は減少する。

〔実施例〕

第４図は本発明に係る曲線の折線近似装置が適用される
図形表示装置である。第４図るこおいて、１は図形デー
タ入力装置、２は座標変換装置、；シは曲線発生装置１
４は描画処理装置、５はＣＲＴ６を制御する表示制御装
置である。本発明に係る曲線の折線近似装置は曲線発生
装置リとして用いられる。また、本発明は図形印刷装置
にも適用される。

この場合には、第４図の表示制御装′＃、５およびＣＲ
Ｔ６は印刷制御装置および印刷装置となる。

第５図は本発明に係る曲線の折線近似装置の一実施例を
示すブロック回路図である。第５図において、データ入
力回路５０１は３次ヘシ丁−曲線を表す４つの曲線定義
座標０１１〜Ｑ１４を入力処理する。

曲線分割回路５０２はデータ入力回路５０１からの人力
座標の曲線もしくは誤差判定回路５０４から戻された曲
線データの曲線をｔｓ：］−ｔｓで分Ｉ、す処理をづる
。誤差演算回路５０３はデータ入力回路５０１からの入
力座標もしくは分割された曲線とそれを近イρする線分
との誤差を演算する。誤差判別回路５０４は誤差演算回
路５０３により計算された誤差と、予め設定された誤差
の闇値との比較を行い、誤差か闇値以内である場合には
、データをデータ出力回路５０５に渡し、闇値以内でな
い場合には、データを再び曲線分割回路５０２に戻す。

データ出力回路５０５は、折線近似された曲線のデータ
を出力する処理を行う。

以下、各回路５０２　、５０３について詳述する。

曲線分割回路５０２は、たとえば、３次のヘジエ曲線の
性質から曲線を比率Ｌｓ：１−ｔｓで分割する曲線」−
の点を求める方法（参考文献：ＬｌｌＬＪ富十夫著°“
コンピュータデイスプレィによる形状処理工学（２）　
　”　ＦＩ　Ｆｌｌ　Ｔ’、ｌＡ　ｐＱ〜１５、昭和５
７）ヲ用イテ、曲線を分割するものである。第６図に示
すように、曲線分割回路５０２は、レジスタ６０１〜６
０４、座標分割回路６０５〜６Ｑ、レジスタ６１１〜６
１８　Ｇコより構成されている。すなわち、第２図に示
すように、曲線を表す座標としてＱｌ、〜Ｑ＋４か与え
られたとすると、これらの座標はレジスタに０１〜６０
４に格納される。座４ｆｆＱ＋＋　、Ｑｌａはそのまま
レジスタ６１１．６１８に格納される。座標分割回路（
）０５は座標Ｑ、、、Ｑ、２間を比率Ｌｓ＋Ｉ−Ｌｓで
分割した座標Ｑ２１を発生してレジスタ６１２に格納し
、座標分割回路６０６は座標Ｑｌ２．Ｑ、１間を比率ｔ
ｓ：１−１ｓで分割し７た座標Ｑ２２を発生し、座標分
割回路６０７は座標Ｑ、３４Ｑ１４間を比率ｔｓ　：　
Ｌｔｓで分割した座標Ｑ２１を発生してレジスタ６１７
に格納する。また、座標分割回路６０８は座標Ｑ２．　
、　Ｑ２□間を比率ｔｓ：Ｉ−Ｌｓで分割した座標Ｑ、
１を発生してレジスタ６１３に格納し、座標分割回路６
０９ば座標Ｑ２□、Ｃｌ２３間を比率Ｌｓ：１４ｓで分
割した座標Ｑ、２を発１１ニジてレジスタ６１６ζこ格
納する。さらに、座標分割１１１Ｊ　ｉ踏６Ｑは座標Ｑ
３＋、（１１□を比率ｔｓ　：　ｌ−１ｓで分割した座
標Ｑ、１を発生してレジスタ６１４　．６１５に格納す
る。

このとき、第２図に示すように座標の４．ば、ＱＱ＋ｚ
＋　Ｑ１３＋　Ｑｌａにより与えられた曲線比率ｔｓ・
１−ｔｓで分割する曲線上の座標となり、また同時に、
この座標において曲線は２つの曲線（にｌ１１．Ｑ２Ｑ
、、、Ｑ、、とＱ、、、Ｑ３□、　Ｑ２：１　、０．１
−）に分割される。

なお、第６　ＩＮ’ｌ　４こおけるレジスタ６０１〜６
０４の入力座標Ｑ、〜Ｑ、のデータ入力回路５０１　も
しくは誤差判別回路５０４・＼の切替は図示し２ないス
イッチによって行われる。

第６図の各座標分割回路６０５〜６Ｑは、たとえば、第
７図Ｇこ小ずように、乗葬器７０１　　、７０２　、お
よびＩＪＩＩ′ｌＪ、器７０３により構成される。

第３図の線分Ｑ１２Ｑ１１の中点Ｒと線分Ｑ、、Ｑ、。

の中点Ｐとの誤差（距離）を演算する場合、２中Ｉｔ人
の座標を（ＸＩ　　、Ｙｌ）、（Ｘ２　　、Ｙｚ）とす
ると、２点間の１７（ｉ離の計算は、ｒ（（１）に示す
ように表される。

距離−１（Ｘ、−Ｘ、）２４−　いｒ、　　　Ｙ２）Ｚ
　Ｉ　Ｉ／２・・（１）式（１）では、乗除算を必要とするため、高速な処理を
要求される場合には、不利である。これを加減算のみで
処理を行うため乙こ、式（２）に示すよう６ご、２点間
の座標差を用いる。

距離−Ｉ　ＸＩ　−Ｘ２　１　ｔ　ｌ　Ｙｌ　　’−Ｙ
ｚ　　：・・・（２）このようにすることで、演算を単
純にかつ高速に実行することができ、また、式（２）に
より求められた距離は、式（１）により求められた距に
１より必ず長くなる。このため、求められた距離を誤差
と比較し判断する場合に、近似された曲線の精度が低ト
ーすることがないため、近（１１Ｊされた曲線がなめら
かである。

弐（２）に示す誤差を演算するだめの第５図の誤差演算
回路５０３の詳細は第８図に示３トれる。第８図におい
て、８０１，８０２，８０３，８０４，８０８　＋：＋
レジスタ、８０５　、　８０６は入力された２つの座標
の中点を求める中点演算回路、８０７は人力された２り
の中点坤標Ｒ、Ｐから式（２）に示したＡＩ算式乙、二
より求められる座標誤差を演算する座標差公演′Ｑ回路
である。中点演算回路８０５　　、８０４ｉは、たとえ
ば、第９図に示すように、加算器９０１および除’４２
器９０２により構成される。

最初に、データ入力回路４０１　よの出力されたよ１′
４差演算に必要なＱｚ　、　Ｑ、＋２　、　Ｑｌｌ、　
Ｑ１４が、それぞれ、レジスタ８０１〜８０４に格納さ
れる。ごごで、Ｑ、１は始点、Ｑ１４は終点、Ｑ、、、
Ｑ、ｌは制御点で（Ｉ２）ある。この結果、中点演算回路８０５には、Ｑ、□と（
１，３が入力され、中点演算回路８０５の出力として制
御点Ｑ、２．Ｑ、３を結ぶ線分の中点Ｒが求められる。

また、中点演算回路８０６には、ＱｌｌとＱ１４が人力
され、中点演算回路８０６の出力として、始点Ｑｌ＋と
終点Ｑ１４を結ぶ線分の中点Ｐが求められる。

さらに、座標差分演算回路８０７には、中点演算回路８
０５により求められた中点Ｒと中点演算ｒｇＪ路８０６
により求められた中点Ｐとが入力され、座標差分演算回
路８０７の出力として、この２つの中点の差分が求めら
れる。この演算結果が誤差ｅとして、レジスタ８０８４
．：格納される。

なお、第８図におりるレジスタ８０１〜８０４の人力座
標Ｑ１．〜Ｑ１４のデータ入力回路５０１　もしくは曲
線分割回路５０２への切替は図示しないスイッチによっ
て行われる。

［述の誤差ｅを、第５図の誤差判定回路５０４が閾値と
比較して、誤差が閾値より小さい場合には、線分Ｑ、、
Ｑ、、かデータ出力部８０５より出力される。

また、＋ｉ！′ｉ差か闇値より大きい場合には、曲線Ｑ
ｌｌＱ２１　＋　Ｑｔｌ　＋　Ｑ４１が再び曲線分割回
路５０２に入力され、分割される。このとき、もう１つ
の曲線であるＱ４１．Ｑ３□、　Ｑ２３．　Ｑ、、は、
誤差判定回路５０４内部に一時的に保持しておき、曲線
Ｑ、。

Ｑ２１　、　Ｑ３１．　Ｑａ＋（ＩＪ分割’ｌ＞（Ｐニ
アした時点で、曲線分割回路５０２に入力され、処理が
行われる。

この一連の処理により、３次のヘジェ曲線は折線近イ以
され出力される。

上述の実施例は汎用のマイクロコンピュータを用いてそ
のプログラムとして実現することも可能である。たとえ
ば、第Ｑ図に示すように、ステップＱ０Ｈこて３次ヘジ
ェ曲線用データ（コ８．〜Ｑ１イを入力し、ステップＱ
０２にて−に述弐（２）にもとづき距離（誤差）ｅを演
算し、ステップＱ０３にて距１％ｌｅが闇値以下か否か
を判別する。この結果、距ｆｄ４ｅ≦闇値であればステ
ップＱ０６にて折線データとして線分Ｑ、、Ｑ、、を出
力し、距離（・〉閾値であればステップＱ０４　、Ｑ０
５に進む。

ステップＱ０４では、３次ヘジェ曲線データをイＩ；成
することにより曲線の分割を行い、ステ、ブＱ０５にて
８個のＱ１□、　Ｑ２．　、・・・、Ｑ１４をメモリに
格納する。ぞして、ステップ１ｏ０２ｃこ戻る。

ずなわら、曲線弁、ｌ；＋１を繰り返−４゜また、ステ
ップＱＦ＋７　、　ＨＩＯ２にて曲線のず−て折線近似
が終了するま−Ｃスス−−ノブＱ０２〜Ｑ０６が繰り返
される。

（発明の効果）以り説明したように本発明によれは、曲線の曲率に応１
ノで分割回数すなわち近似折線の数か変化−するので、
処理時間およびデータ量を増大さ一ロるごとなく、曲線
を効・ｒよく、なめらかに折線近似することかできる。

【図面の簡単な説明】

第１図は本発明の基本構成を２ｉず図、第２図は；（次
ヘジェ曲線の分割を説明する図、第；３図は本発明の詳
細な説明する図、第４図は本発明に係る曲線の折線近似
装置が適用される図形表示装置を示ず）ｌ：Ｉ−、り回
路図、第５図は本発明に係る曲線の折線近似装置の一実
施例を２１辷４゛ブ１１・り回路図、第６図は第５図の
曲線分割回路を示すプロ、り図、第７図は第６図の座標分割回路の一例を示す回路図、第８図は第５図の誤差演算回路を示１回路図、第９図は
第８図の中心演算回路を示す回路図、第Ｑ図は他の実施
例を示すフローチャートである。５０１・・・データ入力回路、５０２・・・曲線分割回
路、５０３・・・誤差演算回路、　５０４・・誤差判別
回路、５０５・・・データ出力回路。

Claims

【特許請求の範囲】１、３次ベジェ曲線の始点（Ｑ＿１＿１）、第１の制御
点（Ｑ＿１＿２）、第２の制御点（Ｑ＿１＿３）、およ
び終点（Ｑ＿１＿４）を入力する３次ベジェ曲線座標入
力手段と、前記始点（Ｑ＿１＿１）と前記終点（Ｑ＿１
＿４）とを結ぶ線分（Ｑ＿１＿１Ｑ＿１＿４）の中点（
Ｐ）と、前記第１の制御点（Ｑ＿１＿２）と前記第２の
制御点（Ｑ＿１＿３）とを結ぶ線分（Ｑ＿１＿２Ｑ＿１
＿３）の中点（Ｒ）と、の誤差を演算する誤差演算手段
と、該誤差が所定値以上か否かを判別する誤差判別手段と、該誤差が所定値未満の場合には当該曲線の始点および終
点を結ぶ線分（Ｑ＿１＿１Ｑ＿１＿４）を前記曲線の折
線データとして発生する折線データ発生手段と、前記誤
差が所定値以上の場合には前記３次ベジェ曲線を分割し
、該分割された各３次ベジェ曲線に対して前記誤差演算
手段および前記誤差判別手段の動作を繰り返させる曲線
分割手段とを具備する３次ベジェ曲線の折線近似装置。２、前記誤差演算手段は、前記誤差として、前記２つの
中点（Ｐ、Ｒ）の距離を演算する請求項１に記載の３次
ベジェ曲線の折線近似装置。３、前記誤差演算手段は、前記２つの中点（Ｐ、Ｒ）の
距離として座標差を演算する請求項２に記載の３次ベジ
ェ曲線の折線近似装置。