JPH0810467B2 - ストロークに相当する輪郭線を迅速に生成する曲線近似方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】〔発明の背景〕 本発明は、原軌道の両側に等しい距離で離れている２つ
の線を生成するためのアルゴリズムであり、更に詳細に
は、そのような平行線を生成するために使用し得る原軌
道のセグメントを決定する第１のステップと、それらを
生成する第２のステップとを含む。

【０００２】ページ記述言語（ＰＤＬ）の一つであるイ
ンタープレス（Ｉｎｔｅｒｐｒｅｓｓ）の用語では、
「マスク・ストローク (mask stroke)」は原軌道に対し
て平行で等距離にある２つの線を与えることによりオー
プン軌道に幅を与え、その結果、以下に「パラゾイド
(parazoid) 」、すなわち２つの平行側面がカーブして
いるトラペゾイド (trapezoid)として参照され、かつ領
域を埋めるものとして定義されている。原軌道のセグメ
ントは３次曲線スプライン、放物線、円錐曲線、円弧お
よび直線であり得る。

【０００３】従来のアプローチは、軌道を線セグメント
に分解し、それから各線セグメントに相当するトラペゾ
イドの座標を計算するか、オフセット放物線を生成する
ために放物線に沿って楕円ペン(eliptical pen) をトレ
ースするかであった。それからこのパラゾイドは、マス
クされたストローク(masked stroke) を生成するために
充満させられ得る。

【０００４】〔発明の要約〕 本方法は、パラゾイドがマスクされたストロークを適当
に近似するかどうかを決定する第１のステップを有す
る。もしそうでなければ、アルゴリズムは、各セグメン
トが試験を満足するまで回帰的に軌道を細分割する。第
２のステップは、各セグメントに相当するパラゾイドを
直接的に計算するためのアルゴリズムである。

【０００５】〔図面の簡単な説明〕 図１および図２は第１章の解析例に使用した曲線であ
る。図３は３次曲線スプラインを理解する際の補助であ
る。図４は円錐曲線を理解する際の補助である。図５か
ら図９までは３次曲線スプラインを放物線セグメントで
近似するアルゴリズムのフローチャートである。図１０
は円弧の近似を示す。図１１は放物線軌道を示す。図１
２は任意の放物線を正規化放物線に変換する際に関係す
るステップを示す。図１３は放物線の一例である。図１
４は最大ねじれを夾角の関数として示す。図１５は第
５．４章で規定した放物線である。図１６から図２１は
ねじれと夾角との間の関係を示す。

【０００６】〔発明の詳細な説明〕 １．０ 概要このシステムは、コンピュータ、データ入力のためのキ
ーボード、およびラスタ出力スキャナを有しており、ラ
スタ出力スキャナはＣＲＴユーザーインターフェースま
たはプリンタであり得る。そのようなシステムの一つ
は、特願昭６０−１２２４２８号及び特願昭６０−１２
８１２１号に基づいて優先権主張された米国特許第４，
８２９，４５６号「三次元表面ディスプレイ方法」に記
載されており、これは本願の引用文献に取り込まれる。
この特許の図１は、データを入力するためのキーボード
１と、グラフィックディスプレイユニット３と、キーボ
ード１を制御するためのグラフィックコントローラ４
と、コンピュータ５を含むグラフィックディスプレイシ
ステムを示している。この特許に記載されているのは、
通常はページ記述言語（ＰＤＬ）のフォームで入力デー
タから曲線を計算する方法であり、前記グラフィックデ
ィスプレイ端末のフォームでラスタ出力スキャナ 上にそ
の結果を表示することである。 本発明は、ＰＤＬ分析お
よび作像によるグラフィックに関連する２つの計算集約
的問題を考慮している。

【０００７】考慮する第１の問題はそのセグメントが３
次曲線スプライン、放物線、円錐曲線、円弧、および直
線であり得る軌道の発生である。普及している方法は、
複雑な曲線を線分に分割し、次いで汎用の計算要素およ
びハードウエア加速器の組合せを使用して線分を発生す
ることである。曲線の線分への分割は一般に、近似誤差
が受容可能な限界内に入るまで反復細分割および試験の
過程を通して行われる。この明細書で筆者らは高次曲線
を放物線セグメントに分解するアルゴリズムを示すが、
このアルゴリズムでは曲線を所要レベルの正確さで近似
するに必要な放物線セグメントの数を演繹的に決定する
ことができる。次に、この得られた性質を利用して、放
物線セグメントに対する制御点を直接発生するソフトウ
エアによる簡単なステッパアルゴリズムを組み立てる。
放物線軌道はステッパハードウエアによって発生するこ
とができる。厳密なソフトウエアの方法が必要な場合に
は、先の過程で発生された放物線を更に簡単なステッパ
アルゴリズムにより線分に分解するアルゴリズムもこれ
に備わっている。

【０００８】表１は曲線を線分の代わりに放物線セグメ
ントに分解する利点を示している。考察中の例では曲線
を近似するのに必要なセグメントの数は、直線セグメン
トの代わりに放物線セグメントを使用すれば、３倍から
９倍ほど少なくすることができる。解析例に使用する別
の曲線をその制御点と共に図１および図２に示す。図１
ａ〜ｄは３次曲線スプラインであり、図２ａは円弧であ
り、図２ｂおよび図ｃは円錐曲線セグメントである。正
確な曲線とその近似との間にたかだか１画素誤差を許容
すると仮定している。

【０００９】考慮する第２の問題は、そのセグメントを
３次曲線スプライン、放物線、円錐曲線、円弧、および
直線とし得る中心線軌道を用いて隠れた画線を発生する
ことである。ここで再び普及している方法は軌道を線分
に分解し、次いで各線分に対応する台形の座標を計算す
ることである。この明細書で筆者らは所定の放物線に対
応する「パラゾイド (parazoid) 」を直接計算するアル
ゴリズムを示している。このパラゾイドを埋めて隠れた
画線を発生することができる。「パラゾイド」は「平行
な」辺が放射線であり、他の２辺が直線である四辺図形
である。筆者らはパラゾイドが隠れた画線を的確に近似
するために満足しなければならない簡単な試験をも示し
ている。放物線が所定の試験を満足しなければ、各成分
が試験を満足するまで反復して放物線を最適に細分する
他のアルゴリズムを示す。特に重要なのは放物線により
円弧を近似するのに示された先のアルゴリズムが常に試
験を満足する放物線セグメントを発生するという事実で
ある。

【００１０】次に掲げる表は隠れた画線を台形の代わり
にパラゾイドに分解する利点を示している。再び考慮中
の例については、隠れた画線を近似するのに必要な台形
の数の１／３と１／９との間にすることができる。解析
例に使用する別の曲線をその制御点と共に図１及び図２
に示している。正確な画線とその近似との間にたかだか
１画素誤差を許容することができると仮定している。

【００１１】

【表１】

【００１２】本明細書に使用した方法を自然に拡張する
と放物線セグメントおよびパラゾイドの代わりに３次曲
線スプラインおよび「キューベゾイド (cubezoid) 」を
使用することにより、所定の曲線を近似するのに必要な
セグメントの数がさらに減少する。しかし、これらのア
ルゴリズムを有効にするのに必要なここで開発されたも
のと同様な原理は非常に複雑でほとんど処理しにくい。
また、任意の３次曲線スプラインには自己交差が存在す
る可能性があり、一層複雑になる。３次曲線スプライン
を何らかの方法で細分して自己交差を排除することがで
き、またステッピング処理を始める前にステッパの効率
を向上させることができる。他方、放物線は挙動が非常
に良好な曲線である。非常に効率が良くかつ単純に適用
できるステッピングアルゴリズムは、ハードウエアのサ
ポートが必要である場合には、放物線に関するハードウ
エアで実施することができる。ここでは簡潔性と効率と
の両方を考慮すると、すべての曲線を放物線セグメント
に分解するのが最適な方法であることを主張する。この
ような方法に留意して、この明細書では一つの理論およ
び一組のアルゴリズムを開発する。

【００１３】２．０ 緒言 インタープレスやポストスクリプト（Ｐｏｓｔｓｃｒｉ
ｐｔ）のようなページ記述言語（ＰＤＬ）は、その輪郭
線が３次曲線スプライン、円錐曲線、放物線、円弧、お
よび直線で規定されている埋め込み領域を発生すること
ができるかなり強力な図形原線をサポートする。またこ
の言語はその中心線を３次曲線スプライン、円錐曲線、
放物線、円弧、および直線とすることができる特別な幅
の画線をサポートする。この明細書では数学的結果およ
び筆者の希望によりこれらこれら輪郭線を迅速に発生す
ることができる幾つかのアルゴリズムを示している。明
細書の多くの部分は一連の低次の簡単な原線により高次
の困難な原線を近似する判定基準を取り扱っている。数
学的結果のいくつかは当然に重要なものである。

【００１４】第３章では３次曲線スプライン、円錐曲
線、放物線、円弧、および直線の性質を見直す。特に、
これら各曲線に対するパラメータ方程式およびこれら曲
線を細分割するルールを示す。またアルゴリズムの簡潔
な説明をフローチャートの形で示す。フローチャートは
アルゴリズムの神髄をフローチャートを複雑にしないで
述べるように示している。これらアルゴリズムを符号化
するときに幾つかの別の最適化を行うことができる。こ
こではこれら最適化のすべてを明白に述べようとはしな
かった。

【００１５】第４章では所定の曲線を一連の「より簡単
な曲線」により所要レベルの正確さで近似する数学的理
論を示してある。曲線は、これら曲線を簡単なアルゴリ
ズムおよび／またはハードウエアにより迅速に発生する
既知の方法が存在すれば、「簡単」であると考えられ
る。

【００１６】第４章は輪郭線を発生する問題に限定され
る。これはＰＤＬ分解の重要な部分であるが、その中心
線を先に述べた曲線のいずれか一つとすることができる
所定幅の画線を発生する必要も存在する。一般に画線は
インクを詰めた楕円ペンを中心線に沿って歩行させるこ
とにより得られる。リウ(Liu) は楕円ペンを歩行させる
技法を使用して画線の輪郭を発生し、囲まれた領域を埋
め込みアルゴリズムにより埋めた。第５章では、第３章
に示したアルゴリズムに至る理論を展開する。このアル
ゴリズムは画線の輪郭を直接、楕円ペンを中心線に沿っ
て歩行させる必要なしに、一連の合成曲線として発生す
るのに使用することができる。

【００１７】３．０ 定義、属性、およびアルゴリズム この章では３次曲線スプライン、円錐曲線、放物線、円
弧、および直線に対するパラメータ方程式を示す。また
これら曲線についての重要な性質の幾つかを述べる。次
いで高次曲線を放物線に、放物線を直線に、および隠れ
た曲線をパラゾイドに効率良く分解するアルゴリズムを
示す。

【００１８】３．１ ３次曲線スプライン 制御点〔Ａ，Ｂ，Ｃ，Ｄ〕を有する三次曲線スプライン
は次のパラメータ方程式で記述することができる。

【００１９】 [X(t),Y(t)]=A(1-t)³+3Bt(1-t)²+3Ct²(1-t)+Dt³ ここで０≦ｔ≦１およびA=[A_x,A_y], B=[B_x,B_y], C=[C_x,C_y], D=[D_x,D_y]

【００２０】この方程式は次のようにも書くことができ
る。

【００２１】 [X(t),Y(t)]=D₀+3D₁t+3D₂t²+D₃t³ ここで０≦ｔ≦１およびD₀=A, D₁=B-A, D₂=C-2B+A, D₃=D-3C+3B-A

【００２２】図３は３次曲線スプラインの定義および属
性を理解するのに役立つ。制御点Ａ，Ｂ，Ｃ，Ｄにより
規定される３次曲線スプラインが示されている。図３ａ
において、曲線はＡでＡＢに、ＤでＣＤに正接してい
る。図３ｂにおいて３次曲線スプラインＡ，Ｂ，Ｃ，Ｄ
は２つの３次曲線スプラインＡ，Ｕ，Ｖ，ＷおよびＷ，
Ｘ，Ｙ，Ｄに細分割されている。

【００２３】３次曲線スプライン〔Ａ，Ｂ，Ｃ，Ｄ〕は
そのセグメントも３次曲線スプラインであるという属性
を備えている。特に３次曲線スプラインはその制御点が
次式で示される２つの３次曲線スプラインに細分割する
ことができる。

【００２４】 [A,(A+B)/2,(A+2B+C)/4,(A+3B+3C+D)/8] [(A+3B+3C+D)/8,(B+2C+D)/4,(C+D)/2,D]

【００２５】３．２ 円錐曲線 制御点〔Ａ，Ｂ，Ｃ〕および形状パラメータ「ｐ」，こ
こで０≦ｐ≦１，を有する円錐曲線は次のパラメータ方
程式で記述することができる。

【００２６】 (q+pcost)[X(t),Y(t)]＝[(A+C)/2]q−[(A-C)/2]qsint+pBcost ここで -π/2≦ｔ≦π/2, q=1-p およびA=[A_x,A_y], B=[B_x,B_y], C=[C_x,C_y]

【００２７】図４は円錐曲線の定義および属性を理解す
るのに役立つ。図４ａの円錐曲線は制御点Ａ，Ｂ，Ｃに
より定義され、図４ｂの円錐曲線Ａ，Ｂ，Ｃは２つの円
錐曲線Ａ，Ｗ，ＸおよびＸ，Ｙ，Ｃに細分割されてい
る。

【００２８】円錐曲線〔Ａ，Ｂ，Ｃ〕はそのセグメント
も円錐曲線であるという属性を備えている。特に円錐曲
線はその制御点が次式で示される２つの円錐曲線に細分
割することができる。

【００２９】 [A,(qA+pB),q(A+C)/2+pB)] [q(A+C)/2+pB),(qC+pB),C]

【００３０】各副円錐曲線は次式で与えられる新しい形
状パラメータ「ｐ' 」を備えている。

【００３１】 P'＝1/[1+ √(2-2p)]

【００３２】３．３ 放物線 制御点〔Ａ，Ｂ，Ｃ〕を有する放物線は制御点〔Ａ，
Ｂ，Ｃ〕および形状パラメータｐ＝０．５を有する円錐
曲線の特別の場合である。また放物線のパラメータ方程
式は下に示される形に大幅に簡単化することができる。

【００３３】 [X(t),Y(t)]=A(1-t)²+2Bt(1-t)+Ct² ここで０≦ｔ≦１およびA=[A_x,A_y], B=[B_x,B_y], C=[C_x,C_y]

【００３４】この方程式は次のように書くこともでき
る。

【００３５】 [X(t),Y(t)]=D₀+2D₁t+D₂t² ここで０≦ｔ≦１およびD₀=A, D₁=B-A, D₂=C-2B+A

【００３６】放物線〔Ａ，Ｂ，Ｃ〕はその切片も放物線
であるという属性を備えている。特に放物線はその制御
点が次式で与えられる２つの放物線に細分割することが
できる。

【００３７】 [A,(A+B)/2,(A+2B+C)/4] [(A+2B+C)/4,(B+C)/2,C]

【００３８】わかるとおり、放物線は３次曲線スプライ
ンの特別の場合である。事実、放物線は二次曲線スプラ
インである。後章で円錐曲線および３次曲線スプライン
の双方を一連の隣接放物線で近似する仕方を求めること
にする。

【００３９】３．４ 円弧 制御点〔Ａ，Ｂ，Ｃ〕を有する円弧もＢ線が辺ＡＣの垂
直二等分線上にありかつその形状パラメータ「ｐ」が次
式で示されるという制約を有する円錐曲線の特別の場合
である。

【００４０】 p=m[√(1+m²)]-m², ここでm=tanABC/2

【００４１】円弧はＰから出発しＱを通ってＲで終わる
弧を有する点〔Ｐ，Ｑ，Ｒ〕により規定することもでき
ることに注目されたい。後に制御点〔Ａ，Ｂ，Ｃ〕をパ
ラメータｐと共に〔Ｐ，Ｑ，Ｒ〕から求める仕方を示す
ことにする。

【００４２】３．５ 直線 制御点〔Ａ，Ｂ〕を有する直線線分はＡから出発してＢ
で終わるが、次のパラメータ方程式で規定することがで
きる。

【００４３】 [X(t),Y(t)]=A(1-t)+Bt ここで０≦ｔ≦１およびA=[A_x,A_y], B=[B_x,B_y]

【００４４】３．６ アルゴリズム図５ から図７までは３次曲線スプライン、円弧および円
錐曲線を放物線セグメントに分解するアルゴリズムを示
している。図８は放物線を線分に分解するアルゴリズム
を示す。図９は放物線を、必要ならば、副放物線に分割
し、次いでパラゾイドを発生するアルゴリズムを示して
いる。

【００４５】図６で、ｄは隣接画素間の座標系内の距離
であり、ｍは３次曲線スプラインを近似するに必要な放
物線セグメントの数である。図６で、Ｒが完全な円であ
れば、ｍ＝１６，Ｚ＝（Ａ＋Ｂ）／２，およびＤ＝Ｅ＝
Ｚ＋（ｒ，０）。ｃ₀ ＝cos22.5 、ｃ₂ ＝sin22.5 そし
てｃ₃ ＝tan11.25。

【００４６】ＲはＡから出発してＢを通りＣで終わる円
弧である。代わりに、Ｒは中心がＺにあり、半径ｒ、開
始角θ₁ および終了角θ₂ を有する円弧である。ｃは横
断が時計方向か反時計方向かを示す。インタープレスは
第１の体系（時計方向）を使用しているが、ポストスク
リプトは第２を使用していることに注意されたい。筆者
らはこれらいずれの表現をも、ＲがＤから始まり、Ｅで
終わり、Ｚに中心を有し、反時計方向に横断する第３の
表現に変換する。ｍ＝θ／22.5で、最も近い整数に丸め
られるが、θは中心においてＲを臨む角度である。

【００４７】図８で、ｄは隣接画素間の座標系内の距離
であり、ｍは放物線Ｐを近似するのに必要な線分の数で
ある。

【００４８】４．０ 近似 この章では、前の章で導入した高次曲線を低次曲線によ
り所要レベルの正確さで近似することができる条件を求
めることにする。

【００４９】４．１ ３次曲線スプラインの放物線によ
る近似 [S(t)]=A+3(B-A)t+3(C-2B+A)t²+(D-3C+3B-A)t³ で記述される制御点〔Ａ，Ｂ，Ｃ，Ｄ〕を有する３次曲
線スプラインは、 [P(t)]=A+2(E-A)t+(D-2E+A)t² で記述される制御点〔Ａ，Ｅ，Ｄ〕を有する放物線で、
下記条件が良好に保持されれば正確さを損なわずに、置
き換えることができる。

【００５０】 D-3C+3B-A=0, E=(3B+3C-A-D)/4

【００５１】上の２つの条件は第３の方程式に３を掛
け、これに第２の方程式を加えることにより下に示す２
つの条件に縮小することができる。

【００５２】 D-3C+3B-A=0, E=(3B+3C-A-D)/4

【００５３】制御点〔Ａ，Ｂ，Ｃ，Ｄ〕を有する３次曲
線スプラインＳは制御点〔Ａ，（３Ｂ＋３Ｃ−Ａ−Ｄ）
／４，Ｄ〕を有する放物線で近似することができ、２つ
の曲線の間の差ｄは規定誤差ベクトル「ｅ」の関数とし
て次のように表される。

【００５４】 d(t)=[S(t)-P(t)]=-(e/2)[2t ³ -3t ² +t] ここで e=3C-3B-D+A

【００５５】この差はｔ＝０，0.5 および１のときゼロ
である。この差はｔ＝0.2113および0.7887で最大にな
り、最大差は次式で与えられる。

【００５６】

【００５７】最大誤差は原制御点〔Ａ，Ｂ，Ｃ，Ｄ〕の
単純な関数であることに注目されたい。最大誤差が隣接
画素間の間隔のような公差限界内にあれば、近似は受容
可能である。計算を簡単にするには上の式で│ｅ│を
（│ｅ_x │＋│ｅ_y │）で置き換えればさらに厳格な制
約を課すことができる。

【００５８】４．２ ３次曲線スプラインの放物線によ
る近似 上で計算した最大差が公差限界を超えていれば、３次曲
線スプラインを細分割して各セグメントを放物線で近似
することができる。今度はスプラインのセグメントの放
物線近似に対する最大差の式をスプライン全体の放物線
近似に対する最大差の関数として求める。

【００５９】Ｓ₁(t)をｘ≦ｔ≦ｘ＋δについて３次曲線
スプラインＳ(t) のセグメントを表すものとする。

【００６０】ｔ＝（ｘ＋ｕδ）をＳ(t) に代入して並べ
換えると次の方程式が得られる。

【００６１】 [S₁(u)]=X₀+3X₁(x+δu)+3X₂(x+δu)²+X₃(x+δu)³ ただし０≦ｕ≦１、ここで X₀=A, X₁=(B-A), X₂=(C-2B+A), X₃=(D-3C+3B-A)

【００６２】展開して並び換えると次の方程式を得る。

【００６３】 [S₁(u)]=Y₀+3Y₁u+3Y₂u²+Y₃u³ ただし０≦ｕ≦１、ここで Y₀=A+3(B-A)x+3(C-2B+A)x²+(D-3C+3B-A)x³ Y₁=[(B-A)+2(C-2B+A)x+(D-3C+3B-A)x²]δ Y₂=[(C-2B+A)+(D-3C+3B-A)x]δ² Y₃=(D-3C+3B-A)δ³

【００６４】予想されるように、Ｓ₁ も３次曲線スプラ
インである。これは下に示すように制御点〔Ａ₁,Ｂ₁,Ｃ
₁,Ｄ₁ 〕を備えている。

【００６５】 A₁=Y₀, B₁=Y₁+Y₀, C₁=(Y₂+2Y₁+Y₀), D₁=(Y₃+3Y₂+3Y₁+Y₀)

【００６６】前述のように、Ｓ₁ を制御点〔Ａ₁,Ｅ₁,Ｄ
₁ 〕を有する放物線Ｐで近似することができる。ただ
し、Ｅ₁ ＝（３Ｂ₁ ＋３Ｃ₁ −Ａ₁ −Ｄ₁ ）／４であ
る。Ａ₁＝Ｓ(x) であり、Ｄ₁ ＝Ｓ(x+δ) であることに
注意されたい。

【００６７】Ａ₁,Ｂ₁,Ｃ₁ およびＤ₁ を代入し、Ｅ₁ の
式をＳ，ｘ，およびδの項で下のように簡単にすること
ができる。

【００６８】 E₁=(4Y₀+6Y₁-Y₃)/4

【００６９】更に簡単化しかつＳ(x) の導関数に記号
Ｓ' を使用すれば、次式が得られる。

【００７０】 E₁=S(x)+S'(x)δ/2-S'''(x)δ³/24

【００７１】Ｐ₁ の制御点はいま、次のように与えられ
る。

【００７２】 [S(x), S'(x)δ/2-S'''(x)δ ³ /24, S(x+δ)]

【００７３】曲線Ｓ₁ とＰ₁ との間の差ｄ₁ は規定の誤
差ベクトル「ｅ₁ 」の関数として下のように示される。

【００７４】 d₁(u)=[S₁(u)-P₁(u)]=-(e/2)[2u³-3u²+u] ここでe₁=3C₁-3B₁-D₁+A₁

【００７５】再び、この差はｕ＝0,0.5,１のときゼロで
ある。この差はｕ＝0.2113および0.7887のとき最大にな
り、最大差は│ｄ₁ │_max ＝0.0481│ｅ₁ │で与えられ
る。

【００７６】代入し、簡単化すると、ｄ₁ およびｅ₁ に
対して次の式が得られる。

【００７７】

【００７８】結論：ｄ₁ は元のスプラインの「ｔ」軸に
沿うセグメントの「長さ」，「δ」の関数に過ぎないの
であって、セグメントの開始点「ｘ」の関数ではないこ
とに注目されたい。ｄ₁ はδの３次関数であるから、３
次曲線スプラインを放物線で近似する過程は急速に収束
する。したがって、所要レベルの正確さについて、放物
線による近似に必要なセグメントの数「ｎ」（≧１／
δ）は細分過程を経ずに演繹的に決定することができ
る。各セグメントについてδを同じにすることにより、
一般性が失われることはないことに注目されたい。計算
の目的では、「ｎ」を２の累乗にするのが有利である。

【００７９】４．３ 放物線の直線による近似 [P(t)]=A+2(E-A)t+(D-2E+A)t² により記述される制御点〔Ａ，Ｅ，Ｄ〕を有する放物線
は、 [L(t)]=A+(D-A)t により記述される制御点〔Ａ，Ｄ〕を有する直線Ｌで置
き換えることができ、下記条件が良好に保持されていれ
ば正確さは損なわれない。

【００８０】 D-2E+A=0 および 2(E-A)=(D-A)

【００８１】上の２つの条件は下に示すように１つの条
件に縮小することができる。

【００８２】 D-2E+A=0

【００８３】制御点〔Ａ，Ｅ，Ｄ〕を有する放物線Ｐは
制御点〔Ａ，Ｄ〕を有する直線Ｌで近似することがで
き、２つの曲線の間の差ｄは次のように規定誤差ベクト
ル「ｅ」の関数である。

【００８４】 d(t)=[P(t)-L(t)]=e[t ² -t] ここで e=D-2E+A

【００８５】この差はｔ＝０および１のときゼロであ
る。この差はｔ＝0.5 のとき最大となり、最大差は次の
ように与えられる。

【００８６】

【００８７】最大誤差は原制御点〔Ａ，Ｅ，Ｄ〕の単純
な関数であることに注目されたい。最大誤差が１画素の
大きさのような公差限界内にあれば、近似は受容可能で
ある。計算を簡単にするには、上の式で│ｅ│を（│ｅ
_x │＋│ｅ_y │）で置き換えれば一層厳格な制約を課す
ことができる。

【００８８】４．４ 放物線セグメントの直線による近
似 前記で計算した最大差が公差限界を超えていれば、放物
線を細分割し、各セグメントを直線で近似することがで
きる。今度は放物線セグメントき直線近似に対する最大
差の式を放物線全体の直線近似に対する最大差の関数と
して求める。

【００８９】Ｐ₁(t)を、ｘ≦ｔ≦ｘ＋δについて、放物
線Ｐ(t) のセグメントを表すものとする。

【００９０】ｔ＝（ｘ＋ｕδ）をＰ(t) に代入し、並べ
換えれば次の方程式を得る。

【００９１】 [P₁(u)]=A₁+2(E₁-A₁)u+(D₁-2E₁+A₁)u² ただし０≦ｕ≦１、ここで A₁=A+2(E-A)x+(D-2E+A)x² E₁=A₁+[(E-A)+(D-2E+A)x] δ D₁=2E₁-A₁+(D-2E+A)δ²

【００９２】予想されるように、Ｐ₁ も制御点〔Ａ₁,Ｄ
₁ 〕を有する直線Ｌ₁ で近似することができる放物線で
あり、この近似での曲線間の差は規定誤差ベクトル「ｅ
₁ 」の関数として次のように表される。

【００９３】 d₁(u)=[S₁(u)-P₁(u)]=e₁[u²-u] ここで e₁=(D₁-2E₁+A₁)=(D-2E+A)δ²

【００９４】再び、この差はｕ＝０および１のときゼロ
である。この差はｕ＝0.5 のとき最大になり、最大差は
│ｄ₁ │_max ＝0.25│ｅ₁ │で与えられる。

【００９５】置換および簡略化の後、ｄ₁ およびｅ₁ に
対して次の式を得る。

【００９６】

【００９７】検討：ｄ₁ は元の放物線の「ｔ」軸に沿う
セグメントの「長さ」，「δ」の関数に過ぎないのであ
って、セグメントの開始点「ｘ」の関数ではないことに
注目されたい。ｄ₁ はデルタの２次関数であるから、放
物線セグメントを直線で近似する過程も、３次曲線スプ
ラインを放物線で近似する過程ほど速くはないにして
も、急速に収束する。したがって、所要レベルの正確さ
について、直線による近似に必要なセグメントの数
「ｎ」（≧１／δ）は細分過程を経ずに演繹的に決定す
ることができる。各セグメントについてデルタを同じに
することにより、一般性が失われることはないことに注
目されたい。計算の目的ではｎを２の累乗にするのが有
利である。

【００９８】４．５ 円錐曲線の放物線による近似 制御点〔Ａ，Ｂ，Ｃ〕および (q+pcost)N(t)]=[(A+C)/2]q-[(A-C)/2]qsint+pBcost ここで −π/2≦ｔ≦π/2 および q=1-p で記述される形状パラメータｐを有する円錐曲線Ｎは、 (1+cost)P(t)]=[(A+C)/2]-[(A-C)/2]sint+Bcost ここで −π/2≦ｔ≦π/2 または代わりに、 [P(u)]=A+2(B-A)u+(C-2B+A)u² ここで０≦ｕ≦１ で記述される制御点〔Ａ，Ｂ，Ｃ〕を有する放物線で置
き換えることができ、次の条件が良好に保持されていれ
ば正確さは失われない。

【００９９】 q=p=0.5

【０１００】制御点〔Ａ，Ｂ，Ｃ〕を有する円錐曲線Ｎ
は制御点〔Ａ，Ｂ，Ｃ〕を有する放物線Ｐで近似するこ
とができ、この近似での２つの曲線間の差ｄは次式で与
えられる。

【０１０１】 (2+2cost-2psin ² t)d(t)=(q-p)[(C-2B+A)+(C-A)sint]cost

【０１０２】この差はｔ＝−π／２および＋π／２のと
きゼロである。この差の最大値を簡単に計算することは
できない。しかしｔ＝０のときその値は最大値に非常に
近く、最大値を近似するにはこの値を使用する。それゆ
え、

【０１０３】

【０１０４】最大誤差が１画素の大きさのような公差限
界内にあれば、近似は受容可能である。計算を簡単にす
るには上の式で│ｅ│を（│ｅ_x │＋│ｅ_y │）で置き
換えれば一層厳格な制約を課すことができる。

【０１０５】４．６ 円錐曲線セグメントの放物線によ
る近似 上で計算した最大差が公差限界を超えていれば、円錐曲
線を細分割して各セグメントを放物線で近似することが
できる。今度は、円錐曲線セグメントの放物線近似に対
する最大差の式を円錐曲線全体の放物線近似に対する最
大差の関数として求める。

【０１０６】Ｎ₁(t)およびＮ₂(t)が細分割後のＮ(t) の
副円錐曲線を表すものとする。

【０１０７】円錐曲線の性質に関する章で先に述べた通
り、Ｎ₁ およびＮ₂ に対する制御点および形式パラメー
タ「Ｐ₁ 」および「ｐ₂ 」は次式で与えられる。

【０１０８】 N₁に対し[A,(qA+pB),q(A+C)/2+pB] N₂に対し[q(A+C)/2+pB,(qC+pB),C] p₁=p₂=1/[1+ √2(1-p)]

【０１０９】さてＮ₁ は、 [P₁(u)]=A₁+2(C₁-A₁)u+(C₁-2B₁+A₁)u² ただし０≦ｕ≦１ここで A₁=A, B₁=(qA+pB), C₁=q(A+C)/2+pB) で規定される放物線Ｐ₁ で近似することができ、そのと
きの最大近似誤差は、次のように与えられる。

【０１１０】

【０１１１】置換すると、次式を得る。

【０１１２】

【０１１３】同様にＮ₂ は、 [P₂(u)]=A₂+2(C₂-A₂)u+(C₂-2B₂+A₂)u² ただし０≦ｕ≦１ここで A₂=q(A+C)/2pB, B₂=(qC+pB), C₁=C で規定される放物線Ｐ₂ に近似することができ、そのと
きの最大近似誤差は次で与えられる。

【０１１４】

【０１１５】置換すると次式を得る。

【０１１６】

【０１１７】ｐ＝0.5 −δとし、デルタの２次以上の高
次項を無視すると、次の簡略式を得ることができる。

【０１１８】 p₁=p₂≒0.5 −δ/4

【０１１９】検討：上の式は各セグメントを放物線で近
似しようとして円錐曲線を細分割する過程が急速に収束
し、そのときの近似誤差が各細分についてほぼ１６分の
１に減少することを示している。リウ(Liu) はそのレポ
ートの中で細分割過程を停止する判定基準として、現在
のところδを0.01に設定して、│ｐ’−0.5 │≦δの試
験を行っている。この試験を行うと誤差は円錐曲線を細
分割する毎に４分の１だけしか減少しない。このような
場合には近似により生じる誤差が１画素より大きくなる
ようにメジアンが充分長い円錐曲線を作図することが可
能である。不必要な細分割を行って試験をちょうど満足
する充分短いメジアンの円錐曲線を作図することも可能
である。ここでは│ｄ│_max ≦隣接画素間の間隔という
更に最適な試験を細分割過程停止の判定基準として行う
ことを示しておく。

【０１２０】ｐ₁ およびｐ₂ の近似： 円錐曲線を細分割する毎に新しい形状パラメータを計算
しなければならない。この計算には、共に計算の費用が
大きい、平方根および除算の演算を行う必要があること
に注目されたい。ここでは平方根および除算の演算子を
使用しない簡略近似公式を示しておく。ここでは誘導の
過程を省いて公式だけを示す。

【０１２１】 p ₁ =p ₂ ≒0.5-0.25 (δ−δ ² ＋δ ³ ) ここでδ=(0.5-p)

【０１２２】表２は上の公式を使用したときのｐの差値
についてｐ₁ およびｐ₂ の正確な値と近似値との間の差
を示すものである。

【０１２３】

【表２】

【０１２４】今度はｐ’に関する所定の簡略化公式を使
用して細分割した円錐曲線での画素誤差の半分以下にし
か寄与しないという判定基準を使用する。また原円錐曲
線は包囲三角形のメジアンを８．５”×１１”（２２ｃ
ｍ×２８ｃｍ）の紙の対角線の長さ程にすることができ
るようなものであると仮定する。この判定喜寿を使用す
ると近似に対する最大許容誤差は６００ｓｐｉで３．３
×１０^-4、３００ｓｐｉで６．６×１０^-4になり、次の
ルールを述べることができる。

【０１２５】「６００ｓｐｉでは ０．２５≦ｐ≦０．
６２ に関して簡略式を使用し、その他の場合には正確
な式を使用すること。」

【０１２６】更に６００ｓｐｉでは、以後の細分割に簡
略式を使用することができる前に０．０≦ｐ＜０．２５
および ０．６２＜ｐ≦０．８ に関して正確な公式
をちょうど１回使用しなければならないということを立
証することができる。

【０１２７】「３００ｓｐｉでは ０．２１≦ｐ≦０．
６６ に関して簡略式を使用し、その他の場合には正確
な式を使用すること。」

【０１２８】更に３００ｓｐｉでは、以後の細分割に簡
略式を使用することができる前に０．６６≦ｐ＜０．２
１ および ０．６６＜ｐ≦０．８７ に関して正確な
公式をちょうど１回使用しなければならないということ
を立証することができる。

【０１２９】４．７ 円弧の放物線による近似 (q+pcost)R(t)]=[(A+C)/2]q-[(A-C)/2]qsint+pBcost ここで−π/2≦ｔ≦π/2 および q=1-p で記述される制御点〔Ａ，Ｂ，Ｃ〕および形状パラメー
タｐを有する円弧Ｒは (1+cost)P(t)]=[(A+C)/2]-[(A-C)/2]sint+Bcost ここで−π/2≦ｔ≦π/2 または代わりに、 [P(u)]=A+2(B-A)u+(C-2B+A)u² ここで０≦ｕ≦１ で記述される制御点〔Ａ，Ｂ，Ｃ〕を有する放物線Ｐで
近似することができ、このとき２つの曲線の間の差ｄは
次式で与えられる。

【０１３０】 (2+2cost-2psin²t)d(t)=(q-p)[(C-2B+A)+(C-A)sint]cost

【０１３１】この差はｔ＝−π／２および＋π／２のと
きゼロである。この差はｔ＝０のとき最大になり、最大
差は次式で与えられる。

【０１３２】

【０１３３】最大誤差が１画素の大きさのような公差限
界内にあれば、近似は受容可能である。計算を簡単にす
るには上の式で│ｅ│を（│ｅ_x │＋│ｅ_y │）で置き
換えれば一層厳格な制約を課すことができる。

【０１３４】図１０で円弧Ｒの半径を「ｒ」とし、その
中心ＺからＲを臨む角を図のように「θ」とする。

【０１３５】次の関係を得ることができる。

【０１３６】 (1-2p)=(1-cosθ/2)²/sin²θ/2

【０１３７】表３は半径「ｒ」の円を放物線で近似する
ときの「θ」の異なる値に対する最大誤差を示す。この
表は誤差を１画素に限定した場合の円の最大半径をも示
している。

【０１３８】

【表３】

【０１３９】検討：円弧をその中心から臨む角が１５度
以下になるように細分すれば、各副円弧を放物線で直接
置き換えることができ、関係するすべての解像度および
半径について受容可能誤差内にすることができる。２
２．５度の臨み角も受容可能であり、おそらくは好適な
選択であろう。

【０１４０】５．０ 隠れた画線の放物線で規定される
埋め込み領域による近似 インタープレスおよびポストスクリプトは用紙上の隠れ
た画線を描くように太くすることができる軌道を規定す
ることができる。軌道それ自身は直線、円弧、円錐曲
線、放物線、および３次曲線スプラインから構成するこ
とができる。一般に、他の曲線に平行な曲線は元のもの
より次数の高い数学方程式でのみ表すことができるとい
うことに注目すべきである。隠れた画線の充足のほとん
どはこれをすべての曲線を線分に分解し、その中心線が
分解した線分である一連の台形を埋めることにより行っ
ている。曲線を直線に分解することに関連する計算の他
に、各台形の頂点を計算するにはかなりな量の計算を行
わなければならない。必要な計算の量は近似に必要な線
分の数に直接比例する。ジャック・ルイ (Jack Lui)は
彼の論文で太くした放物線の内部軌道および外部軌道を
一連の放物線自身で近似することができる方法を示し
た。３次曲線スプライン、円弧、および円錐曲線は少数
の放物線セグメント (第３章に示されているような) に
分解することができることから、隠れた画線は放物線お
よび直線の閉軌道を埋めることにより実現することがで
きる。カリーナ (Carina) のチームによりこれまでに行
われた測定で、内部軌道および外部軌道を楕円ブラシを
放物線の中心線に沿って歩行させることにより計算する
リウの方法は多量の計算を必要とするという事実にも拘
わらず効率の良い過程であることがわかった。この章で
は、放物線の隠れた画線の内部軌道および外部軌道を放
物線自身で近似し、中心線軌道に沿って実際に歩行させ
る必要のない改良されたアルゴリズムを作ることができ
る方法に関する数学理論を展開する。

【０１４１】図１１は放物線軌道ＷＸＹを示す。軌道Ｂ
ＣＤおよびＥＦＡはＷＸＹに平行な曲線であり、軌道Ａ
ＢＣＤＥＦＡは、埋めれば曲線ＷＸＹの隠れた画線を発
生する領域を規定する。ＢＣＤおよびＥＦＡは一般に放
物線ではないことに注目されたい。

【０１４２】この章では、放物線ＷＸＹがＢＣＤおよび
ＥＦＡを放物線で近似することができるために満たさな
ければならない試験しやすい条件を求める。またＷＸＹ
を最適に細分して細分した放物線が原放物線ＷＸＹが必
要な条件を満足しないときその必要な条件を満たすよう
にする方法を求める。

【０１４３】５．１ 正規化放物線 数学方程式の幾つかを簡単にするために、正規化放物線
を規定し、正規化放物線に対するすべての条件を求め
る。任意の放物線はすべて変位、回転、および拡大縮小
からなる一連の変換の後ここに規定する正規化放物線に
帰着させることができる。結果の一般性を維持するに
は、この拡大縮小をＸ軸およびＹ軸に沿って対称にする
必要がある。

【０１４４】制御点〔Ａ，Ｂ，Ｃ〕を有する放物線は、
Ａ＝（０，０），Ｃ＝（０，１），およびＢ＝（Ｂ_x ,
Ｂ_y ) でＢ_x およびＢ_y に制約が無い場合、正規化放物
線である。図１２は任意の放物線を正規化放物線に変換
することに関連する各段階を示している。放物線の形状
はこの正規化過程の後で変形しないことに注目された
い。

【０１４５】それゆえ、正規化放物線は原放物線に必要
な６個のパラメータ（Ａ_x, Ａ_y,Ｂ_x, Ｂ_y, Ｃ_x, Ｃ_y)
に反して２個のパラメータ（Ｂ_x, Ｂ_y) により完全に規
定することができる。ここでの議論の目的に対しては、
議論を正規化放物線の族に限定することで充分である。
また正規化放物線を、ｋ（後にねじれという）を辺ＡＢ
とＡＣとの長さの比、θをその夾角ＡＢＣとして、パラ
メータ（SD，θ）で規定することが便利であることもわ
かる。後の説明では、ｋをねじれパラメータと言うこと
にする。（ｋ，θ）および（Ｂ_x，Ｂ_y）は次の方程式に
より関連付けられていることを確認することができる。

【０１４６】 k=(B² _x+B² _y)/([1-B² _x]+B² _x 5.1.1 cosθ=(B² _x+B² _y-B_x)/√｛(B² _x+B² _y)([1-B² _x]+B² _y)｝ 5.1.2 B_x=(k²-kcosθ)/(1+k²-2kcosθ) 5.1.3 B_y=(sinθ)/(1+k²-2kcosθ) 5.1.4

【０１４７】５．２ 「平行」放物線の構成 図１３に示すように、〔Ａ，Ｂ，Ｃ〕で規定される放物
線Ｐ１を考える。ＤＥがＡＢに平行に、ＥＦがＢＣに平
行に、かつ、ｄのある値に対して、│ＡＤ│＝│ＣＦ│
＝ｄになるように〔Ｄ，Ｅ，Ｆ〕で規定される他の放物
線Ｐ２を考える。次に、Ａ，Ｂ，Ｃ，およびｄを知って
Ｄ，Ｅ，およびＦを計算する方程式を示す。

【０１４８】下記方程式が有効である。

【０１４９】 D=A+d[-sinθ₁, cosθ1] 5.2.1 E=B-d[(cosθ₁+cosθ₂), (sinθ₁+sinθ₂)]/sin(θ₁-θ₂) 5.2.2 F=C+d[sinθ₂,-cosθ₂] 5.2.3 T=(C+2B+A)/4 および U=(F+2E+D)/4 5.2.6 U_x-T_x=d[sinθ₂-sinθ₁-2(cosθ₁+cosθ₂)/sin(θ₁-θ₂)]/4 5.2.7 U_y-T_y=d[cosθ₁-cosθ₂-2(sinθ₁+sinθ₂)/sin(θ₁-θ₂)]/4 5.2.8

【０１５０】次に、Ｐ１に平行な曲線からのＰ２の偏
差、およびその曲線からの距離「ｄ」を決定する。構成
により、この偏差は端点ＤおよびＦではゼロである。詳
細な計算に進む前に、ある特別な場合を考え、解に対す
る直観的感触を求める。放物線Ｐ１がその二等分線ＢＸ
に沿って対象である場合を考える。この場合には、│Ａ
Ｂ│＝│ＡＣ│であり│ＴＵ│と「ｄ」との差は平行曲
線をＰ２で近似するときの誤差の推定値を与える。この
特別な場合については、この差は事実最大誤差に等し
い。分かるとおり、この差はθが１８０度に近づくにつ
れて小さくなり、ゼロになる。この限られた場合には、
放物線は直線に退化し、したがって近似は正確である。
予想したように誤差は夾角θがゼロに近づくとき無限大
になる。

【０１５１】θが１８０度に近づく場合には、方程式
５．２．２の各項は限界０／０に近づき、計算誤差を生
ずる。Ｅを計算する下記代替公式を限界の場合に使用す
るとよい。

【０１５２】 E=B+d[-sinθ₁+cosθ₁cotθ/2), (cosθ₁+sinθcotθ/2)] 5.2.10

【０１５３】５．３ 近似平行放物線に対する誤差の計
算 ５．２章で、考慮した特別な場合に対し、放物線に平行
な曲線を他の適切に選択した放物線で近似するときの最
大誤差を精密に与える公式を得た。誤差を推定するため
のこのような閉じた形態の解は任意の放物線に対しては
不可能である。それゆえ、この章では一般的な場合に対
する誤差推定値を得る数学的方法を追求する。筆者らは
この探索を、そうすることで充分であるから、我々の考
慮を正規化放物線の等級に限定することにより絞り込
む。

【０１５４】表４は平行曲線を端点で原放物線に平行な
放物線で近似するとき数値探索手順の結果として観察さ
れる最大百分率誤差のリストである。このプロセスを正
規化放物線の等級内の等級内の異なるメンバーについて
繰り返す。等級内の各放物線について、外部平行放物線
と原放物線との間の距離を、「ｔ」を０．０から１．０
まで０．０１きざみに進めたとき原放物線に沿う異なる
点で計算した。２曲線間の所要分離長ｄの百分率として
観察した最大誤差を下表に掲げる。構成により、この誤
差はｔ＝０．０およびｔ＝０で常にゼロである。表５は
内部平行放物線について得られた結果のリストである。

【０１５５】表６は表５および表４のデータを異なる方
法で表したものである。この表では、平行曲線のいずれ
かに対する最大許容ねじれ（ｋ）をθ（夾角）および最
大許容誤差限界の関数として掲げている。図１４は同じ
データを図式形態で対数尺度により描いたものである。

【０１５６】

【表４】

【０１５７】

【表５】

【０１５８】

【表６】

【０１５９】図１４から分かるとおり、θが（１２０，
１５０）の範囲にあるときは適度な大きさのねじれの値
を、θが（１５０，１７０）の範囲にあるときははるか
に大きなねじれの値を、許容することができ、θが（１
７０，１８０）の範囲にあるときはねじれに関する実際
上の制限は存在しない。次章では夾角θを有する任意の
放物線を各成分放物線の夾角が（９０＋θ／２）になる
ように常に細分割できる方法を示す幾つかの結果を求め
る。このプロセスを継続するにつれて、各成分放物線
が、平行曲線を放物線で近似するとき、最大誤差が所要
誤差原価以内にあるように値（ｋ，θ）を有する状態に
急速に到達する。表７は原放物線をｎ個の成分に細分割
した後の各成分放物線の夾角を示す。

【０１６０】

【表７】

【０１６１】５．４ 放物線の細分割 この章では任意の放物線を各成分放物線の夾角が元の夾
角より大きいように細分割することができる仕方を示
す。事実、θを原放物線の夾角とすれば、ここで得られ
る細分手順は両成分放物線について（９０＋θ／２）の
夾角を常に生ずる。この細分は継続すると、急速に収束
して各成分放物線の夾角およびねじれが近似レベルに対
する限界内にあるようになる。

【０１６２】Ｐ＝〔Ａ，Ｂ，Ｃ〕が図１５に示す放物線
を規定するとする。ｔ＝ｕでＰを細分割することにより
得られた２つのＰのセグメントをＰ１およびＰ２とす
る。Ｐ１＝〔Ａ，Ｄ，Ｅ〕およびＰ２＝〔Ｅ，Ｆ，Ｃ〕
とする。

【０１６３】θ，θ₁ およびθ₂ をそれぞれＰ，Ｐ１お
よびＰ２に対する夾角とする。ｋ，ｋ１およびｋ２をそ
れぞれＰ，Ｐ１およびＰ２に対するねじれとする。そこ
で次の方程式が得られる。

【０１６４】 (180-θ₁)+(180-θ₂)＝180-θ 5.4.4 θ₁ ＝θ₂ であれば θ₁ ＝θ₂ ＝90＋θ/2 5.4.5 θ＜180 であれば 90＋θ/2＞θ 5.4.6

【０１６５】ベクトル代数学から、Ｖ₁ ＝（Ｖ_1x，Ｖ
_1y）およびＶ₂ ＝（Ｖ_2x，Ｖ_2y）が２つのベクトルで
あれば、これら２つのベクトルの間の角φは次の方程式
で与えられる。なお、本明細書において、倍角文字はベ
クトルを示すものである。

【０１６６】

【０１６７】３．４章の結果を使用して、Ｄ，Ｅおよび
Ｆに対する次の式を書くことができる。

【０１６８】 D=A+(B-A)u,E=A+2(B-A)u+(C-2B+A)u² および F=C+(B-C)(1-u) 5.4.8

【０１６９】θはベクトルＢＡとＢＣとの間の
角であり、θ₁ はベクトルＤＡとＤＦとの間の
角であり、θ₂ はベクトルＦＤとＦＣとの間の
角であるから、次の式を書くことができる。

【０１７０】 cosθ=[(A_x-B_x)(C_x-B_x)+(A_y-B_y)(C_y-B_y)]/l₁l₂ 5.4.9

【０１７１】次の方程式が有効であることを立証するこ
とができる。

【０１７２】 Ａ−Ｄ＝（Ａ−Ｂ）u 5.4.13 Ｆ−Ｄ＝（Ｃ−Ｂ）u （Ｂ−Ａ）(1-u) 5.4.14 Ｃ−Ｆ＝（Ｃ−Ｂ）(1-u) 5.4.15

【０１７３】もしθ₁ ＝θ₂ 、したがって cosθ₁ ＝ c
osθ₂ と簡略化すれば、最終的に、両成分放物線の夾角
が大きくなるように放物線を分解しなければならない点
である「ｕ」に対する下記の簡単な解が得られる。

【０１７４】 u=l ₁ /(l ₁ +l ₂ ) または u=k(k+1) 5.4.18

【０１７５】今度は成分放物線についての幾つかの有用
な性質を、原放物線の性質によって求め、成分放物線を
試験しやすくしてそれらが近似に対する必要条件を満た
しているか否か確認することができるようにする。特
に、 cosθ₁, cosθ₂,ｋ₁ およびｋ₂ の式を cosθおよ
びｋの項により表す。

【０１７６】ｋ₁ およびｋ₂ の式を求める前にまず│Ｄ
Ｅ│および│ＥＦ│を計算する。

【０１７７】 5.4.21 ｕにｋ／（ｋ＋１）を代入すると次式を得る。 k ₁ =(1+k)/√[2(1-cosθ)] 5.4.26

【０１７８】同様にして、│ＥＦ│およびｋ₂ に対して
次式を得ることができる。

【０１７９】 k₂=(k√[2(1-cosθ)]/(1+k) 5.4.28

【０１８０】θ₁ ＝θ₂ ＝（９０＋θ／２）であるか
ら、次の方程式が得られる。

【０１８１】 cosθ₁ ＝ cosθ₂ ＝−√[(1-cosθ)/2] 5.4.29

【０１８２】５．５ 経験的に得られた試験判定基準 ５．４章で、放物線に平行な曲線を放物線自身により近
似することができるために放物線を如何に細分割するか
に関する理論を展開した。また、成分放物線の性質を原
放物線の性質によってかなり容易に計算することができ
る結果を得た。５．２章で、記述した近似過程を使用し
て観察される最大誤差の表を作った。この章では、放物
線を更に細分すべきか否かを試験するのに使用すること
ができる簡単ではあるが経験的に得られた判定基準を示
す。またこの判定基準を使用する場合、観察される最大
誤差の表を作る。ここで展開する理論は、判定基準それ
自身の最大許容誤差および受容可能な複雑さに関する仮
定の異なる組合せに基づいて、全く異なる試験判定基準
を選択するのにもやはり使用することができることに注
目すべきである。事実、異なる場合について異なる試験
判定基準を選択することさえできる。ここに示す試験判
定基準は下に掲げる３つの望ましい資質に基づいて選択
した。

【０１８３】１．試験するのに簡単である。 ２．広範囲の曲線にわたって使用できる。 ３．線幅に関して導入される最大誤差が受容可能であ
る。

【０１８４】θおよびｋをそれぞれ、先に規定したよう
な所定放物線の夾角およびねじれとすれば、下記試験を
行って放物線を細分割すべきか否かを決定することがで
きる。放物線を細分割するときはすべて方程式５．４．
１４で与えられる点で行われる。

【０１８５】下記試験はｋの許容範囲を、画線幅に対す
る最大誤差限界が所定幅の１．２５％に設定されている
とき、夾角の余弦の関数として与える。

【０１８６】 -0.391≧cosθ＞-0.843:1(-0.11-3.61cosθ)≦ｋ≦(-0.11-3.61cosθ) -0.843≧cosθ＞-0.940:1(-21.00-28.25cosθ)≦ｋ≦(-21.00-28.25cosθ) -0.940≧cosθ＞-0.980:1(-334.76-362.00cosθ)≦ｋ≦(-334.76-362.00cosθ) -0.980≧cosθ＞-1.000:0≦ｋ≦∞

【０１８７】下記試験はｋの許容範囲を、画線幅に対す
る最大誤差限界が所要幅の２．５０％に設定されている
とき、夾角の余弦の関数として与える。

【０１８８】 -0.340≧cosθ＞-0.891:1(-1.19-6.75cosθ)≦ｋ≦(-1.19-6.75cosθ) -0.891≧cosθ＞-0.965:1(-160.50-187.50cosθ)≦ｋ≦(-160.50-187.50cosθ) -0.965≧cosθ＞-1.000:0≦ｋ≦∞

【０１８９】下記試験はｋの許容範囲を、画線幅に対す
る最大誤差限界が所要幅の５．００％に設定されている
とき、夾角の余弦の関数として与える。

【０１９０】 -0.010≧cosθ＞-0.710:1(-1.70-4.20cosθ)≦ｋ≦(-1.70-4.20cosθ) -0.710≧cosθ＞-0.874:1(-21.50-37.00cosθ)≦ｋ≦(-21.50-37.00cosθ) -0.874≧cosθ＞-0.950:1(-880.00-1020.00cosθ)≦k≦(-880.00-1020.00cosθ) -0.950≧cosθ＞-1.000:0≦ｋ≦∞

【０１９１】上に示した条件における夾角の余弦は、制
御点を知れば、方程式５．４．９を使用して三角法の演
算を行わずに直接計算することができることに注目され
たい。このようにして計算するには一つの除算、一つの
平方根の演算、および幾つかの加算および除算が必要で
ある。考察中の放物線を他の放物線を細分割することに
より得ている場合には、この放物線に対する新しい夾角
の余弦を親放物線に対する夾角の余弦を知って方程式
５．４．２９を使用して更に容易に計算することができ
る。

【０１９２】図１６から図２１までは、ｋに対する限界
を上に示した方程式に従って選択した場合の実際の最大
誤差限界を夾角の関数としてプロットしたものである。
三つのプロットは設計最大誤差限界をそれぞれ１．２５
％，２．５％，および０．５０％になるように選んだ三
つの場合に対応する。図はまた夾角の関数としてのｋの
プロットを示している。

【０１９３】本発明について特定の実施例を参照して説
明してきたが、当業者には本発明の真の精神および範囲
から逸脱することなく、各種変更を行うことができ、そ
の要素について同等なものを置き換えることができるこ
とを理解するであろう。加えて、多数の修正を本発明の
本質的教示から逸脱することなく行うことができる。

【図面の簡単な説明】

【図１】 第１章の解析例に使用した曲線である。

【図２】 第１章の解析例に使用した曲線である。

【図３】 ３次曲線スプラインを理解する際の補助のた
めの説明図である。

【図４】 円錐曲線を理解する際の補助のための説明図
である。

【図５】 ３次曲線スプラインを放物線セグメントで近
似するアルゴリズムのフローチャートである。

【図６】 円弧を放物線セグメントで近似するアルゴリ
ズムのフローチャートである。

【図７】 円錐曲線を放物線セグメントで近似するアル
ゴリズムのフローチャートである。

【図８】 放物線を線分に分解するアルゴリズムのフロ
ーチャートである。

【図９】 放物線を副放物線に分解し、パラゾイドを発
生するアルゴリズムのフローチャートである。

【図１０】 円弧の近似を示す説明図である。

【図１１】 放物線軌道を示す説明図である。

【図１２】 任意の放物線を正規化放物線に変換する際
に関係するステップを示す。

【図１３】 放物線の一例を示す説明図である。

【図１４】 最大ねじれを夾角の関数として示すグラフ
である。

【図１５】 第５．４章で規定した放物線を示す図であ
る。

【図１６】 ねじれと夾角との間の関係を示すグラフで
ある。

【図１７】 ねじれと夾角との間の関係を示すグラフで
ある。

【図１８】 ねじれと夾角との間の関係を示すグラフで
ある。

【図１９】 ねじれと夾角との間の関係を示すグラフで
ある。

【図２０】 ねじれと夾角との間の関係を示すグラフで
ある。

【図２１】 ねじれと夾角との間の関係を示すグラフで
ある。

Claims (3)

【特許請求の範囲】
1. 【請求項１】 コンピュータで生成された、ページ記述
   言語で記述された画像をラスタ出力スキャナ上に表示す
   るための、次のステップを含む方法： 前記ページ記述言語から、ページ記述言語で記述される
   軌道を生成するステップ； 前記軌道の一部を近似する原放物線によって、前記軌道
   の一部を、予め定められた誤差範囲内に近似するステッ
   プ； 前記原放物線に対し、共に前記原放物線に対し平行で、
   かつ該原放物線から予め定められた距離離れた２つの曲
   線を構成する近似放物線の一組を生成するステップであ
   って、この生成ステップは次のことを含む： ａ．各セグメントに対して近似放物線を生成し得るよう
   に、原放物線が分割されるべきセグメント数を決定し、 ｂ．原放物線を前記セグメント数に分割し、そして ｃ．前記セグメントのそれぞれに対して前記近似放物線
   を生成する。 前記近似放物線の組をビットマップに変換し、同ビット
   マップをラスタ出力スキャナに送るステップ。
2. 【請求項２】 前記決定ステップが次のことを含む請求
   項１記載の方法： ａ．制御点Ａ，Ｂ，Ｃを持つ原放物線を、ＡＢおよびＢ
   Ｃの長さの長い方を短い方により分割することによって
   試験し、そしてその結果Ｋを夾角ＡＢＣの関数であるあ
   る制限値と比較し、 ｂ．もしその結果が前記制限値よりも小さければ、放物
   線は細分割不要とし、 ｃ．もしその結果が前記制限値よりも大きければ、放物
   線を細分割し、そして結果的に得られた各セグメントに
   ついて、ａのステップに戻って処理を行う。
3. 【請求項３】 各近似放物線Ａ，Ｂ，Ｃに対する前記発
   生のステップが、次のことを含む、請求項１記載の方
   法。 ＡＢおよびＢＣにそれぞれ平行な線Ａ₁ Ｂ₁ およびＢ₁
   Ｃ₁ を決定し、そして 前記近似放物線を生成するために制御点Ａ₁ Ｂ₁ Ｃ₁ を
   用いる。