JPH04346182A

JPH04346182A - 多角形の識別方法、多角形を識別するシステム

Info

Publication number: JPH04346182A
Application number: JP4025997A
Authority: JP
Inventors: David J Erb; ダビッド・ジヨン・エルブ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-04-30
Filing date: 1992-01-17
Publication date: 1992-12-02
Anticipated expiration: 2010-11-22
Also published as: US5347619A; EP0511835A3; JPH07109629B2; EP0511835A2

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、コンピユータの作図シ
ステムにおいて、デイスプレイに表示される画像のデー
タを処理し、デイスプレイ・スクリーン上に多角形の画
像を作図し、表示することに関する。より具体的に言え
ば、本発明は、頂点だけを与えられたノンコンベツクス
多角形（ｎｏｎｃｏｎｖｅｘ　ｐｏｌｙｇｏｎ）（凹み
を持つ多角形）を識別する方法に関する。

【０００２】

【従来の技術】コンピユータの作図システムにおいて図
形を作図し、そして表示しなければならない多角形には
３つのクラスがある（図５参照）。第１のクラスに属す
るコンベツクス多角形（凹みを持たない多角形）は、そ
の多角形を取り囲む辺が決して交差することがなく、か
つ、常に同じ方向に回転するので、コンベツクス多角形
は、作図するのに最も簡単なクラスの多角形である。こ
のクラスの多角形の構造は、カルテシアン座標系の「Ｙ
」軸方向において、完全に連続した１つのスパンがある
ことと、多角形内に含まれた各「Ｙ」軸の値に対して、
最小値及び最大値（上部及び底部）の間に、連続したス
パンを持つていることとを保証する。連続したスパンと
は、コンピユータの作図システムにおいて表示するため
にスクリーン上に示された多角形に含まれる画素（ピク
セル）の走査線を意味する。

【０００３】第２のクラスに属するノンコンベツクス多
角形は、周辺が交差することはないけれども、内部角度
は１８０度よりも大きな角度を含んでいる（ノンコンベ
ツクス多角形は明確に区別できる１つの内部領域と、１
つの外部領域とを持つている）。従つて、ノンコンベツ
クス多角形が作図される時、任意に与えられた「Ｙ」座
標軸の値に対して、２つの別個のスパンがある。つまり
、ノンコンベツクス多角形は、凹面領域（窪んだ部分）
の何れかの側において、「Ｙ」座標軸方向に走査変換さ
れるスパンを作る凹面部分を持つていると言うことであ
る。

【０００４】第３のクラスに分類されるコンプレツクス
多角形は、最も複雑な多角形のクラスに属するものであ
り、この多角形は、１つの内部領域と、１つの外部領域
とを明確に分けることができないから、それに応じて、
走査変換処理が最も難しいクラスの多角形である。コン
プレツクス多角形の辺は、あらゆる方向に回転すること
ができ、交差することができる。従つて、多角形中に、
「Ｙ」座標軸方向の複数の走査ラインを持たせる問題や
、幾つかの「Ｙ」軸方向の走査ラインに対して走査線を
持たせないという問題に加えて、コンプレツクス多角形
は、多角形を完成するために、２つの経路を持つている
問題がある。つまり、コンプレツクス多角形には、２つ
に分けられた明確な内部領域及び外部領域がないので、
多角形を完結するために、多角形のどちらの領域を完結
するのかを決定しなければならない問題があるというこ
とである。

【０００５】コンプレツクス多角形を完結する従来の方
法は、「奇−偶（ｏｄｄ−ｅｖｅｎ）」ルール及び「ワ
インデイング（ｗｉｎｄｉｎｇ）」ルールを含んでいる
（１９９０年アデイソン・ウエスリー社（Ａｄｄｉｓｏ
ｎ−Ｗｅｓｌｙ）刊行のホレイ（Ｊ．Ｆｏｌｅｙ）等の
共同の著作物の「コンピユータ・グラフイツクス、原理
と実際（Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ：　Ｐｒ
ｉｎｃｉｐｌｅｓ　ａｎｄ　Ｐｒａｃｔｉｃｅ）」と題
する記述の９６５頁を参照）。コンプレツクス多角形を
作図することは、ノンコンベツクス多角形、またはコン
ベツクス多角形を作図する処理に比べて、非常に多くの
計算処理を含んでおり、より多くのリソースと、より多
くの時間とが必要である。通常、コンプレツクス多角形
を作図するのに絶対必要な必須時間は、ノンコンベツク
ス多角形を作図するための必須時間よりも、１０倍程度
の長い時間を必要とする。

【０００６】Ｘウインドウ・システム（Ｘウインドウ・
システム（Ｘ　Ｗｉｎｄｏｗ　Ｓｙｓｔｅｍ）はＭＩＴ
の商標）のような通常のグラフイツク・システムにおい
て、クライエント・プログラムは、作図されるべき多角
形のクラスについてのヒントを送る。多角形を作図する
ために、少なくとも最適なクラスを使用しなければなら
ないと言う意味において、上述のヒントは排他的なもの
である。つまり、排他的であるということは、これらの
ヒントが、実際に入力され、作図されるべき多角形のク
ラスよりも、より簡単な多角形のクラスを表示すること
ができないと言うことを意味する。例えば、コンベツク
ス多角形において、Ｘウインドウ・システムのクライエ
ント・プログラムは、コンベツクス多角形、ノンコンベ
ツクス多角形、またはコンプレツクス多角形のためのヒ
ントを与えて、コンベツクス多角形を正しく作図するこ
とができる。然しながら、ノンコンベツクス多角形にお
いて、ノンコンベツクス多角形、またはコンプレツクス
多角形に向けられたヒントは、ノンコンベツクス多角形
を適正に作図するのを保証するヒントだけしか含んでい
ない。更に、コンプレツクス多角形において、コンプレ
ツクス多角形のためのヒントは、コンプレツクス多角形
を適正に作図するためのヒントだけしか含んでいない。若し、コンベツクス多角形を作図するためのヒントが、
Ｘウインドウ・システムのサーバ・プログラムに与えら
れ、そして、実際に作図される多角形がコンプレツクス
多角形ならば、コンベツクス多角形を作図するための方
法はコンプレツクス多角形には当て嵌らないので、それ
らのヒントに従つた結果は、意味を明らかにすることが
できず、その結果、作図された多角形は不正確に作図さ
れることになる。また、コンピユータ・グラフイツクに
関する従来の技術において、一組の頂点と、それらの頂
点に対応したヒントを与えることによつてコンベツクス
多角形を識別する方法がある。

【０００７】

【発明が解決しようとする課題】多角形のクラスを知る
ことは、多角形を作図する手段を最も効果的に利用する
ことができるので、ノンコンベツクス多角形からコンプ
レツクス多角形を識別する方法があれば、非常に有益で
あることは、上述の記載から容易に理解できるであろう
。これにより、多角形を走査変換するための非常に複雑
なプロシージヤを必要とする従来の方法を回避すること
ができ、ノンコンベツクス多角形を作図することは従来
よりも１０倍も早くすることができる。

【０００８】

【課題を解決するための手段】従来の技術とは異なつて
、本発明は多角形がコンプレツクス多角形としてマーク
されているとしても、多角形の頂点だけを与えて、ノン
コンベツクス多角形を識別するための経済的な計算方法
を与える。つまり、コンプレツクス多角形として多角形
を知らせる「ヒント」が与えられた時に、本発明は、実
際に作図される多角形をノンコンベツクス多角形として
識別するか、または、作図されるべき多角形が実際には
コンプレツクス多角形であることを確かめる。

【０００９】本発明は、総括的に言うと、多角形の辺（
エツジ）が相互に交差しているかを検出するために、多
角形の辺を比較することを基本としている。最初に、多
角形の「基本の辺、即ち「ベース辺」と、これと比較す
るための「比較辺」とが指定され、そして、これらの辺
の各々に対して領域ボツクス（ｂｏｕｎｄｉｎｇ　ｂｏ
ｘ）が決められる。領域ボツクスは、各辺を対角線とし
て包含する単純な矩形であつて、カルテシアン座標系の
座標軸の最大値及び最小値（ｘ値及びｙ値）を持つてい
る。次に、２つの領域ボツクスが比較され、若し、領域
ボツクスが重なるならば、ベース辺と比較辺とは共通点
を持つており、これに反して、若し、領域ボツクスが重
ならなければ、これら２つの辺には共通点はなく、そし
て、これらの辺の順序の番号は増加され、他の辺の領域
ボツクスとの比較を行なう。

【００１０】領域ボツクスが重なることが決定されたな
らば、現在処理している２つの辺が交差する交差点の座
標が計算される。若し、この交差点が両方の領域ボツク
スの中に含まれていれば、その多角形はコンプレツクス
多角形であり、このテストは終了する。然しながら、若
し、交差点が、いずれの領域ボツクスの中にも含まれて
いなければ、多角形の辺の順序番号は増加され、そして
、関係するすべての辺が処理されるまで、同様な処理が
続けられる。

【００１１】

【実施例】図１を参照すると、本発明を実施するための
代表的なコンピユータの作図システムのブロツク図が示
されている。図１において、参照数字１は、Ｘウインド
ウ・システムのライブラリ（ＸＬｉｂ）３を含むＸウイ
ンドウ・システムのクライエント・プログラム（Ｘ−Ｃ
ｌｉｅｎｔ）と呼ばれるソフトウエアのアプリケーシヨ
ン・プログラムを示している。Ｘウインドウ・システム
のクライエント・プログラム１は、デイスプレイ９と、
キーボードや、マウスなどのような入力装置７との間に
相互接続されたＸウインドウ・システムのサーバ・プロ
グラム５と相互通信を行なう。Ｘウインドウ・システム
のクライエント・プログラム１及びＸウインドウ・シス
テムのサーバ・プログラム５はＸウインドウ・システム
を実行することのできるワークステーシヨンを動作する
ことができ、そして、ＩＢＭ社で生産されているＲＩＳ
Ｃシステム／６０００を含んでいることは注意を要する
（ＲＩＳＣシステム／６０００及びＩＢＭは商標である
）。Ｘウインドウ・システムのクライエント・プログラ
ム１によつてヒントがＸウインドウ・システムのサーバ
・プログラム５に与えられたときに、コンプレツクス多
角形、またはノンコンベツクス多角形を作図する必要が
あるか否かを決定する動作を、本発明が遂行することが
できるように、参照数字１１で示されている本発明は、
Ｘウインドウ・システムのサーバ・プログラム５中に含
まれている。ここで、アプリケーシヨン・プログラム（
図示せず）と関連して入力装置７を介してＸウインドウ
・システムのサーバ・プログラム５へ入力される特定の
多角形を作図することをユーザが望んでいるものとする
。従つて、Ｘウインドウ・システムのサーバ・プログラ
ム５は、どのようにして多角形が作図されるべきかに関
してヒントを与えるＸウインドウ・システムのクライエ
ント・プログラム１と通信する。若し、そのヒントが「
コンベツクス」ならば、本発明は、最も簡単なコンベツ
クス多角形が作図されることを知り、そして、そのよう
に処理する。然しながら、若し、Ｘウインドウ・システ
ムのクライエント・プログラム１からのヒントが「コン
プレツクス」であれば、Ｘウインドウ・システムのクラ
イエント・プログラムは、これら２つのクラスの間を区
別する能力がないから、描かれるべき多角形は、「コン
プレツクス」多角形であるか、または、「ノンコンベツ
クス」多角形であるかを決定するために、本発明の技術
が呼び出される。この決定がなされたならば、Ｘウイン
ドウ・システムのサーバ・プログラム５は、最も効果的
な方法で、その多角形をデイスプレイ９に作図すること
ができる。

【００１２】図２乃至図４を参照すると、ノンコンベツ
クス多角形を識別するために、本発明に従つた方法を説
明するための流れ図が示されている。図２乃至図４によ
つて示された処理ステツプは、Ｘウインドウ・システム
のサーバ・プログラム５にあるソフトウエア及びそれに
関連して動作するソフトウエア・コードによつて実行さ
れる。このソフトウエア・コードは、ノンコンベツクス
多角形及びコンプレツクス多角形の物理的な形状をデイ
スプレイ９に表示するように、ワークステーシヨンのＸ
−サーバ・プログラム５を制御する。

【００１３】図２を参照すると、ステツプ１において、
コンプレツクス多角形であるか、ノンコンベツクス多角
形であるかのテストが開始される。この時点で、コンプ
レツクスのヒントがＸウインドウ・システムのクライエ
ント・プログラムによつて受け取られており、そして、
Ｎ個の辺を持つコンプレツクス多角形が作図されるのか
、またはＮ個の辺を持つ単なるノンコンベツクス多角形
が作図されるのかを決定するために、本発明が呼び出さ
れる。ステツプ２において、多角形の基本辺、即ち「ベ
ース辺」が処理され、順序番号１、つまり第１番目の辺
として設定される。本発明の実施例を説明するために、
例えば参照数字１０１をベース辺であるとし、この辺が
第１の辺であるものとして示されている図５のノンコン
ベツクス多角形を考えてみる。ここで、多角形のどの辺
をベース辺として決めるかとは関係なしに、本発明を機
能させることができるので、ベース辺の指定は任意に決
めることができる。次に、ステツプ３において、図５の
ノンコンベツクス多角形の周りを時計方向の向きに処理
し、図５の多角形の３番目の辺は「比較辺」として処理
され、参照数字１０３で示されている。ステツプ４にお
いて、反時計方向に回つてベース辺と隣り合うであろう
「最終比較辺」は、Ｎ−１番目の辺として設定される。参照数字１０５は、図５のノンコンベツクス多角形の「
最終比較辺」を示している。ステツプ５において、「最
終ベース辺」は、反時計方向回りで最終比較辺と隣接し
たＮ−２番目の辺に設定され、参照数字１０７で示され
ている。ステツプ６において、図５のノンコンベツクス
多角形において現在対象としているベース辺のための領
域ボツクスが決定される。図６に示したノンコンベツク
ス多角形Ａは、ベース辺１０１を包括する領域ボツクス
１０９を示している。領域ボツクス１０９は、ベース辺
１０１のＸ座標軸の最大値及び最小値及びＹ座標軸の最
大値及び最小値で形成された単純な矩形であることが判
る。ステツプ６に続くステツプ７において、比較辺１０
３のための領域ボツクス１１１が決められる。図６のコ
ンベツクス多角形Ｂを参照すると、比較辺１０３を対角
線として包括する領域ボツクス１１１は、ベース辺１０
１を対角線として包括している領域ボツクス１０９の上
に重なつていることが示されている。図３の流れ図のス
テツプ８において、ベース辺の領域ボツクス１０９と比
較辺の領域ボツクス１１１との間の比較が行なわれる。次に、ステツプ９において、領域ボツクスが重なつてい
るか否かが決定される。若し、重なりがなければ、処理
は、後述するステツプ１７に進む。これらの領域ボツク
スが重なつているものと仮定すると、ステツプ１０にお
いて、例えば、Ｙの切片等式（ｉｎｔｅｒｃｅｐｔ　ｅ
ｑｕａｔｉｏｎ）（Ｙ＝ＭＸ＋Ｂ）のような線型代数学
を用いることによつて、辺１０１及び１０３の傾斜を計
算することができる。次に、ステツプ１１において、こ
れらの辺の線が交差するか否かが決定される（この例に
おいては、辺１０１及び１０３は交差する）。図７にお
いて、辺１０１及び１０３の線が点１１３で交差するこ
とが判る。然しながら、若し、これらの辺の線が交差し
なければ（辺が平行な場合）、処理は、ステツプ１７に
続く。ステツプ１２において、交差点１１３の座標軸の
値が計算され、そして、ステツプ１３において、交差点
１１３とベース辺の領域ボツクス１０９との比較と、交
差点１１３と領域辺の比較ボツクス１１１との比較が夫
々行なわれる。ステツプ１４において、交差点１１３は
比較辺の領域ボツクス及びベース辺の領域ボツクスの両
方の中にあるか否かが決定される。若し、交差点１１３
がこれらの領域ボツクス中に含まれていれば、本発明は
、この多角形はコンプレツクス多角形であると決定する
。次に、ステツプ１５において、このテストはステツプ
１６に移動し、ステツプ１６において、コンプレツクス
多角形を作図するためのプロシージヤが実行される。然
しながら、図５のノンコンベツクス多角形のベース辺１
０１及び比較辺１０３とを比較してみると、交差点１１
３は、それらの辺の領域ボツクス１０９及び１１１の中
には入つていないことが図７から判る。従つて、この処
理はステツプ１７（図４）に続き、このステツプにおい
て、現在処理されている比較辺は「最終比較辺」である
か否か、つまり、ステツプ４におけるＮ−１番目の辺で
あるか否かが決定される。このノンコンベツクス多角形
の辺の最初の処理、つまり、この流れ図の処理の第１の
処理の場合のように、若し、その比較辺が「最終比較辺
」でなければ、ステツプ１８において、比較辺の処理は
ステツプ７の処理に戻され、ステツプ７において、次の
順番の番号を持つ比較辺の新しい領域ボツクスが決定さ
れる。この新しい領域ボツクスは、ステツプ８において
既に説明したように、ベース辺の領域ボツクスと比較さ
れる。ステツプ１７において、若し、比較辺１０５が「
最終比較辺」（Ｎ−１番目の辺）に遭遇したならば、ス
テツプ１９は、「最終比較辺」を、図５のノンコンベツ
クス多角形の参照数字１０６によつて示されているＮ番
目の比較辺に設定する。ステツプ１７における「最終比
較辺」に遭遇するまで、「ベース辺」１０１と比較しな
ければならない「比較辺」がある限り、本発明の比較動
作が遂行されることは、上述の説明から理解されるであ
ろう。「最終比較辺」がステツプ１９においてＮ番目の辺に設
定された後、ステツプ２０において、そのベース辺が、
事実上、「最終ベース辺」（ステツプ５のＮ−２番目の
辺）であるか否かが決定される。若し、「最終ベース辺
」１０７（図５）が、ステツプ２０において遭遇されな
ければ、ステツプ２１において、そのベース辺の順番は
増加され、そして、比較辺はベース辺に２を加えた値に
設定される。ベース辺の順番を１つだけ増加すると、ベ
ース辺に隣接した比較辺として取り扱われ、隣り合う２
つの辺は相互に交差することはできないという定義があ
るので、ベース辺の順序番号に関して、比較辺の順序番
号を２つだけ増加することができるのが判る。次の処理
は、ステツプ６に移り、そして、処理は、前に説明した
図２、図３及び図４の流れ図のように進行する。ステツ
プ２０において、そのベース辺が最終的なベース辺であ
ることが決定されたならば、この多角形の辺を処理して
いる間で、ベース辺の領域ボツクス及び比較辺の領域ボ
ツクスの両方のボツクスの中に包含された２つの辺の交
差点は存在しなかつたので、その多角形はコンプレツク
ス多角形ではないことが判る。ステツプ２３において、
テスト処理はステツプ２４に移動し、ステツプ２４にお
いて、図１に示したコンピユータの作図システムにおい
て、ノンコンベツクス多角形を作図するプロシージヤが
呼び出される。

【００１４】図８を参照すると、第１の辺１１４を包括
する領域ボツクス１１５と、比較辺１１７を包括する領
域ボツクス１１９を有する図５のコンプレツクス多角形
が示されている。図９は領域ボツクス１１５及び１１９
が相互に重なつていることを示している。本発明の方法
の説明に戻つて、ステツプ９において、これらの領域ボ
ツクスが重複するか否かが決定される。図９を参照する
と、ボツクス１１５と１１７とは重なり合つている。次
に、ステツプ１０において、辺１１４及び１１７の傾斜
が比較され、そして、ステツプ１１において、辺１１４
と辺１１７とを表わす線が交差するか否かが決定される
。辺１１４及び１１７は交差していることが判り、ステ
ツプ１２において、交差点１２０の座標が計算される。次に、交差点１２０は領域ボツクス１１５及び１１９と
比較され、そして、ステツプ１４において、交差点１２
０は領域ボツクス１１５及び１１９の両方の中に含まれ
ているか否かが決定される。図９は交差点１２０が領域
ボツクス１１５及び領域ボツクス１１９の中にあること
を示している。従つて、この多角形は相互に交差する辺
を持ち、この多角形はコンプレツクス多角形のクラスに
分類されることが判る。次に、この多角形は、図１に示
したコンピユータの作図システムにおいて、コンプレツ
クス多角形に関するプロシージヤを使用することによつ
て描かれる。

【００１５】以上の説明によつて、本発明は、ノンコン
ベツクス多角形か、またはコンプレツクス多角形かを決
定する手段を与えることが理解された。従つて、本発明
によつて、多角形を作図するための適切な作図技術が与
えられ、これにより、従来の技術の作図方法に比べて１
０倍の速さでノンコンベツクス多角形を作図することが
できる。

【００１６】

【発明の効果】本発明は多角形の頂点だけを与えて、ノ
ンコンベツクス多角形を識別することができ、しかも、
コンプレツクス多角形を走査変換するための非常に複雑
なプロシージヤを用いずにノンコンベツクス多角形を作
図することができる。

【図面の簡単な説明】

【図１】本発明を実施することのできるハードウエア構
成のタイプを示すブロツク図である。

【図２】コンプレツクス多角形からノンコンベツクス多
角形を判別するための本発明の処理方法を説明するため
の流れ図である。

【図３】コンプレツクス多角形からノンコンベツクス多
角形を判別するための本発明の処理方法を説明するため
の流れ図である。

【図４】コンプレツクス多角形からノンコンベツクス多
角形を判別するための本発明の処理方法を説明するため
の流れ図である。

【図５】本発明によつて処理することのできる多角形の
３つのタイプの例を示す図である。

【図６】ノンコンベツクス多角形の２つの辺に対応する
領域ボツクスの例を示す図である。

【図７】図６に示したボツクスによつて領域付けられた
辺の交差点を示す図である。

【図８】コンプレツクス多角形の２つの辺に対応する領
域ボツクスの例を示す図である。

【図９】図８で取り扱われた２つの辺の交差点を示し、
そして、その交差点が両方の領域ボツクスの中に含まれ
ていることを示す図である。

【符合の説明】

１　　Ｘウインドウ・システムのクライエント・プログ
ラム３　　Ｘウインドウ・システムのライブラリ５　　Ｘウ
インドウ・システムのサーバ・プログラム７　　入力装
置９　　デイスプレイ１０１　　ベース辺１０３、１０６　　比較辺１０５　　最終比較辺１０７　　最終ベース辺１０９、１１１、１１５、１１９　　領域ボツクス１１
３、１２０　　交差点

Claims

【特許請求の範囲】

【請求項１】　　コンピユータの作図システムにおいて
表示される多角形を識別するための方法において、上記
多角形の少なくとも２つの辺のための領域ボツクスを決
定するステツプと、上記少なくとも２つの辺の交差点を
決定するステツプと、上記交差点と上記領域ボツクスと
を比較するステツプと、上記多角形を識別するために上
記比較するステツプの処理によつて得られた結果を用い
るステツプとからなる多角形の識別方法。
【請求項２】　　領域ボツクスを決定する上記ステツプ
は、上記少なくとも２つの辺のうちの一方の辺がベース
辺であると指定し、他方の辺が比較辺であると指定する
ステツプを含むことを特徴とする請求項１に記載の多角
形の識別方法。
【請求項３】　　上記結果を用いるステツプは、上記交
差点が上記領域ボツクスの各々の中に含まれているか否
かを決定するステツプと、上記多角形はコンプレツクス
多角形であると識別するステツプとを含むことを特徴と
する請求項２に記載の多角形の識別方法。
【請求項４】　　上記識別するステツプは、上記コンプ
レツクス多角形を処理するプロシージヤを呼び出すステ
ツプと、上記コンピユータの作図システムにおいて、上
記コンプレツクス多角形を表示するステツプとを含むこ
とを特徴とする請求項３に記載の多角形の識別方法。
【請求項５】　　上記結果を用いるステツプは、上記領
域ボツクスが重なつているか否かを決定するステツプと
、上記交差点が少なくとも１つの上記領域ボツクスの外
側にあるか否かを決定するステツプと、上記ベース辺と
上記比較辺の上記交差点のすべては、その交差点に関連
した上記領域ボツクスの中にはないことが決定されるか
、または、すべての上記領域ボツクスが重ならないこと
が決定されるまで、識別するための上記方法を続けるス
テツプと、上記多角形はノンコンベツクス多角形である
ことを識別するステツプとを含むことを特徴とする請求
項２に記載の多角形の識別方法。
【請求項６】　　上記識別するステツプは、ノンコンベ
ツクス多角形を処理するプロシージヤを呼び出すステツ
プと、上記コンピユータの作図システムにおいて、上記
ノンコンベツクス多角形を表示するステツプとを含むこ
とを特徴とする請求項５に記載の多角形の識別方法。
【請求項７】　　識別するための上記方法を続けるステ
ツプは、上記ベース辺及び上記比較辺の順番を増加する
ステツプと、順番を増加された上記ベース辺及び順番を
増加された上記比較辺に対して、順番を増加された夫々
の領域ボツクスを決定するステツプと、順番を増加され
た上記ベース辺及び順番を増加された上記比較辺の交差
点を決定するステツプと、順番を増加された上記交差点
は、順番を増加された上記領域ボツクスのいずれかの領
域ボツクスの外側にあることを決定するステツプとを含
むことを特徴とする請求項５に記載の多角形の識別方法
。
【請求項８】　　順番を増加する上記ステツプは上記ベ
ース辺の順番を１つだけ増加し、上記比較辺の順番を２
だけ増加するステツプを含むことを特徴とする請求項７
に記載の多角形の識別方法。
【請求項９】　　交差点を決定する上記ステツプは、上
記ベース辺及び上記比較辺の傾斜を計算するステツプと
、計算された上記傾斜に基づいて、上記ベース辺及び上
記比較辺の交差点の座標を計算するステツプとを含むこ
とを特徴とする請求項８に記載の多角形の識別方法。
【請求項１０】　　コンピユータにより読み取り可能な
媒体を含み、コンピユータの作図システムにおいて表示
される多角形を識別するためのプログラム・プロダクト
において、上記多角形の少なくとも２つの辺のための領
域ボツクスを決定する手段と、少なくとも２つの辺の交
差点を決定する手段と、上記交差点と上記領域ボツクス
とを比較する手段と、上記多角形を識別するために上記
比較するステツプの処理によつて得られた結果を用いる
手段とからなる多角形を識別するプログラム・プロダク
ト。
【請求項１１】　　領域ボツクスを決定する上記手段は
、上記少なくとも２つの辺のうちの一方の辺がベース辺
であると指定し、他方の辺が比較辺であると指定する手
段を含むことを特徴とする請求項１０に記載の多角形を
識別するプログラム・プロダクト。
【請求項１２】　　上記結果を用いる手段は、上記交差
点が上記領域ボツクスの各々の中に含まれているか否か
を決定する手段と、上記多角形はコンプレツクス多角形
であると識別する手段とを含むことを特徴とする請求項
１１に記載の多角形を識別するプログラム・プロダクト
。
【請求項１３】　　上記識別する手段は、上記コンプレ
ツクス多角形を処理するプロシージヤを呼び出す手段と
、上記コンピユータの作図システムにおいて、上記コン
プレツクス多角形を表示する手段とを含むことを特徴と
する請求項１２に記載の多角形を識別するプログラム・
プロダクト。
【請求項１４】　　上記結果を用いる手段は、上記領域
ボツクスが重なるか否かを決定する手段と、上記交差点
が少なくとも１つの上記領域ボツクスの外側にあるか否
かを決定する手段と、上記ベース辺と上記比較辺の上記
交差点のすべてが上記領域ボツクスの関連した領域ボツ
クスの中にはないことが決定されるか、または、上記領
域ボツクスのいずれもが重ならないことが決定されるま
で、識別するための上記方法を続けるステツプと、上記
多角形はノンコンベツクス多角形であることを識別する
手段とを含むことを特徴とする請求項１１に記載の多角
形を識別するプログラム・プロダクト。
【請求項１５】　　上記識別する手段は、ノンコンベツ
クス多角形を処理するプロシージヤを呼び出す手段と、
上記コンピユータの作図システムにおいて、上記ノンコ
ンベツクス多角形を表示する手段とを含むことを特徴と
する請求項１４に記載の多角形を識別するプログラム・
プロダクト。
【請求項１６】　　上記方法を続ける上記手段は、上記
ベース辺及び上記比較辺の順番を増加する手段と、順番
を増加された上記ベース辺及び順番を増加された上記比
較辺に対して、増加された夫々の領域ボツクスを決定す
る手段と、順番を増加された上記ベース辺及び順番を増
加された上記比較辺の交差点を決定する手段と、順番を
増加された上記交差点は順番を増加された上記領域ボツ
クスのいずれかの領域ボツクスの外側にあることを決定
する手段とを含むことを特徴とする請求項１４に記載の
多角形を識別するプログラム・プロダクト。
【請求項１７】　　順番を増加する上記ステツプは上記
ベース辺の順番を１つだけ増加し、上記比較辺の順番を
２だけ増加する手段を含むことを特徴とする請求項１６
に記載の多角形を識別するプログラム・プロダクト。
【請求項１８】　　交差点を決定する上記手段は、上記
ベース辺及び上記比較辺の傾斜を計算する手段と、計算
された上記傾斜に基づいて、上記ベース辺及び上記比較
辺の交差点の座標を計算する手段とを含むことを特徴と
する請求項１７に記載の多角形を識別するプログラム・
プロダクト。
【請求項１９】　　コンピユータの作図システムにおい
て表示される多角形を識別するためのシステムにおいて
、上記多角形の少なくとも２つの辺のための領域ボツク
スを決定する手段と、上記少なくとも２つの辺の交差点
を決定する手段と、上記交差点と上記領域ボツクスとを
比較する手段と、上記多角形を識別するために上記比較
するステツプの処理によつて得られた結果を用いる手段
とからなる多角形の識別システム。
【請求項２０】　　領域ボツクスを決定する上記手段は
、上記少なくとも２つの辺のうちの一方の辺がベース辺
である指定し、他方の辺が比較辺であると指定する手段
を含むことを特徴とする請求項１９に記載の多角形の識
別システム。
【請求項２１】　　上記結果を用いる手段は、上記交差
点が上記領域ボツクスの各々の中に含まれているか否か
を決定する手段と、上記多角形はコンプレツクス多角形
であると識別する手段とを含むことを特徴とする請求項
２０に記載の多角形の識別システム。
【請求項２２】　　上記識別する手段は、上記コンプレ
ツクス多角形を処理するプロシージヤを呼び出す手段と
、上記コンピユータの作図システムにおいて、上記コン
プレツクス多角形を表示する手段とを含むことを特徴と
する請求項２１に記載の多角形の識別システム。
【請求項２３】　　上記結果を用いる手段は、上記領域
ボツクスが重なるか否かを決定する手段と、上記交差点
が少なくとも１つの上記領域ボツクスの外側にあるか否
かを決定する手段と、上記ベース辺と上記比較辺の上記
交差点のすべてが上記領域ボツクスの関連した領域ボツ
クスの中にはないことが決定されるか、または、上記領
域ボツクスのいずれもが重ならないことが決定されるま
で、識別するための上記方法を続ける手段と、上記多角
形はノンコンベツクス多角形であることを識別する手段
とを含むことを特徴とする請求項２０に記載の多角形の
識別システム。
【請求項２４】　　上記識別する手段は、ノンコンベツ
クス多角形を処理するプロシージヤを呼び出す手段と、
上記コンピユータの作図システムにおいて、上記ノンコ
ンベツクス多角形を表示する手段とを含むことを特徴と
する請求項２３に記載の多角形の識別システム。
【請求項２５】　　識別する上記方法を続ける上記手段
は、上記ベース辺及び上記比較辺の順番を増加する手段
と、順番を増加された上記ベース辺及び順番を増加され
た上記比較辺に対して、順番を増加された夫々の領域ボ
ツクスを決定する手段と、順番を増加された上記ベース
辺及び順番を増加された上記比較辺の交差点を決定する
手段と、順番を増加された上記交差点は、順番を増加さ
れた上記領域ボツクスのいずれかの領域ボツクスの外側
にあることを決定する手段とを含むことを特徴とする請
求項２３に記載の多角形の識別システム。
【請求項２６】　　順番を増加する上記ステツプは上記
ベース辺の順番を１つだけ増加し、上記比較辺の順番を
２だけ増加する手段を含むことを特徴とする請求項２５
に記載の多角形の識別システム。
【請求項２７】　　交差点を決定する上記手段は、上記
ベース辺及び上記比較辺の傾斜を計算する手段と、計算
された上記傾斜に基づいて、上記ベース辺及び上記比較
辺の交差点の座標を計算する手段とを含むことを特徴と
する請求項２６に記載の多角形の識別システム。