JPH07109629B2 - 多角形の識別方法、多角形を識別するシステム - Google Patents
多角形の識別方法、多角形を識別するシステムInfo
- Publication number
- JPH07109629B2 JPH07109629B2 JP4025997A JP2599792A JPH07109629B2 JP H07109629 B2 JPH07109629 B2 JP H07109629B2 JP 4025997 A JP4025997 A JP 4025997A JP 2599792 A JP2599792 A JP 2599792A JP H07109629 B2 JPH07109629 B2 JP H07109629B2
- Authority
- JP
- Japan
- Prior art keywords
- polygon
- comparison
- order
- determining
- identifying
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
Landscapes
- Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computer Graphics (AREA)
- Geometry (AREA)
- Software Systems (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Image Generation (AREA)
- Image Analysis (AREA)
Description
【０００１】
【産業上の利用分野】本発明は、コンピユータの作図シ
ステムにおいて、デイスプレイに表示される画像のデー
タを処理し、デイスプレイ・スクリーン上に多角形の画
像を作図し、表示することに関する。より具体的に言え
ば、本発明は、頂点だけを与えられたノンコンベツクス
多角形（nonconvex polygon）（凹みを持つ多角形）を
識別する方法に関する。
ステムにおいて、デイスプレイに表示される画像のデー
タを処理し、デイスプレイ・スクリーン上に多角形の画
像を作図し、表示することに関する。より具体的に言え
ば、本発明は、頂点だけを与えられたノンコンベツクス
多角形（nonconvex polygon）（凹みを持つ多角形）を
識別する方法に関する。
【０００２】
【従来の技術】コンピユータの作図システムにおいて図
形を作図し、そして表示しなければならない多角形には
３つのクラスがある（図５参照）。第１のクラスに属す
るコンベツクス多角形（凹みを持たない多角形）は、そ
の多角形を取り囲む辺が決して交差することがなく、か
つ、常に同じ方向に回転するので、コンベツクス多角形
は、作図するのに最も簡単なクラスの多角形である。こ
のクラスの多角形の構造は、カルテシアン座標系の
「Ｙ」軸方向において、完全に連続した１つのスパンが
あることと、多角形内に含まれた各「Ｙ」軸の値に対し
て、最小値及び最大値（上部及び底部）の間に、連続し
たスパンを持つていることとを保証する。連続したスパ
ンとは、コンピユータの作図システムにおいて表示する
ためにスクリーン上に示された多角形に含まれる画素
（ピクセル）の走査線を意味する。
形を作図し、そして表示しなければならない多角形には
３つのクラスがある（図５参照）。第１のクラスに属す
るコンベツクス多角形（凹みを持たない多角形）は、そ
の多角形を取り囲む辺が決して交差することがなく、か
つ、常に同じ方向に回転するので、コンベツクス多角形
は、作図するのに最も簡単なクラスの多角形である。こ
のクラスの多角形の構造は、カルテシアン座標系の
「Ｙ」軸方向において、完全に連続した１つのスパンが
あることと、多角形内に含まれた各「Ｙ」軸の値に対し
て、最小値及び最大値（上部及び底部）の間に、連続し
たスパンを持つていることとを保証する。連続したスパ
ンとは、コンピユータの作図システムにおいて表示する
ためにスクリーン上に示された多角形に含まれる画素
（ピクセル）の走査線を意味する。
【０００３】第２のクラスに属するノンコンベツクス多
角形は、周辺が交差することはないけれども、内部角度
は１８０度よりも大きな角度を含んでいる（ノンコンベ
ツクス多角形は明確に区別できる１つの内部領域と、１
つの外部領域とを持つている）。従つて、ノンコンベツ
クス多角形が作図される時、任意に与えられた「Ｙ」座
標軸の値に対して、２つの別個のスパンがある。つま
り、ノンコンベツクス多角形は、凹面領域（窪んだ部
分）の何れかの側において、「Ｙ」座標軸方向に走査変
換されるスパンを作る凹面部分を持つていると言うこと
である。
角形は、周辺が交差することはないけれども、内部角度
は１８０度よりも大きな角度を含んでいる（ノンコンベ
ツクス多角形は明確に区別できる１つの内部領域と、１
つの外部領域とを持つている）。従つて、ノンコンベツ
クス多角形が作図される時、任意に与えられた「Ｙ」座
標軸の値に対して、２つの別個のスパンがある。つま
り、ノンコンベツクス多角形は、凹面領域（窪んだ部
分）の何れかの側において、「Ｙ」座標軸方向に走査変
換されるスパンを作る凹面部分を持つていると言うこと
である。
【０００４】第３のクラスに分類されるコンプレツクス
多角形は、最も複雑な多角形のクラスに属するものであ
り、この多角形は、１つの内部領域と、１つの外部領域
とを明確に分けることができないから、それに応じて、
走査変換処理が最も難しいクラスの多角形である。コン
プレツクス多角形の辺は、あらゆる方向に回転すること
ができ、交差することができる。従つて、多角形中に、
「Ｙ」座標軸方向の複数の走査ラインを持たせる問題
や、幾つかの「Ｙ」軸方向の走査ラインに対して走査線
を持たせないという問題に加えて、コンプレツクス多角
形は、多角形を完成するために、２つの経路を持つてい
る問題がある。つまり、コンプレツクス多角形には、２
つに分けられた明確な内部領域及び外部領域がないの
で、多角形を完結するために、多角形のどちらの領域を
完結するのかを決定しなければならない問題があるとい
うことである。
多角形は、最も複雑な多角形のクラスに属するものであ
り、この多角形は、１つの内部領域と、１つの外部領域
とを明確に分けることができないから、それに応じて、
走査変換処理が最も難しいクラスの多角形である。コン
プレツクス多角形の辺は、あらゆる方向に回転すること
ができ、交差することができる。従つて、多角形中に、
「Ｙ」座標軸方向の複数の走査ラインを持たせる問題
や、幾つかの「Ｙ」軸方向の走査ラインに対して走査線
を持たせないという問題に加えて、コンプレツクス多角
形は、多角形を完成するために、２つの経路を持つてい
る問題がある。つまり、コンプレツクス多角形には、２
つに分けられた明確な内部領域及び外部領域がないの
で、多角形を完結するために、多角形のどちらの領域を
完結するのかを決定しなければならない問題があるとい
うことである。
【０００５】コンプレツクス多角形を完結する従来の方
法は、「奇−偶（odd-even）」ルール及び「ワインデイ
ング（winding）」ルールを含んでいる（１９９０年ア
デイソン・ウエスリー社（Addison-Wesly）刊行のホレ
イ（J.Foley）等の共同の著作物の「コンピユータ・グ
ラフイツクス、原理と実際（Computer Graphics: Princ
iples and Practice）」と題する記述の９６５頁を参
照）。コンプレツクス多角形を作図することは、ノンコ
ンベツクス多角形、またはコンベツクス多角形を作図す
る処理に比べて、非常に多くの計算処理を含んでおり、
より多くのリソースと、より多くの時間とが必要であ
る。通常、コンプレツクス多角形を作図するのに絶対必
要な必須時間は、ノンコンベツクス多角形を作図するた
めの必須時間よりも、１０倍程度の長い時間を必要とす
る。
法は、「奇−偶（odd-even）」ルール及び「ワインデイ
ング（winding）」ルールを含んでいる（１９９０年ア
デイソン・ウエスリー社（Addison-Wesly）刊行のホレ
イ（J.Foley）等の共同の著作物の「コンピユータ・グ
ラフイツクス、原理と実際（Computer Graphics: Princ
iples and Practice）」と題する記述の９６５頁を参
照）。コンプレツクス多角形を作図することは、ノンコ
ンベツクス多角形、またはコンベツクス多角形を作図す
る処理に比べて、非常に多くの計算処理を含んでおり、
より多くのリソースと、より多くの時間とが必要であ
る。通常、コンプレツクス多角形を作図するのに絶対必
要な必須時間は、ノンコンベツクス多角形を作図するた
めの必須時間よりも、１０倍程度の長い時間を必要とす
る。
【０００６】Ｘウインドウ・システム（Ｘウインドウ・
システム（X Window System）はＭＩＴの商標）のよう
な通常のグラフイツク・システムにおいて、クライエン
ト・プログラムは、作図されるべき多角形のクラスにつ
いてのヒントを送る。多角形を作図するために、少なく
とも最適なクラスを使用しなければならないと言う意味
において、上述のヒントは排他的なものである。つま
り、排他的であるということは、これらのヒントが、実
際に入力され、作図されるべき多角形のクラスよりも、
より簡単な多角形のクラスを表示することができないと
言うことを意味する。例えば、コンベツクス多角形にお
いて、Ｘウインドウ・システムのクライエント・プログ
ラムは、コンベツクス多角形、ノンコンベツクス多角
形、またはコンプレツクス多角形のためのヒントを与え
て、コンベツクス多角形を正しく作図することができ
る。然しながら、ノンコンベツクス多角形において、ノ
ンコンベツクス多角形、またはコンプレツクス多角形に
向けられたヒントは、ノンコンベツクス多角形を適正に
作図するのを保証するヒントだけしか含んでいない。更
に、コンプレツクス多角形において、コンプレツクス多
角形のためのヒントは、コンプレツクス多角形を適正に
作図するためのヒントだけしか含んでいない。若し、コ
ンベツクス多角形を作図するためのヒントが、Ｘウイン
ドウ・システムのサーバ・プログラムに与えられ、そし
て、実際に作図される多角形がコンプレツクス多角形な
らば、コンベツクス多角形を作図するための方法はコン
プレツクス多角形には当て嵌らないので、それらのヒン
トに従つた結果は、意味を明らかにすることができず、
その結果、作図された多角形は不正確に作図されること
になる。また、コンピユータ・グラフイツクに関する従
来の技術において、一組の頂点と、それらの頂点に対応
したヒントを与えることによつてコンベツクス多角形を
識別する方法がある。
システム（X Window System）はＭＩＴの商標）のよう
な通常のグラフイツク・システムにおいて、クライエン
ト・プログラムは、作図されるべき多角形のクラスにつ
いてのヒントを送る。多角形を作図するために、少なく
とも最適なクラスを使用しなければならないと言う意味
において、上述のヒントは排他的なものである。つま
り、排他的であるということは、これらのヒントが、実
際に入力され、作図されるべき多角形のクラスよりも、
より簡単な多角形のクラスを表示することができないと
言うことを意味する。例えば、コンベツクス多角形にお
いて、Ｘウインドウ・システムのクライエント・プログ
ラムは、コンベツクス多角形、ノンコンベツクス多角
形、またはコンプレツクス多角形のためのヒントを与え
て、コンベツクス多角形を正しく作図することができ
る。然しながら、ノンコンベツクス多角形において、ノ
ンコンベツクス多角形、またはコンプレツクス多角形に
向けられたヒントは、ノンコンベツクス多角形を適正に
作図するのを保証するヒントだけしか含んでいない。更
に、コンプレツクス多角形において、コンプレツクス多
角形のためのヒントは、コンプレツクス多角形を適正に
作図するためのヒントだけしか含んでいない。若し、コ
ンベツクス多角形を作図するためのヒントが、Ｘウイン
ドウ・システムのサーバ・プログラムに与えられ、そし
て、実際に作図される多角形がコンプレツクス多角形な
らば、コンベツクス多角形を作図するための方法はコン
プレツクス多角形には当て嵌らないので、それらのヒン
トに従つた結果は、意味を明らかにすることができず、
その結果、作図された多角形は不正確に作図されること
になる。また、コンピユータ・グラフイツクに関する従
来の技術において、一組の頂点と、それらの頂点に対応
したヒントを与えることによつてコンベツクス多角形を
識別する方法がある。
【０００７】
【発明が解決しようとする課題】多角形のクラスを知る
ことは、多角形を作図する手段を最も効果的に利用する
ことができるので、ノンコンベツクス多角形からコンプ
レツクス多角形を識別する方法があれば、非常に有益で
あることは、上述の記載から容易に理解できるであろ
う。これにより、多角形を走査変換するための非常に複
雑なプロシージヤを必要とする従来の方法を回避するこ
とができ、ノンコンベツクス多角形を作図することは従
来よりも１０倍も早くすることができる。
ことは、多角形を作図する手段を最も効果的に利用する
ことができるので、ノンコンベツクス多角形からコンプ
レツクス多角形を識別する方法があれば、非常に有益で
あることは、上述の記載から容易に理解できるであろ
う。これにより、多角形を走査変換するための非常に複
雑なプロシージヤを必要とする従来の方法を回避するこ
とができ、ノンコンベツクス多角形を作図することは従
来よりも１０倍も早くすることができる。
【０００８】
【課題を解決するための手段】従来の技術とは異なつ
て、本発明は多角形がコンプレツクス多角形としてマー
クされているとしても、多角形の頂点だけを与えて、ノ
ンコンベツクス多角形を識別するための経済的な計算方
法を与える。つまり、コンプレツクス多角形として多角
形を知らせる「ヒント」が与えられた時に、本発明は、
実際に作図される多角形をノンコンベツクス多角形とし
て識別するか、または、作図されるべき多角形が実際に
はコンプレツクス多角形であることを確かめる。
て、本発明は多角形がコンプレツクス多角形としてマー
クされているとしても、多角形の頂点だけを与えて、ノ
ンコンベツクス多角形を識別するための経済的な計算方
法を与える。つまり、コンプレツクス多角形として多角
形を知らせる「ヒント」が与えられた時に、本発明は、
実際に作図される多角形をノンコンベツクス多角形とし
て識別するか、または、作図されるべき多角形が実際に
はコンプレツクス多角形であることを確かめる。
【０００９】本発明は、総括的に言うと、多角形の辺
（エツジ）が相互に交差しているかを検出するために、
多角形の辺を比較することを基本としている。最初に、
多角形の「基本の辺、即ち「ベース辺」と、これと比較
するための「比較辺」とが指定され、そして、これらの
辺の各々に対して領域ボツクス（bounding box）が決め
られる。領域ボツクスは、各辺を対角線として包含する
単純な矩形であつて、カルテシアン座標系の座標軸の最
大値及び最小値（ｘ値及びｙ値）を持つている。次に、
２つの領域ボツクスが比較され、若し、領域ボツクスが
重なるならば、ベース辺と比較辺とは共通点を持つてお
り、これに反して、若し、領域ボツクスが重ならなけれ
ば、これら２つの辺には共通点はなく、そして、これら
の辺の順序の番号は増加され、他の辺の領域ボツクスと
の比較を行なう。
（エツジ）が相互に交差しているかを検出するために、
多角形の辺を比較することを基本としている。最初に、
多角形の「基本の辺、即ち「ベース辺」と、これと比較
するための「比較辺」とが指定され、そして、これらの
辺の各々に対して領域ボツクス（bounding box）が決め
られる。領域ボツクスは、各辺を対角線として包含する
単純な矩形であつて、カルテシアン座標系の座標軸の最
大値及び最小値（ｘ値及びｙ値）を持つている。次に、
２つの領域ボツクスが比較され、若し、領域ボツクスが
重なるならば、ベース辺と比較辺とは共通点を持つてお
り、これに反して、若し、領域ボツクスが重ならなけれ
ば、これら２つの辺には共通点はなく、そして、これら
の辺の順序の番号は増加され、他の辺の領域ボツクスと
の比較を行なう。
【００１０】領域ボツクスが重なることが決定されたな
らば、現在処理している２つの辺が交差する交差点の座
標が計算される。若し、この交差点が両方の領域ボツク
スの中に含まれていれば、その多角形はコンプレツクス
多角形であり、このテストは終了する。然しながら、若
し、交差点が、いずれの領域ボツクスの中にも含まれて
いなければ、多角形の辺の順序番号は増加され、そし
て、関係するすべての辺が処理されるまで、同様な処理
が続けられる。
らば、現在処理している２つの辺が交差する交差点の座
標が計算される。若し、この交差点が両方の領域ボツク
スの中に含まれていれば、その多角形はコンプレツクス
多角形であり、このテストは終了する。然しながら、若
し、交差点が、いずれの領域ボツクスの中にも含まれて
いなければ、多角形の辺の順序番号は増加され、そし
て、関係するすべての辺が処理されるまで、同様な処理
が続けられる。
【００１１】
【実施例】図１を参照すると、本発明を実施するための
代表的なコンピユータの作図システムのブロツク図が示
されている。図１において、参照数字１は、Ｘウインド
ウ・システムのライブラリ（ＸＬｉｂ）３を含むＸウイ
ンドウ・システムのクライエント・プログラム（X-Clie
nt）と呼ばれるソフトウエアのアプリケーシヨン・プロ
グラムを示している。Ｘウインドウ・システムのクライ
エント・プログラム１は、デイスプレイ９と、キーボー
ドや、マウスなどのような入力装置７との間に相互接続
されたＸウインドウ・システムのサーバ・プログラム５
と相互通信を行なう。Ｘウインドウ・システムのクライ
エント・プログラム１及びＸウインドウ・システムのサ
ーバ・プログラム５はＸウインドウ・システムを実行す
ることのできるワークステーシヨンを動作することがで
き、そして、ＩＢＭ社で生産されているＲＩＳＣシステ
ム／６０００を含んでいることは注意を要する（ＲＩＳ
Ｃシステム／６０００及びＩＢＭは商標である）。Ｘウ
インドウ・システムのクライエント・プログラム１によ
つてヒントがＸウインドウ・システムのサーバ・プログ
ラム５に与えられたときに、コンプレツクス多角形、ま
たはノンコンベツクス多角形を作図する必要があるか否
かを決定する動作を、本発明が遂行することができるよ
うに、参照数字１１で示されている本発明は、Ｘウイン
ドウ・システムのサーバ・プログラム５中に含まれてい
る。ここで、アプリケーシヨン・プログラム（図示せ
ず）と関連して入力装置７を介してＸウインドウ・シス
テムのサーバ・プログラム５へ入力される特定の多角形
を作図することをユーザが望んでいるものとする。従つ
て、Ｘウインドウ・システムのサーバ・プログラム５
は、どのようにして多角形が作図されるべきかに関して
ヒントを与えるＸウインドウ・システムのクライエント
・プログラム１と通信する。若し、そのヒントが「コン
ベツクス」ならば、本発明は、最も簡単なコンベツクス
多角形が作図されることを知り、そして、そのように処
理する。然しながら、若し、Ｘウインドウ・システムの
クライエント・プログラム１からのヒントが「コンプレ
ツクス」であれば、Ｘウインドウ・システムのクライエ
ント・プログラムは、これら２つのクラスの間を区別す
る能力がないから、描かれるべき多角形は、「コンプレ
ツクス」多角形であるか、または、「ノンコンベツク
ス」多角形であるかを決定するために、本発明の技術が
呼び出される。この決定がなされたならば、Ｘウインド
ウ・システムのサーバ・プログラム５は、最も効果的な
方法で、その多角形をデイスプレイ９に作図することが
できる。
代表的なコンピユータの作図システムのブロツク図が示
されている。図１において、参照数字１は、Ｘウインド
ウ・システムのライブラリ（ＸＬｉｂ）３を含むＸウイ
ンドウ・システムのクライエント・プログラム（X-Clie
nt）と呼ばれるソフトウエアのアプリケーシヨン・プロ
グラムを示している。Ｘウインドウ・システムのクライ
エント・プログラム１は、デイスプレイ９と、キーボー
ドや、マウスなどのような入力装置７との間に相互接続
されたＸウインドウ・システムのサーバ・プログラム５
と相互通信を行なう。Ｘウインドウ・システムのクライ
エント・プログラム１及びＸウインドウ・システムのサ
ーバ・プログラム５はＸウインドウ・システムを実行す
ることのできるワークステーシヨンを動作することがで
き、そして、ＩＢＭ社で生産されているＲＩＳＣシステ
ム／６０００を含んでいることは注意を要する（ＲＩＳ
Ｃシステム／６０００及びＩＢＭは商標である）。Ｘウ
インドウ・システムのクライエント・プログラム１によ
つてヒントがＸウインドウ・システムのサーバ・プログ
ラム５に与えられたときに、コンプレツクス多角形、ま
たはノンコンベツクス多角形を作図する必要があるか否
かを決定する動作を、本発明が遂行することができるよ
うに、参照数字１１で示されている本発明は、Ｘウイン
ドウ・システムのサーバ・プログラム５中に含まれてい
る。ここで、アプリケーシヨン・プログラム（図示せ
ず）と関連して入力装置７を介してＸウインドウ・シス
テムのサーバ・プログラム５へ入力される特定の多角形
を作図することをユーザが望んでいるものとする。従つ
て、Ｘウインドウ・システムのサーバ・プログラム５
は、どのようにして多角形が作図されるべきかに関して
ヒントを与えるＸウインドウ・システムのクライエント
・プログラム１と通信する。若し、そのヒントが「コン
ベツクス」ならば、本発明は、最も簡単なコンベツクス
多角形が作図されることを知り、そして、そのように処
理する。然しながら、若し、Ｘウインドウ・システムの
クライエント・プログラム１からのヒントが「コンプレ
ツクス」であれば、Ｘウインドウ・システムのクライエ
ント・プログラムは、これら２つのクラスの間を区別す
る能力がないから、描かれるべき多角形は、「コンプレ
ツクス」多角形であるか、または、「ノンコンベツク
ス」多角形であるかを決定するために、本発明の技術が
呼び出される。この決定がなされたならば、Ｘウインド
ウ・システムのサーバ・プログラム５は、最も効果的な
方法で、その多角形をデイスプレイ９に作図することが
できる。
【００１２】図２乃至図４を参照すると、ノンコンベツ
クス多角形を識別するために、本発明に従つた方法を説
明するための流れ図が示されている。図２乃至図４によ
つて示された処理ステツプは、Ｘウインドウ・システム
のサーバ・プログラム５にあるソフトウエア及びそれに
関連して動作するソフトウエア・コードによつて実行さ
れる。このソフトウエア・コードは、ノンコンベツクス
多角形及びコンプレツクス多角形の物理的な形状をデイ
スプレイ９に表示するように、ワークステーシヨンのＸ
−サーバ・プログラム５を制御する。
クス多角形を識別するために、本発明に従つた方法を説
明するための流れ図が示されている。図２乃至図４によ
つて示された処理ステツプは、Ｘウインドウ・システム
のサーバ・プログラム５にあるソフトウエア及びそれに
関連して動作するソフトウエア・コードによつて実行さ
れる。このソフトウエア・コードは、ノンコンベツクス
多角形及びコンプレツクス多角形の物理的な形状をデイ
スプレイ９に表示するように、ワークステーシヨンのＸ
−サーバ・プログラム５を制御する。
【００１３】図２を参照すると、ステツプ１において、
コンプレツクス多角形であるか、ノンコンベツクス多角
形であるかのテストが開始される。この時点で、コンプ
レツクスのヒントがＸウインドウ・システムのクライエ
ント・プログラムによつて受け取られており、そして、
Ｎ個の辺を持つコンプレツクス多角形が作図されるの
か、またはＮ個の辺を持つ単なるノンコンベツクス多角
形が作図されるのかを決定するために、本発明が呼び出
される。ステツプ２において、多角形の基本辺、即ち
「ベース辺」が処理され、順序番号１、つまり第１番目
の辺として設定される。本発明の実施例を説明するため
に、例えば参照数字１０１をベース辺であるとし、この
辺が第１の辺であるものとして示されている図５のノン
コンベツクス多角形を考えてみる。ここで、多角形のど
の辺をベース辺として決めるかとは関係なしに、本発明
を機能させることができるので、ベース辺の指定は任意
に決めることができる。次に、ステツプ３において、図
５のノンコンベツクス多角形の周りを時計方向の向きに
処理し、図５の多角形の３番目の辺は「比較辺」として
処理され、参照数字１０３で示されている。ステツプ４
において、反時計方向に回つてベース辺と隣り合うであ
ろう「最終比較辺」は、Ｎ−１番目の辺として設定され
る。参照数字１０５は、図５のノンコンベツクス多角形
の「最終比較辺」を示している。ステツプ５において、
「最終ベース辺」は、反時計方向回りで最終比較辺と隣
接したＮ−２番目の辺に設定され、参照数字１０７で示
されている。ステツプ６において、図５のノンコンベツ
クス多角形において現在対象としているベース辺のため
の領域ボツクスが決定される。図６に示したノンコンベ
ツクス多角形Ａは、ベース辺１０１を包括する領域ボツ
クス１０９を示している。領域ボツクス１０９は、ベー
ス辺１０１のＸ座標軸の最大値及び最小値及びＹ座標軸
の最大値及び最小値で形成された単純な矩形であること
が判る。ステツプ６に続くステツプ７において、比較辺
１０３のための領域ボツクス１１１が決められる。図６
のコンベツクス多角形Ｂを参照すると、比較辺１０３を
対角線として包括する領域ボツクス１１１は、ベース辺
１０１を対角線として包括している領域ボツクス１０９
の上に重なつていることが示されている。図３の流れ図
のステツプ８において、ベース辺の領域ボツクス１０９
と比較辺の領域ボツクス１１１との間の比較が行なわれ
る。次に、ステツプ９において、領域ボツクスが重なつ
ているか否かが決定される。若し、重なりがなければ、
処理は、後述するステツプ１７に進む。これらの領域ボ
ツクスが重なつているものと仮定すると、ステツプ１０
において、例えば、Ｙの切片等式（intercept equatio
n）（Ｙ＝ＭＸ＋Ｂ）のような線型代数学を用いること
によつて、辺１０１及び１０３の傾斜を計算することが
できる。次に、ステツプ１１において、これらの辺の線
が交差するか否かが決定される（この例においては、辺
１０１及び１０３は交差する）。図７において、辺１０
１及び１０３の線が点１１３で交差することが判る。然
しながら、若し、これらの辺の線が交差しなければ（辺
が平行な場合）、処理は、ステツプ１７に続く。ステツ
プ１２において、交差点１１３の座標軸の値が計算さ
れ、そして、ステツプ１３において、交差点１１３とベ
ース辺の領域ボツクス１０９との比較と、交差点１１３
と領域辺の比較ボツクス１１１との比較が夫々行なわれ
る。ステツプ１４において、交差点１１３は比較辺の領
域ボツクス及びベース辺の領域ボツクスの両方の中にあ
るか否かが決定される。若し、交差点１１３がこれらの
領域ボツクス中に含まれていれば、本発明は、この多角
形はコンプレツクス多角形であると決定する。次に、ス
テツプ１５において、このテストはステツプ１６に移動
し、ステツプ１６において、コンプレツクス多角形を作
図するためのプロシージヤが実行される。然しながら、
図５のノンコンベツクス多角形のベース辺１０１及び比
較辺１０３とを比較してみると、交差点１１３は、それ
らの辺の領域ボツクス１０９及び１１１の中には入つて
いないことが図７から判る。従つて、この処理はステツ
プ１７（図４）に続き、このステツプにおいて、現在処
理されている比較辺は「最終比較辺」であるか否か、つ
まり、ステツプ４におけるＮ−１番目の辺であるか否か
が決定される。このノンコンベツクス多角形の辺の最初
の処理、つまり、この流れ図の処理の第１の処理の場合
のように、若し、その比較辺が「最終比較辺」でなけれ
ば、ステツプ１８において、比較辺の処理はステツプ７
の処理に戻され、ステツプ７において、次の順番の番号
を持つ比較辺の新しい領域ボツクスが決定される。この
新しい領域ボツクスは、ステツプ８において既に説明し
たように、ベース辺の領域ボツクスと比較される。ステ
ツプ１７において、若し、比較辺１０５が「最終比較
辺」（Ｎ−１番目の辺）に遭遇したならば、ステツプ１
９は、「最終比較辺」を、図５のノンコンベツクス多角
形の参照数字１０６によつて示されているＮ番目の比較
辺に設定する。ステツプ１７における「最終比較辺」に
遭遇するまで、「ベース辺」１０１と比較しなければな
らない「比較辺」がある限り、本発明の比較動作が遂行
されることは、上述の説明から理解されるであろう。
「最終比較辺」がステツプ１９においてＮ番目の辺に設
定された後、ステツプ２０において、そのベース辺が、
事実上、「最終ベース辺」（ステツプ５のＮ−２番目の
辺）であるか否かが決定される。若し、「最終ベース
辺」１０７（図５）が、ステツプ２０において遭遇され
なければ、ステツプ２１において、そのベース辺の順番
は増加され、そして、比較辺はベース辺に２を加えた値
に設定される。ベース辺の順番を１つだけ増加すると、
ベース辺に隣接した比較辺として取り扱われ、隣り合う
２つの辺は相互に交差することはできないという定義が
あるので、ベース辺の順序番号に関して、比較辺の順序
番号を２つだけ増加することができるのが判る。次の処
理は、ステツプ６に移り、そして、処理は、前に説明し
た図２、図３及び図４の流れ図のように進行する。ステ
ツプ２０において、そのベース辺が最終的なベース辺で
あることが決定されたならば、この多角形の辺を処理し
ている間で、ベース辺の領域ボツクス及び比較辺の領域
ボツクスの両方のボツクスの中に包含された２つの辺の
交差点は存在しなかつたので、その多角形はコンプレツ
クス多角形ではないことが判る。ステツプ２３におい
て、テスト処理はステツプ２４に移動し、ステツプ２４
において、図１に示したコンピユータの作図システムに
おいて、ノンコンベツクス多角形を作図するプロシージ
ヤが呼び出される。
コンプレツクス多角形であるか、ノンコンベツクス多角
形であるかのテストが開始される。この時点で、コンプ
レツクスのヒントがＸウインドウ・システムのクライエ
ント・プログラムによつて受け取られており、そして、
Ｎ個の辺を持つコンプレツクス多角形が作図されるの
か、またはＮ個の辺を持つ単なるノンコンベツクス多角
形が作図されるのかを決定するために、本発明が呼び出
される。ステツプ２において、多角形の基本辺、即ち
「ベース辺」が処理され、順序番号１、つまり第１番目
の辺として設定される。本発明の実施例を説明するため
に、例えば参照数字１０１をベース辺であるとし、この
辺が第１の辺であるものとして示されている図５のノン
コンベツクス多角形を考えてみる。ここで、多角形のど
の辺をベース辺として決めるかとは関係なしに、本発明
を機能させることができるので、ベース辺の指定は任意
に決めることができる。次に、ステツプ３において、図
５のノンコンベツクス多角形の周りを時計方向の向きに
処理し、図５の多角形の３番目の辺は「比較辺」として
処理され、参照数字１０３で示されている。ステツプ４
において、反時計方向に回つてベース辺と隣り合うであ
ろう「最終比較辺」は、Ｎ−１番目の辺として設定され
る。参照数字１０５は、図５のノンコンベツクス多角形
の「最終比較辺」を示している。ステツプ５において、
「最終ベース辺」は、反時計方向回りで最終比較辺と隣
接したＮ−２番目の辺に設定され、参照数字１０７で示
されている。ステツプ６において、図５のノンコンベツ
クス多角形において現在対象としているベース辺のため
の領域ボツクスが決定される。図６に示したノンコンベ
ツクス多角形Ａは、ベース辺１０１を包括する領域ボツ
クス１０９を示している。領域ボツクス１０９は、ベー
ス辺１０１のＸ座標軸の最大値及び最小値及びＹ座標軸
の最大値及び最小値で形成された単純な矩形であること
が判る。ステツプ６に続くステツプ７において、比較辺
１０３のための領域ボツクス１１１が決められる。図６
のコンベツクス多角形Ｂを参照すると、比較辺１０３を
対角線として包括する領域ボツクス１１１は、ベース辺
１０１を対角線として包括している領域ボツクス１０９
の上に重なつていることが示されている。図３の流れ図
のステツプ８において、ベース辺の領域ボツクス１０９
と比較辺の領域ボツクス１１１との間の比較が行なわれ
る。次に、ステツプ９において、領域ボツクスが重なつ
ているか否かが決定される。若し、重なりがなければ、
処理は、後述するステツプ１７に進む。これらの領域ボ
ツクスが重なつているものと仮定すると、ステツプ１０
において、例えば、Ｙの切片等式（intercept equatio
n）（Ｙ＝ＭＸ＋Ｂ）のような線型代数学を用いること
によつて、辺１０１及び１０３の傾斜を計算することが
できる。次に、ステツプ１１において、これらの辺の線
が交差するか否かが決定される（この例においては、辺
１０１及び１０３は交差する）。図７において、辺１０
１及び１０３の線が点１１３で交差することが判る。然
しながら、若し、これらの辺の線が交差しなければ（辺
が平行な場合）、処理は、ステツプ１７に続く。ステツ
プ１２において、交差点１１３の座標軸の値が計算さ
れ、そして、ステツプ１３において、交差点１１３とベ
ース辺の領域ボツクス１０９との比較と、交差点１１３
と領域辺の比較ボツクス１１１との比較が夫々行なわれ
る。ステツプ１４において、交差点１１３は比較辺の領
域ボツクス及びベース辺の領域ボツクスの両方の中にあ
るか否かが決定される。若し、交差点１１３がこれらの
領域ボツクス中に含まれていれば、本発明は、この多角
形はコンプレツクス多角形であると決定する。次に、ス
テツプ１５において、このテストはステツプ１６に移動
し、ステツプ１６において、コンプレツクス多角形を作
図するためのプロシージヤが実行される。然しながら、
図５のノンコンベツクス多角形のベース辺１０１及び比
較辺１０３とを比較してみると、交差点１１３は、それ
らの辺の領域ボツクス１０９及び１１１の中には入つて
いないことが図７から判る。従つて、この処理はステツ
プ１７（図４）に続き、このステツプにおいて、現在処
理されている比較辺は「最終比較辺」であるか否か、つ
まり、ステツプ４におけるＮ−１番目の辺であるか否か
が決定される。このノンコンベツクス多角形の辺の最初
の処理、つまり、この流れ図の処理の第１の処理の場合
のように、若し、その比較辺が「最終比較辺」でなけれ
ば、ステツプ１８において、比較辺の処理はステツプ７
の処理に戻され、ステツプ７において、次の順番の番号
を持つ比較辺の新しい領域ボツクスが決定される。この
新しい領域ボツクスは、ステツプ８において既に説明し
たように、ベース辺の領域ボツクスと比較される。ステ
ツプ１７において、若し、比較辺１０５が「最終比較
辺」（Ｎ−１番目の辺）に遭遇したならば、ステツプ１
９は、「最終比較辺」を、図５のノンコンベツクス多角
形の参照数字１０６によつて示されているＮ番目の比較
辺に設定する。ステツプ１７における「最終比較辺」に
遭遇するまで、「ベース辺」１０１と比較しなければな
らない「比較辺」がある限り、本発明の比較動作が遂行
されることは、上述の説明から理解されるであろう。
「最終比較辺」がステツプ１９においてＮ番目の辺に設
定された後、ステツプ２０において、そのベース辺が、
事実上、「最終ベース辺」（ステツプ５のＮ−２番目の
辺）であるか否かが決定される。若し、「最終ベース
辺」１０７（図５）が、ステツプ２０において遭遇され
なければ、ステツプ２１において、そのベース辺の順番
は増加され、そして、比較辺はベース辺に２を加えた値
に設定される。ベース辺の順番を１つだけ増加すると、
ベース辺に隣接した比較辺として取り扱われ、隣り合う
２つの辺は相互に交差することはできないという定義が
あるので、ベース辺の順序番号に関して、比較辺の順序
番号を２つだけ増加することができるのが判る。次の処
理は、ステツプ６に移り、そして、処理は、前に説明し
た図２、図３及び図４の流れ図のように進行する。ステ
ツプ２０において、そのベース辺が最終的なベース辺で
あることが決定されたならば、この多角形の辺を処理し
ている間で、ベース辺の領域ボツクス及び比較辺の領域
ボツクスの両方のボツクスの中に包含された２つの辺の
交差点は存在しなかつたので、その多角形はコンプレツ
クス多角形ではないことが判る。ステツプ２３におい
て、テスト処理はステツプ２４に移動し、ステツプ２４
において、図１に示したコンピユータの作図システムに
おいて、ノンコンベツクス多角形を作図するプロシージ
ヤが呼び出される。
【００１４】図８を参照すると、第１の辺１１４を包括
する領域ボツクス１１５と、比較辺１１７を包括する領
域ボツクス１１９を有する図５のコンプレツクス多角形
が示されている。図９は領域ボツクス１１５及び１１９
が相互に重なつていることを示している。本発明の方法
の説明に戻つて、ステツプ９において、これらの領域ボ
ツクスが重複するか否かが決定される。図９を参照する
と、ボツクス１１５と１１７とは重なり合つている。次
に、ステツプ１０において、辺１１４及び１１７の傾斜
が比較され、そして、ステツプ１１において、辺１１４
と辺１１７とを表わす線が交差するか否かが決定され
る。辺１１４及び１１７は交差していることが判り、ス
テツプ１２において、交差点１２０の座標が計算され
る。次に、交差点１２０は領域ボツクス１１５及び１１
９と比較され、そして、ステツプ１４において、交差点
１２０は領域ボツクス１１５及び１１９の両方の中に含
まれているか否かが決定される。図９は交差点１２０が
領域ボツクス１１５及び領域ボツクス１１９の中にある
ことを示している。従つて、この多角形は相互に交差す
る辺を持ち、この多角形はコンプレツクス多角形のクラ
スに分類されることが判る。次に、この多角形は、図１
に示したコンピユータの作図システムにおいて、コンプ
レツクス多角形に関するプロシージヤを使用することに
よつて描かれる。
する領域ボツクス１１５と、比較辺１１７を包括する領
域ボツクス１１９を有する図５のコンプレツクス多角形
が示されている。図９は領域ボツクス１１５及び１１９
が相互に重なつていることを示している。本発明の方法
の説明に戻つて、ステツプ９において、これらの領域ボ
ツクスが重複するか否かが決定される。図９を参照する
と、ボツクス１１５と１１７とは重なり合つている。次
に、ステツプ１０において、辺１１４及び１１７の傾斜
が比較され、そして、ステツプ１１において、辺１１４
と辺１１７とを表わす線が交差するか否かが決定され
る。辺１１４及び１１７は交差していることが判り、ス
テツプ１２において、交差点１２０の座標が計算され
る。次に、交差点１２０は領域ボツクス１１５及び１１
９と比較され、そして、ステツプ１４において、交差点
１２０は領域ボツクス１１５及び１１９の両方の中に含
まれているか否かが決定される。図９は交差点１２０が
領域ボツクス１１５及び領域ボツクス１１９の中にある
ことを示している。従つて、この多角形は相互に交差す
る辺を持ち、この多角形はコンプレツクス多角形のクラ
スに分類されることが判る。次に、この多角形は、図１
に示したコンピユータの作図システムにおいて、コンプ
レツクス多角形に関するプロシージヤを使用することに
よつて描かれる。
【００１５】以上の説明によつて、本発明は、ノンコン
ベツクス多角形か、またはコンプレツクス多角形かを決
定する手段を与えることが理解された。従つて、本発明
によつて、多角形を作図するための適切な作図技術が与
えられ、これにより、従来の技術の作図方法に比べて１
０倍の速さでノンコンベツクス多角形を作図することが
できる。
ベツクス多角形か、またはコンプレツクス多角形かを決
定する手段を与えることが理解された。従つて、本発明
によつて、多角形を作図するための適切な作図技術が与
えられ、これにより、従来の技術の作図方法に比べて１
０倍の速さでノンコンベツクス多角形を作図することが
できる。
【００１６】
【発明の効果】本発明は多角形の頂点だけを与えて、ノ
ンコンベツクス多角形を識別することができ、しかも、
コンプレツクス多角形を走査変換するための非常に複雑
なプロシージヤを用いずにノンコンベツクス多角形を作
図することができる。
ンコンベツクス多角形を識別することができ、しかも、
コンプレツクス多角形を走査変換するための非常に複雑
なプロシージヤを用いずにノンコンベツクス多角形を作
図することができる。
【図１】本発明を実施することのできるハードウエア構
成のタイプを示すブロツク図である。
成のタイプを示すブロツク図である。
【図２】コンプレツクス多角形からノンコンベツクス多
角形を判別するための本発明の処理方法を説明するため
の流れ図である。
角形を判別するための本発明の処理方法を説明するため
の流れ図である。
【図３】コンプレツクス多角形からノンコンベツクス多
角形を判別するための本発明の処理方法を説明するため
の流れ図である。
角形を判別するための本発明の処理方法を説明するため
の流れ図である。
【図４】コンプレツクス多角形からノンコンベツクス多
角形を判別するための本発明の処理方法を説明するため
の流れ図である。
角形を判別するための本発明の処理方法を説明するため
の流れ図である。
【図５】本発明によつて処理することのできる多角形の
３つのタイプの例を示す図である。
３つのタイプの例を示す図である。
【図６】ノンコンベツクス多角形の２つの辺に対応する
領域ボツクスの例を示す図である。
領域ボツクスの例を示す図である。
【図７】図６に示したボツクスによつて領域付けられた
辺の交差点を示す図である。
辺の交差点を示す図である。
【図８】コンプレツクス多角形の２つの辺に対応する領
域ボツクスの例を示す図である。
域ボツクスの例を示す図である。
【図９】図８で取り扱われた２つの辺の交差点を示し、
そして、その交差点が両方の領域ボツクスの中に含まれ
ていることを示す図である。
そして、その交差点が両方の領域ボツクスの中に含まれ
ていることを示す図である。
【符合の説明】 １ Ｘウインドウ・システムのクライエント・プログラ
ム ３ Ｘウインドウ・システムのライブラリ ５ Ｘウインドウ・システムのサーバ・プログラム ７ 入力装置 ９ デイスプレイ １０１ ベース辺 １０３、１０６ 比較辺 １０５ 最終比較辺 １０７ 最終ベース辺 １０９、１１１、１１５、１１９ 領域ボツクス １１３、１２０ 交差点
ム ３ Ｘウインドウ・システムのライブラリ ５ Ｘウインドウ・システムのサーバ・プログラム ７ 入力装置 ９ デイスプレイ １０１ ベース辺 １０３、１０６ 比較辺 １０５ 最終比較辺 １０７ 最終ベース辺 １０９、１１１、１１５、１１９ 領域ボツクス １１３、１２０ 交差点
Claims (20)
- 【請求項１】 コンピュータの作図システムにおいて表
示される多角形を識別するための方法において、 上記多角形の隣接しない少なくとも２つの辺のｘ及びｙ
座標に対応する最大値と最小値を有する上記少なくとも
２つの辺のための領域ボックスを夫々決定するステップ
と、 上記少なくとも２つの辺の延長線の交差点を決定するス
テップと、 上記交差点が夫々の上記領域ボックスの中に含まれるか
否か判断するステップと、 上記多角形を識別するために上記判断するステップの処
理によって得られた結果を用いるステップと、 を含む多角形の識別方法。 - 【請求項２】 領域ボツクスを決定する上記ステツプ
は、上記少なくとも２つの辺のうちの一方の辺がベース
辺であると指定し、他方の辺が比較辺であると指定する
ステツプを含むことを特徴とする請求項１に記載の多角
形の識別方法。 - 【請求項３】 上記結果を用いるステツプは、 上記交差点が上記領域ボツクスのうちの２つ以上の中に
含まれている場合、上記多角形はコンプレツクス多角形
であると識別するステツプを含むことを特徴とする請求
項２に記載の多角形の識別方法。 - 【請求項４】 上記識別するステツプは、 上記コンプレツクス多角形を処理するプロシージヤを呼
び出すステツプと、 上記コンピユータの作図システムにおいて、上記コンプ
レツクス多角形を表示するステツプとを含むことを特徴
とする請求項３に記載の多角形の識別方法。 - 【請求項５】 上記結果を用いるステツプは、 上記領域ボツクスのうちの２つ以上が重なつているか否
かを決定するステツプと、 上記交差点が少なくとも１つの上記領域ボツクスの外側
にあるか否かを決定するステツプと、 上記ベース辺と上記比較辺の上記交差点のすべてが、そ
の交差点に関連した辺の上記領域ボツクスの中にはない
場合、または、すべての上記領域ボツクスが重ならない
場合に、上記多角形はノンコンベツクス多角形であるこ
とを識別するステツプとを含むことを特徴とする請求項
２に記載の多角形の識別方法。 - 【請求項６】 上記識別するステツプは、 ノンコンベツクス多角形を処理するプロシージヤを呼び
出すステツプと、 上記コンピユータの作図システムにおいて、上記ノンコ
ンベツクス多角形を表示するステツプとを含むことを特
徴とする請求項５に記載の多角形の識別方法。 - 【請求項７】 上記多角形の各辺を一定方向に第１番目
乃至第Ｎ番目の辺に順番付けるステツプと、 上記ベース辺を第１番目の辺に設定するステツプと、 上記比較辺を第３番目の辺に設定するステップと、 を含むことを特徴とする請求項５に記載の多角形の識別
方法。 - 【請求項８】 最終比較辺を第Ｎ−１番目の辺に設定す
るステップと、 上記比較辺の順番が上記最終比較辺の順番に等しくない
場合、上記比較辺の順番を１つ増加するステップと、 上記順番を１つ増加した比較辺の夫々に対して、上記領
域ボックスを夫々決定するステップと、上記交差点を決
定するステップと、上記含まれるか否か判断するステッ
プ及び上記結果を用いるステップを繰り返すステップ
と、 を含むことを特徴とする請求項７に記載の多角形の識別
方法。 - 【請求項９】 最終比較辺を第Ｎ番目の辺に設定するス
テップと、 最終ベース辺を第Ｎ−２番目の辺に設定するステップ
と、 上記ベース辺の順番が上記最終ベース辺の順番に等しく
ない場合、上記ベース辺の順番を１つ増加し、上記比較
辺の順番を上記１つ増加したベース辺の順番＋２に設定
するステップと、 上記比較辺の順番が上記最終比較辺の順番に等しくない
場合、上記比較辺の順番を１つ増加するステップと、 上記順番を１つ増加した比較辺の夫々に対して、上記領
域ボックスを夫々決定するステップと、上記交差点を決
定するステップと、上記含まれるか否か判断するステッ
プ及び上記結果を用いるステップを繰り返すステップ
と、 を含むことを特徴とする請求項８に記載の多角形の識別
方法。 - 【請求項１０】 交差点を決定する上記ステツプは、上
記ベース辺及び上記比較辺の傾斜を計算するステツプ
と、 計算された上記傾斜に基づいて、上記ベース辺及び上記
比較辺の交差点の座標を計算するステツプとを含むこと
を特徴とする請求項９に記載の多角形の識別方法。 - 【請求項１１】 コンピュータの作図システムにおいて
表示される多角形を識別するためのシステムにおいて、 上記多角形の隣接しない少なくとも２つの辺のｘ及びｙ
座標に対応する最大値と最小値を有する上記少なくとも
２つの辺のための領域ボックスを夫々決定する手段と、 上記少なくとも２つの辺の延長線の交差点を決定する手
段と、 上記交差点が夫々の上記領域ボックスの中に含まれるか
否か判断する手段と、 上記多角形を識別するために上記判断する手段の処理に
よって得られた結果を用いる手段と、 を含む多角形の識別システム。 - 【請求項１２】 領域ボツクスを決定する上記手段は、
上記少なくとも２つの辺のうちの一方の辺がベース辺で
あると指定し、他方の辺が比較辺であると指定する手段
を含むことを特徴とする請求項１１に記載の多角形の識
別システム。 - 【請求項１３】 上記結果を用いる手段は、 上記交差点が上記領域ボツクスのうちの２つ以上の中に
含まれている場合、上記多角形はコンプレツクス多角形
であると識別する手段を含むことを特徴とする請求項１
２に記載の多角形の識別システム。 - 【請求項１４】 上記識別する手段は、 上記コンプレツクス多角形を処理するプロシージヤを呼
び出す手段と、 上記コンピユータの作図システムにおいて、上記コンプ
レツクス多角形を表示する手段とを含むことを特徴とす
る請求項１３に記載の多角形の識別システム。 - 【請求項１５】 上記結果を用いる手段は、 上記領域ボツクスのうちの２つ以上が重なつているか否
かを決定する手段と、 上記交差点が少なくとも１つの上記領域ボツクスの外側
にあるか否かを決定する手段と、 上記ベース辺と上記比較辺の上記交差点のすべてが、そ
の交差点に関連した辺の上記領域ボツクスの中にはない
場合、または、すべての上記領域ボツクスが重ならない
場合に、上記多角形はノンコンベツクス多角形であるこ
とを識別する手段とを含むことを特徴とする請求項１２
に記載の多角形の識別システム。 - 【請求項１６】 上記識別する手段は、 ノンコンベツクス多角形を処理するプロシージヤを呼び
出す手段と、 上記コンピユータの作図システムにおいて、上記ノンコ
ンベツクス多角形を表示する手段とを含むことを特徴と
する請求項１５に記載の多角形の識別システム。 - 【請求項１７】 上記多角形の各辺を一定方向に第１番
目乃至第Ｎ番目の辺に順番付ける手段と、 上記ベース辺を第１番目の辺に設定する手段と、 上記比較辺を第３番目の辺に設定する手段と、 を含むことを特徴とする請求項１５に記載の多角形の識
別システム。 - 【請求項１８】 最終比較辺を第Ｎ−１番目の辺に設定
する手段と、 上記比較辺の順番が上記最終比較辺の順番に等しくない
場合、上記比較辺の順番を１つ増加する手段と、 上記順番を１つ増加した比較辺の夫々に対して、上記領
域ボックスを夫々決定する手段と、上記交差点を決定す
る手段と、上記含まれるか否か判断する手段及び上記結
果を用いる手段を繰り返す手段と、 を含むことを特徴とする請求項１７に記載の多角形の識
別システム。 - 【請求項１９】 最終比較辺を第Ｎ番目の辺に設定する
手段と、 最終ベース辺を第Ｎ−２番目の辺に設定する手段と、 上記ベース辺の順番が上記最終ベース辺の順番に等しく
ない場合、上記ベース辺の順番を１つ増加し、上記比較
辺の順番を上記１つ増加したベース辺の順番＋２に設定
する手段と、 上記比較辺の順番が上記最終比較辺の順番に等しくない
場合、上記比較辺の順番を１つ増加する手段と、 上記順番を１つ増加した比較辺の夫々に対して、上記領
域ボックスを夫々決定する手段と、上記交差点を決定す
る手段と、上記含まれるか否か判断する手段及び上記結
果を用いる手段を繰り返す手段と、 を含むことを特徴とする請求項１８に記載の多角形の識
別システム。 - 【請求項２０】 交差点を決定する上記手段は、 上記ベース辺及び上記比較辺の傾斜を計算する手段と、 計算された上記傾斜に基づいて、上記ベース辺及び上記
比較辺の交差点の座標を計算する手段とを含むことを特
徴とする請求項１９に記載の多角形の識別システム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/693,828 US5347619A (en) | 1991-04-30 | 1991-04-30 | Nonconvex polygon identifier |
| US693828 | 1991-04-30 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04346182A JPH04346182A (ja) | 1992-12-02 |
| JPH07109629B2 true JPH07109629B2 (ja) | 1995-11-22 |
Family
ID=24786288
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4025997A Expired - Lifetime JPH07109629B2 (ja) | 1991-04-30 | 1992-01-17 | 多角形の識別方法、多角形を識別するシステム |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5347619A (ja) |
| EP (1) | EP0511835A3 (ja) |
| JP (1) | JPH07109629B2 (ja) |
Families Citing this family (18)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3332165B2 (ja) * | 1992-08-08 | 2002-10-07 | 株式会社リコー | 画像処理装置 |
| US5574835A (en) * | 1993-04-06 | 1996-11-12 | Silicon Engines, Inc. | Bounding box and projections detection of hidden polygons in three-dimensional spatial databases |
| US5644691A (en) * | 1994-10-14 | 1997-07-01 | Compaq Computer Corporation | Method and apparatus for accelerated filling of polygons on a computer display by rectangular decomposition |
| AU3313895A (en) * | 1994-10-14 | 1996-04-26 | Compaq Computer Corporation | Method and apparatus for determining simple convex polygons |
| JP3239975B2 (ja) * | 1994-11-29 | 2001-12-17 | 富士通株式会社 | 多角形描画装置 |
| US6172682B1 (en) * | 1996-01-24 | 2001-01-09 | Hewlett-Packard Co. | Detecting insideness of a rectangle to an arbitrary polygon |
| US6771264B1 (en) * | 1998-08-20 | 2004-08-03 | Apple Computer, Inc. | Method and apparatus for performing tangent space lighting and bump mapping in a deferred shading graphics processor |
| AU5686299A (en) | 1998-08-20 | 2000-03-14 | Raycer, Inc. | Method and apparatus for generating texture |
| AUPP771798A0 (en) * | 1998-12-14 | 1999-01-14 | Canon Kabushiki Kaisha | Overlapping edge blends and other texture mapped regions |
| US6917877B2 (en) | 2001-08-14 | 2005-07-12 | Navteq North America, Llc | Method for determining the intersection of polygons used to represent geographic features |
| US20030132932A1 (en) * | 2001-09-17 | 2003-07-17 | Xiangheng Yang | Method for constructing polygons used to represent geographic features |
| US6870533B2 (en) * | 2001-12-27 | 2005-03-22 | Texas Instruments Incorporated | Invalid shape detector (ISD) |
| US7599044B2 (en) | 2005-06-23 | 2009-10-06 | Apple Inc. | Method and apparatus for remotely detecting presence |
| US9298311B2 (en) * | 2005-06-23 | 2016-03-29 | Apple Inc. | Trackpad sensitivity compensation |
| US7577930B2 (en) | 2005-06-23 | 2009-08-18 | Apple Inc. | Method and apparatus for analyzing integrated circuit operations |
| US7433191B2 (en) | 2005-09-30 | 2008-10-07 | Apple Inc. | Thermal contact arrangement |
| US7598711B2 (en) | 2005-11-23 | 2009-10-06 | Apple Inc. | Power source switchover apparatus and method |
| US8707167B2 (en) * | 2006-11-15 | 2014-04-22 | Ebay Inc. | High precision data extraction |
Family Cites Families (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3889107A (en) * | 1972-10-16 | 1975-06-10 | Evans & Sutherland Computer Co | System of polygon sorting by dissection |
| US4783829A (en) * | 1983-02-23 | 1988-11-08 | Hitachi, Ltd. | Pattern recognition apparatus |
| US4791582A (en) * | 1985-09-27 | 1988-12-13 | Daikin Industries, Ltd. | Polygon-filling apparatus used in a scanning display unit and method of filling the same |
| US4862392A (en) * | 1986-03-07 | 1989-08-29 | Star Technologies, Inc. | Geometry processor for graphics display system |
| US4901251A (en) * | 1986-04-03 | 1990-02-13 | Advanced Micro Devices, Inc. | Apparatus and methodology for automated filling of complex polygons |
| US4809065A (en) * | 1986-12-01 | 1989-02-28 | Kabushiki Kaisha Toshiba | Interactive system and related method for displaying data to produce a three-dimensional image of an object |
| US4933865A (en) * | 1986-12-20 | 1990-06-12 | Fujitsu Limited | Apparatus for recognition of drawn shapes or view types for automatic drawing input in CAD system |
| US4930091A (en) * | 1987-11-04 | 1990-05-29 | Schlumberger Systems, Inc. | Triangle classification setup method and apparatus for 3-D graphics display system |
| US4962468A (en) * | 1987-12-09 | 1990-10-09 | International Business Machines Corporation | System and method for utilizing fast polygon fill routines in a graphics display system |
| US4897805A (en) * | 1988-05-17 | 1990-01-30 | Prime Computer, Inc. | Method and apparatus for performing polygon fills in graphical applications |
| US4951227A (en) * | 1988-09-30 | 1990-08-21 | Tektronix, Inc. | Dimension analysis of drawings |
| US5276783A (en) * | 1989-11-21 | 1994-01-04 | International Business Machines Corporation | Tessellating complex polygons in modeling coordinates |
| US5129051A (en) * | 1990-03-16 | 1992-07-07 | Hewlett-Packard Company | Decomposition of arbitrary polygons into trapezoids |
-
1991
- 1991-04-30 US US07/693,828 patent/US5347619A/en not_active Expired - Fee Related
-
1992
- 1992-01-17 JP JP4025997A patent/JPH07109629B2/ja not_active Expired - Lifetime
- 1992-04-28 EP EP19920303835 patent/EP0511835A3/en not_active Withdrawn
Also Published As
| Publication number | Publication date |
|---|---|
| EP0511835A2 (en) | 1992-11-04 |
| JPH04346182A (ja) | 1992-12-02 |
| EP0511835A3 (en) | 1994-07-06 |
| US5347619A (en) | 1994-09-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH07109629B2 (ja) | 多角形の識別方法、多角形を識別するシステム | |
| EP0112942B1 (en) | Graphics display system and method | |
| EP0356103B1 (en) | Scan-conversion process and processor | |
| JP3030206B2 (ja) | グラフィック多角形をクリップ領域にクリップする方法および装置 | |
| JP2585515B2 (ja) | 図形描画方法 | |
| US5546524A (en) | Method and apparatus for interlocking graphical objects | |
| JP3066599B2 (ja) | コンピュータ出力表示装置で表示するための多角形をクリップする方法 | |
| US5369741A (en) | Method for pre-clipping a line lying within a clipping rectangular region which is a subset of a region of a display screen | |
| US6172682B1 (en) | Detecting insideness of a rectangle to an arbitrary polygon | |
| US7714861B1 (en) | Method of producing electronically readable documents with updatable pie charts | |
| US6831660B1 (en) | Method and apparatus for graphics window clipping management in a data processing system | |
| US5261032A (en) | Method for manipulation rectilinearly defined segmnts to form image shapes | |
| US5563990A (en) | Method and apparatus for processing a pick event | |
| US6304270B1 (en) | Method and apparatus for determining simple convex polygons | |
| US5644691A (en) | Method and apparatus for accelerated filling of polygons on a computer display by rectangular decomposition | |
| US5727190A (en) | Method and system for the acceleration of graphics images in a multiprocessor or preemptive processing computer system | |
| JP2955995B2 (ja) | 画像操作方法 | |
| JP2520007B2 (ja) | ビットマップディスプレイ装置における図形のピック方式 | |
| JP2714114B2 (ja) | グラフィック処理方法及びグラフィックシステム | |
| JPH01261722A (ja) | マルチウインドウ表示装置とマルチウインドウ表示制御方法およびマルチウインドウ表示制御装置 | |
| JP2937219B2 (ja) | ピック入力方式 | |
| JP2780496B2 (ja) | 描画装置のクリッピング処理方式 | |
| JPS63228274A (ja) | マルチウインドウにおけるクリツピング方式 | |
| JPH0746388B2 (ja) | 色塗り描画装置 | |
| Paisner | The evolution and architecture of a high-speed workstation for interactive graphics |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
| S533 | Written request for registration of change of name |
Free format text: JAPANESE INTERMEDIATE CODE: R313533 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| LAPS | Cancellation because of no payment of annual fees | ||
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |