JPH07319444A - アウトライン文字描画方法 - Google Patents

Abstract

(57)【要約】 【目的】 アウトラインデータによる高速塗りつぶしを
実現する。 【構成】 予め文字の輪郭線により囲まれた図形を複数
のポリゴンに分割する。このとき、文字の内部を横切る
ような分割線分１１−１〜１１−３が必要となる。この
分割線分にはポリゴン生成の際に、分割線分である旨を
表示する識別情報を付与しておく。この情報は文字塗り
つぶしの際は無視されるが、文字の輪郭を印刷したり表
示する場合に利用され、識別情報が付与された線分の表
示が抑制される。従って、分割線分を含むポリゴンデー
タ１４により構成されたフォントデータを使用した場合
に、その輪郭表示の際、分割線分の表示が自動的に抑制
される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ＣＲＴディスプレイや
ページプリンタに表示され出力される文字等をアウトラ
インフォントを用いて描画する場合のアウトライン文字
描画方法に関する。

【０００２】

【従来の技術】アウトラインフォントは、文字の形状を
アウトライン即ち輪郭線によって表現する。これは、同
一のフォントデータを用いて文字を拡大、縮小、回転し
て表示出力できる特徴を持つ。このため、アウトライン
フォントはディスプレイやプリンタに広く採用されてい
る。このようなアウトラインフォントの描画を行う場合
には、文字等の輪郭形状を規定する頂点座標を表示画面
上に座標変換した後に、輪郭線で囲まれた領域を一定の
塗りつぶしパタンで塗りつぶす。輪郭線で囲まれた領域
を高速に塗りつぶすための技術は、例えば特願平４−２
０５９８８号に記載されている。

【０００３】

【発明が解決しようとする課題】ところで、上記のよう
な従来のアウトライン文字描画方法には次のような解決
すべき課題があった。既に紹介した従来のアウトライン
フォントの高速塗りつぶし方法では、文字の内部領域を
複数の多角形（ポリゴン）に分割し、ポリゴン毎に塗り
つぶしを実行する。従って、予めフォントデータはこの
ようなポリゴン毎の輪郭線の連鎖構造として加工されて
いる。ところが、このようなデータをそのまま使用する
と、文字の輪郭のみを印刷したり表示しようとすると、
全てのポリゴンの輪郭線が表示され、実際には便宜上の
分割線であって、文字を構成しない分割線も表示されて
しまう。

【０００４】

【課題を解決するための手段】本発明は上記の点を解決
するため、次の構成を採用する。即ち、この方法では、
まず文字の輪郭線を複数の線分に分割し、輪郭線を、各
線分の頂点座標の環状連鎖構造として表現してポリゴン
データを得る場合に、予め設定された基準座標軸につい
て見た輪郭線上の任意の点の位置座標が、極大または極
小となるような輪郭線に囲まれた図形の凹頂点を抽出す
る。次に、前記凹頂点を通る基準座標軸に平行な線分に
より、輪郭線により囲まれた図形を複数のポリゴンに分
割し、凹頂点を通る基準座標軸に平行な線分に分割線分
である旨を表示する識別情報を付与する。その後、文字
を構成する全てのポリゴンについて、分割線分を含まな
い輪郭線を描画する。

【０００５】

【作用】この方法では、アウトラインデータによる高速
塗りつぶしを実現するために、予め文字の輪郭線により
囲まれた図形を複数のポリゴンに分割する。このとき、
文字の内部を横切るような分割線分が必要となる。この
分割線分にはポリゴン生成の際に、分割線分である旨を
表示する識別情報を付与しておく。この情報は文字塗り
つぶしの際は無視されるが、文字の輪郭を印刷したり表
示する場合に利用され、識別情報が付与された線分の表
示が抑制される。従って、分割線分を含むポリゴンデー
タにより構成されたフォントデータを使用した場合に、
その輪郭表示の際、分割線分の表示が自動的に抑制され
る。

【０００６】

【実施例】以下、本発明を図の実施例を用いて詳細に説
明する。図１は、本発明のアウトライン文字描画方法を
示す説明図である。この図は、「Ｗ］の文字の形状が１
３個の頂点Ｖ１〜Ｖ１３から成る多角形で表現され、こ
の多角形がｙ軸に平行な３本の分割線分１１−１〜１１
−３によって４つの単純な形のポリゴン（多角形と同
義）に分割され、分割された４つのポリゴンＰ１，Ｐ
２，Ｐ３，Ｐ４を順番に塗りつぶせばよいことを示して
いる。

【０００７】４つのポリゴンは実際には互いに接触して
いるが、分割線分１１−１〜１１−３のところでｘ方向
に引き離して描いてある。分割線分１１−１は輪郭線上
のｙ座標が極大または極小となる凹頂点１２（ここでは
文字Ｗの頂点Ｖ６）を起点としている。これらのポリゴ
ンはポインタによって関係付けられたポリゴンリスト１
３及びポリゴンデータ１４によってひとまとまりのデー
タとされる。分割された各ポリゴンの形状は、ｙ座標の
極小点と極大点が１個ずつしかなく、任意の水平線と２
個以下の交点を持つ形状であるため、単純な処理手順で
塗りつぶしができる。即ち、多角形の塗りつぶしは、ｘ
軸に平行な走査線と多角形の左右稜線との２個の交点を
求め、その線分上の画素を塗りつぶすことを多角形の極
小頂点から極大頂点に至る全ての走査線について実行す
る。

【０００８】本実施例では、全ての文字のアウトライン
フォントをポリゴン分割して左右稜線データを得て、中
間フォントデータとして記憶装置に格納し、その後表示
面上に文字描画を行う。

【０００９】［ポリゴン分割処理］図２は、図１に示し
たものの原型であるアウトライン文字の例説明図であ
る。また、図３及び図４は本発明によるポリゴン分割フ
ローチャートである。以下、図２の文字「Ｗ］を具体的
にポリゴン分割する処理を用いて説明する。まず、図３
ステップＳ１で１文字分のアウトラインフォントデータ
を読み込む。アウトラインは１個以上の外部輪郭線から
成るものとし、最初は穴を囲む内部輪郭線が存在しない
場合を考える。

【００１０】次に、ステップＳ２で、外部輪郭線の１つ
を頂点の環状連鎖構造として表現したポリゴンデータを
作成する。この例では、外部輪郭線が１個しかなく、そ
のポリゴンデータは、図２の１４個の頂点ｖ１〜ｖ１３
をｖ１から始め、反時計回りに閉ループを形成したもの
となっている。頂点データは、それぞれ次の頂点へのポ
インタ、ｘ座標、ｙ座標、その他の情報を含む記憶ブロ
ックから成る。

【００１１】次に、図３ステップＳ３でポリゴン再帰分
割を行うが、これは図４に示すようなポリゴン再帰分割
処理を実行することである。図４のステップＳ８の頂点
の分類では、始点ｖ１から反時計回りに進んでｘ座標と
ｙ座標の増減を調べ、ｙ座標について極大及び極小点を
検出し、更に各頂点の凹凸を判別する。

【００１２】図５に、この頂点分類結果を示す。図は、
各頂点ｖ１〜ｖ１３について、そのｘ座標とｙ座標を示
し、ｄｘ，ｄｙは頂点を１つ進んだときのｘ座標及びｙ
座標の増減を＋１（増加）、−１（減）または０（増減
なし）で示す。また、ｙ座標が増加を開始する頂点（極
小点）をｓ＝１で、ｙ座標が減少を開始する頂点（極大
点）をｓ＝−１で示し、凸頂点をｔ＝１で、凹頂点をｔ
＝−１で示す。

【００１３】なお、図５の表の各欄は具体的には次式に
よって求めたものである。i ，i+1，i-1 はそれぞれ添
字で、頂点の添字１〜１３に対応する。また、ｓｇｎは
ｓｉｎのことである。 ａ） ｄｘ i＝ｓｇｎ（ｘ i+1−ｘ i） ｂ） ｄｙ i＝ｓｇｎ（ｙ i+1−ｙ i） ｃ） ｄｙ i＝１かつｄｙ i-1＝１のときｓ i＝１ ｄ） ｄｙ i＝−１かつｄｙ i-1＝−１のときｓ i＝−
１ ｅ） その他のとき ｓ i＝０ ｆ） ｔ i＝ｓｇｎ｛（ｘ i+1−ｘ i）（ｙ i−ｙ i-
1）−（ｙ i+1−ｙ i）（ｘ i−ｘ i-1）｝ 但し、 ｇ） ｘ＞０のとき ｓｇｎ（ｘ）＝１ ｈ） ｘ＜０のとき ｓｇｎ（ｘ）＝−１ ｉ） ｘ＝０のとき ｓｇｎ（ｘ）＝０

【００１４】次に、図４のステップＳ９でｙ座標が極大
または極小となる凹頂点を探す。これは、図５におい
て、ｓ＝１またはｓ＝−１で、かつｔ＝−１の頂点であ
る。

【００１５】図５の表からこの条件を満たす頂点は、ｖ
３、ｖ６、及びｖ１１である。これらの頂点から文字の
内部領域に向かって（ｓ＝１なら上方、ｓ＝−１なら下
方に）分割線を引き、内部領域を横断してポリゴンの輪
郭線と最初に出会う点までを分割線分とする（図４ステ
ップＳ１０、Ｓ１１）。こうして得られた３本の垂直線
分を分割線分として文字の内部領域を４個のポリゴンに
分割する（図４ステップＳ１２）。

【００１６】これを図４のフローチャートステップＳ９
〜Ｓ１４に従って逐次的に処理すれば、最初に頂点ｖ３
を通る分割線分ｖ３ｖ１４で左右に分割し、その左側ポ
リゴンを分割線分ｖ６ｖ１５で左右に分割し、更にその
右側ポリゴンを分割線分ｖ１１ｖ１６で分割する。ポリ
ゴンを分割した場合には、分割によって得られたポリゴ
ンデータの輪郭のうち、どの部分が分割線分であるかを
識別できるように、識別情報を付与するものとする。

【００１７】例えば、図１のように分割したポリゴンＰ
１のポリゴンデータは、頂点ｖ１５にｄｉｖ＝１の符号
を付与する。これは、頂点ｖ１５から次の頂点ｖ６まで
が分割線分であることを示す。ポリゴンの分割が終了し
たら、図３ステップＳ３からＳ４に進み、４個のポリゴ
ンの左右稜線リストを作成する。ポリゴン分割の済んだ
ポリゴンデータＰ１〜Ｐ４にステップＳ８と同じ頂点の
分類を行うと図６に示すようになる。

【００１８】図６は、分割された頂点分類リストを示
す。図において、例えばポリゴンＰ１については、ｓ＝
１の極小点ｖ８とｓ＝−１の極大点ｖ１５が各々１個ず
つ存在する。この例では、極小点ｖ８から極大点ｖ１５
まで反時計回りに進んで頂点の連鎖構造を作ったものを
左側稜線リストとし、極小点ｖ８から極大点１５まで時
計回りに進んで頂点の連鎖構造を作ったものを右側稜線
リストとする。図中、ｄｉｖの欄には、頂点ｖ１５が分
割線分である識別情報が示されている。他のポリゴンＰ
２〜Ｐ４も同様である。

【００１９】図７に、ポリゴンリストと左右稜線リスト
説明図を示す。図６のリストを展開すれば、図７のポリ
ゴンリスト上のポリゴンポインタＰ１から枝別れした左
側稜線リスト及び右側稜線リストになる。左側稜線リス
トはポリゴンデータの一部をそのまま用いて作り、右側
稜線リストは、頂点データｖ８及びｖ１５の複製と、ポ
リゴンデータの残りの頂点データを用いて、ポインタの
向きを逆方向にしたリストを作り、ポリゴンポインタＰ
１にポインタを１つ追加し、右側稜線リストを指すよう
にする。右側稜線リストは時計回りになるので、分割線
分についての描画処理を開始する前に、分割線分の識別
情報をその線分の終点でなく、始点データに含まれるよ
うに処理する必要がある。こうして１本の外部輪郭線を
分割した結果のポリゴンリストと、全てのポリゴンの左
右稜線リストが図７のように求められる。

【００２０】以上述べたポリゴン分割処理は、フォント
データに移動、伸縮、回転等の座標変換を施す前のフォ
ントの定義座標値を用いて行われるもので、後に座標変
換をする際に、移動伸縮はするが、文字の回転はしない
ことを前提としている。

【００２１】図３のステップＳ５では、以上述べたポリ
ゴン分割処理を１文字の全ての外部輪郭線に対して実行
したかを判断している。全ての処理終了後はステップＳ
６で、その結果である左右稜線データの単純な集積を新
規のアウトラインフォントとして記憶装置に格納する。
ステップＳ７では、アウトラインデータの定義された全
文字に対して以上のポリゴン分割処理を実行したかを判
断している。これらが終了した結果、中間フォントデー
タが得られる。

【００２２】［ポリゴン描画処理］次に、ポリゴン分割
により得られた中間フォントデータを用いて描画処理を
行う手順を説明する。図８は、本発明の走査変換フロー
チャートを示す。この図は、ある文字列の文字描画にお
いて、最初に文字の内部領域を塗りつぶし、次に文字の
輪郭線を描画するフローチャートである。この図で、ル
ープは文字描画の繰り返し処理を、ループはポリゴ
ン描画の繰り返し処理を、ループはポリゴンの極小点
から極大点までの走査線の描画処理を示す。

【００２３】始めに、ステップＳ１６は、文字列表示コ
マンドを解釈し、実行する準備をする処理である。次
に、ステップＳ１７では、１文字分のポリゴン分割中間
フォントデータを読み込み、ステップＳ１８では全ての
頂点座標に表示面への伸縮と移動から成る座標変換を施
している。ステップＳ１９では左右稜線を構成する全て
の線分の高さと勾配を計算する。

【００２４】ポリゴン描画の繰り返しループに入る
と、ステップＳ２０では分割ポリゴンの左右稜線リスト
の最初の線分データを取り出す。ここでは、左側稜線の
始点（エッジ）のｘ座標をｘｌに、高さをｈｌに、勾配
をｄｘｌに設定し、右側稜線の始点のｘ座標をｘｒに、
高さをｈｒに、勾配をｄｘｒに設定する。ステップＳ２
１でｙ座標の初期値をｙｍｉｎに設定し、走査線ループ
に入る。ステップＳ２２、Ｓ２３、Ｓ２４で座標（ｘ
ｌ，ｙ）から座標（ｘｒ，ｙ）までの画素を塗りつぶ
す。

【００２５】ステップＳ２５とＳ２９とＳ３０では左右
稜線のｘ座標と高さｈとｙ座標を次の走査線に更新し、
ｈｌまたはｈｒが０になると、ステップＳ２８またはＳ
３１で次の線分データを取り出し、極大点に達するとス
テップＳ２７で左側稜線が途切れたことを検出するの
で、そのポリゴンの処理を終了する（ステップＳ２７か
らＳ３３へ）。以上でポリゴンの内部が塗りつぶされる
ので、これを全てのポリゴンについて順に実行すればよ
い。

【００２６】次に、ステップＳ３４でこの文字の輪郭線
を描画する。これも中間フォントデータを用いて、分割
されたポリゴンの輪郭を一定の線幅で塗りつぶす。ただ
し、図６に示したデータより、輪郭線の中で分割線分の
識別情報のある部分は描画しない。

【００２７】図９は、外部輪郭線のみから成るアウトラ
イン文字（６文字）のポリゴン分割結果と表示結果を示
す。図９の下段は、この文字列をポリゴン単位に同じパ
タンで塗りつぶした後、ポリゴンの左右稜線の内、分割
線分を除く部分を一定の線幅で線描画を施し、以上の塗
りつぶしと線描画の操作を座標値をずらして２回実行す
ることにより、重ね書きしたものである。なお、文字外
部の横罫線は単なる背景を示している。

【００２８】［内部輪郭線除去］次に、内部輪郭線を含
む文字のポリゴン分割のための内部輪郭線除去方法を図
１０を用いて説明する。図１０は、「Ｂ」の字のアウト
ラインフォントである。この文字には外部輪郭線が１本
と内部輪郭線が２本ある。このように内部輪郭線を含む
場合には、内部輪郭線と外部輪郭線を適当な線分で結
び、その線分を往復経路として１本の新たな外部輪郭線
に合成する。

【００２９】同図では、分割線分Ａ１Ｂ１及びＡ２Ｂ２
によって文字の内部領域が局部的に分離されている。一
方の領域の境界線をＡ１Ｂ１とし、他方の領域の境界線
をＡ２Ｂ２として左右に分離し、これら境界線を往復経
路として外部輪郭線と内部輪郭線とを結合すると、１本
の新たな外部輪郭線が形成される。ここで、Ａ１とＡ
２、及びＢ１とＢ２はそれぞれ同じ座標値を持つが、ｘ
方向に引き離して描いてある。これは、ポリゴンデータ
を２分割する方法と似ているが、ここでは逆に２つのポ
リゴンデータが１つに融合する。こうして内部輪郭線を
除去することができる。この操作を内部輪郭線の個数だ
け実行すれば全ての内部輪郭線が除去される。

【００３０】即ち、図１０の例では、第２の内部輪郭線
を分割線分Ｃ１Ｄ１及びＣ２Ｄ２によって除去してい
る。こうしてできた外部輪郭線のみに囲まれた文字領域
を、ポリゴン分割する方法は既に述べた通りである。ま
た、この文字を画面に表示する際には、内部輪郭線の除
去に用いた分割線分にも分割線分の識別情報を付与し
て、輪郭線として表示されないようにすればよい。従っ
て、図１０の線分Ａ１Ｂ１、Ａ２Ｂ２、Ｃ１Ｄ１、Ｃ２
Ｄ２は輪郭線としては表示されない。

【００３１】図１１の上段は、内部輪郭線を含む文字に
ついて、その内部輪郭線を分割線分によって除去した結
果を示し、同図下段は更にポリゴン分割した結果を示
す。例えば、文字「あ」は内部輪郭線を２個含むので、
２本の分割線分によって１本の外部輪郭線に統合され、
その外部輪郭線の囲む領域がその後８本の垂直分割線分
によって９個のポリゴンに分割される。

【００３２】本発明は以上の実施例に限定されない。本
発明は文字の輪郭線を表現するアウトラインデータを複
数のポリゴンに分割したものとして表現し、その中に文
字の内部領域を横切るような分割線が存在するような場
合に、その線分の表示を抑制することを目的としてい
る。従って、分割線分を設ける位置や方向等は分割され
た結果のポリゴンの形状が任意の走査線と２個以下の交
点をもつようにすればよく、またその分割線分の識別情
報は上記の実施例に限らず他の線分と区別できるような
ものであれば何でもよい。また、本発明は文字の輪郭線
の表示出力のみの場合であっても、内部領域を塗りつぶ
す処理と併用した場合であっても実施できることはいう
までもない。

【００３３】

【発明の効果】以上説明した本発明のアウトライン文字
描画方法は、文字の内部領域を予め一定の多角形（ポリ
ゴン）に分割することによって塗りつぶしを高速化する
ことができる。更に、そのようなポリゴンデータの中に
分割線分が含まれる場合に、これを他の線分と区別し、
描画を抑制するようにしたので、文字の本来必要な輪郭
線のみの描画を行うことができる。従って、上記のよう
な高速化のための加工をアウトラインデータに加えた後
においても、ポリゴン分割のための処理をした形跡が残
らない良好な表示や印刷を実行できる。

【００３４】また、文字の塗りつぶしとアウトラインの
描画の両方が同一のフォントデータを用いて実行できる
ので、ポストスクリプト等のページ記述言語による文字
描画機能が実現できる。また、このような文字塗りつぶ
しとアウトライン描画を同時にできるポリゴン分割中間
フォントを用いることができれば、ポリゴン描画処理が
高速になり、しかもフォントデータ保存のためのメモリ
を削減することができる。

【図面の簡単な説明】

【図１】本発明のアウトライン文字描画方法実施例を示
す説明図である。

【図２】アウトライン文字の例説明図である。

【図３】本発明によるポリゴン分割フローチャートであ
る。

【図４】本発明によるポリゴン再帰分割フローチャート
である。

【図５】頂点分類結果説明図である。

【図６】分割された頂点分類結果説明図である。

【図７】ポリゴンリストと左右稜線リスト説明図であ
る。

【図８】本発明の走査変換フローチャートである。

【図９】文字のポリゴン分割結果と表示結果説明図であ
る。

【図１０】内部輪郭線の除去方法説明図である。

【図１１】文字の内部輪郭線除去結果とポリゴン分割結
果説明図である。

【符号の説明】

１１−１〜１１−３ 分割線分 １２ 凹頂点 １３ ポリゴンリスト １４ ポリゴンデータ

Claims (3)

【特許請求の範囲】
1. 【請求項１】 文字の輪郭線を複数の線分に分割し、前
   記輪郭線を、各線分の頂点座標の環状連鎖構造として表
   現してポリゴンデータを得る場合に、 予め設定された基準座標軸について見た輪郭線上の任意
   の点の位置座標が、極大または極小となるような前記輪
   郭線に囲まれた図形の凹頂点を抽出し、 前記凹頂点を通る前記基準座標軸に平行な線分により、
   前記輪郭線により囲まれた図形を複数のポリゴンに分割
   し、 前記凹頂点を通る前記基準座標軸に平行な線分に分割線
   分である旨を表示する識別情報を付与し、 前記文字を構成する全てのポリゴンについて、分割線分
   を含まない輪郭線を描画することを特徴とするアウトラ
   イン文字描画方法。
2. 【請求項２】 所定の起点よりポリゴンの輪郭線をそれ
   ぞれ反対方向にたどる、基準座標軸の方向に見てその位
   置座標を単調増加または単調減少させる、一対の左側稜
   線データと右側稜線データを作成し、 前記複数のポリゴンについての前記左右稜線データを集
   積した中間フォントデータを、描画を要求される文字毎
   に予め記憶しておき、 前記中間フォントデータを読み出して、 前記文字を構成する全てのポリゴンについて、前記左右
   稜線データと前記基準座標軸に垂直な走査線との交点を
   認識して、前記ポリゴンを塗りつぶし、 前記文字を構成する全てのポリゴンについて、前記左右
   稜線データの内、前記分割線分の識別情報の付与されて
   いない全ての線分を、所定の線幅で描画し、 前記分割線分を含まない輪郭線を描画することを特徴と
   する請求項１記載のアウトライン文字描画方法。
3. 【請求項３】 文字の輪郭線に外部輪郭線とこの外部輪
   郭線に囲まれる内部輪郭線が存在する場合に、 前記内部輪郭線上の１点と、その内部輪郭線を包囲する
   外部輪郭線上の１点を結ぶ線分が、その両端点以外では
   文字のいかなる輪郭線とも交差しないように輪郭線に新
   たに含める線分を選定し、 その線分を往復経路として、前記外部輪郭線と内部輪郭
   線を連結して１本の新たな輪郭線を合成し、 当該線分に分割線分である旨を表示する識別情報を付与
   し、 前記輪郭線の連続処理によって、全ての前記内部輪郭線
   を除去した後、 前記輪郭線について、凹頂点の抽出を実行することを特
   徴とする請求項１記載のアウトライン文字描画方法。