図面 (/)

技術 多角形判別方式

出願人 ブラザー工業株式会社
発明者 深谷浩祐
出願日 1997年3月25日 (22年3ヶ月経過) 出願番号 1997-072161
公開日 1998年10月9日 (20年9ヶ月経過) 公開番号 1998-269372
状態 未査定
技術分野 イメージ生成
主要キーワード Y座標 ベクトル外積 外積値 判別方式 X座標 凸多角形 計算幾何学 多角形データ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1998年10月9日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (10)

課題

凸多角形の辺が相互に交わるか否かの判定を効率よく行い、その判定処理時間を短縮すること、ひいてはラスタライズ処理時間を短縮すること。

解決手段

多角形を所定の方向の両端に位置する二つの頂点によって二組の連続した辺群に分離した場合に、その分離された連続した辺群の各頂点が、その所定の方向のいずれか一方に沿って、前記多角形の辺の配列順序に従って配列される多角形について、その多角形の辺が相互に交わるか否かを判別するものであって、前記分離されたいずれか一方の連続した辺群から二つの頂点を含む一辺を選択すると共に、他方の連続した辺群から一頂点を選択し、引き続き他の一辺及び一頂点を前記配列順序に従って順次繰り返し選択する(S202〜S215)。

概要

背景

従来、プリンタ等の印刷装置コンピュータ等の情報処理装置においては、それらの使用者仕事の効率を向上させるために、文字及び図形等のグラフィック処理一環として、多角形の内部を塗り潰すいわゆるラスタライズ処理高速に行うための方法や装置が実施されている。

例えば、特公平7−43771号公報や特開平5−61987号公報には、そのラスタライズ処理を高速に行うために、多角形を判別する方法が開示されている。

これらは、いずれもラスタライズする走査線(以下、単に走査線という)と垂直な方向に凸である多角形、すなわち、走査線とその多角形の辺が交差する交点が2点以下である多角形(以下、Y凸多角形という)を判別している。

ここで、Y凸多角形の形状例を図5及び図6に示す。図5は、辺の交差がない場合のY凸多角形(以下、Y凸単純多角形という)の形状図であり、図6は、辺の交差がある場合のY凸多角形(以下、Y凸複雑多角形という)の形状図である。

以下、本明細書では、便宜上、紙面の横に水平な方向をX軸方向、そのX軸と垂直な方向をY軸とし、走査線の方向を、X軸と同一の方向として説明する。

前記公報においては、図5及び図6に示すように、ラスタライズする方法として、走査線とその多角形の辺が交差する交点のうちX座標値の小さい方を始点、大きい方を終点とし、始点から終点までの間を塗り潰す方法を使用している。この方法は、1つの走査線に対して始点と終点が1組しか存在しないため、従来から高速なY凸多角形の処理方法として実施されているが、走査線ごとに2つの交点を有し、その二つの交点の位置関係、すなわち、X座標値の大小関係が不明であるので、そのX座標値の大小比較を走査線ごとに行わなければならなかった。更に具体的には、Y凸多角形が図5に示すように辺が交差しないY凸単純多角形であるのか、図6に示すように辺が交差するY凸複雑多角形であるのかを判別する必要があったので、高解像度化した図形や大型化した図形等においては、走査線数が増加し、その増加した走査線の数に応じて処理時間が増加し、結果的にラスタライズ処理が遅延するという問題があった。

そこで、本発明者は、この問題に着目してY凸単純多角形専用のラスタライズ処理を考案した。図7を参照してその処理について説明する。

図7は、Y凸単純多角形ラスタライズ処理を説明するための説明図である。まず、Y凸多角形をY座標値の最大の頂点TとY座標値の最小の頂点Bとにより2つの頂点及び辺の並び(以下、辺群という)、すなわち、前述した塗り潰す始点を求めるための辺群L(太線で示した辺群)と終点を求めるための辺群R(細線で示した辺群)に分離する。この分離は、Y凸多角形の頂点Tの両隣の頂点をP1及びP2とし、P1・TベクトルとT・P2ベクトルを想定して、それらの外積値P1・T×T・P2を計算し、その計算した結果の符号の正負により判定される。

具体的には、図8を参照して説明することができる。図8は、ベクトル外積計算の結果によって、一辺と一頂点との位置関係を説明する説明図である。すなわち、二つの点A及びBを結ぶ線分ABに対して、頂点Cが図面上右に位置するのか、左に位置するのか、それとも線分AB上に位置するのかを判定する方法を説明した図である。図8は、便宜上、辺の両端の点をA及びBとし、その辺との位置関係を判定される頂点をCとする。これらの点及び頂点は、図7において、例えば、頂点Tが点Aに、頂点P1が点Bに、頂点P2が頂点Cにそれぞれ対応する。

図8(a)は、ベクトル外積計算の計算結果がゼロ未満の場合を示し、この場合、頂点Cは、線分ABの右側に位置すると判定される。図8(b)のように計算結果がゼロを超える場合には、頂点Cは、線分ABの左側に位置すると判定され、図8(c)のように計算結果がゼロである場合には、頂点Cは、線分AB上に位置すると判定される。

次に、辺群L及び辺群Rと走査線との交点をそれぞれ始点、終点とし、その始点から終点までの間を塗り潰す。従って、Y凸単純多角形の場合は、走査線ごとに2つの交点のX座標値の大小比較を行う必要がないので、走査線数が増加したとしても、始点と終点との位置関係を比較する計算処理がなく、ラスタライズ処理に要する時間の増加を少なく抑えることができる。従って、Y凸単純多角形の場合であれば、ラスタライズ処理を高速で行うことができる。

しかし、一般に使用される印刷装置やディスプレイ装置等においては、処理する多角形がY凸単純多角形であることが予め判別されていないためY凸単純多角形であることを判定する処理が必要である。このY凸単純多角形の判定処理アルゴリズムは、多角形の交差判定アルゴリズムとして一般的に使用されているBentley−Ottmanの交点列挙アルゴリズムで実現することできる。このアルゴリズムについては、浅野哲夫著「計算幾何学」102頁から108頁に記載されている。また、このアルゴリズムに用いる2線分の交差判定の具体的な計算式は、原厚吉著「計算幾何工学」1頁から3頁に記載の外積を用いた計算方式で実現することができる。

次に、図9を参照して、従来の交点列挙アルゴリズムと2線分の交差判定を用いたY凸単純多角形を判定する処理を説明する。図9は、従来のY凸単純多角形の判定処理を示すフローチャートである。

この処理を説明するに当たって、後述する図3を具体例とする。

本処理を説明する前に、まず、Y凸多角形をY座標値の最も大きな頂点と最も小さな頂点によって二組の連続した辺群に分離する。

具体的には、図3(a)のY凸多角形のうち、Y座標値の最も大きな頂点P1と最も小さな頂点P4によって二組の連続した辺群に分離する。すなわち、P1、P2、P3、P4の一連の辺群LとP1、P9、P8、P7、P6、P5、P4の一連の辺群Rに分離する。

そして、辺群Lから一つの辺を選択し、その選択された辺の両端の頂点のうち、Y座標値の大きな頂点をL1、Y座標値の小さな頂点をL2とする。

また、辺群Rから一つの辺を選択し、その選択された辺の両端の頂点のうち、Y座標値の大きな頂点をR1、Y座標値の小さな頂点をR2とする。

本処理は、まず、初期設定として、交差判定される二つの辺を選択するために、L1に1、L2に2、R1に1、R2にNが代入される(ステップ1101、以下、ステップをSと記す)。具体的には、辺群Lから辺P1・P2、辺群Rから辺P1・P9を選択する。ここで、「N」とは、Y凸多角形の頂点の数を示し、具体的には、図3(a)のY凸多角形の頂点の数、9を意味する。

そして、L2のY座標値であるY[L2]とR2のY座標値であるY[R2]との大小を比較し(S1102)、Y[L2]がY[R2]よりも大きい場合には、L1にL2の値、L2にL2+1の値を代入する(S1103)。すなわち、図3(a)においては、交差判定される辺群Lの一辺を連続したY座標の一つ小さな辺に変更すること、例えば、辺P1・P2から辺P2・P3に変更することを意味する。

また、Y[L2]がY[R2]よりも小さい場合は、R1にR2の値、R2にR2−1の値を代入する(S1104)。すなわち、図3(a)においては、交差判定される辺群Rの一辺を連続したY座標の一つ小さな辺に変更すること、例えば、辺P1・P9から辺P9・P8に変更することを意味する。

次にL2とR2が等しいか否かを判断し(S1105)、L2とR2が等しい場合は、交差なしと判断し、処理を終了し、L2とR2が等しくない場合は、線分L1・R1と頂点L2、線分L1・R2と頂点L2、線分R1・L1と頂点R2及び線分R1・L2と頂点R2の位置関係を外積計算し、その結果としてそれぞれL1L2R1、L1L2R2、R1R2L1、R1R2L2を求める(S1106)。そして、L1L2R1×L1L2R2の値が「0」以上か否かを判断し(S1107)、L1L2R1×L1L2R2の値が「0」以上でない場合は、L1L2R1×L1L2R2が「0」か否かを判断する(S1109)。

S1109において、L1L2R1×L1L2R2が「0」である場合には、交差ありと判断し、処理を終了し、L1L2R1×L1L2R2が「0」でない場合には、更に、R1R2L1×R1R2L2が「0」以上か否かを判断する(S1110)。

S1110において、R1R2L1×R1R2L2が「0」以上でない場合には、交差ありと判断し、処理を終了し、L1L2R1×L1L2R2が「0」以上である場合には、処理をS1102に戻す。

なお、S1107において、L1L2R1×L1L2R2が「0」以上である場合には、R1R2L1×R1R2L2が「0」であるか否かを判断し(S1108)、R1R2L1×R1R2L2が「0」である場合には、交差ありと判断する。また、R1R2L1×R1R2L2が「0」でない場合には、処理をS1102に戻す。

以上説明したように、Y凸単純多角形であることを判定する処理は、多角形から取り出した2線分に着目し2線分の交差判定を行なっていた。

概要

Y凸多角形の辺が相互に交わるか否かの判定を効率よく行い、その判定処理時間を短縮すること、ひいてはラスタライズ処理時間を短縮すること。

多角形を所定の方向の両端に位置する二つの頂点によって二組の連続した辺群に分離した場合に、その分離された連続した辺群の各頂点が、その所定の方向のいずれか一方に沿って、前記多角形の辺の配列順序に従って配列される多角形について、その多角形の辺が相互に交わるか否かを判別するものであって、前記分離されたいずれか一方の連続した辺群から二つの頂点を含む一辺を選択すると共に、他方の連続した辺群から一頂点を選択し、引き続き他の一辺及び一頂点を前記配列順序に従って順次繰り返し選択する(S202〜S215)。

目的

本発明は、上述した問題を解決するためになされたものであり、Y凸多角形の辺が相互に交わるか否かの判定を効率よく行い、その判定処理時間を短縮すること、ひいてはラスタライズ処理時間を短縮することを目的とする。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

多角形を所定の方向の両端に位置する二つの頂点によって二組の連続した辺群に分離した場合に、その分離された連続した辺群の各頂点が、前記多角形の辺群の配列順序に従って、前記所定の方向に対して順方向あるいは逆方向に並んでいる多角形について、その多角形の辺が相互に交わるか否かを判別する多角形判別方式において、前記分離されたいずれか一方の連続した辺群から二つの頂点を含む一辺を選択すると共に、他方の連続した辺群から一頂点を選択し、引き続き他の一辺及び一頂点を前記配列順序に従って繰り返し選択する選択手段と、前記選択手段により選択された多角形の頂点と辺の位置関係を判定する位置判定手段と、前記位置判定手段の判定結果に基づいて前記多角形の辺が相互に交差するか否かを判定する交差判定手段とを備えたことを特徴とする多角形判別方式。

請求項2

前記選択手段は、選択された二つの頂点を含む一辺及び一頂点のうち、一辺に含まれる二つの頂点が前記所定の方向の両端に位置するような一辺を選択することを特徴とする請求項1に記載の多角形判別方式。

技術分野

0001

本発明は、多角形の内部を塗り潰すいわゆるラスタライズ処理高速に行うために、多角形を判別する多角形判別方式に関するものである。

背景技術

0002

従来、プリンタ等の印刷装置コンピュータ等の情報処理装置においては、それらの使用者仕事の効率を向上させるために、文字及び図形等のグラフィック処理一環として、多角形の内部を塗り潰すいわゆるラスタライズ処理を高速に行うための方法や装置が実施されている。

0003

例えば、特公平7−43771号公報や特開平5−61987号公報には、そのラスタライズ処理を高速に行うために、多角形を判別する方法が開示されている。

0004

これらは、いずれもラスタライズする走査線(以下、単に走査線という)と垂直な方向に凸である多角形、すなわち、走査線とその多角形の辺が交差する交点が2点以下である多角形(以下、Y凸多角形という)を判別している。

0005

ここで、Y凸多角形の形状例を図5及び図6に示す。図5は、辺の交差がない場合のY凸多角形(以下、Y凸単純多角形という)の形状図であり、図6は、辺の交差がある場合のY凸多角形(以下、Y凸複雑多角形という)の形状図である。

0006

以下、本明細書では、便宜上、紙面の横に水平な方向をX軸方向、そのX軸と垂直な方向をY軸とし、走査線の方向を、X軸と同一の方向として説明する。

0007

前記公報においては、図5及び図6に示すように、ラスタライズする方法として、走査線とその多角形の辺が交差する交点のうちX座標値の小さい方を始点、大きい方を終点とし、始点から終点までの間を塗り潰す方法を使用している。この方法は、1つの走査線に対して始点と終点が1組しか存在しないため、従来から高速なY凸多角形の処理方法として実施されているが、走査線ごとに2つの交点を有し、その二つの交点の位置関係、すなわち、X座標値の大小関係が不明であるので、そのX座標値の大小比較を走査線ごとに行わなければならなかった。更に具体的には、Y凸多角形が図5に示すように辺が交差しないY凸単純多角形であるのか、図6に示すように辺が交差するY凸複雑多角形であるのかを判別する必要があったので、高解像度化した図形や大型化した図形等においては、走査線数が増加し、その増加した走査線の数に応じて処理時間が増加し、結果的にラスタライズ処理が遅延するという問題があった。

0008

そこで、本発明者は、この問題に着目してY凸単純多角形専用のラスタライズ処理を考案した。図7を参照してその処理について説明する。

0009

図7は、Y凸単純多角形ラスタライズ処理を説明するための説明図である。まず、Y凸多角形をY座標値の最大の頂点TとY座標値の最小の頂点Bとにより2つの頂点及び辺の並び(以下、辺群という)、すなわち、前述した塗り潰す始点を求めるための辺群L(太線で示した辺群)と終点を求めるための辺群R(細線で示した辺群)に分離する。この分離は、Y凸多角形の頂点Tの両隣の頂点をP1及びP2とし、P1・TベクトルとT・P2ベクトルを想定して、それらの外積値P1・T×T・P2を計算し、その計算した結果の符号の正負により判定される。

0010

具体的には、図8を参照して説明することができる。図8は、ベクトル外積計算の結果によって、一辺と一頂点との位置関係を説明する説明図である。すなわち、二つの点A及びBを結ぶ線分ABに対して、頂点Cが図面上右に位置するのか、左に位置するのか、それとも線分AB上に位置するのかを判定する方法を説明した図である。図8は、便宜上、辺の両端の点をA及びBとし、その辺との位置関係を判定される頂点をCとする。これらの点及び頂点は、図7において、例えば、頂点Tが点Aに、頂点P1が点Bに、頂点P2が頂点Cにそれぞれ対応する。

0011

図8(a)は、ベクトル外積計算の計算結果がゼロ未満の場合を示し、この場合、頂点Cは、線分ABの右側に位置すると判定される。図8(b)のように計算結果がゼロを超える場合には、頂点Cは、線分ABの左側に位置すると判定され、図8(c)のように計算結果がゼロである場合には、頂点Cは、線分AB上に位置すると判定される。

0012

次に、辺群L及び辺群Rと走査線との交点をそれぞれ始点、終点とし、その始点から終点までの間を塗り潰す。従って、Y凸単純多角形の場合は、走査線ごとに2つの交点のX座標値の大小比較を行う必要がないので、走査線数が増加したとしても、始点と終点との位置関係を比較する計算処理がなく、ラスタライズ処理に要する時間の増加を少なく抑えることができる。従って、Y凸単純多角形の場合であれば、ラスタライズ処理を高速で行うことができる。

0013

しかし、一般に使用される印刷装置やディスプレイ装置等においては、処理する多角形がY凸単純多角形であることが予め判別されていないためY凸単純多角形であることを判定する処理が必要である。このY凸単純多角形の判定処理アルゴリズムは、多角形の交差判定アルゴリズムとして一般的に使用されているBentley−Ottmanの交点列挙アルゴリズムで実現することできる。このアルゴリズムについては、浅野哲夫著「計算幾何学」102頁から108頁に記載されている。また、このアルゴリズムに用いる2線分の交差判定の具体的な計算式は、原厚吉著「計算幾何工学」1頁から3頁に記載の外積を用いた計算方式で実現することができる。

0014

次に、図9を参照して、従来の交点列挙アルゴリズムと2線分の交差判定を用いたY凸単純多角形を判定する処理を説明する。図9は、従来のY凸単純多角形の判定処理を示すフローチャートである。

0015

この処理を説明するに当たって、後述する図3を具体例とする。

0016

本処理を説明する前に、まず、Y凸多角形をY座標値の最も大きな頂点と最も小さな頂点によって二組の連続した辺群に分離する。

0017

具体的には、図3(a)のY凸多角形のうち、Y座標値の最も大きな頂点P1と最も小さな頂点P4によって二組の連続した辺群に分離する。すなわち、P1、P2、P3、P4の一連の辺群LとP1、P9、P8、P7、P6、P5、P4の一連の辺群Rに分離する。

0018

そして、辺群Lから一つの辺を選択し、その選択された辺の両端の頂点のうち、Y座標値の大きな頂点をL1、Y座標値の小さな頂点をL2とする。

0019

また、辺群Rから一つの辺を選択し、その選択された辺の両端の頂点のうち、Y座標値の大きな頂点をR1、Y座標値の小さな頂点をR2とする。

0020

本処理は、まず、初期設定として、交差判定される二つの辺を選択するために、L1に1、L2に2、R1に1、R2にNが代入される(ステップ1101、以下、ステップをSと記す)。具体的には、辺群Lから辺P1・P2、辺群Rから辺P1・P9を選択する。ここで、「N」とは、Y凸多角形の頂点の数を示し、具体的には、図3(a)のY凸多角形の頂点の数、9を意味する。

0021

そして、L2のY座標値であるY[L2]とR2のY座標値であるY[R2]との大小を比較し(S1102)、Y[L2]がY[R2]よりも大きい場合には、L1にL2の値、L2にL2+1の値を代入する(S1103)。すなわち、図3(a)においては、交差判定される辺群Lの一辺を連続したY座標の一つ小さな辺に変更すること、例えば、辺P1・P2から辺P2・P3に変更することを意味する。

0022

また、Y[L2]がY[R2]よりも小さい場合は、R1にR2の値、R2にR2−1の値を代入する(S1104)。すなわち、図3(a)においては、交差判定される辺群Rの一辺を連続したY座標の一つ小さな辺に変更すること、例えば、辺P1・P9から辺P9・P8に変更することを意味する。

0023

次にL2とR2が等しいか否かを判断し(S1105)、L2とR2が等しい場合は、交差なしと判断し、処理を終了し、L2とR2が等しくない場合は、線分L1・R1と頂点L2、線分L1・R2と頂点L2、線分R1・L1と頂点R2及び線分R1・L2と頂点R2の位置関係を外積計算し、その結果としてそれぞれL1L2R1、L1L2R2、R1R2L1、R1R2L2を求める(S1106)。そして、L1L2R1×L1L2R2の値が「0」以上か否かを判断し(S1107)、L1L2R1×L1L2R2の値が「0」以上でない場合は、L1L2R1×L1L2R2が「0」か否かを判断する(S1109)。

0024

S1109において、L1L2R1×L1L2R2が「0」である場合には、交差ありと判断し、処理を終了し、L1L2R1×L1L2R2が「0」でない場合には、更に、R1R2L1×R1R2L2が「0」以上か否かを判断する(S1110)。

0025

S1110において、R1R2L1×R1R2L2が「0」以上でない場合には、交差ありと判断し、処理を終了し、L1L2R1×L1L2R2が「0」以上である場合には、処理をS1102に戻す。

0026

なお、S1107において、L1L2R1×L1L2R2が「0」以上である場合には、R1R2L1×R1R2L2が「0」であるか否かを判断し(S1108)、R1R2L1×R1R2L2が「0」である場合には、交差ありと判断する。また、R1R2L1×R1R2L2が「0」でない場合には、処理をS1102に戻す。

0027

以上説明したように、Y凸単純多角形であることを判定する処理は、多角形から取り出した2線分に着目し2線分の交差判定を行なっていた。

発明が解決しようとする課題

0028

しかし、前述した従来のアルゴリズムを利用したY凸単純多角形の判定処理は、2辺の交差判定を行うに当たって4回の外積計算を行うため、例えば、Y凸多角形の頂点の数がN個の場合は、S1106における4回の外積計算がN−3回行われることになる。更に、各々の外積計算は、2回の乗算を含むため、この判定処理は、多大な時間を要するという問題があった。

0029

従って、Y凸多角形を直接ラスタライズ処理するよりも、Y凸単純多角形の判定処理を行った後、ラスタライズ処理する方が処理時間が遅くなるという問題も生じていた。

0030

本発明は、上述した問題を解決するためになされたものであり、Y凸多角形の辺が相互に交わるか否かの判定を効率よく行い、その判定処理時間を短縮すること、ひいてはラスタライズ処理時間を短縮することを目的とする。

課題を解決するための手段

0031

この目的を達成するために、本発明の請求項1に記載の多角形判別方式は、多角形を所定の方向の両端に位置する二つの頂点によって二組の連続した辺群に分離した場合に、その分離された連続した辺群の各頂点が、前記多角形の辺群の配列順序に従って、前記所定の方向に対して順方向あるいは逆方向に並んでいる多角形について、その多角形の辺が相互に交わるか否かを判別するものを対象として、特に、前記分離されたいずれか一方の連続した辺群から二つの頂点を含む一辺を選択すると共に、他方の連続した辺群から一頂点を選択し、引き続き他の一辺及び一頂点を前記配列順序に従って繰り返し選択する選択手段と、前記選択手段により選択された多角形の頂点と辺の位置関係を判定する位置判定手段と、前記位置判定手段の判定結果に基づいて前記多角形の辺が相互に交差するか否かを判定する交差判定手段とを備えたことを特徴としている。

0032

上記の構成を有する請求項1に記載の多角形判別方式は、多角形を所定の方向の両端に位置する二つの頂点によって二組の連続した辺群に分離した場合に、その分離された連続した辺群の各頂点が、前記多角形の辺群の配列順序に従って、前記所定の方向に対して順方向あるいは逆方向に並んでいる多角形について、その多角形の辺が相互に交わるか否かを判別するものであって、選択手段は、分離されたいずれか一方の連続した辺群から二つの頂点を含む一辺を選択すると共に、他方の連続した辺群から一頂点を選択し、引き続き他の一辺及び一頂点を前記配列順序に従って繰り返し選択する。

0033

そして、位置判定手段は、選択手段により選択された多角形の頂点と辺の位置関係を判定し、交差判定手段は、位置判定手段の判定結果に基づいて多角形の辺が相互に交差するか否かを判定する。

0034

また、請求項2に記載の多角形判別方式は、前記選択手段が、選択された二つの頂点を含む一辺及び一頂点のうち、一辺に含まれる二つの頂点が前記所定の方向の両端に位置するような一辺を選択することを特徴としている。

0035

上記の構成を有する請求項2に記載の多角形判別方式において、選択手段は、選択された二つの頂点を含む一辺及び一頂点のうち、一辺に含まれる二つの頂点が所定の方向の両端に位置するような一辺を選択する。

発明を実施するための最良の形態

0036

以下、本発明の実施の形態を、添付図面を参照して詳細に説明する。図1は、本発明の実施の形態におけるY凸単純多角形のラスタライズ処理の概略を説明するフローチャートである。図1において、まず、図示しないCPUは、ラスタライズ処理される多角形の形状を認識するため、その頂点の座標値等の多角形データを読み込む(S101)。そして、読み込んだ多角形データにより、ラスタライズ処理される多角形(以下、処理多角形という)がY凸多角形であるか否かを判断し(S102)、処理多角形がY凸多角形であると判断した場合には、更に、その処理多角形がY凸単純多角形であるか否かを判別する(S103)。ここで、処理多角形がY凸単純多角形であると判定した場合には、Y凸単純多角形のラスタライズ処理を行った後(S104)、処理を終了する。また、CPUがS103において、処理多角形をY凸単純多角形でないと判定した場合には、Y凸多角形のラスタライズ処理を行った後(S105)、処理を終了する。更に、S102において、処理多角形をY凸多角形でないと判定した場合には、その他の多角形ラスタライズ処理を行った後(S106)、処理を終了する。

0037

なお、本発明は、Y凸単純多角形であるか否かを判別する多角形判別方式(S103)に関するものであるので、本実施の形態では、Y凸多角形であるか否かの判断(S102)、Y凸多角形のラスタライズ処理(S105)及びその他の多角形ラスタライズ処理(S106)については、説明を省略する。

0038

次に、図2を用いて、本実施の形態のY凸単純多角形判別処理の流れを説明する。

0039

この処理の流れを説明するに当たって、その具体例である図3図4を説明しておく。図3(a)は、辺の交差がないY凸多角形の例を示した形状図であり、図3(b)は、そのY凸多角形の座標値を示した表である。また、図4(a)は、辺の交差があるY凸多角形の例を示した形状図であり、図4(b)は、そのY凸多角形の座標値を示した表である。

0040

図3(a)におけるY凸多角形は、9つの頂点を有し、これら頂点のうち、Y座標値の最も大きな頂点がP1に設定されている。そして、その頂点P1から辺の配列順序に沿って左周りに、各頂点が当該凸多角形の各頂点に対応してP2からP9に設定されている。図3(b)において、P1乃至P9は、図3(a)のY凸多角形における各頂点を示し、xは、その頂点のX座標値を、yは、その頂点のY座標値を示す。

0041

また、図4(a)におけるY凸多角形は、図3(a)と同様に、9つの頂点を有し、これら頂点のうち、Y座標値の最も大きな頂点がQ1に設定されている。そして、その頂点Q1から辺の配列順序に沿って左周りに、各頂点が当該凸多角形の各頂点に対応してQ2からQ9に設定されている。図4(b)において、Q1乃至Q9は、図4(a)のY凸多角形における各頂点を示し、xは、その頂点のX座標値を、yは、その頂点のY座標値を示す。

0042

さて、図2は、本実施の形態のY凸単純多角形判別処理の流れを示すフローチャートである。図2においては、まず、初期設定として、交差判定される一つの辺と一つの頂点を選択するために、Aに1、Bに2、CにNを代入する(S201)。この初期設定は、図3(a)においては、辺群Lから辺P1・P2、辺群Rから頂点P9を選択したことを意味する。そして、線分ABと頂点Cの位置関係を外積計算し、外積値SIGN(=BA×AC)を求める(S202)。

0043

次に、頂点BのY座標値であるY[B]と頂点CのY座標値であるY[C]との大小を比較し(S203)、Y[B]がY[C]よりも小さい場合には、CにC−1が代入される(S204)。すなわち、頂点Cを連続した辺群Rのうち、Y座標値の一つ小さな頂点に変更する。すなわち、図3(a)においては、頂点P9をP8に変更する。そして、その変更した頂点P8のY座標であるY[C]とP2のY座標値であるY[B]との大小を比較する(S205)。そして、Y[B]がY[C]よりも大きくない場合には、BがCに等しいか否かを判断する(S210)。また、S205において、Y[B]がY[C]よりも大きい場合には、AにC+1を代入する(S206)。すなわち、図3(a)においては、頂点P1を連続した辺群Rのうち、Y座標値が一つ小さな頂点P9に変更する。そして、頂点Bが頂点Cに等しいか否かを判断する(S210)。

0044

なお、S203において、Y[B]がY [C]よりも小さくない場合は、BにB+1を代入する(S207)。すなわち、図3(a)においては、交差判定される辺群Lの頂点のうち、連続したY座標の一つ小さな頂点に変更する。例えば、頂点P2を頂点P3に変更する。

0045

そして、その変更したP3のY座標であるY[B]とP9のY座標値であるY[C]との大小を比較する(S208)。ここで、Y[C]がY[B]よりも大きくない場合には、BがCに等しいか否かを判断する(S210)。また、S208において、Y[C]がY[B]よりも大きい場合には、AにB−1を代入する(S209)。すなわち、図3(a)においては、交差判定される辺群Lの頂点のうち、連続したY座標の一つ小さな頂点に変更する。例えば、頂点P1を頂点P2に変更する。

0046

そして、頂点Bが頂点Cに等しいか否かを判断し(S210)、頂点Bと頂点Cが等しくない場合は、線分A・Bと頂点Cの位置関係を外積計算し、その結果をABCとして求める(S211)。ここで、その計算結果ABCが「0」の場合は、交差ありと判定し、処理を終了する。その計算結果が「0」でない場合は、計算結果ABCが「0」以上であるか否かを判断し(S213)、「0」以上でない場合は、更に、S202で求めたSIGNが「0」以下であるか否かを判断する(S215)。SIGNが、「0」以下でなければ、交差ありと判定し、処理を終了し、S215において、SIGNが「0」以下であれば、処理をS203に戻す。

0047

なお、S213において計算結果ABCが「0」以上である場合は、SIGNが「0」以上であるか否かを判断し(S214)、SIGNが「0」以上でなければ、交差ありと判定し、処理を終了し、SIGNが「0」以上であれば、処理をS203に戻す。

0048

ここで、S203からS209の処理は、一辺と一頂点を選択する選択手段に該当し、S210からS213の処理は、一辺と一頂点の位置関係を判定する位置判定手段に該当する。また、S214からS215の処理は、多角形の辺の交差を判定する交差判定手段に該当する。

0049

以下に、図3(a)の多角形を図2で示したY凸単純多角形判定処理で処理した場合の計算結果を示す。S203からS210の一連の処理の繰り返し回数を1列目に挙げ、繰り返し回数毎の各変数の値と計算結果とを2列目以降に列挙した。

0050

0051

この場合の外積ABCの計算回数は、7回となる。

0052

これに対し、図3(a)の多角形を従来の図9で示した処理で処理した場合の計算結果を以下に示す。

0053

0054

この場合の外積計算回数は、6×4の24回となる。

0055

また、以下に、図4の多角形を図2で示したY凸単純多角形判定処理で処理した場合の計算結果を示す。

0056

0057

この場合は、4回目の外積計算で交差していることが判定できる。

0058

これに対し、図4の多角形を図9で示したY凸単純多角形判定処理で処理した場合の計算結果を以下に示す。

0059

0060

この場合は、3×4の12回の外積計算で交差していることが判定される。

0061

なお、本実施の形態では、位置判定ステップは走査線と垂直な方向の座標値が大きい頂点から昇順に処理を行なっていたが、座標値が小さい頂点から降順に処理を行なっても同様の効果を得ることができる。

発明の効果

0062

以上説明したことから明らかなように、請求項1に記載の多角形判別方式は、多角形を所定の方向の両端に位置する二つの頂点によって二組の連続した辺群に分離した場合に、その分離された連続した辺群の各頂点が、前記多角形の辺群の配列順序に従って、前記所定の方向に対して順方向あるいは逆方向に並んでいる多角形について、その多角形の辺が相互に交わるか否かを判別するものであって、選択手段は、前記分離されたいずれか一方の連続した辺群から二つの頂点を含む一辺を選択すると共に、他方の連続した辺群から一頂点を選択し、引き続き他の一辺及び一頂点を前記配列順序に従って繰り返し選択し、位置判定手段は、前記選択手段により選択された多角形の頂点と辺の位置関係を判定し、交差判定手段は、前記位置判定手段の判定結果に基づいて前記多角形の辺が相互に交差するか否かを判定するので、一辺と一頂点の位置関係を判定する外積計算回数を少なくすることができ、処理時間を短くすることができる。

0063

また、請求項2記載の多角形判別装置は、選択手段は、前記多角形の頂点を選択すると共に、選択された二つの頂点を含む一辺及び一頂点のうち、一辺に含まれる二つの頂点が常に前記所定の方向の両端に位置するような一辺を選択するので、更に、一辺と一頂点の位置関係を判定する外積計算回数を少なくすることができ、処理時間を短くすることができる。

図面の簡単な説明

0064

図1本発明の実施の形態におけるY凸単純多角形のラスタライズ処理の概略を説明するフローチャートである。
図2本実施の形態のY凸単純多角形判別処理の流れを示すフローチャートである。
図3辺の交差がないY凸多角形の例を示した形状図と座標値を示した表である。
図4辺の交差があるY凸多角形の例を示した形状図と座標値を示した表である。
図5辺の交差がないY凸多角形の例を示した形状図である。
図6辺の交差があるY凸多角形の例を示した形状図である。
図7Y凸単純多角形のラスタライズ処理を説明するための説明図である。
図8一辺と一頂点との位置関係を説明する説明図である。
図9従来のY凸単純多角形判定処理を示すフローチャートである。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • キヤノン株式会社の「 画像形成装置、画像形成方法、プログラム」が 公開されました。( 2019/05/23)

    【課題】エッジデータのソートをプロセッサで実行し、所定の合成演算を演算回路で行うことができる画像形成装置を提供する。【解決手段】印刷データによって表現されるページ内のライン上にあるオブジェクトのエッジ... 詳細

  • キヤノン株式会社の「 画像処理システム、画像処理システムの制御方法及びプログラム」が 公開されました。( 2019/05/23)

    【課題】仮想視点画像の生成に要する時間を短縮することである。【解決手段】画像処理システムは、複数のカメラが被写体を複数の方向から撮影した画像から仮想視点画像を生成する画像処理システムであって、生成され... 詳細

  • マイフィジーク リミテッドの「 ボディの画像化」が 公開されました。( 2019/05/23)

    【課題】ボディを画像化する装置を提供する。【解決手段】装置は、コントローラと、コントローラを制御するための電子プログラム命令を記憶する記憶装置と、ユーザインタフェースを表示するためのディスプレイと、入... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ