JPS63188281A - 図形処理装置 - Google Patents
図形処理装置Info
- Publication number
- JPS63188281A JPS63188281A JP62020225A JP2022587A JPS63188281A JP S63188281 A JPS63188281 A JP S63188281A JP 62020225 A JP62020225 A JP 62020225A JP 2022587 A JP2022587 A JP 2022587A JP S63188281 A JPS63188281 A JP S63188281A
- Authority
- JP
- Japan
- Prior art keywords
- line segments
- intersection
- line
- polygon
- axis
- 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.)
- Granted
Links
- 238000003672 processing method Methods 0.000 title claims description 6
- 238000000034 method Methods 0.000 description 16
- 238000010586 diagram Methods 0.000 description 7
- 238000007796 conventional method Methods 0.000 description 3
- 230000000694 effects Effects 0.000 description 3
- 230000012447 hatching Effects 0.000 description 2
- 241000251468 Actinopterygii Species 0.000 description 1
- 238000012217 deletion Methods 0.000 description 1
- 230000037430 deletion Effects 0.000 description 1
- 235000015170 shellfish Nutrition 0.000 description 1
Landscapes
- Image Generation (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は、任意個の中空多角形を含む多角形に対して、
中空多角形の内部を除いた多角形ｆｉｎ １８に、Ｙ軸
に平行な等間隔の線分群を生成する図形処理方法に関す
る。
中空多角形の内部を除いた多角形ｆｉｎ １８に、Ｙ軸
に平行な等間隔の線分群を生成する図形処理方法に関す
る。
本発明は、多角形に含まれる中空多角形の内部を除く領
域にＹ軸に平行でかつ等間隔の線分群を生成する方法に
おいて、 Ｙ軸に平行な直線群に関しての交点のソーティング処理
に代わり、多角形の外周を構成する線分を頂点ごとの集
合にソーティングおよびＸ軸方向に対して共有１部分を
もつ線分のＹ軸方向の上下関係によるソーティングを行
うことにより、等間隔の線分群の生成に要する時間を短
縮することができるようにしたものである。
域にＹ軸に平行でかつ等間隔の線分群を生成する方法に
おいて、 Ｙ軸に平行な直線群に関しての交点のソーティング処理
に代わり、多角形の外周を構成する線分を頂点ごとの集
合にソーティングおよびＸ軸方向に対して共有１部分を
もつ線分のＹ軸方向の上下関係によるソーティングを行
うことにより、等間隔の線分群の生成に要する時間を短
縮することができるようにしたものである。
第２図に示すように、中空多角形領域を含む多角形領域
に対して作画用のハンチング・データ（点線部分）を生
成する図形処理は、例えばプリント基板のパターン図面
を作画する処理などで必要とされる。
に対して作画用のハンチング・データ（点線部分）を生
成する図形処理は、例えばプリント基板のパターン図面
を作画する処理などで必要とされる。
従来、ハツチング・データを生成する場合に、多角形と
Ｙ軸に平行に等間隔に引かれた直線群との交点を求め、
すべての交点が求まった後にそれぞれの直線に対して交
点をＸ座標値でソーティングし、奇数番目の交点から直
後の交点までの線分をとりだす方法が行われていた。
Ｙ軸に平行に等間隔に引かれた直線群との交点を求め、
すべての交点が求まった後にそれぞれの直線に対して交
点をＸ座標値でソーティングし、奇数番目の交点から直
後の交点までの線分をとりだす方法が行われていた。
このような従来の方法では、平面上に等間隔に引かれた
直線群から求めるべき線分群をとりだす処理過程で、直
線上の交点群をそれぞれの直線ごとにソーティングする
必要があり、ハツチング線分の間隔および対象とする平
面の大きさなどにより直線の数が増大すると、それに比
例して処理時間が増大する欠点がある。
直線群から求めるべき線分群をとりだす処理過程で、直
線上の交点群をそれぞれの直線ごとにソーティングする
必要があり、ハツチング線分の間隔および対象とする平
面の大きさなどにより直線の数が増大すると、それに比
例して処理時間が増大する欠点がある。
本発明はこのような欠点を除去するもので、直線上の交
点群のソーティング処理を行うことなく求むべき線分群
が得られる図形処理方法を提供することを目的とする。
点群のソーティング処理を行うことなく求むべき線分群
が得られる図形処理方法を提供することを目的とする。
本発明は、Ｘ軸およびＹ軸が直交する座標面上にあり、
任意価の中空多角形を含む多角形に対し、この中空多角
形の内部を除く多角形領域に上記Ｙ軸に平行な等間隔の
線分群を生成する図形処理方法において、はじめに、上
記多角形の外周を構成する線分ごとに上記Ｘ軸方向に対
して共有部分をもつ線分につき上記Ｙ軸方向の上下関係
に従って一方向に順序づけ、ひきつづき、この順序に従
って取りだした線分と上記Ｙ軸に平行に等間隔の直線群
との交点を求め、さらに、この直線のそれぞれに対して
交点の求められた順序に従って奇数番目の交点とその直
後の順序の交点とを結ぶ線分を上記Ｙ軸に平行な等間隔
の線分群とすることを特徴とする。
任意価の中空多角形を含む多角形に対し、この中空多角
形の内部を除く多角形領域に上記Ｙ軸に平行な等間隔の
線分群を生成する図形処理方法において、はじめに、上
記多角形の外周を構成する線分ごとに上記Ｘ軸方向に対
して共有部分をもつ線分につき上記Ｙ軸方向の上下関係
に従って一方向に順序づけ、ひきつづき、この順序に従
って取りだした線分と上記Ｙ軸に平行に等間隔の直線群
との交点を求め、さらに、この直線のそれぞれに対して
交点の求められた順序に従って奇数番目の交点とその直
後の順序の交点とを結ぶ線分を上記Ｙ軸に平行な等間隔
の線分群とすることを特徴とする。
多角形の外周を線分に分解し、この線分をＸ方向に対し
て共有部分をもつものに関してＹ方向の上下関係に従っ
て１方向に順序づけ、この順序に従って線分を取り出し
、この線分とＹ軸に平行に等間隔に引かれた直線群との
交点を求め、それぞれの直線に対して交点の求められた
順序に従って奇数番目の交点から直後の交点までの線分
をとりだすことにより、直線上の交点群のソーティング
処理を行うことなく求めるべき線分群を得る。
て共有部分をもつものに関してＹ方向の上下関係に従っ
て１方向に順序づけ、この順序に従って線分を取り出し
、この線分とＹ軸に平行に等間隔に引かれた直線群との
交点を求め、それぞれの直線に対して交点の求められた
順序に従って奇数番目の交点から直後の交点までの線分
をとりだすことにより、直線上の交点群のソーティング
処理を行うことなく求めるべき線分群を得る。
次に、本発明の一実施例を図面を参照して説明する。
第１図は、本発明の一実施例の構成を示す概念図である
。この実施例は、多角形の外周を線分に分解する手段と
、多角形の頂点の集合をＸ座標を第１キー、Ｘ座標を第
２キーとしてソーティングする手段と、線分をＸ方向に
対して共有部分をもつものに関してＹ方向の上下関係に
従って１方向に順序づける手段と、線分を順次とり出し
この線分とＹ軸に平行に等間隔に引かれた直線群との交
点を求める手段と、それぞれの直線に対して交点の求め
られた順序に従って奇数番目の交点から直後の交点まで
の線分をとり出す手段とで構成される。
。この実施例は、多角形の外周を線分に分解する手段と
、多角形の頂点の集合をＸ座標を第１キー、Ｘ座標を第
２キーとしてソーティングする手段と、線分をＸ方向に
対して共有部分をもつものに関してＹ方向の上下関係に
従って１方向に順序づける手段と、線分を順次とり出し
この線分とＹ軸に平行に等間隔に引かれた直線群との交
点を求める手段と、それぞれの直線に対して交点の求め
られた順序に従って奇数番目の交点から直後の交点まで
の線分をとり出す手段とで構成される。
第３図は、中空多角形を含む多角形の一例であり、点線
が中空多角形、実線がそれを含む多角形 。
が中空多角形、実線がそれを含む多角形 。
を示している。
第４図は第３図の多角形の外周を線分に分解し、多角′
形の頂点の集合をＸ座標を第１キ・−１Ｙ座標を第２キ
ーとしてソーティングした結果を示す。
形の頂点の集合をＸ座標を第１キ・−１Ｙ座標を第２キ
ーとしてソーティングした結果を示す。
なお、それぞれの点は、それがどの線分の左端点（線分
の両端点を比較し、Ｘ座標の小さい方、等しければＸ座
標の小さい方）または右端点であるかがわかるようにな
っている。
の両端点を比較し、Ｘ座標の小さい方、等しければＸ座
標の小さい方）または右端点であるかがわかるようにな
っている。
次に、線分をＸ方向に対して共有部分をもつものに関し
てＹ方向の上下関係に従って１方向に順序づける手段を
実施例に基づいて説明する。
てＹ方向の上下関係に従って１方向に順序づける手段を
実施例に基づいて説明する。
第５図は第３図における点Ｅを通りＹ軸に平行な直線ｌ
の場合に、直線ｌと共有点をもつ線分をＹ方向の上下関
係で順序づけた線分のならびを示す。なお、同一点に左
端点がある線分は傾きが大きい方が上位になるものとし
ている。以下の説明では、この直線ｉ上における線分の
ならびの集合をＱと呼ぶことにする。
の場合に、直線ｌと共有点をもつ線分をＹ方向の上下関
係で順序づけた線分のならびを示す。なお、同一点に左
端点がある線分は傾きが大きい方が上位になるものとし
ている。以下の説明では、この直線ｉ上における線分の
ならびの集合をＱと呼ぶことにする。
第６図はこの実施例の順序づけ手段の処理手順を示すフ
ローチャートである。すなわち、ｉ）ソーティングされ
た順序に従って点をとりだしくとりだす点がなければ終
了）、 １１）線分の左端点であればｉｉｉ ）へ、右端点であ
ればｉｖ）へ進む、 ｉｉｉ ）その点を通る直線ｌに関する集合Ｑへその点
を左端点とする線分を挿入してｉ）へ進む、ｉｖ）その
点を右端点とする線分を集合Ｑから削除するが、削除す
る時点で集合Ｑに隣接する上位の線分があるときは、そ
の線分あるいはその線分がリンクする線分群示あればそ
の最後尾の線分の直後に削除する線分がくるようなリン
ク・ポインタを両者間に設定し、また、上位の線分がな
い場合には隣接する下位の線分があればその線分を、あ
るいはその線分がリンクする線分群であればその先頭の
線分の直前に削除する線分がくるようなリンク・ポイン
タを両者間に設定し、また、上位および下位とも線分が
存在しない場合はすでに処理された線分群の最後尾にく
るようにリンク・ポインタを設定してｉ）へ進む。
ローチャートである。すなわち、ｉ）ソーティングされ
た順序に従って点をとりだしくとりだす点がなければ終
了）、 １１）線分の左端点であればｉｉｉ ）へ、右端点であ
ればｉｖ）へ進む、 ｉｉｉ ）その点を通る直線ｌに関する集合Ｑへその点
を左端点とする線分を挿入してｉ）へ進む、ｉｖ）その
点を右端点とする線分を集合Ｑから削除するが、削除す
る時点で集合Ｑに隣接する上位の線分があるときは、そ
の線分あるいはその線分がリンクする線分群示あればそ
の最後尾の線分の直後に削除する線分がくるようなリン
ク・ポインタを両者間に設定し、また、上位の線分がな
い場合には隣接する下位の線分があればその線分を、あ
るいはその線分がリンクする線分群であればその先頭の
線分の直前に削除する線分がくるようなリンク・ポイン
タを両者間に設定し、また、上位および下位とも線分が
存在しない場合はすでに処理された線分群の最後尾にく
るようにリンク・ポインタを設定してｉ）へ進む。
以上の処理をすべての点に対して行うことにより、Ｘ方
向に対して共有部分をもつ線分に関するＹ方向の上下関
係に従う１方向の順序づけが実現される。
向に対して共有部分をもつ線分に関するＹ方向の上下関
係に従う１方向の順序づけが実現される。
第７図は上記手順の流れに従って線分の順序づけがなさ
れる経過を第３図の例を使っ、て説明したものである。
れる経過を第３図の例を使っ、て説明したものである。
なお、Ｙ軸に平行な線分に関しては処理過程で順序づけ
の対象からはずしてもかまわな゛い。すなわち、ハツチ
ング線分はＹ軸に平行であると仮定しているからである
。
の対象からはずしてもかまわな゛い。すなわち、ハツチ
ング線分はＹ軸に平行であると仮定しているからである
。
このようにして順序づけられた線分を順次とりだし、Ｙ
軸に平行に等間隔に引かれた直線群との交点を求めれば
、それぞれの直線上の交点はＹ座標の大きい順に順番に
求められる。したがってミそれぞれの直線に対して交点
の求められた順序に従って奇数番目の交点から直後の交
点までの線分をとり出すことで所望のハツチング・デー
タが生成される。
軸に平行に等間隔に引かれた直線群との交点を求めれば
、それぞれの直線上の交点はＹ座標の大きい順に順番に
求められる。したがってミそれぞれの直線に対して交点
の求められた順序に従って奇数番目の交点から直後の交
点までの線分をとり出すことで所望のハツチング・デー
タが生成される。
本発明は、以上説明したように、従来方式と比較して、
多角形の外周を線分に分解したあとの多角形の頂点の集
合のソーティングおよびＸ方向に対して共有部分をもつ
線分のＹ方向の上下関係によるソーティング処理が加わ
るが、Ｙ軸に平行な直線群に関しての交点のソーティン
グ処理をしなくてもすむ利点がある。
多角形の外周を線分に分解したあとの多角形の頂点の集
合のソーティングおよびＸ方向に対して共有部分をもつ
線分のＹ方向の上下関係によるソーティング処理が加わ
るが、Ｙ軸に平行な直線群に関しての交点のソーティン
グ処理をしなくてもすむ利点がある。
すなわち、分解された線分数をｎ、Ｙ軸に平行な直線の
数をｐ、直線上の交点の平均数をｑとすれば、従来方式
と比較して加わる計算の手間は共にｎｌｏｇｎであわせ
て２ｎｌｏｇｎであり、また削減される計算の手間はｐ
ｘｑｔｏｇｑになる。ｑが士数個、ｎがｑの数十倍、ｐ
が数千であるとじても処理時間が短縮されることになり
、ｐが増大すれば増大するほど本方式の効果は顕著にな
る。
数をｐ、直線上の交点の平均数をｑとすれば、従来方式
と比較して加わる計算の手間は共にｎｌｏｇｎであわせ
て２ｎｌｏｇｎであり、また削減される計算の手間はｐ
ｘｑｔｏｇｑになる。ｑが士数個、ｎがｑの数十倍、ｐ
が数千であるとじても処理時間が短縮されることになり
、ｐが増大すれば増大するほど本方式の効果は顕著にな
る。
第１図は、本発明実施例の構成を示す概念図。
第２図は、中空多角形を含む多角形に点線でハンチング
を施した状態図。 第３図は、中空多角形を含む多角形の一例を示す説明図
。 第・４図は、第３図の多角形の外周を線分に分解し、多
角形の頂点をソーティングした結果を示す説明図。 第５図は、Ｙ方向の上下関係により順序づけられた線分
群の説明図。 第６図は、Ｘ方向に対して共有部分をもつ線分に関して
Ｙ方向の上下関係により線分を１方向に順序づけを行う
処理手順を示すフローチャート。 第７図は、第３図の例に対して線分の順序づけがなされ
る過程を示す説明図。 夾廃例の講義 ；￥ｉ ｉ 図 八ツ÷ン７乏発した玖＝帆 ＷＪ ２ 図 り 多角形の一例 ′Ｍ ３ 図 魚介の嗅序ブ１↑ ＋ＡＤ＞ＡＢＩ （緬〉ＥＧ〉ＥＦ＞ＡＢ ］ ＠ ４ＥＧ （ＤＣ＞ＥＧ＞ＥＦ＞ＡＳ Ｉ Ａｏ−ｍＥｅ、＠ （ＤＣ＞ＥＧ＞ＦＧ＞Ａ３１ １Ｄｃ＞ＥＧ＞ＦＧ＞ＢＣＩ ＦＧ
４＠ＡＤ−、ＥＧ−ＥＦ−３−ＡＳ
を施した状態図。 第３図は、中空多角形を含む多角形の一例を示す説明図
。 第・４図は、第３図の多角形の外周を線分に分解し、多
角形の頂点をソーティングした結果を示す説明図。 第５図は、Ｙ方向の上下関係により順序づけられた線分
群の説明図。 第６図は、Ｘ方向に対して共有部分をもつ線分に関して
Ｙ方向の上下関係により線分を１方向に順序づけを行う
処理手順を示すフローチャート。 第７図は、第３図の例に対して線分の順序づけがなされ
る過程を示す説明図。 夾廃例の講義 ；￥ｉ ｉ 図 八ツ÷ン７乏発した玖＝帆 ＷＪ ２ 図 り 多角形の一例 ′Ｍ ３ 図 魚介の嗅序ブ１↑ ＋ＡＤ＞ＡＢＩ （緬〉ＥＧ〉ＥＦ＞ＡＢ ］ ＠ ４ＥＧ （ＤＣ＞ＥＧ＞ＥＦ＞ＡＳ Ｉ Ａｏ−ｍＥｅ、＠ （ＤＣ＞ＥＧ＞ＦＧ＞Ａ３１ １Ｄｃ＞ＥＧ＞ＦＧ＞ＢＣＩ ＦＧ
４＠ＡＤ−、ＥＧ−ＥＦ−３−ＡＳ
Claims (1)
- （１）Ｘ軸およびＹ軸が直交する座標面上にあり、任意
個の中空多角形を含む多角形に対し、この中空多角形の
内部を除く多角形領域に上記Ｙ軸に平行な等間隔の線分
群を生成する図形処理方法において、 はじめに、上記多角形の外周を構成する線分ごとに上記
Ｘ軸方向に対して共有部分をもつ線分につき上記Ｙ軸方
向の上下関係に従って一方向に順序づけ、 ひきつづき、この順序に従って取りだした線分と上記Ｙ
軸に平行に等間隔の直線群との交点を求め、 さらに、この直線のそれぞれに対して交点の求められた
順序に従って奇数番目の交点とその直後の順序の交点と
を結ぶ線分を上記Ｙ軸に平行な等間隔の線分群とする ことを特徴とする図形処理方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62020225A JPH0750510B2 (ja) | 1987-01-30 | 1987-01-30 | 図形処理装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62020225A JPH0750510B2 (ja) | 1987-01-30 | 1987-01-30 | 図形処理装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63188281A true JPS63188281A (ja) | 1988-08-03 |
| JPH0750510B2 JPH0750510B2 (ja) | 1995-05-31 |
Family
ID=12021224
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62020225A Expired - Lifetime JPH0750510B2 (ja) | 1987-01-30 | 1987-01-30 | 図形処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0750510B2 (ja) |
-
1987
- 1987-01-30 JP JP62020225A patent/JPH0750510B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0750510B2 (ja) | 1995-05-31 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| AU2023201614B2 (en) | Device and method for improving route planning computing devices | |
| US7499045B2 (en) | Graphics image generation | |
| Capson | An improved algorithm for the sequential extraction of boundaries from a raster scan | |
| US5276789A (en) | Graphic display of network topology | |
| Reinelt | Fast heuristics for large geometric traveling salesman problems | |
| JP2626153B2 (ja) | レイアウトのコンパクション方法 | |
| Lee et al. | An improved algorithm for the rectangle enclosure problem | |
| US7608844B2 (en) | Charged particle beam drawing apparatus | |
| JPS63188281A (ja) | 図形処理装置 | |
| JP2701003B2 (ja) | ソリッドモデル合成装置及びソリッドモデル合成方法 | |
| CN106651993A (zh) | 一种在fpga中填充非自相交多边形的填充方法 | |
| US6314554B1 (en) | Method of generating mask pattern data for graphics and apparatus for the same | |
| US7423643B2 (en) | Method and system for tesselating a polygon | |
| CN113177145A (zh) | 一种流程图排序方法、装置、电子设备及存储介质 | |
| CN116092102B (zh) | 包含文本信息的结构图的处理方法、电子设备、存储介质 | |
| US6535222B1 (en) | Graphic method | |
| EP0479496A2 (en) | High speed graphic image generation using multiple steppers | |
| JP3460339B2 (ja) | 対象選択装置及び方法 | |
| JP2590327B2 (ja) | 図面情報の管理方法 | |
| CN116720235A (zh) | Cad文件自动标注方法、装置及电子设备 | |
| JP3951644B2 (ja) | 配電線路図の表示方法 | |
| JPS63311428A (ja) | 線分文字デ−タ最適化処理方法 | |
| JP2857260B2 (ja) | 矩形領域の判定方法 | |
| JP2614356B2 (ja) | 閉図形抽出方式 | |
| JPH0679339B2 (ja) | 画像処理方法 |