JPH07118023B2 - 任意多角形の内部点算出装置 - Google Patents
任意多角形の内部点算出装置Info
- Publication number
- JPH07118023B2 JPH07118023B2 JP5854987A JP5854987A JPH07118023B2 JP H07118023 B2 JPH07118023 B2 JP H07118023B2 JP 5854987 A JP5854987 A JP 5854987A JP 5854987 A JP5854987 A JP 5854987A JP H07118023 B2 JPH07118023 B2 JP H07118023B2
- Authority
- JP
- Japan
- Prior art keywords
- polygon
- line
- constant width
- internal point
- memory
- 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
Landscapes
- Digital Computer Display Output (AREA)
- Image Generation (AREA)
Description
【発明の詳細な説明】 （産業上の利用分野） 本発明はラスタスキヤン形デイスプレイ装置におけるグ
ラフイツク機能実現方式、さらに詳しくいえば複数の頂
点を指定して、構成される任意多角形の内部点を算出す
る装置に関する。
ラフイツク機能実現方式、さらに詳しくいえば複数の頂
点を指定して、構成される任意多角形の内部点を算出す
る装置に関する。
（従来の技術） 従来、複数の頂点を指定し、それによつて構成される任
意多角形の内部点算出の一つの方式として多角形の各辺
をすべてベクトルで表わし、数値計算によつて算出する
方式が考えられていた。
意多角形の内部点算出の一つの方式として多角形の各辺
をすべてベクトルで表わし、数値計算によつて算出する
方式が考えられていた。
（発明が解決しようとする問題点） しかし、この方式は計算量が多く中央処理装置に大きな
負荷を与える結果となり、処理速度の遅い中央処理装置
では処理時間が長くなるという欠点がある。また、計算
で求めた内部点の値と実際にリフレツシユメモリ上に書
かれた多角形の内部点が計算誤差のために一致しない場
合があり、かかる場合には正確な内部点を算出すること
ができない 他の方式として指定された多角形の頂点のうち最左点を
Ｎとし、その前後の頂点をＮ−1,N＋１として点Ｎ−１
とＮ＋１の中点Ｐを計算により求める方式がある。これ
は最左点Ｎと点Ｐを結ぶ直線ｌに沿つてワークメモリＷ
の内容を順次読出し、最初に“0"となつた点を内部点と
することにより決定するものである。この方式では多角
形により２つ以上の矩形が生成された場合、矩形すべて
の内部点を求めることができず、また、頂点N,N−1,N＋
１以外の頂点が直線ｌ上にあり、かつ、Ｎに隣接した場
合にも、その内部点を求めることができない。
負荷を与える結果となり、処理速度の遅い中央処理装置
では処理時間が長くなるという欠点がある。また、計算
で求めた内部点の値と実際にリフレツシユメモリ上に書
かれた多角形の内部点が計算誤差のために一致しない場
合があり、かかる場合には正確な内部点を算出すること
ができない 他の方式として指定された多角形の頂点のうち最左点を
Ｎとし、その前後の頂点をＮ−1,N＋１として点Ｎ−１
とＮ＋１の中点Ｐを計算により求める方式がある。これ
は最左点Ｎと点Ｐを結ぶ直線ｌに沿つてワークメモリＷ
の内容を順次読出し、最初に“0"となつた点を内部点と
することにより決定するものである。この方式では多角
形により２つ以上の矩形が生成された場合、矩形すべて
の内部点を求めることができず、また、頂点N,N−1,N＋
１以外の頂点が直線ｌ上にあり、かつ、Ｎに隣接した場
合にも、その内部点を求めることができない。
本発明の目的は、以上の従来の欠点を解決するもので、
複雑な計算処理や誤差修正を行う必要のない、また、複
雑なリフレツシユメモリ上の走査も行う必要のない任意
多角形の内部点を求めることのできる内部点算出装置を
提供することにある。
複雑な計算処理や誤差修正を行う必要のない、また、複
雑なリフレツシユメモリ上の走査も行う必要のない任意
多角形の内部点を求めることのできる内部点算出装置を
提供することにある。
（問題点を解決するための手段） 前記目的を達成するために本発明による任意多角形の内
部点算出装置は、中央処理装置と、前記中央処理装置か
ら指定された多角形の頂点位置、線種等に基づいて対応
するリフレッシュメモリ上に表示すべき図形を書込んだ
り、読出したりするグラフ表示制御部と、赤、緑、青等
の各色に対応する表示データを画素に対応するアドレス
位置に格納し、読出データによってCRT表示部への図形
表示を行うリフレッシュメモリを備え、指定された多角
形の内部点を算出する内部点算出装置において、前記リ
フレッシュメモリと同じ描画ドット数を持つワークメモ
リを備え、前記グラフ表示制御部は指定された多角形の
輪郭を前記ワークメモリに書込み、前記多角形を構成す
る各頂点に等しくない１以上の座標を求め、これら座標
を含んで形成される一定幅の線と計算上で求めた多角形
を構成する直線とが交わる数を前記一定幅の線毎に算出
し、一方、前記座標に対応する多角形のデータを前記ワ
ークメモリから読み出し、一定の形式でデータが変化す
る部分の数を前記一定幅の線対応毎に求め、前記一定幅
の線と計算上で求めた多角形を構成する直線とが交わる
数と前記一定の形式でデータが変化する部分の数が一致
する一定幅の線上であって所定の形式でデータが変化す
る部分を内部点とするように構成してある。
部点算出装置は、中央処理装置と、前記中央処理装置か
ら指定された多角形の頂点位置、線種等に基づいて対応
するリフレッシュメモリ上に表示すべき図形を書込んだ
り、読出したりするグラフ表示制御部と、赤、緑、青等
の各色に対応する表示データを画素に対応するアドレス
位置に格納し、読出データによってCRT表示部への図形
表示を行うリフレッシュメモリを備え、指定された多角
形の内部点を算出する内部点算出装置において、前記リ
フレッシュメモリと同じ描画ドット数を持つワークメモ
リを備え、前記グラフ表示制御部は指定された多角形の
輪郭を前記ワークメモリに書込み、前記多角形を構成す
る各頂点に等しくない１以上の座標を求め、これら座標
を含んで形成される一定幅の線と計算上で求めた多角形
を構成する直線とが交わる数を前記一定幅の線毎に算出
し、一方、前記座標に対応する多角形のデータを前記ワ
ークメモリから読み出し、一定の形式でデータが変化す
る部分の数を前記一定幅の線対応毎に求め、前記一定幅
の線と計算上で求めた多角形を構成する直線とが交わる
数と前記一定の形式でデータが変化する部分の数が一致
する一定幅の線上であって所定の形式でデータが変化す
る部分を内部点とするように構成してある。
（実施例） 以下、図面を参照して本発明をさらに詳しく説明する。
第１図は、本発明による内部点算出装置の一実施例を示
すブロック図である。中央処理装置（CPU）２、ランダ
ムアクセスメモリ（RAM）３、およびグラフ表示制御部
４はバス１によつて接続されている。中央処理装置２は
指定されたコマンドを解析し、グラフ表示に必要なパラ
メータ（座標位置など）の計算を行い、バス１を介して
グラフ表示制御部４に与える。
すブロック図である。中央処理装置（CPU）２、ランダ
ムアクセスメモリ（RAM）３、およびグラフ表示制御部
４はバス１によつて接続されている。中央処理装置２は
指定されたコマンドを解析し、グラフ表示に必要なパラ
メータ（座標位置など）の計算を行い、バス１を介して
グラフ表示制御部４に与える。
グラフ表示制御部４は後述するように映像メモリ５の書
込み、読出しの制御を行う。
込み、読出しの制御を行う。
RAM3は中央処理装置２が演算する場合のワークエリアお
よび映像メモリ５のリード／ライトのためのバツフア等
として使用される。映像メモリ５を構成する赤、緑、青
用のリフレツシユメモリR,G,Bの読出しデータはビデオ
制御部６によつてビデオ信号に変換され、CRT表示部７
上に表示される。
よび映像メモリ５のリード／ライトのためのバツフア等
として使用される。映像メモリ５を構成する赤、緑、青
用のリフレツシユメモリR,G,Bの読出しデータはビデオ
制御部６によつてビデオ信号に変換され、CRT表示部７
上に表示される。
ワークメモリW8はリフレツシユメモリと同様な機能を持
つワーク用メモリであつて、内部点算出動作時に多角形
の輪郭の書込み、読出すアドレスを求めるために使用さ
れ、その内容はビデオ制御部６へは出力されない。
つワーク用メモリであつて、内部点算出動作時に多角形
の輪郭の書込み、読出すアドレスを求めるために使用さ
れ、その内容はビデオ制御部６へは出力されない。
グラフ表示制御部４は、中央処理装置２から与えられた
パラメータによつて点、線分、円、円弧等のグラフイツ
クパターンを映像メモリ５内に描く。
パラメータによつて点、線分、円、円弧等のグラフイツ
クパターンを映像メモリ５内に描く。
任意の多角形の内部点を算出する場合は、以下に示すよ
うな処理手順によつて行われる。
うな処理手順によつて行われる。
（１） グラフ表示制御部４は、中央処理装置２からの
指示によりワークメモリＷをクリアする。
指示によりワークメモリＷをクリアする。
（２） そして、多角形の輪郭を、指定された色に対応
するリフレツシユメモリR,G,Bに、指定された線種、
（点線、実線、破線等）で描く。
するリフレツシユメモリR,G,Bに、指定された線種、
（点線、実線、破線等）で描く。
（３） 次に、ワークメモリW8上に上記多角形の輪郭の
コピーを実線で描く。なお、多角形の輪郭が一部欠けて
いて閉領域を構成していないと中央処理装置が判断した
ときは適当な補助線を追加して閉領域を構成させる。
コピーを実線で描く。なお、多角形の輪郭が一部欠けて
いて閉領域を構成していないと中央処理装置が判断した
ときは適当な補助線を追加して閉領域を構成させる。
（４） 多角形を構成する各頂点のＹ方向の最小値と最
大値の範囲より、いかなる頂点とも等しくない１つまた
は複数のＹ座標を求める。
大値の範囲より、いかなる頂点とも等しくない１つまた
は複数のＹ座標を求める。
（５） 上記により（４）により決定されたｙ座標がア
ナログ的に多角形を構成する直線と交わる直線の総数を
求める。
ナログ的に多角形を構成する直線と交わる直線の総数を
求める。
これは次の手順により行われる。
（４）で求めたｙ座標を含む一定幅の線yN,yN+1・・・
を求め、その範囲内に存在する多角形を構成する直線の
総数を求める。第２図は前記一定幅の線の範囲内に存在
する多角形を構成する直線の例を示している。第２図の
例ではａすなわちy1〜y2の範囲をyN、ｂすなわちy3〜y4
の範囲をyN+1・・・としており、実線の太い部分をyN,y
N+1・・・としている。第２図ではａの範囲に存在する
多角形を構成する直線の総数は４個であり、b,cの範囲
についてもそれぞれ４個である。
を求め、その範囲内に存在する多角形を構成する直線の
総数を求める。第２図は前記一定幅の線の範囲内に存在
する多角形を構成する直線の例を示している。第２図の
例ではａすなわちy1〜y2の範囲をyN、ｂすなわちy3〜y4
の範囲をyN+1・・・としており、実線の太い部分をyN,y
N+1・・・としている。第２図ではａの範囲に存在する
多角形を構成する直線の総数は４個であり、b,cの範囲
についてもそれぞれ４個である。
（６） 次に多角形を構成する各頂点のＸ方向の最大値
と最小値を求め、その範囲内を（４）で求めたｙ座標に
従つて対応するワークメモリW8上のデータを読出し、
“0"→“1"となる総数を求める。
と最小値を求め、その範囲内を（４）で求めたｙ座標に
従つて対応するワークメモリW8上のデータを読出し、
“0"→“1"となる総数を求める。
第３図に第２図のｙ座標に従つて対応するワークメモリ
W8上のデータを読出した例を示してある。
W8上のデータを読出した例を示してある。
かかる場合、ｙ＝ａの場合は３、ｙ＝ｂの場合は４、ｙ
＝ｃの場合は２となる。なお、図中の黒丸は“1"に、白
丸は“0"にそれぞれ対応する。
＝ｃの場合は２となる。なお、図中の黒丸は“1"に、白
丸は“0"にそれぞれ対応する。
（７） 次いで（５）で求めた総数と（６）で求めた総
数が等しいものを求め、（６）において最初に“0"→
“1"となり、次に“1"→“0"となつた“0"のアドレスを
内部点とする。
数が等しいものを求め、（６）において最初に“0"→
“1"となり、次に“1"→“0"となつた“0"のアドレスを
内部点とする。
第２図と第３図で示した例ではｙ＝ｂの場合のみ、
（５）で求めた総数と（６）で求めた総数が等しくな
る。
（５）で求めた総数と（６）で求めた総数が等しくな
る。
第４図は、内部点算出の具体的な例を示す図で、各範囲
において矢印で示したアドレスが（７）で示す条件を満
たすもので、内部点と判断される。
において矢印で示したアドレスが（７）で示す条件を満
たすもので、内部点と判断される。
（発明の効果） 以上説明したように本発明は、リフレツシユメモリの他
に多角形の輪郭等を書込むことができるワークメモリを
備え、このワークメモリに輪郭を書込んで当該ワークメ
モリのデータを参照しながら、多角形の内部点を算出す
るように構成されているので、リフレツシユメモリR,G,
B上のデータに影響することなしに内部点を判別するこ
とができる。また、多角形の線種が破線等で指定された
場合もワークメモリ上に実線で描画することにより内部
点を算出することが可能である。したがつて、本発明は
複雑な計算処理をすることなく任意多角形の内部点を制
限なく求めることができるという効果がある。
に多角形の輪郭等を書込むことができるワークメモリを
備え、このワークメモリに輪郭を書込んで当該ワークメ
モリのデータを参照しながら、多角形の内部点を算出す
るように構成されているので、リフレツシユメモリR,G,
B上のデータに影響することなしに内部点を判別するこ
とができる。また、多角形の線種が破線等で指定された
場合もワークメモリ上に実線で描画することにより内部
点を算出することが可能である。したがつて、本発明は
複雑な計算処理をすることなく任意多角形の内部点を制
限なく求めることができるという効果がある。
第１図は、本発明による任意多角形の内部点算出装置の
一実施例を示すブロツク図、第２図は論理的な多角形の
直線総数を示す図、第３図は物理的な多角形の直線総数
を示す図、第４図は内部点算出の具体的な図である。 １……バス ２……中央処理装置（CPU） ３……ランダムアクセスメモリ（RAM） ４……グラフ表示制御部 ５……リフレツシユメモリ ６……ビデオ制御部 ７……CRT表示部 ８……ワークメモリ
一実施例を示すブロツク図、第２図は論理的な多角形の
直線総数を示す図、第３図は物理的な多角形の直線総数
を示す図、第４図は内部点算出の具体的な図である。 １……バス ２……中央処理装置（CPU） ３……ランダムアクセスメモリ（RAM） ４……グラフ表示制御部 ５……リフレツシユメモリ ６……ビデオ制御部 ７……CRT表示部 ８……ワークメモリ
Claims (1)
- 【請求項１】中央処理装置と、前記中央処理装置から指
定された多角形の頂点位置、線種等に基づいて対応する
リフレッシュメモリ上に表示すべき図形を書込んだり、
読出したりするグラフ表示制御部と、赤、緑、青等の各
色に対応する表示データを画素に対応するアドレス位置
に格納し、読出しデータによってCRT表示部への図形表
示を行うリフレッシュメモリを備え、指定された多角形
の内部点を算出する内部点算出装置において、 前記リフレッシュメモリと同じ描画ドット数を持つワー
クメモリを備え、 前記グラフ表示制御部は指定された多角形の輪郭を前記
ワークメモリに書込み、前記多角形を構成する各頂点に
等しくない１以上の座標を求め、これら座標を含んで形
成される一定幅の線と計算上で求めた多角形を構成する
直線とが交わる数を前記一定幅の線毎に算出し、一方、
前記座標に対応する多角形のデータを前記ワークメモリ
から読み出し、予め定めた第１の形式でデータが変化す
る画素の数を前記一定幅の線対応毎に求め、前記一定幅
の線と計算上で求めた多角形を構成する直線とが交わる
数と前記予め定めた第１の形式でデータが変化する画素
の数が一致する一定幅の線上であって予め定めた第２の
形式でデータが変化する画素を内部点とするように構成
したことを特徴とする任意多角形の内部点算出装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5854987A JPH07118023B2 (ja) | 1987-03-13 | 1987-03-13 | 任意多角形の内部点算出装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5854987A JPH07118023B2 (ja) | 1987-03-13 | 1987-03-13 | 任意多角形の内部点算出装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63223981A JPS63223981A (ja) | 1988-09-19 |
| JPH07118023B2 true JPH07118023B2 (ja) | 1995-12-18 |
Family
ID=13087537
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5854987A Expired - Lifetime JPH07118023B2 (ja) | 1987-03-13 | 1987-03-13 | 任意多角形の内部点算出装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH07118023B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107705311B (zh) * | 2017-08-16 | 2020-10-09 | 歌尔科技有限公司 | 图像轮廓的内外识别方法及设备 |
-
1987
- 1987-03-13 JP JP5854987A patent/JPH07118023B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPS63223981A (ja) | 1988-09-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4914729A (en) | Method of filling polygonal region in video display system | |
| JPH0554114B2 (ja) | ||
| JPH07146952A (ja) | ３次元画像処理装置 | |
| US5461703A (en) | Pixel image edge enhancement method and system | |
| WO2006080115A1 (ja) | 描画方法、画像生成装置、および電子情報機器 | |
| US4747042A (en) | Display control system | |
| JP3547250B2 (ja) | 描画方法 | |
| US6215501B1 (en) | Method and filling a polygon and recording medium | |
| US4967376A (en) | Method for displaying characters and/or figures in a computer graphics and apparatus thereof | |
| EP0356262B1 (en) | Image processing apparatus | |
| AU4613600A (en) | Method and apparatus for generating outlines | |
| JP3872056B2 (ja) | 描画方法 | |
| US6900804B1 (en) | Method of forming polygon image and image processing apparatus using the same | |
| JP2660707B2 (ja) | 三次元図形のピック方法 | |
| JP4320604B2 (ja) | 画像処理方法および画像処理装置 | |
| JPS63223981A (ja) | 任意多角形の内部点算出装置 | |
| JPS62204389A (ja) | 任意多角形によるクリツピング・シ−ルデイング方法 | |
| JPH0711780B2 (ja) | 図形表示装置 | |
| JPH06150015A (ja) | フィルポリゴンの作成方法 | |
| JP2787497B2 (ja) | 図形描画方法及び装置 | |
| JP2988936B2 (ja) | 三次元図形の処理装置 | |
| JPH08305865A (ja) | 図形描画装置 | |
| JP2634906B2 (ja) | 画像処理方法 | |
| JPS6314286A (ja) | 円描画方式 | |
| JPH10261095A (ja) | 画像処理装置及び画像処理方法 |