JPS63163985A - 多角形クリツピング装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、多角形クリッピング装置に関し、更に詳しく
は、与えられた多角形を境界線でクリッピングしてでき
る新たな多角形を出力する装置に関する。

発明の課題 与えられた多角形のうち所定の領域に含まれる部分だけ
を表示したり、プリントアウトしたい場合がある。

このような場合には、与えられた多角形を境界線でクリ
ッピングして、領域内に含まれる新たな多角形を得る必
要がある。

本発明の目的とするところは、かかる新たな多角形を好
適に得ることができる多角形クリッピング装置を提供す
ることにある。

発明の構成 本発明の多角形クリッピング装置は、多角形を境界線（
ｘ＝ｘ３又はｙ＝ｙｔ）でクリッピングして出来る新た
な多角形を出力する装置であって、多角形の１つの辺を
境界線（ｘｘｘ３又はｙ＝ｙ３）でクリッピングして線
分を得る辺りリフピング手段と、前記辺クリッピング手
段により多角形のすべての辺についてクリッピングを繰
り返し、得られた線分の端点を頂点とする新たな多角形
を出力する多角形出力手段とを具備したことを構成上の
特徴とするものである。

また、本発明の多角形クリッピング装置は、多角形を境
界領域（Ｘ　＊＋＊≦Ｘ≦ｘｌａｇ　ｌ　　３’　８１
１≦Ｙ　’　Ｙ　−ｘ）でクリッピングして出来る新た
な多角形を出力する装置であって、多角形の１つの辺を
境界線（Ｘ”Ｘ３又はｙ−３’ｉ）でクリッピングして
線分を得る辺りリフピング手段と、前記辺クリッピング
手段により多角形のすべての辺についてクリッピングを
繰り返し、得られた線分の端点を頂点とする新たな多角
形を出力する多角形出力手段と、Ｘ　ａｎ　、Ｘ　−＋
　　Ｙ　ａｎ　、Ｙ−のうちいずれか一つを境界線とし
て選択して、与えられた多角形から前記多角形出力手段
により新たな多角形を得、次に、Ｘ　ｍ　、Ｘ　ｗｈｙ
　、３’　＠１１　、）’−のうちの他の一つを境界線
として選択して、前記新たな多角形から前記多角形出力
手段により更に新たな多角形を得、これをＸ　、ｎ　、
Ｘ　−＋　　３’　Ａｌｌ　ｌ　　１　、のうちの更に
他の２つについても行って多角形を得るクリッピング反
復手段とを具備したことを構成上の特徴とするものであ
る。

前者の多角形クリッピング装置は、与えられた多角形を
一本の境界線でクリッピングしてできる新たな多角形を
出力するものであり、後者の多角形クリッピング装置は
与えられた多角形を４本の境界線で囲まれた境界領域で
クリッピングしてできる新たな多角形を出力するもので
ある。

実方缶イタリ 以下、図に示す実施例に基づいて、本発明を更に詳しく
説明する。ここに第１図は本発明の一実施例の多角形ク
リッピング装置を含むレーザプリンタ装置の構成概念図
、第２図は与えられた多角形と境界領域の例示図、第３
図は境界領域でクリッピングされた新たな多角形の例示
図、第４図は第１図に示すレーザプリンタ装置における
多角形クリッピング処理の作動の一例のフローチャート
、第５図は新しい辺を求める処理の作動の一例のフロー
チャート、第６図は線分と境界線の関係を示す例示図、
第７図は辺クリッピング処理の作動の一例のフローチャ
ート、第８図は境界点出力処理の作動の一例のフローチ
ャート、第９図〜第１２図は多角形を境界線でクリッピ
ングすることによりできる新たな多角形の例示図である
。なお、図に示す実施例により本発明が限定されるもの
ではない。

第１図に示すレーザプリンタ装Ｅ１において、巳ンピエ
ータから多角形の頂点の座標データと境界領域が与えら
れると、コントローラ２は、与えられた多角形を境界領
域でクリッピングして新たな多角形を生成し、その新た
な多角形の画像データをビットマツプメモリ３にストレ
ージする。そして、ビットマツプメモリ３にストレージ
した画像データを順に読み出し、レーザダイオードドラ
イバ４に出力する。

レーザダイオードドライバ４は、レーザダイオード５を
発光させ、画像をプリントする。

従って、このレーザプリンタ装置１によれば、コンピュ
ータから指定された境界領域に含まれる画像部分のみを
プリントアウトできる０例えば、第２図に示すように、
頂点Ａ、Ｂ、Ｃを持つ三角形が与えられ、境界領域とし
てｘＩＩＩ≦Ｘ≦ｘ−２ｙ、１．≦ｙ≦ｙ−が与えられ
ると、第３図に示すように、ΔＡＢＣを境界領域でクリ
ッピングしてできる多角形Ａ＋　Ｂ＋　Ｒ３Ｃ２Ｃ３Ａ
２をプリントアウトできる。

このように境界領域でクリッピングして新たな多角形を
得る作動を、第４図〜第１２図を参照して、以下に詳説
する。なお、説明の都合上、第２図に示すように、多角
形として△ＡＢＣが与えられ、境界領域としてＸ　ＩＩ
Ｉ≦Ｘ　：５Ｘ　、＋　　Ｙ　ｈ、≦ｙ≦ｙ−がコンピ
ュータから与えられたものとする。

まず、コントローラ２は、第４図に示すように、境界線
として”　＝”　８１１を選択する（Ｇ１）。

次に、その選択した境界線ｘ−ｘ　、、で、与えられた
多角形をクリッピングして出来る新しい多角形の新しい
辺を求める処理を行う（Ｇ２）。

新しい辺を求める処理では、第５図に示すように、多角
形の各辺の内から一辺を取り出し、その両端点の座標を
得る（Ｈｌ）、例えば、△ＡＢＣの一辺ＡＢを取り出し
、その端点Ａ、Ｈの座標（Ｘ、、ｙａ　）、　　（Ｘｂ
　、ｙｂ　）を得る。

次いで、辺タリンピング処理を行う（Ｒ２）。

辺りリフピング処理とは、第６図に示すように、２点α
、βを結ぶ線分αβを境界線Ｘ”Ｘ３でクリッピングし
て、新たな線分子βを得る処理である。

境界線Ｘ”’Ｘ３としては、前記ステップＧ１で境界線
ｘ”　ｘＩｌｌが与えられており、点αには前記端点Ｂ
が対応し、点βには前記端点Ａが対応する。

なお、辺ＡＢに関する点γを点Ｂ、と名付ける。

第７図に示すように、コントローラ２は、まずｘｃＬ＜
ｘ３であるか否かをチェックする（Ｓｌ）。

第６図に示す関係の場合は、Ｘ、＜Ｘ３だから、ステッ
プＳ２に移行する。

ステップＳ２では、Ｘ６＜Ｘ３であるか否かをチェック
する。第６図に示す条件の場合は、ｘ８＜Ｘ、でないか
らステップＳ３に移行する。

ステップＳ３では、Ｘ６’ｘＸ３か否かをチェ７りする
。第２図に示す例では、ｘ８はｘ３でないから、ステッ
プＳ４に移行する。

ステ、プＳ４では、α点をＰ、点と置き、かつ、β点を
２２点と置く。すなわち、ｘｃｌ　−Ｘ　Ｉ　＋Ｙ　ａ
　−Ｙ　＋と置き、！＄−１２，ｙａ　１Ｙ２と置く。

次いで、境界点出力処理を行うが（Ｓ５）、この境界点
出力処理は第８図に詳細に示すものである。

まず、Ｘ座標値同志を加算して加算値Ｘ、を求めると共
に、ｙ座標同志を加算して加算値ｙ、を算出する（Ｒ１
）。

次に、加算値Ｘ、をＬＳＢ方向へｌビア）シフトしてシ
フト値Ｘ４とする（Ｒ２）、これは、加算値Ｘ、を２で
除算することに相当するが、シフト処理であるから、除
算処理に比べて格段に高速に行うことができる。

次に、加算値ｙ、をＬ　Ｓ　Ｂ方向へ１ビツトシフトし
てシフト値ｙ１とする（Ｒ３）、これも加算値ｙｌを２
で除算することに相当するが、格段に高速に処理できる
。

上記ステップＲ１〜Ｒ３は、点Ｐｌ　ＯＣ＋＋Ｙ＋）と
点Ｐ２　（Ｘ２１　７２）の区分点を算出する処理に外
ならないので、第６図における点αとβの区分点が得ら
れることになる。

次に、シフト値Ｘｌと境界線のＸ座標値ｘ３の差の絶対
値が１より小であるか否かをチェックする（Ｒ４）。

シフト値ｘＩがｘ３より１以上小ならば（Ｒ４、Ｒ６）
、算出した各分点は境界線Ｘ＝ｘ３より左にあるので、
ｘｆ−ｘｌ、ｙｆ−ｙＩとおいて（Ｒ７）、前記ステッ
プＲ１に戻る。これは、２点α、βを結ぶ線分を、区分
点とβを結ぶ線分に置き換えたことに相当する。

一方、Ｘ（がＸ３より１以上大ならば（Ｒ４゜Ｒ６）、
ｘｆ−ｘ２．ｙｆ−ｙ２と置き（Ｒ８）、前記ステップ
Ｒ１に戻る。これは、２点α、βを結ぶ線分を、αと２
分点を結ぶ線分に置き換えたことに相当する。

このようにして線分の２分点を次々に求めて行き、ｘａ
に実質的に一致するまで繰り返す。

ｘａに実質的に一致すると、シフト値Ｘ（と境界線のＸ
座標値ｘ３の差の絶対値が１より小となるので、シフト
値ｙＩを境界点Ｐ３のｙ座標値ｙ。

として設定する（Ｒ５）。

ステップＲ１〜Ｒ８によって、境界点Ｐ３のｙ座標値ｙ
３が求まるが、この処理は乗算、除算を含んでいないの
で、高速かつ高精度にｙ、を得ることができる。

境界点出力処理（Ｓ５）によって、境界点Ｐ。

の座標（Ｘｌ、ｙｔ）が得られると、その境界点Ｐ３を
１点と置き（Ｓ６）、プリントアウトすべき線分として
線分子βをセントする（Ｓ７）。

かくして、第６図に示すように、境界線Ｘ”’Ｘ３より
右側の線分子βが得られるが、これは新たな辺ＡＢ、が
得られたことを意味する。

さて、第６図に示す例では、ｘ、＜Ｘａ＜ｘａであった
が、その他の場合でも同様にして新たな辺が得られる。

例えば、Ｘ工＞Ｘ、＞ｘ６ならば、第７図のα点とβ点
とを入れ換えた処理（８２′〜８７′）によって新たな
辺を得られる。

また、Ｘ、、Ｘａがｘａに一致する場合は、境界点出力
処理を行うまでもなく、新たな辺を得られる（３８’　
、３８）。

また、２点α、β共に領域内にあれば、元の辺αβがそ
のまま新たな辺となる。（３１０）。

さらに、２点α、βのいずれの点も領域内になければ、
元の辺から新たな辺を生じないこととなる（３１１）。

さて、第５図に戻り、上記辺りリフピング処理（Ｂ２）
によって、新しい辺が得られると、その辺をメモリにス
トアする（Ｂ３）、例えば第６図の場合は、元の辺ＡＢ
が新たな辺ＡＢ、に置き換えられてストアされる。

次に、上記処理を行った辺が最後の辺でなければ（Ｈ４
）、次の辺を取り出して、その端点の座標を得（Ｂ５）
、前記辺クリッピング処理Ｈ２に戻る０例えば、△ＡＢ
Ｃの場合、辺ＡＢが終われば、次の辺ＢＣについて再び
辺クリッピング処理（Ｂ２）が行われるわけである。ま
た、それが終われば、辺ＣＡについて行われることにな
る。

そこで、第９図に示すように、辺ＡＢからは新たな辺Ａ
Ｂ、が得られ、辺ＢＣからは新たな辺Ｂ２Ｃが得られ、
辺ＣＡからは元の辺ＣＡがそのまま新しい辺ＣＡとして
得られる。

すべての辺について処理を終了すると（Ｈ４）、新たな
辺で形成される多角形の頂点テーブルが作成される（Ｈ
６）、第９図に示す例の場合は、新たに得られた辺が、
ＡＢＩ　、８２　Ｃ，ＣＡであるから、その頂点はＡ、
Ｂ、、Ｂ２．Ｃとなり、四角形であることが分かる。そ
して、その四角形の新たな辺は、ＡＢＩ　、ＢＩ　８２
．８２　Ｃ，ＣＡであることが分かる。

第４図に戻り、ステップＧ２によって、境界線””　ｘ
＠Ｉｍでクリッピングした多角形の新しい辺が求まると
、次には、境界線をＶ　−Ｙ　ｍ＝とじ（Ｇ３）、その
境界線で、先に得た新たな多角形をクリッピングして、
新しい辺を求める処理を行う（Ｇ４）。

第１０図はその結果を示すもので、口ＡＢ、Ｂ。

ＣＩの元の辺ＡＢ、はそのまま新しい辺ＡＢ、となり、
元の辺Ｂ、Ｂ、からは新しい辺Ｂ、Ｂ、が得られ、元の
辺８２　Ｃからは新しい辺が生じず、元の辺ＣＡからは
新しい辺Ｃ，Ａが得られる。そこで、新しい頂点はＡＢ
、Ｂ、Ｃ，であり、新しい多角形は四角形であることが
分かる。そしてその四角形の辺は、ＡＢ１＋　　Ｂｌ　
Ｂｔ＋　　Ｂ３　Ｃ１ＩＣ，Ａであることが分かる。

次に、ステップＧ５，０６によって、第１１図に示すよ
うに、頂点Ａ＋　　Ｂ　１．Ｂ３　、Ｃｘ　、Ｃ３が得
られ、新しい多角形が五角形であると分かる。

そして、その五角形の辺は、ＡＢＩ　、Ｂｌ　ｎ、。

Ｂ３　Ｃ２、Ｃ２Ｃ３、Ｃｉ　Ａであると分かる。

同様に、ステップＧ７．Ｇ８によって、第１２図に示す
ように、新たな多角形Ａ、Ｂ、Ｂ、Ｃ２Ｃ。

Ａ２が得られるが、第３図と比較すれば理解されるよう
に、これは結局のところ、元のΔＡＢＣを境界領域Ｘ３
０．≦Ｘ≦ｘ、＋　　３’　ｔｖ≦ｙ≦ｙ、でクリフピ
ングした新たな多角形である。

以上のように、このレーザプリンタ装置ｉ！１では、多
角形をクリッピングしてできる新たな多角形を好適に出
力し得るから、所望の領域に含まれる部分の画像のみを
好適にプリントアウトすることができる。

発明の効果 本発明によれば、多角形を境界線（ｘ＝ｘ３又はｙ＝ｙ
ａ）でクリッピングして出来る新たな多角形を出力する
装置であって、多角形の１つの辺を境界線（ｘ＝ｘ３又
はｙ＝ｙ３）でクリッピングして線分を得る辺クリッピ
ング手段と、前記辺クリッピング手段により多角形のす
べての辺についてクリ・７ピングを繰り返し、得られた
線分の端点を頂点とする新たな多角形を出力する多角形
出力手段とを具備したことを特徴とする多角形クリ７ピ
ング装置が提供される。

また、多角形を境界領域（”　ｍ＋１≦Ｘ　Ｓ　Ｘ　＠
ｚ　＋　　３’　＊＋＋≦ｙ５ｙ、、、）でクリッピン
グして出来る新たな多角形を出力する装置であって、多
角形の１つの辺を境界線（ｘ＝ｘ３又はｙ−Ｙ３）でク
リッピングして線分を得る辺クリッピング手段と、前記
辺りリフピング手段により多角形のすべての辺について
クリッピングを繰り返し、得られた線分の端点を頂点と
する新たな多角形を出力する多角形出力手段と、Ｘ　＠
ＩＩ　、Ｘ−１ｙ＊＋ｍ　、）’−のうちいずれか一つ
を境界線として選択して、与えられた多角形から前記多
角形出力手段により新たな多角形を得、次に、Ｘ　ｍ　
、Ｘ　−９ｙ＊＋ｍ　、Ｙ−のうちの他の一つを境界線
として選択して、前記新たな多角形から前記多角形出力
手段により更に新たな多角形を得、これをＸ　ｓ＋＋　
＋　　ｘ−＋　　ｙａｎ　、３’−のうちの更に他の２
つについても行って多角形を得るクリッピング反復手段
とを具備したことを特徴とする多角形クリッピング装置
が提供される。

そして、これにより、与えられた多角形を境界線又は境
界線領域でクリッピングしてできる新たな多角形を好適
に出力できるようになる。

【図面の簡単な説明】

第１図は本発明の一実施例の多角形クリッピング装置を
含むレーザプリンタ装置の構成概念図、第２図は与えら
れた多角形と境界領域の例示図、第３図は境界領域でク
リッピングされた新たな多角形の例示図、第４図は第１
図に示すレーザプリンタ装置における多角形クリッピン
グ処理の作動の一例のフローチャート、第５［ｍは新し
い辺を求める処理の作動の一例のフローチャート、第６
図は線分と境界線の関係を示す例示図、第７図は辺クリ
ッピング処理の作動の一例のフローチャート、第８図は
境界点出力処理の作動の一例のフローチャート、第９図
〜第１２図は多角形を境界線でクリッピングすることに
よりできる新たな多角形の例示図である。 （符号の説明） Ｉ・・・レーザプリンタ装置　　２・・・コントローラ
３・・・ビットマツプメモリ ４・・・レーザダイオードドライバ。

Claims (1)

1. 【特許請求の範囲】 １、多角形を境界線（ｘ＝ｘ＿３又はｙ＝ｙ＿３）でク
   リッピングして出来る新たな多角形を出力する装置であ
   って、 （ａ）多角形の１つの辺を境界線（ｘ＝ｘ＿３又はｙ＝
   ｙ＿３）でクリッピングして線分を得る辺クリッピング
   手段と、 （ｂ）前記辺クリッピング手段により多角形のすべての
   辺についてクリッピングを繰り返 し、得られた線分の端点を頂点とする新た な多角形を出力する多角形出力手段と を具備したことを特徴とする多角形クリッ ピング装置。 ２、多角形を境界領域（ｘ＿ｍ＿ｉ＿ｎ≦ｘ≦ｘ＿ｍ＿
   ａ＿ｘ、ｙ＿ｍ＿ｉ＿ｎ≦ｙ≦ｙ＿ｍ＿ａ＿ｘ）でクリ
   ッピングして出来る新たな多角形を出力する装置であっ
   て、 （ａ）多角形の１つの辺を境界線（ｘ＝ｘ＿３又はｙ＝
   ｙ＿３）でクリッピングして線分を得る辺クリッピング
   手段と、 （ｂ）前記辺クリッピング手段により多角形のすべての
   辺についてクリッピングを繰り返 し、得られた線分の端点を頂点とする新た な多角形を出力する多角形出力手段と （ｃ）ｘ＿ｍ＿ｉ＿ｎ、ｘ＿ｍ＿ａ＿ｘ、ｙ＿ｍ＿ｉ＿
   ｎ、ｙ＿ｍ＿ａ＿ｘのうちいずれか一つを境界線として
   選択して、与えられた 多角形から前記多角形出力手段により新た な多角形を得、次に、ｘ＿ｍ＿ｉ＿ｎ、ｘ＿ｍ＿ａ＿ｘ
   、ｙ＿ｍ＿ｉ＿ｎ、ｙ＿ｍ＿ａ＿ｘのうちの他の一つを
   境界線として選択して、前記新たな多角形から前記多角
   形出 力手段により更に新たな多角形を得、これ をｘ＿ｍ＿ｉ＿ｎ、ｘ＿ｍ＿ａ＿ｘ、ｙ＿ｍ＿ｉ＿ｎ、
   ｙ＿ｍ＿ａ＿ｘのうちの更に他の２つについても行って
   多角形を得るクリ ッピング反復手段と を具備したことを特徴とする多角形クリッピング装置。