JPH11191155A - ピーカー検知及び補正 - Google Patents

Abstract

(57)【要約】 【課題】 印刷するための分解能独立性頁記述をラスタ
ライズするための改良した方法及び装置を提供する。 【解決手段】 ピーカー（即ち、プリンタピクセルより
幅狭のベクトル表示における２つの可視的なエッジの間
のギャップ）が第一可視的エッジと第二可視的エッジと
の間において識別され、且つ該エッジのうちの少なくと
も一方に対してカラー調節が行なわれる。１実施形態に
おいては、第一可視的エッジの側部に対面する第二可視
的エッジの側部が識別される。第一可視的エッジの識別
された側部のカラーが、第二可視的エッジの識別された
側部のカラーに基づいて変更される。このカラー調節は
トラッピング方法に関連して有益的なものである。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は頁を正確にトラッピ
ング処理することが可能であるように頁記述言語で記述
されているカラー頁を修正する技術に関するものであ
る。

【０００２】

【従来の技術】印刷業界においては、プレスレジストレ
ーション即ち版位置合わせは印刷した用紙上でのインク
の２つ又はそれ以上のカラーの正確な位置決めである。
用紙上のカラーが位置合わせされている場合には、カラ
ーの間でのギャップ又はカラーのオーバーラップなし
で、全てのカラーが意図された箇所において正確に表わ
れる。位置ずれは多数のファクターによって発生され、
例えば製版におけるエラー及び製版前のフィルム取扱い
におけるエラー、印刷機のメンテナンスがよくないこ
と、又はオペレータのトレーニングがよくないこと、用
紙の精度がよくないか又は不安定であること、及び環境
制御が欠如していること等がある。位置ずれの１つの結
果は、印刷しない箇所であることを意図したものではな
い箇所においてカラー間における印刷されない部分が発
生することである。例え小さな位置ずれであっても、用
紙上のカラー間に細い白色のラインが発生する場合があ
る。

【０００３】トラッピングは、印刷前において意図的に
カラーをオーバーラップさせることによって版ずれを保
証するプロセスである。例えば、スプレッドトラップは
背景カラーとオーバーラップさせるために前景イメージ
のカラーを拡大させるものである。逆に、チョークトラ
ップは前景イメージとオーバーラップさせるために背景
カラーを拡大させるものである。トラップと呼ばれるオ
ーバーラップを形成するために付加されるカラーの区域
は位置ずれ即ち版ずれによって発生されるギャップに対
するある程度の保護を与える。トラップカラーは背景又
は前景のカラーと同一のものとすることが可能である
が、その必要性はない。トラッピングはどこにトラップ
を配置させるかを決定し、且つ人間の目にとって気が付
くことが最小のものであるように発生しうる版ずれを補
正するためのトラップの寸法及びカラーを設定するもの
である。

【０００４】分解能独立性要素を使用して頁を記述する
ために例えばアドビ社のポストスクリプト（ＰｏｓｔＳ
ｃｒｉｐｔ）（商標）言語のような頁記述言語（ＰＤ
Ｌ）を使用して頁を設計することが電子出版業界におい
て行なわれている。ポストスクリプトにおいては、パス
とは、エッジと呼称される順番付けされ指向付けされ接
続された直線的なラインセグメントの集まりである。頁
上において１つの形状として表われるパスは閉じられな
ければならない。パス内の各エッジは開始点（ｆｒｏｍ
ｐｏｉｎｔ）及び到達点（ｔｏ ｐｏｉｎｔ）を有し
ており、それらはエッジの位置と方向とを画定する。１
つのパス内の１個のエッジの開始点は該パス内のその次
のエッジの開始点と同一の点であり、且つ該パス内の最
後のエッジの到達点は該パス内の第一エッジの開始点と
同一の点である。パス内のエッジは交差することが可能
である。

【０００５】オブジェクトは全てが単一のカラーで充填
されているか又は描かれている１つ又はそれ以上のパス
から構成することが可能である。オブジェクトはＺ順又
はペイント順とも呼称される独特のシーケンスナンバー
を有しており、それは該オブジェクト内のパスの各々に
よって共用される。オブジェクトのシーケンスナンバー
は、他のオブジェクトに関連してその頁上にいつそのオ
ブジェクトを描画するかを特定する。最も低いシーケン
スナンバーを有するオブジェクトが最初に描画され、次
いで次に最も低いシーケンスナンバーを有するオブジェ
クトが続く。このオブジェクトの逐次的な描画はより高
いシーケンスナンバーを有する他のオブジェクトによっ
て部分的に又は完全に閉塞されている１つのオブジェク
トとなることが可能である。

【０００６】プリンタ等の出力装置上においてポストス
クリプト頁（即ち頁のポストスクリプト言語記述）をレ
ンダリングさせるためには、その頁を、最初に、ラスタ
ライズせねばならず、即ち、その頁のベクトル表現をピ
クセルの二次元アレイへ変換せねばならない。出力装置
の分解能は、単位面積当たり又は単位距離当たりの出力
装置の出力媒体上でのピクセル数によって画定される。

【０００７】ポストスクリプト頁記述を解析して、トラ
ップを包含する新たなポストスクリプト頁記述を発生す
ることが可能である。次いで、この新たなポストスクリ
プト頁記述を使用して、従来の方法に従って、トラップ
を有する頁をレンダリングさせることが可能である。一
方、ポストスクリプト頁を最初にラスタライズさせ、そ
の後に、ラスタライズした頁を解析することによってラ
スタライズ形態でトラップを発生させることが可能であ
る。

【０００８】

【発明が解決しようとする課題】本発明は、以上の点に
鑑みなされたものであって、上述した如き従来技術の欠
点を解消し、印刷用の分解能独立性頁記述をラスタライ
ズする改良した方法及び装置を提供することを目的とす
る。

【０００９】

【課題を解決するための手段】ピーカー（ｐｅｅｋｅ
ｒ）は、ベクトルをレンダリングさせるべき出力装置の
分解能における装置ピクセルよりもより幅狭のベクトル
表示における２つのエッジ間のギャップのことである。
本発明は、ピーカーが存在する場合に正確にトラップを
発生することが可能であるように、ラスタライズ形態で
レンダリングされるべきベクトルイメージを修正する。
特に、本発明は、ベクトル空間カラー遷移を補正し、従
ってそれらはラスタライズ形態においてカラー遷移と一
致する。

【００１０】１側面においては、本発明はトラッピング
用の領域の分解能独立性表現を用意する。特に、該領域
内の第一エッジと該領域内の第二エッジとの間において
ピーカーを見つけ出し且つ該第一エッジがラスタライズ
形態でレンダリングされる場合に該第一エッジと該第二
エッジとの間において該第一エッジの側部に当接する当
接カラーを識別する。次いで、該第一エッジと該第二エ
ッジとの間の該第一エッジの側部上の該第一エッジのカ
ラーを該当接カラーへ変化させる。次いで、該領域をト
ラッピング即ちトラップ処理し且つ例えばプリンタ等の
出力装置上でレンダリングさせる。

【００１１】別の側面においては、本発明は他のパス内
の他のエッジの内部カラーから派生された情報に基づい
て１つのパス内の分解能独立性エッジの外部カラーを識
別する。次いで、そのようにして識別された外部カラー
は、ピーカー検知及びカラー補正において、及びトラッ
ピングにおいて効果的に使用することが可能である。本
発明は以下に記載するような１つ又はそれ以上の技術的
な効果を有している。

【００１２】本発明の１つの利点は、ラスタライズを行
なう前にそれらがベクトル形態にある状態でオブジェク
トに関してピーカーカラー補正を実施することである。
このことはそれ自身によってラスタライズされた頁に基
づいてトラッピングを行なうよりもトラップをより正確
に位置決めする基礎を提供している。更に、本発明は分
解能独立性トラッピングに対する基礎を提供しているの
で、本発明に従ってトラッピングされた頁は、再度トラ
ッピングする必要性なしに多数の分解能においてレンダ
リングすることが可能である。

【００１３】本発明の別の利点は、ベクトル表現の使用
が、ラスタライズ期間中に失われるオブジェクトに関し
ての情報を保存し、エッジテーブルのより完全且つ多様
な処理を行なうことを可能としていることである。

【００１４】更に、ベクトル空間は、ラスター空間より
もある区域のレンダリングさせた様相をより効率的に表
現するものであり、長さにおいて数百個のピクセルから
なるカラー遷移はベクトル形態において１つの小さなデ
ータ構造において記述することが可能である。この格納
効率は高い処理能力及び効率的なトラッピング性能を得
る上で重要なものである。

【００１５】

【発明の実施の形態】図１を参照すると、本発明のピー
カーカラーを検知し且つ補正するＰＤＬ頁をトラッピン
グする方法は、最初に、頁の分解能独立性記述（例え
ば、ポストスクリプトフォーマットにおいて）を獲得し
（ステップ２）、次いで、該頁記述をオブジェクトのリ
ストへ変換する（ステップ４）。次いで、本方法は、該
頁から隠されているエッジを識別し且つ除去し（ステッ
プ６）、且つ該頁上の各エッジの外部カラー及び外部シ
ーケンスナンバーを識別する（ステップ８）。次いで、
本方法は、該頁上のオブジェクトのベクトル表現及び出
力装置上においてラスタライズ形態でその頁がレンダリ
ングされる分解能に関する情報を使用してピーカーを識
別する（ステップ１０）。

【００１６】次いで、本方法は、ピーカーが存在する各
エッジの外部カラーを、出力装置上でレンダリングさせ
た場合に該エッジの外部側部に当接するカラーへ変更さ
せる（ステップ１２）。このことは、ベクトル空間にお
けるエッジ間のカラー遷移を変化させ、従ってそれらは
ラスタライズさせた形態におけるエッジ間のカラー遷移
と一致する。

【００１７】最後に、補正したカラー情報を使用し、多
様なトラッピング方法のうちのいずれかを使用して、該
頁上においてトラッピングを実施する（ステップ１
４）。

【００１８】次に、図１の方法について更に詳細に説明
する。

【００１９】図２ａを参照すると、ポストスクリプトパ
ス１６は順番付けされているエッジＥ１，Ｅ２，Ｅ３，
Ｅ４，Ｅ５，Ｅ６，Ｅ７を有している。第一エッジＥ１
は開始点Ｐ１及び到達点Ｐ２を有している。残りのエッ
ジも、同様に、開始点と到達点とを有しており、それら
は反時計方向においてパス１６の形状を画定し、点Ｐ１
において終了する。パス１６の各エッジをその開始点か
らその到達点へトレースすると、パス１６の内部が該エ
ッジの左側上に画定され、パス１６の外部は該エッジの
右側上に画定される。パス１６における各エッジは該エ
ッジの内部（左）側に関するカラー即ち色を特定する内
部カラーを有している。パス１６の各エッジの内部カラ
ーはイエローであり、出力装置上でレンダリングされた
場合に、パス１６の内部をイエローで表わす。

【００２０】図２ｂを参照すると、ポストスクリプトパ
ス１８は順番付けされているエッジＥ８，Ｅ９，Ｅ１
０，Ｅ１１，Ｅ１２を有している。第一エッジＥ８は開
始点Ｐ３と到達点Ｐ４とを有している。残りのエッジ
は、同様に、開始点と到達点とを有しており、それらは
反時計方向においてパス１８をトレースし、点Ｐ３にお
いて終了する。各エッジの内部カラーはマゼンタであ
り、出力装置上でレンダリングされた場合にパス１８の
内部をマゼンタで表わす。

【００２１】ポストスクリプト頁上のオブジェクトはオ
ーバーラップすることが可能である。従って、幾つかの
オブジェクトエッジは他のオブジェクトによって隠され
る場合があり且つ、従って、その頁を出力装置上でレン
ダリングした場合に見ることができない場合がある。パ
ス１８はパス１６よりも一層高いシーケンスナンバーを
有している場合には、該パスは出力装置によってレンダ
リングされる場合に図２ｃに示したように表われる。図
２ｃに示したように、パス１６の内部領域の一部はパス
１８の内部領域の一部によって閉塞されている。パス１
６のエッジＥ３，Ｅ４，Ｅ５，Ｅ６はパス１８によって
完全に閉塞されており、且つパス１６のエッジＥ２及び
Ｅ７の一部はパス１８によって閉塞されている。

【００２２】ポストスクリプト頁を、例えばポストスク
リプトプリンタ又はイメージセッター等のポストスクリ
プトを使用することの可能な装置へ転送する。トラッピ
ングエンジンが該ポストスクリプト頁を従来の方法を使
用して頁上に表われる１組のオブジェクトへ変換する。
各オブジェクトは共通の独特のシーケンスナンバーを共
用する１つ又はそれ以上のパスから構成されている。

【００２３】１つのパスにおける各エッジは多数の属性
を有している。各エッジは開始点と到達点とを有してお
り、それらは該エッジの位置及び方向を画定する。１つ
のエッジの元の内部カラー及び実効的な内部カラーは該
エッジの内部カラーの値へ初期化される。１つのエッジ
の所有即ち内部シーケンスナンバーはそのエッジが属す
るパスのシーケンスナンバーである。１つのエッジの元
の外部カラー、実効的な外部カラー及び外部シーケンス
ナンバーについて後述する。子エッジ（後に説明する）
もその子のエッジの親のエッジに対する参照を包含して
いる。

【００２４】トラッピングエンジンがポストスクリプト
頁を１組のオブジェクトへ変換した後に、該頁は小さな
矩形状のタイルへ分割される。本発明をこのようなタイ
ルに関して動作するものとして説明するが、それは、
又、タイルへ分割されていない頁に関して動作すること
も可能である。各タイル境界は開始点と、到達点と、内
部カラーとを有している。

【００２５】頁をレンダリングさせた場合に見ることが
可能な１つのタイル内のエッジがエッジテーブル内に記
録される。図３ａを参照すると、トラッピングエンジン
が１つのタイルに対し空のエッジテーブルを形成し且つ
そのエッジテーブルに対して該タイルのタイル境界を付
加する（ステップ２０）。次いで、該タイル内の最も低
いシーケンスナンバーを有するオブジェクトｏが選択さ
れ（ステップ２１）、且つオブジェクトｏのエッジの元
の外部カラーが未知の値へ初期化される。次いで、オブ
ジェクトｏのエッジをエッジテーブルへ付加する（ステ
ップ２３）。

【００２６】次いで、該エッジテーブルに対して隠れラ
イン除去方法を適用する。該隠れライン除去方法は該エ
ッジテーブル内の各エッジを該エッジが別のオブジェク
トの１つのエッジと交差する各点においてより小さな２
つのエッジへ分割する。分割によって発生する各エッジ
はそれが派生されたエッジの元の内部カラー及び内部シ
ーケンスナンバーを継承する。

【００２７】例えば、図２ｄを参照すると、オブジェク
ト１６のエッジＥ２はエッジＥ１３（端点Ｐ２及びＰ７
を有する）及びエッジＥ１４（端点Ｐ７及びＰ５を有す
る）へ分割される。何故ならば、エッジＥ２は点Ｐ７に
おいてオブジェクト１８の境界と交差するからである。
同様に、オブジェクト１６のエッジＥ７は、エッジＥ１
５（端点Ｐ６及びＰ８を有する）とエッジＥ１６（端点
Ｐ８及びＰ１を有する）へ分割される。何故ならば、エ
ッジＥ７は点Ｐ８においてオブジェクト１８の境界と交
差するからである。

【００２８】複合点は、２つを超える可視的なエッジが
交差する点である。図２ｄを参照すると、例えば、点Ｐ
７は複合点である。スプラインはオブジェクト境界を交
差することのない隣接した一連の接続されているエッジ
である。スプラインは複合点において開始及び終了する
か又は単一点において開始及び終了する。隠れライン除
去方法は各オブジェクトを複数個のスプラインへ分割
し、且つ各オブジェクトのエッジの各々を可視的なもの
であるか又は不可視的なもののいずれかとして識別す
る。次いで、各不可視的なスプラインのエッジを該エッ
ジテーブルから除去する。

【００２９】例えば、隠れライン除去方法をオブジェク
ト１６及びオブジェクト１８を包含するタイルに対して
適用した結果として、オブジェクト１６が２つのスプラ
インに分割され、即ちそのうちの１つのスプライン（ｓ
１）はエッジＥ１３，Ｅ１，Ｅ１６を有しており、且つ
他方のスプライン（ｓ２）はエッジＥ１４，Ｅ３，Ｅ
４，Ｅ５，Ｅ６，Ｅ１５を有している。同様に、オブジ
ェクト１８は２つのスプラインへ分割され、そのうちの
一方のスプライン（ｓ３）はエッジＥ２１，Ｅ１７を有
しており、且つ他方のスプライン（ｓ４）はエッジＥ１
８，Ｅ１９，Ｅ２０を有している。スプラインｓ１，ｓ
３，ｓ４は、図２ｃに示したように、可視的なものであ
り、スプラインｓ２は不可視的なものである。

【００３０】隠れライン除去方法がタイル内における可
視的なエッジ及び不可視的なエッジを識別した後に、オ
ブジェクトｏ内の第一の可視的なエッジｅが選択される
（ステップ２６）。エッジｅの元の外部カラーが不知で
ある場合には（ステップ３０）、エッジｅの端点が複合
点にあるか否かを決定する（ステップ３２）。エッジｅ
のいずれかの端点が複合点にある場合には、エッジｅの
外部カラー及び外部シーケンスナンバーに図３ｂの方法
に従って値が割り当てられる（ステップ５０）。次い
で、ステップ２６−５０が該タイル内の各残りの可視的
なエッジに対して繰返し行なわれる。

【００３１】図３ｂを参照すると、複合点ｐと交差する
エッジｅの元の外部カラー及び外部シーケンスナンバー
は以下のようにして値が割り当てられる。隠れエッジ除
去期間中に、点ｐへ接続されている全ての可視的なエッ
ジのリストが維持される。第一に、点ｐへ接続されてい
る可視的なエッジがソーティング即ち種類分けされる
（ステップ５２）。エッジは、点ｐに関して、増加する
角度方向（時計方向）の順番でソーティングされる。ソ
ーティングの目的のために、各エッジの方向は、該エッ
ジがあたかも点ｐから離れる方向に向いているかのよう
に取扱われる。例えば、点Ｐ８におけるエッジ（図２
ｄ）はＥ２０，Ｅ２１，Ｅ１６のようにソーティングさ
れる。注意すべきことであるが、エッジＥ１５は該リス
ト内には含まれていない。何故ならば、それは隠れライ
ン除去方法によって不可視的なものとして以前に識別さ
れていたからである。次に、エッジｅが点ｐに向かって
いる場合には、ラップアラウンドによってソーティング
されたリスト内のｅの前のエッジとしてｅｅが選択され
る（ステップ５３）。エッジｅが点ｐから離れる方向に
向かっている場合には、ラップアラウンドによってソー
ティングされたリスト内のｅに続くエッジとしてｅｅが
選択される（ステップ５４）。換言すると、該リスト内
の第一エッジの前のエッジは該リスト内の最後のエッジ
であり、且つ該リスト内の最後のエッジの後のエッジは
該リスト内の最初のエッジである。例えば、Ｅ２１の前
のエッジはＥ２０であり、且つソーティング順番におい
てＥ１６の後のエッジはＥ２０である。

【００３２】次に、ｅの元の外部カラーはｅの外部に面
するｅｅの側部上のｅｅの元のカラーへ設定され、且つ
ｅの外部シーケンスナンバーはｅの外部に面するｅｅの
側部上のｅｅのシーケンスナンバーへ設定される（ステ
ップ５５）。例えば、図２ｄを参照すると、ｐは点Ｐ８
であり且つｅはエッジＥ２１である場合には、ｅｅはエ
ッジＥ７である。エッジＥ７の内部はエッジＥ２１の外
部へ面している。従って、エッジＥ２１の元の外部カラ
ーはエッジＥ７の元の内部カラー（イエロー）へ設定さ
れ、且つエッジＥ７の内部シーケンスナンバーはエッジ
Ｅ２１の外部シーケンスナンバー内へコピーされる。

【００３３】次いで、エッジｅの元の外部カラー及び外
部シーケンスナンバーは、エッジｅのスプライン内のそ
の他のエッジへ伝搬される（ステップ５７）。次いで、
本方法は図３ａにおけるステップ３４へ進行する（ステ
ップ６０）。

【００３４】図３ａの方法が動作を完了した後に、図３
ｃの方法が、外部カラーがいまだに未知である全てのエ
ッジに対して適用される。図２ｅを参照すると、オブジ
ェクト１６は、タイル境界ＴＢＥ１，ＴＢＥ２，ＴＢＥ
３，ＴＢＥ４を有するタイル１９内の唯一のオブジェク
トである。オブジェクト１６のエッジのいずれもがその
他のオブジェクトのエッジ又はいずれかのタイル境界と
交差することはないので、オブジェクト１６の全てのエ
ッジの外部カラーは、図３ａの方法を適用した後におい
て「未知」に止まる。

【００３５】図３ｃを参照すると、未知の元の外部カラ
ーを有する各エッジｅに対して（ステップ１００）、ベ
クトルｖがｅの中間点から発生しｅの外部に向かってポ
イントするｅに対して垂直に構成される（ステップ１０
５）。例えば、図２ｅを参照すると、ベクトルｖがパス
１６のエッジＥ１に対して垂直に構成される。次いで、
本方法は、それがｅと同一のオブジェクト内に存在する
ものではない（ステップ１１５）エッジ又はタイル境界
のいずれかと交差するまで（交差されたエッジｉｅとし
て呼称する）ｖを追従する（ステップ１１０）。例え
ば、図２ｅを参照すると、ベクトルｖはタイル境界ＴＢ
Ｅ２を交差する。ｖがｉｅの外部と交差する場合には、
ｅの元の外部カラーがｉｅの元の外部カラーの値が割り
当てられ、且つｅの外部シーケンスナンバーはｉｅの外
部シーケンスナンバーの値が割り当てられる（ステップ
１２５）。そうでない場合には、ｅの元の外部カラーが
ｉｅの元の内部カラーの値が割り当てられ、且つｅの外
部シーケンスナンバーはｉｅの内部シーケンスナンバー
の値が割り当てられる（ステップ１２０）。次いで、ｅ
の元の外部カラー及び外部シーケンスナンバーはｅのス
プライン内のその他のエッジへ伝搬される（ステップ１
３０）。例えば、図２ｅを参照すると、ベクトルｖはＴ
ＢＥ２の内部と交差する。従って、エッジＥ１の元の外
部カラーは、タイル境界ＴＢＥ２の元の内部カラー及び
元の内部シーケンスナンバーの値が割り当てられ、次い
で、それらは両方ともエッジＥ２，Ｅ３，Ｅ４，Ｅ５，
Ｅ６，Ｅ７へ伝搬される。

【００３６】図４ａを参照すると、それらの分解能独立
性ベクトル表現において、オブジェクト２００及びオブ
ジェクト３００は互いに近づくが、オブジェクト２００
の頂部エッジ２４０近くにおいて接触するか又はオーバ
ーラップすることはない。オブジェクト２００の内部カ
ラーはシアンであり、オブジェクト３００の内部カラー
はマゼンタであり、背景カラーはグリーンである。図示
していないが、オブジェクト３００の曲線は多数の直線
接続されたエッジによってベクトル形態で表わされてい
る。

【００３７】図４ｂはオブジェクト２００の上部エッジ
２４０とオブジェクト３００の底部との間の距離よりも
小さな分解能で装置上でラスタライズした場合に、ボッ
クス３１０内のオブジェクト２００及び３００の部分の
可能なラスタライズ化を示している。

【００３８】図４ｂに示したように、それらのベクトル
表現においては、これらのオブジェクトは接触又はオー
バーラップするものではなくとも、オブジェクト３００
を表わすピクセルはオブジェクト２００を表わすピクセ
ルと接触している。従って、図４ａにおけるベクトル表
示においては、エッジ２４０の外部上のカラーはグリー
ン（背景色）であるが、ラスタライズ形態においては、
エッジ２４０の外部のカラー部分はマゼンタである。従
って、グリーンの外部カラーにのみ基づくトラッピング
エッジ２４０は不正確な結果となる。本発明方法及び装
置は、この場合において、即ち、例えそれらのベクトル
表示が接触しない場合であっても２つのオブジェクトの
ラスター表示が接触する場合において、適切なトラッピ
ングを与える。

【００３９】ピーカー（ｐｅｅｋｅｒ）は、ベクトルが
レンダリングされるべき出力装置の分解能においての装
置ピクセルより幅狭のベクトル表示における２つのエッ
ジの間のギャップである。２つのエッジの間にピーカー
が存在する場合には、それら２つのエッジの間のギャッ
プ内側のカラーは、その頁がラスタライズ形態でレンダ
リングされた場合に可視的なものではない。ピーカーが
存在する場合には、それら２つのエッジの間のカラー
は、正確なトラップを発生することが可能であるように
適宜のカラーへ設定することが必要である。

【００４０】ピーカー距離ＰＤは、ピーカーが存在する
ものと考えられる２つのエッジの間の最大距離として定
義される。トラップ幅は、それらの間においてトラップ
が必要とされる２つのオブジェクトのうちのより暗いも
のの中へトラップが投影する距離である。０．２５ポイ
ントのトラップ幅の場合、ＰＤは、その頁がレンダリン
グされるべき出力装置上のピクセルの最も短い軸の長さ
（最高のｄｐｉ）の２倍に選択される。ＰＤは（ｍａｘ
（ｈ，ｖ）／１２００）×ｌとして固定することも可能
であり、尚ｍａｘは最大値であり、ｈはインチ当たりの
ドット数においての出力装置の水平分解能であり、ｖは
インチ当たりのドット数においての出力装置の垂直分解
能であり、ｌは出力装置上のピクセルの最も短い軸の長
さである。ＰＤを計算するためのその方法を使用するこ
とも可能である。例えば、ＰＤは０乃至９００ｄｐｉの
分解能の場合にはｌに等しくすることが可能であり、９
００乃至１８００ｄｐｉの分解能の場合には１．５×ｌ
と等しくすることが可能であり、且つ１８００ｄｐｉよ
り大きな分解能の場合には（ｍａｘ（ｈ×ｖ）／１２０
０）×ｌと等しくすることが可能である。より幅狭のト
ラップ幅の場合には、ＰＤは適宜スケールダウンすべき
である。

【００４１】図５を参照すると、ピーカー検知及び補正
のフェーズ１（６００）は以下のようにしてタイル内の
エッジの各々を処理する。第一に、タイルのエッジテー
ブルからエッジｅを選択する（ステップ６０５）。エッ
ジは任意の順番で選択することが可能である。エッジｅ
が２個のピーカー距離の長さよりも小さい場合には、エ
ッジｅはフェーズ１によって処理することは必要ではな
い（ステップ６１０）。そうでない場合には、図６ａに
示したように、エッジｅの周りに矩形ｒが構成される
（図５、ステップ６２０）。エッジｅは開始点８００と
到達点８０５とを有している。矩形ｒは角部８２０，８
２５，８３５，８４０を有している。矩形ｒは、以下の
対の点（８１０，８２０），（８１０，８２５），（８
１５，８３５），（８１５，８４０），（８１０，８０
０），（８１５，８０５）の各々における２つの点の間
の距離がＰＤであるように構成される。

【００４２】次に、ステップ６８０において形成された
端点を除いて、矩形ｒ内に該当する全てのエッジ端点を
ポイントリストへ付加する（ステップ６３０）。次に、
ポイントリスト内の各端点ｅｐに対して、図６ｂに示し
たように、ｅに対して垂直の方向においてｅｐからｅへ
ライン８６０を描くことによってｅ上の分割点８７０を
識別する（ステップ６６０）。

【００４３】ｅに対する分割点を識別した後に、選択し
た分割点を除去し、従って２つの分割点がＰＤより大き
な距離だけ離隔しているものはない（ステップ６７
０）。次いで、エッジｅを各分割点において複数個の子
エッジへ分割する（ステップ６８０）。エッジｅに対す
る参照は、エッジｅの子エッジの各々に格納される。エ
ッジｅの内部及び外部カラーは、子エッジの元の内部カ
ラー及び元の外部カラーとして夫々エッジｅの子エッジ
の各々の中に格納される（ステップ６９０）。子エッジ
へ分割した後に、エッジｅはエッジテーブルから除去さ
れ且つ親エッジとして呼称される。例えば、図６ｂを参
照すると、エッジｅは２個の子エッジへ分割されてい
る。１つの子エッジは点８００において開始点を有して
おり且つ点８７０において到達点を有している。他方の
子エッジは点８７０において開始点を有しており且つ点
８０５において到達点を有している。

【００４４】エッジｅが該タイル内の最後のエッジでな
かった場合には（ステップ７００）、フェーズ１（６０
０）の方法は該タイル内の残りのエッジに対して繰返し
行なわれる。フェーズ１（６００）が完了した後に、本
方法はフェーズ２へ進行する（ステップ１０００）。

【００４５】フェーズ２は以下のようにしてタイルのエ
ッジテーブル内のエッジの各々を処理する。図７ａを参
照すると、最初に、テストエッジとして呼称される１個
の可視的なエッジがエッジテーブルから選択される（ス
テップ１０１０）。可視的なエッジは任意の順番でテス
トエッジとして選択することが可能である。テストエッ
ジの長さがピーカー距離の２倍よりも一層大きなもので
ある場合には（ステップ１０１５）、エッジオブジェク
トポインタｔｅｌは該テストエッジに対してポイントへ
するように設定される（ステップ１０２５）。図８ａを
参照すると、ｔｅｌは開始点１３３０と到達点１３４０
とを有している。幅２×ＰＤを有する開始ピーカー正方
形１３１０として呼称される正方形がエッジｔｅｌの開
始点１３３０を中心として描画される（ステップ１０３
０）。開始ピーカー正方形１３１０の２つの平行なエッ
ジはエッジｔｅｌに対して平行であり、該開始ピーカー
正方形１３１０の他の２つの平行なエッジはエッジｔｅ
ｌに対して垂直である。

【００４６】次に、エッジテーブル内のエッジの各々の
端点（ｔｅｌの端点を包含するものではない）を検査
し、且つ開始ピーカー正方形１３１０内にある各端点で
開始点リストを充填することによって開始点リストを形
成する（ステップ１０４０）。次いで、開始点リスト内
の点が属するエッジの全てを開始エッジリスト内に格納
する（ステップ１０５０）。次いで、ステップ１０３０
−１０５０を、到達ピーカー正方形１３２０を使用し
て、エッジｔｅｌの到達点１３４０に対して繰返し行な
う（ステップ１０６０−１０８０）。

【００４７】開始エッジリスト及び到達エッジリストを
形成した後に、候補ピーカーエッジのリスト（候補リス
ト）を形成する（ステップ１０９０−１０９２）。最初
に、開始エッジリスト及び到達エッジリストの両方のメ
ンバーであるエッジを候補リストへ付加する（ステップ
１０９０）。次いで、開始エッジリスト内の子エッジ及
び到達リスト内の別の子エッジを有する親エッジが候補
リストへ付加される（ステップ１０９２）。例えば、図
８ｂを参照すると、エッジ１３６０はエッジｔｅｌの到
達ピーカー正方形１３２０内に開始点１３６２を有して
おり且つエッジｔｅｌの開始ピーカー正方形１３１０内
に到達点１３６４を有している。従って、エッジ１３６
０はステップ１１５０においてエッジｔｅｌの候補リス
トへ付加される。エッジ１３３６は親エッジである。エ
ッジ１３６６の１個の子はエッジｔｅｌの開始ピーカー
正方形内の開始点１３６８を有しており且つ到達点１３
７０を有している。エッジ１３６６の他方の子は開始点
１３７０を有しており、且つエッジｔｅｌの到達ピーカ
ー正方形内に到達点１３７２を有している。従って、親
エッジ１３６６はステップ１１６０においてエッジｔｅ
ｌの候補リストへ付加される。次に、該候補は図７ｃの
方法に従って処理される（ステップ１０９４）。

【００４８】図７ｂを参照すると、テストエッジの長さ
が２×ＰＤ以下である場合には（ステップ１０２０）、
エッジオブジェクトポインタｔｅ２は該テストエッジに
対してポイントすべく設定される（ステップ１１０
０）。図８ｃに示したように、ｔｅ２の周りに単一のピ
ーカー矩形１３５０が描画される（ステップ１１０
２）。ピーカー矩形１３０５の幅はｔｅ２の長さに等し
く、且つｔｅ２はピーカー矩形１３５０を各々が高さＰ
Ｄである等しい矩形の半分へ分割する。ｔｅ２の端点を
包含するピーカー矩形１３５０内の全ての端点の単一点
リストが形成され（ステップ１１０４）、且つ該ポイン
トリスト内の１つ又は両方の端点を有する全てのエッジ
を包含する単一エッジリストが形成される（ステップ１
１０６）。次いで、該候補リストをエッジリスト内のエ
ッジの全てで充填する（ステップ１１０８）。例えば、
図８ｄを参照すると、エッジ１３８０はエッジｔｅ２の
ピーカー正方形１３５０内に開始点１３８２及び到達点
１３８４を有している。従って、エッジ１３８０はステ
ップ１１０８においてエッジｔｅ２の候補リストへ付加
される。次いで、該候補は図７ｃの方法に従って処理さ
れる（ステップ１０９４）。１個のエッジが該候補リス
ト内に配置された場合に、該エッジに関する以下の情報
がデータ構造内に格納される。即ち、（１）エッジテー
ブル内の候補エッジに対するポインタ、（２）テストエ
ッジに関連する候補エッジの開始点の位置（左、右又は
同軸上）、（３）テストエッジに関係する候補エッジの
到達点の位置（左、右又は同軸上）、及び（４）ラジア
ンで測定した候補エッジとテストエッジとの間の方向に
おける差異。

【００４９】図７ｃを参照すると、ピーカー候補リスト
が作成された後に、候補リスト内の各候補エッジが処理
される。最初に、テストエッジの左側上の少なくとも１
個の端点を有し且つテストエッジの右側上の端点を有す
ることのない候補エッジが処理される（ステップ１１２
０）。特に、図７ｄを参照すると、テストエッジの実効
的な内部カラーが処理中の候補エッジの中から最も高い
シーケンスナンバーを有する候補エッジの内部カラーへ
設定される（ステップ１１４０）。

【００５０】次に、テストエッジの右側上に少なくとも
１個の端点を有し且つテストエッジの左側上の端点を有
することのない候補エッジが処理される（ステップ１１
２５、図７ｅ）。最初にテストエッジと同一のオブジェ
クトからの候補エッジが、それらがテストエッジに対し
ほぼ反対の方向にポイントするものではない場合に、考
慮から外され、特に、方向における差異が３π／４ラジ
アンより小さいか又は５π／４ラジアンよりも大きい場
合には排除される（ステップ１１５０）。残りの候補エ
ッジから、最も高い内部シーケンスナンバーを有する候
補エッジが識別される（ステップ１１５５）。テストエ
ッジと識別された候補エッジとの間の方向に関する差異
がπ／２ラジアン以上である場合には、該テストエッジ
の実効的な外部カラーが識別された候補エッジの元の内
部カラーへ設定される（ステップ１１６０）。テストエ
ッジと識別された候補エッジとの間の方向に関する差異
がπ／２ラジアン未満である場合には、該テストエッジ
の実効的な外部カラーは識別された候補エッジの元の外
部カラーへ設定される（ステップ１１７０）。

【００５１】次に、図７ｆを参照すると、両方の端点に
おいてテストエッジで共に終端する候補エッジが処理さ
れる（ステップ１１３０）。最初に、変数ＭＬＳＮ（そ
れまでに遭遇した最も高い候補左シーケンスナンバーを
表わす）及びＭＲＳＮ（それまでに遭遇した最も高い候
補右シーケンスナンバーを表わす）が−１へ初期化され
る（ステップ１２００）。変数ＴＬＳＮはテストエッジ
の左シーケンスナンバーに対するポインタであり、且つ
ＴＲＳＮはテストエッジの右シーケンスナンバーに対す
るポインタである（ステップ１２００）。

【００５２】候補ｃが選択される（ステップ１２２
２）。変数ＣＬＳＮがｃの左シーケンスナンバーに割り
当てられ、且つ変数ＣＲＳＮがｃの右シーケンスナンバ
ーに割り当てられる（ステップ１２０４）。ｃがテスト
エッジと同一の方向にポイントしている場合には（ステ
ップ１２０６）、ＣＬＳＮ＞ＴＬＳＮ及びＣＬＳＮ＞Ｍ
ＬＳＮであり、従ってテストエッジの実効左カラーはｃ
の元の左カラーに割り当てられ、且つＭＬＳＮはＣＬＳ
Ｎの値が割り当てられる（ステップ１２２０−１２２
４）。ｃがテストエッジと同一の方向にポイントしてい
る場合には（ステップ１２０６）、ＣＲＳＮ＞ＴＲＳＮ
及びＣＲＳＮ＞ＭＲＳＮであり、従ってテストエッジの
実効右カラーはｃの元の右カラーが割り当てられ、且つ
ＭＲＳＮはＣＲＳＮの値が割り当てられる（ステップ１
２２６−１２３０）。ｃがテストエッジと反対の方向に
ポイントしている場合には（ステップ１２０６）、ＣＬ
ＳＮ＞ＴＲＳＮ及びＣＬＳＮ＞ＭＬＳＮであり、従って
テストエッジの実効右カラーはｃの元の左カラーが割り
当てられ、且つＭＬＳＮはＣＬＳＮの値が割り当てられ
る（ステップ１２０８−１２１２）。ｃがテストエッジ
と反対の方向にポイントしている場合には（ステップ１
２０６）、ＣＲＳＮ＞ＴＬＳＮ及びＣＲＳＮ＞ＭＲＳＮ
であり、従ってテストエッジの実効左カラーはｃの元の
右カラーが割り当てられ、且つＭＬＳＮはＣＬＳＮの値
が割り当てられる（ステップ１２１４−１２１８）。

【００５３】ピーカー検知及び補正を実施した後に、頁
上のエッジの実効内部及び実効外部カラーを使用してト
ラッピングを実施することが可能である。トラッピング
（トラップ処理）はトラップを配置させるか否か及びど
こに配置させるかを決定し、且つトラップが設定される
べき場合には、そのトラップのカラーはどのカラーとす
べきかを決定する。典型的に、トラップエンジンがエッ
ジテーブル内の各エッジの両側上の実効カラーを検査
し、トラップが必要とされるか否かを決定する。トラッ
プが必要とされる場合には、トラップエンジンがそのト
ラップのカラーをどのカラーとすべきかを決定する。エ
ッジがベクトル形態にある場合にトラッピングを実施す
ることが可能であり、又は、ラスタライズさせた頁上で
実施することも可能である。

【００５４】図９を参照すると、本発明はコンピュータ
ハードウエア、ファームウエア、ソフトウエア又はそれ
らの組合わせ又はデジタル電子回路の形態で実現するこ
とが可能である。本発明装置は、コンピュータプロセサ
によって実行するために機械読取可能な格納装置内に明
確に具体化されたコンピュータプログラム製品の形態で
実現することが可能であり、且つ本発明の方法ステップ
は入力データに関して処理を行ない且つ出力を発生する
本発明の機能を実施するプログラムを実行するコンピュ
ータプロセサによって実施することが可能である。

【００５５】適宜のプロセサ１４８０は、一例として、
汎用及び特別目的の両方のプロセサを包含している。一
般的には、プロセサは、ＣＰＵバス１５００を介してリ
ードオンリメモリ（ＲＯＭ）１５２０及び／又はランダ
ムアクセスメモリ（ＲＡＭ）１５１０から命令及びデー
タを受取る。コンピュータは、通常、Ｉ／Ｏインターフ
ェース１４２０を介して動作する大量記憶インターフェ
ース１４４０又は着脱自在なディスク１４１０を介して
動作する内部ディスク１４３０のような格納媒体からプ
ログラム及びデータを受取る。Ｉ／Ｏバス１４５０を介
してＩ／Ｏ装置１４１０，１４３０，１４６０，１４７
０及びプロセサ１４８０及びメモリ１５１０，１５２０
への及びそれからのデータの流れはＩ／Ｏ制御器によっ
て制御される。ユーザ入力はキーボード１４７０、マウ
ス、スタイラス、マイクロフォン、トラックボール、タ
ッチスクリーン、又はその他の入力装置を介して得られ
る。これらの要素は本明細書に記載した方法を実現する
コンピュータプログラムを実行するのに適した従来のデ
スクトップ又はワークステーションコンピュータ及びそ
の他のコンピュータにおいて見出され、それらは任意の
デジタルプリントエンジン１４７５又はマーキングエン
ジン、ディスプレイモニタ１４６０、又は用紙、フィル
ム、ディスプレイスクリーン又はその他の出力媒体上に
カラー又はグレイスケールピクセルを発生させることの
可能なその他のラスター出力装置に関連して使用するこ
とが可能である。

【００５６】一例として、例えばポストスクリプト言語
等の頁記述言語用のインタプリタを実現する印刷装置１
４７５は、プリンタランダムアクセスメモリ（ＲＡＭ）
１５６０及びプリンタリードオンリメモリ（ＲＯＭ）１
５７０上に格納されているプログラム命令（フォント命
令を包含する）を実行し且つプリンタマーキングエンジ
ン１５８０を制御するマイクロプロセサ１５５０を包含
している。ＲＡＭ１５６０は、オプションとして、例え
ばハードディスク（不図示）等の大量記憶装置によって
補充される。

【００５７】コンピュータプログラム命令を明確に具体
化するのに適した格納装置は、一例として、例えばＥＰ
ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ装置等の半導
体メモリ装置を包含する全ての形態の非揮発性メモリ、
内部ハードディスク１０３０及び着脱自在なディスク１
４１０等の磁気ディスク、ＭＯディスク、及びＣＤ−Ｒ
ＯＭディスクを包含している。前述したもののいずれも
が特別に設計されるＡＳＩＣ（応用特定集積回路）によ
って補充されるか又はその中に組込むことが可能であ
る。

【００５８】以上、本発明の具体的実施の態様について
詳細に説明したが、本発明は、上述した具体的実施の態
様にのみ制限されるべきものではなく、本発明の技術的
範囲を逸脱することなしに種々の変形が可能であること
は勿論である。例えば、上述した実施例においては、本
発明の要素をソフトウエアで実現した場合について説明
したが、本発明はソフトウエア又はハードウエア又はフ
ァームウエア又はこれら３つの組合わせで実現すること
も可能である。

【図面の簡単な説明】

【図１】 本発明方法を示したフローチャート。

【図２ａ】 ポストスクリプトパスの一例を示した概略
図。

【図２ｂ】 ポストスクリプトパスの別の例を示した概
略図。

【図２ｃ】 別のポストスクリプトパスを部分的に閉塞
しているポストスクリプトパスを示した概略図。

【図２ｄ】 １つのタイル内の２つのポストスクリプト
パスに対して隠れライン除去アルゴリズムを適用するこ
とによって発生する可視的なエッジと不可視的なエッジ
とを示した概略図。

【図２ｅ】 タイル内のポストスクリプトパス及び該ポ
ストスクリプトパスの外部カラーを識別するために使用
されるベクトルを示した概略図。

【図３ａ】 タイル内のエッジの外部カラー及び外部シ
ーケンスナンバーを識別するために使用される方法を示
したフローチャート。

【図３ｂ】 タイル内のエッジの外部カラー及び外部シ
ーケンスナンバーを識別するために使用される方法を示
したフローチャート。

【図３ｃ】 タイル内のエッジの外部カラー及び外部シ
ーケンスナンバーを識別するために使用される方法を示
したフローチャート。

【図４ａ】 それらの間にピーカーが存在する２つのポ
ストスクリプトパスを示した概略図。

【図４ｂ】 ピーカーの位置において図２ａにおける２
つのオブジェクトの一部をラスタライズする状態を示し
た概略図。

【図５】 ピーカー検知及び補正のフェーズ１のフロー
チャート。

【図６ａ】 図４の方法に従って第一エッジの周りに描
いた第一ピーカー矩形を示した概略図。

【図６ｂ】 第一ピーカー矩形内において発生する第二
エッジ及び第一エッジ上に発生する分割点を示した概略
図。

【図７ａ】 ピーカー検知及び補正のフェーズ２のフロ
ーチャート。

【図７ｂ】 ピーカー検知及び補正のフェーズ２のフロ
ーチャート。

【図７ｃ】 ピーカー検知及び補正のフェーズ２のフロ
ーチャート。

【図７ｄ】 ピーカー検知及び補正のフェーズ２のフロ
ーチャート。

【図７ｅ】 ピーカー検知及び補正のフェーズ２のフロ
ーチャート。

【図７ｆ】 ピーカー検知及び補正のフェーズ２のフロ
ーチャート。

【図８ａ】 ピーカー距離の２倍より長いエッジの端点
周りに描いた２個のピーカー正方形を示した概略図。

【図８ｂ】 各々が各ピーカー正方形内に端点を有する
２つの付加的なエッジを示した概略図。

【図８ｃ】 その長さがピーカー距離の２倍以下である
エッジの周りに描いたピーカー矩形の概略図。

【図８ｄ】 ピーカー矩形内に両方の端点を有する付加
的なエッジを示した概略図。

【図９】 本発明を実現するのに適したコンピュータ及
びコンピュータ要素を示した概略図。

【符号の説明】

１６，１８ ポストスクリプトパス Ｅ エッジ Ｐ 端点 Ｓ スプライン

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ダグラス アール． ベッカー アメリカ合衆国， マサチューセッツ 01432， エイヤー， プリーザント ス トリート 96 (72)発明者 デニス マーシー アメリカ合衆国， ニュー ハンプシャー 03032， オーバーン， エイコーン ロード 18

Claims (14)

【特許請求の範囲】
1. 【請求項１】 トラッピング用の領域の分解能独立性表
   現を用意する方法において、 前記領域内の第一エッジと前記領域内の第二エッジとの
   間のピーカーを見つけ出し、 前記第一エッジがラスタライズ形態でレンダリングされ
   る場合に前記第一エッジと前記第二エッジとの間におい
   て前記第一エッジの側部に当接する当接カラーを識別
   し、 前記第一エッジと前記第二エッジとの間で前記第一エッ
   ジの側部上の前記第一エッジのカラーを前記当接カラー
   へ変化させる、上記各ステップを有することを特徴とす
   る方法。
2. 【請求項２】 請求項１において、前記領域が１つの頁
   であることを特徴とする方法。
3. 【請求項３】 請求項１において、更に、前記変化させ
   たカラーで前記第一エッジ及び前記第二エッジをレンダ
   リングすることを特徴とする方法。
4. 【請求項４】 請求項３において、レンダリングがトラ
   ッピングを包含していることを特徴とする方法。
5. 【請求項５】 請求項１において、ピーカーを見つける
   場合に、 前記分解能独立性表現から複数個のオブジェクトを派生
   させ、前記複数個のオブジェクトの各々は順序付けされ
   接続され指向付けされた直線的なパスエッジから構成さ
   れている１つ又はそれ以上の閉じた指向付けされたパス
   によって画定されており、各オブジェクトは前記オブジ
   ェクトのエッジの各々によって共用される内部シーケン
   スナンバーを有しており、 前記第一エッジと前記第二エッジとの間の距離がピーカ
   ー距離よりも小さい場合には第一エッジと第二エッジと
   の間のピーカーを見つけ出す、ことを特徴とする方法。
6. 【請求項６】 請求項５において、前記ピーカー距離が
   ラスタライズ形態で表現されている前記領域の１個のピ
   クセルの高さに比例していることを特徴とする方法。
7. 【請求項７】 請求項６において、前記ピーカー距離が
   ラスタライズ形態で表現されている前記領域の１個のピ
   クセルの高さの約２倍であることを特徴とする方法。
8. 【請求項８】 請求項５において、前記ピーカー距離が
   ラスタライズ形態で表現されている前記領域の１個のピ
   クセルの幅に比例していることを特徴とする方法。
9. 【請求項９】 請求項５において、前記ピーカー距離が
   ラスタライズ形態で表現されている前記領域の１個のピ
   クセルの幅の約２倍であることを特徴とする方法。
10. 【請求項１０】 第一パスの第一エッジの外部カラーを
    識別する方法において、 前記第一エッジが第二パスの第二エッジと交差する場合
    であり且つ前記第一エッジの外部と対面する前記第二エ
    ッジの側部のカラーが既知である場合には、前記第一エ
    ッジの外部カラーを前記第一エッジの外部と対面する前
    記第二エッジの側部のカラーへ変化させる、ことを特徴
    とする方法。
11. 【請求項１１】 請求項１０において、更に、前記第一
    エッジへ接続しているエッジのカラーを前記第一エッジ
    の外部と対面する前記第二エッジの側部のカラーへ変化
    させることを特徴とする方法。
12. 【請求項１２】 請求項１１において、更に、前記複数
    個の可視的なエッジの第三サブセットの外部カラーを識
    別するために別の方法を適用することを特徴とする方
    法。
13. 【請求項１３】 請求項１２において、前記別の方法
    が、 前記外部カラーが未知である前記第一パスの各エッジか
    らベクトルを発生させ、 前記ベクトルが前記第二エッジの側部と交差する第二パ
    スの第二エッジを識別し、 前記第一エッジの外部カラーを前記ベクトルが前記第二
    エッジと交差する側部上の前記第二エッジのカラーへ変
    化させる、ことを特徴とする方法。
14. 【請求項１４】 請求項１３において、更に、前記第一
    エッジへ接続しているエッジの外部カラーを前記ベクト
    ルが前記第二エッジと交差する側部上の前記第二エッジ
    のカラーへ変化させることを特徴とする方法。