JPH0660194A - 図形処理装置 - Google Patents

Abstract

(57)【要約】 【構成】 座標入力端子１より与えられた座標から線分
情報作成部２は複数の線分毎の座標情報を作成する。ソ
ーティング部３は、作成された座標情報に基づき、例え
ばｙ座標の小さい順に並べ替える等、各線分の並べ替え
を行う。線分抽出部４は、並べ替えられた各線分によっ
て、交差する可能性のある線分を抽出する。交点検出部
６では抽出された線分のみによって交点演算を行う。 【効果】 交点の存在する線分を絞ることができるた
め、交点検出処理の時間を大幅に短縮することができる

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は図形処理装置に関し、特
に図形を構成する複数の線分の交点を検出する線分処理
方式に関する。

【０００２】

【従来の技術】情報処理装置のディスプレイやプリンタ
等において図形処理を行う場合、図形の中塗りやその他
の処理を行う際に、図形の頂点に加えて線分の交点を求
める必要がある場合が存在する。図２は、このような場
合の説明図である。即ち、図２では、正方形と三角形と
を重ね合わせた場合を示している。このような場合、二
つの図形の交点を求めるには、ある１線分に対して残り
の全線分との交点を１次式を用いて求める、といった処
理を全線分に対して行い、全交点を算出していた。

【０００３】以下、これを詳細に説明する。最初に、元
図形として図２に示した正方形（図形１）を考える。こ
の図形はＸ−Ｙ座標系で表され、外部から正方形の頂点
Ａ、Ｂ、Ｃ、Ｄと三角形（図形２）の頂点Ｅ、Ｆ、Ｇが
この順でＸ座標、Ｙ座標によって与えられたとする。そ
して、これらの各頂点の座標をそれぞれＡ（ＸA 、ＹA
）、Ｂ（ＸB 、ＹB ）、Ｃ（ＸC 、ＹC ）、Ｄ（ＸD
、ＹD ）、Ｅ（ＸE 、ＹE ）、Ｆ（ＸF 、ＹF ）、Ｇ
（ＸG 、ＹG ）と表す。先ず、最初の線分ＡＢに対して
交点を求めるには、次の線分ＢＣとの交点から、線分Ｃ
Ｄ、ＤＡ、ＥＦ、ＦＧ、ＧＥとの交点までを順に求め
る。また、線分ＡＢと線分ＥＦとの交点Ｐ１は、 ｘ＝ＸA ｙ＝｛（ＹE −ＹF ）／（ＸE −ＸF ）｝×（ＸA −Ｘ
E ）＋ＹF で求められ、これは２線分ＡＢ、ＥＦ上にあるので、交
点として情報を持つ。

【０００４】一方、線分ＡＢと線分ＦＧとの交点Ｐ１′
は、 ｘ′＝ＸA ｙ′＝｛（ＹF −ＹG ）／（ＸF −ＸG ）｝×（ＸA −
ＸF ）＋ＹF で求められ、これは線分ＦＧ上となるが、線分ＡＢ上で
はないので交点とはしない。図３に、この状態を拡大し
て示す。

【０００５】以上のようにして線分ＡＢとの交点とし
て、Ｐ１のみが求められる。続いて線分ＢＣに対して交
点を求めるには、次の線分ＣＤとの交点からＤＡ、Ｅ
Ｆ、ＦＧ、ＧＥとの交点まで求め、これ以降同様に繰り
返し、最終的に交点Ｐ１、Ｐ２を得る。

【０００６】

【発明が解決しようとする課題】しかしながら、上記従
来の図形処理装置では、図形の全線分に対してそれぞれ
残りの全線分との交点を求めるため、その処理に非常に
多くの時間を要するという問題点があった。本発明は、
上記従来の問題点を解決するためになされたもので、線
分処理時間を短縮することのできる図形処理装置を提供
することを目的とする。

【０００７】

【課題を解決するための手段】本発明の図形処理装置
は、複数の線分毎の座標情報を作成する線分情報作成部
と、前記線分情報作成部で作成された線分毎の座標情報
に基づき、各線分の並べ替えを行うソーティング部と、
前記ソーティング部で並べ替えられた各線分からある線
分と交差する可能性のある線分を抽出する線分抽出部
と、前記線分抽出部で抽出された線分のみの交点演算を
行う交点検出部とを備えたことを特徴とするものであ
る。

【０００８】

【作用】本発明の図形処理装置においては、例えば図形
の頂点数と各頂点の座標等が座標入力端子から入力され
る。これらの座標等の情報に基づき線分情報作成部で
は、複数の線分毎の座標情報を作成する。ソーティング
部は、線分情報作成部からの座標情報を入力し、例えば
ｙ座標の小さい順に並べ替える等、各線分の並べ替えを
行う。線分抽出部は、ソーティング部で並べ替えられた
線分情報を入力し、交点が存在する可能性のある線分を
抽出する。交点検出部では、線分抽出部で抽出された線
分のみを用いて各線分の交点演算を行い、図形の交点を
求める。

【０００９】

【実施例】以下、本発明の実施例を図面を用いて詳細に
説明する。図１は本発明の図形処理装置を示す機能ブロ
ック図である。図の装置は、座標入力端子１、線分情報
作成部２、ソーティング部３、線分抽出部４、固定線分
カウンタ５、交点検出部６からなる。

【００１０】座標入力端子１は、図形の座標を与えるた
めの入力端子であり、線分情報作成部２は、この座標入
力端子１から入力された図形の複数の線分毎の座標情報
を作成する機能を有し、その座標情報はソーティング部
３に入力されるよう構成されている。また、ソーティン
グ部３は、交点を求め易くするために座標情報を並べ替
えるためのもので、本実施例では、各線分をＹ座標の小
さい順にソーティングを行うよう構成されている。線分
抽出部４は、ソーティング部３で並べ替えられた各線分
毎の座標情報に基づき、各線分の座標を比較し、ある線
分に対して交点の存在する可能性のある線分を抽出する
機能を有している。また、固定線分カウンタ５は、線分
抽出部４の抽出処理においてどの線分を固定線分（比較
元としている線分）としているかをカウントするための
カウンタである。

【００１１】交点検出部６は、交点算出部７、交点範囲
判定部８、交点出力処理部９、比較線分カウンタ１０か
らなる。ここで、交点算出部７は、線分抽出部４で抽出
された交点が存在する可能性のある線分の交点演算を行
う機能を有し、交点範囲判定部８は、交点算出部７で算
出された交点が２線分上にあるか否かを判定し、その結
果によって比較線分カウンタ１０のカウントアップを行
うものである。また、交点出力処理部９は、交点範囲判
定部８で、その交点が２直線上にあると判定された場合
は、その交点を図示しないメモリ等に格納し、かつ比較
線分カウンタ１０をカウントアップする機能を有してい
る。更に、比較線分カウンタ１０は、線分抽出部４、交
点範囲判定部８および交点出力処理部９によって操作さ
れ、固定線分５と比較するための比較線分をカウントす
るためのカウンタである。

【００１２】次に、このように構成された図形処理装置
の動作について説明する。本実施例においても、交点を
検出する図形として図２に示したものを例にとって説明
する。図４は、処理図形に対応して外部から与えられる
座標リストである。即ち、この座標リストには図形１
（正方形）、図形２（三角形）の頂点数と各頂点の座標
が示されている。先ず、このような座標リストを元に、
線分情報作成部２は、それ以降の処理がし易いようにメ
モリリスト構造のような線分毎の情報を作成する。この
時、各線分情報の先頭アドレスのリストも作成する。図
５および図６に、このようなメモリリスト構造および先
頭アドレスのリストを示す。

【００１３】また、図７はこのような処理を行う場合の
フローチャートであり、以下、このフローチャートに沿
って線分情報作成処理を説明する。先ず、図形の頂点数
があるか否かを判定し（ステップＳ１）、頂点数が０で
なかった場合は、座標が頂点数以内であるかを判定し
（ステップＳ２）、そうでなかった場合はステップＳ１
に戻る。ここでは、最初のステップであるため頂点数は
０でなく、また、頂点数内であるためステップＳ３に移
行し、図４に示す座標リストから最初の線分ＡＢの端点
座標を取出す。そして、図５に示すように、座標の始点
・終点として新しく格納する（ステップＳ４）。ここで
は、次のソーティング部３で線分をｙ座標の小さい順に
並べ替えるため、線分の両端点のうちｙ座標の小さい方
の点（ｙ座標が等しい場合は、どちらでもよい）を始
点、もう一方を終点と呼ぶ。従って、始点として点Ａの
座標を、終点として点Ｂの座標を格納する。

【００１４】また、各線分はｘ座標とｙ座標の１次式ｙ
＝ｋｘ＋ｙ0 （ｋ：線分の傾き、ｙ0 ：ｙ切片）で捉
え、傾きと切片も線分情報として保持しておく（ステッ
プＳ５）。尚、線分の傾きと切片は次のように求められ
る。 (1) 水平・垂直の線分 傾き ０ 切片 ｙ座標（水平）、ｘ座標（垂直） (2) その他の部分 傾き （終点のｙ座標−始点のｙ座標）／（終点のｘ座
標−始点のｘ座標） 切片 （一方のｙ座標）−（傾き）×（同じ点のｘ座
標） 例えば、線分ＡＢの場合、傾き「０」、切片「ＸA 」を
格納する。

【００１５】次に、線分ＡＢの一連の情報の先頭アドレ
ス、即ち、始点のｘ座標を格納したアドレスをアドレス
リスト（図６に示したもの）に格納する（ステップＳ
６）。その後は、座標リスト・アドレスリストのカウン
タを更新し（ステップＳ７）、このような線分情報の格
納を頂点数分繰り返すことにより、一つの図形分の線分
情報が作成できる。そして、これをステップＳ１におい
て、頂点数が０となるまで繰り返し、線分情報のリスト
とそのアドレスリストを完成させる。

【００１６】次に、線分情報作成部２で作成された情報
を、ソーティング部３で、各線分の始点のｙ座標を基準
として小さい順にソーティングする。実際には、図５の
線分情報のメモリリストはそのままで、図６のアドレス
リストを並べ替え、そのアドレスリストの順に線分情報
を読むようにする。図８にソーティングされたアドレス
リストを示す。また、図９はソーティング後の図形線分
の順番の説明図である。このように、図８の先頭アドレ
スの順番は図９に示すようになっている。尚、の線分
ＡＢとの線分ＤＣ、また、の線分ＥＦとの線分Ｅ
Ｇは、それぞれ順番が入れ替わっても処理には影響はな
い。以上で、交点を求めるための準備が終了し、次いで
交点の存在する可能性のある線分を抽出する線分抽出部
４の動作と交点演算を行う交点検出部６の動作となる。

【００１７】図１０は、線分抽出部４と交点検出部６の
動作フローチャートである。先ず、ステップＳ１におい
て固定線分カウンタを更新、即ち、最初は固定線分カウ
ンタを「１」とする。そして、ステップＳ２において、
この固定線分が最後の線分かを判定する。ここでは、固
定線分は最後ではないため、ステップＳ３に移行し、図
８に示した各線分の先頭アドレスのリストから１番目の
線分ＡＤを取出す。この時の線分ＡＤを固定線分、その
他の線分を比較線分と呼ぶことにする。次いで、ステッ
プＳ４では、比較線分カウンタの更新を行うが、ここで
は最初であるため、そのカウンタ値を「１」とし、更
に、ステップＳ５では線分数内かを判定するが、ここで
は線分数内であるため、比較線分を取出す（ステップＳ
６）。この比較線分は、アドレスリストにおいて、固定
線分の次から始まる。従って、ステップＳ６では、１番
目の比較線分としてＡＢを取出し、その比較線分と上述
した固定線分に交点が存在するかどうかを判定する（ス
テップＳ７）。

【００１８】ここで、２線分の交点が存在し得る比較線
分は、ｙ座標が固定線分の最小値と最大値の間にかかる
線分であるから、 （固定線分の終点のｙ座標）＞（比較線分の始点のｙ座
標） という条件式を満たす線分である。今、取り出されてい
る２線分の座標を上式で考えると、ＹD ＝ＹA となるか
ら交点は存在し得ず、線分ＡＤとの交点が存在する線分
はないことになる。図１１は、この状態の説明図であ
る。この図１１の（ａ）に示すように、線分ＡＤの終点
座標と線分ＡＢの始点座標は等しいため、点Ａが頂点で
はあっても、２線分の交点は存在しないことになる。ま
た、この２線分のように、ある線分と次の線分との交点
判定を行い、その結果、交点が存在しないと判定された
場合は、線分が予めソーティングされているため、それ
以降の線分との交点判定を行わなくとも済むことにな
る。

【００１９】このように、ステップＳ７において、交点
の存在する可能性がない場合は、ステップＳ１に戻り、
固定線分カウンタを更新する。即ち、次の線分ＡＢが固
定線分となる。そして、ステップＳ３において、その固
定線分ＡＢを取出し、更にステップＳ４では比較線分カ
ウンタを更新するため、比較線分はＤＣとなる（図１１
の（ｂ）にこの状態を示す）。線分ＡＢと線分ＤＣとの
交点の有無を判定すると（ステップＳ７）、ＹB ＞ＹD
となり条件式を満たすが、次のステップＳ８において、
ＡＢとＤＣとは平行であるため交点は存在せず、ステッ
プＳ４に戻る。従って、ステップＳ４で比較線分カウン
タを更新し、ステップＳ６で比較線分ＥＦが取り出され
る。この場合は、ステップＳ７において、ＹB ＞ＹE よ
り条件式が満たされ、かつステップＳ８の平行判定にお
いて、２線分は平行ではないため、ステップＳ９の交点
算出の処理に移る。

【００２０】この交点算出は、ｘ＝Ｘ0 （垂直線）とｙ
＝ａｘ＋ｂとの交点の場合、 ｘP ＝ｘ0 ｙP ＝ａ×Ｘ0 ＋ｂ となり、ｙ＝ａｘ＋ｂとｙ＝ｃｘ＋ｄとの交点の場合
（ａ＝０またはｃ＝０の場合も可）、 ｘp ＝（ｄ−ｂ）／（ａ−ｃ） ｙ＝ａ×ｘp ＋ｂ となる。従って、線分ＡＢと線分ＥＦの場合、交点（ｘ
p ，ｙp ）の座標は、それぞれ、 ｘp ＝ＸA ｙ＝（ＥＦの傾き）×ＸA ＋（ＥＦのｙ切片） で求められる。そして、このように求めた交点の座標
は、２線分ＡＢとＥＦ上であるか否かが判定され（ステ
ップＳ１０）、２線分上にあるためこの座標は交点とし
て図示しないメモリ等に格納される（ステップＳ１
１）。これが、図２に示すＰ１である。

【００２１】続いて、ステップＳ４に戻り、比較線分を
次のＥＧとする。この場合もＹB ＞ＹE と条件式を満た
し、かつ２線分は平行ではないため、ステップＳ９で交
点座標の算出が行われるが、ステップＳ１０において交
点が２線分上にはないと判定されるため、ステップＳ４
に戻る。図１２に、その線分の状態を示す。即ち、ステ
ップＳ９で求めた交点座標は線分ＥＧの延長線と線分Ａ
Ｂとの交点であって、線分ＥＧ上にはないからである。
以降、上記の処理を同様に繰り返し、ステップＳ７にお
いて比較線分が条件式を満たさない時、あるいはステッ
プＳ５において比較線分が最後の線分になった時にステ
ップＳ１で固定線分カウンタを更新する。そして、固定
線分が最後の線分になった時は（ステップＳ２）、比較
線分がなくなるため処理を終了する。以上のようにし
て、図２で示した交点Ｐ１、Ｐ２を検出する。

【００２２】このようにして交点Ｐ１、Ｐ２を求めた場
合、従来の方式では交点の算出が１９回必要であったの
に対し、本実施例では８回で済み、大幅な短縮を図るこ
とが可能となった。例えば、本実施例をページプリンタ
に適用した場合、交点を求める処理時間が従来の０．０
７３１８６秒から本実施例の０．０２７９５０秒とな
り、６１．８％の速度向上を図ることができた。また、
上述した図形を印刷する場合のデータを受信してから印
刷起動までの時間は、０．１６７１０５秒から０．１０
０２７２秒となり、４０．０％の速度向上となった。

【００２３】尚、上記実施例では、ソーティング部３に
おけるソーティングを、ｙ方向について行ったが、これ
をｘ方向としてもよい。また、ソーティングを座標の小
さい順ではなく、大きい順に行っても上記実施例と同様
の効果を奏する。

【００２４】

【発明の効果】以上説明したように、本発明の図形処理
装置によれば、複数の線分をソーティングしてある線分
と交差する可能性のある線分を抽出し、抽出された線分
のみを交点演算に用いるようにしたので、交点算出演算
処理において、交差する可能性のある線分を絞ることが
でき、その結果交点を求める処理時間を大幅に削減する
ことができる。

【図面の簡単な説明】

【図１】本発明の図形処理装置の機能ブロック図であ
る。

【図２】本発明および従来の図形処理装置に係わる図形
例を示す図である。

【図３】図２の頂点Ｂ付近の拡大図である。

【図４】本発明の図形処理装置において外部から与えら
れる図形の座標リストを示す図である。

【図５】本発明の図形処理装置における線分情報のメモ
リリスト構造を示す図である。

【図６】本発明の図形処理装置における各線分の先頭ア
ドレスのリストを示す図である。

【図７】本発明の図形処理装置における線分情報作成の
フローチャートである。

【図８】本発明の図形処理装置におけるソーティング後
の各線分の先頭アドレスのリストを示す図である。

【図９】本発明の図形処理装置におけるソーティング後
の各線分の順番を示す図である。

【図１０】本発明の図形処理装置における線分抽出と交
点検出のフローチャートである。

【図１１】本発明の図形処理装置における固定線分と比
較線分の関係の説明図である。

【図１２】本発明の図形処理装置における線分ＡＢと線
分ＥＧとの交点検出の説明図である。

【符号の説明】

２ 線分情報作成部 ３ ソーティング部 ４ 線分抽出部 ６ 交点検出部

Claims (1)

【特許請求の範囲】
1. 【請求項１】 複数の線分毎の座標情報を作成する線分
   情報作成部と、 前記線分情報作成部で作成された線分毎の座標情報に基
   づき、各線分の並べ替えを行うソーティング部と、 前記ソーティング部で並べ替えられた各線分からある線
   分と交差する可能性のある線分を抽出する線分抽出部
   と、 前記線分抽出部で抽出された線分のみの交点演算を行う
   交点検出部とを備えたことを特徴とする図形処理装置。