(57)【要約】  頂点取得部２は、複数の直線を構成する頂点の集合である直線データ１から頂点を取得し、矩形内外判定部３は、現頂点が表示ウィンドウの内に位置するか外に位置するか判定する。内外状態変化判定部５は、現頂点が表示ウィンドウの内か外か、及び前回の頂点が表示ウィンドウの内か外かの組み合わせに応じて分岐番号１〜４を選択し、点列登録部６が分岐番号に応じた登録処理を行って、現頂点を新点列記憶領域７に登録する。
2011030371.tif 000002
【特許請求の範囲】
【請求項１】
頂点を結んだ直線で構成される折れ線を規定する、当該頂点の集合である直線データから、前記折れ線を構成する順に当該頂点を１つずつ取得する頂点取得部と、
前記頂点取得部が取得した現頂点が、表示ウィンドウの矩形の内か外かの内外判定を行う矩形内外判定部と、
前記矩形内外判定部が判定した前記現頂点の内外判定結果と前回取得した頂点の内外判定結果の組み合わせに応じて前記現頂点を新点列記憶領域に登録し、前記表示ウィンドウに描画する新点列を作成する点列登録部とを備える描画頂点削除装置。
【請求項２】
矩形内外判定部は、表示ウィンドウの矩形を構成する４頂点のＸＹ座標と、直線データから取得された現頂点のＸＹ座標の大小関係に基づき、内外判定を行うことを特徴とする請求項１記載の描画頂点削除装置。
【請求項３】
矩形内外判定部が判定した前回取得した頂点の内外判定結果と現頂点の内外判定結果を、外と外、内と内、内と外、及び外と内のいずれかの組み合わせに分類する内外状態変化判定部を備え、
点列登録部は、前記内外状態変化判定部が分類した組み合わせに応じて、外と外の場合は前記現頂点を新点列記憶領域中の登録位置に登録し、内と内の場合及び内と外の場合は前記現頂点を登録位置に登録した後に当該登録位置を次へ進め、外と内の場合は登録位置を次へ進めた後に前記現頂点を当該次の登録位置に登録して更に当該次の登録位置を次へ進めることを特徴とする請求項１記載の描画頂点削除装置。
【請求項４】
頂点を結んだ直線で構成される折れ線を規定する、当該頂点の集合である直線データから、前記折れ線を構成する順に当該頂点を１つずつ取得する頂点取得部と、
前記頂点取得部が取得した現頂点が、表示ウィンドウの矩形の内か外かの内外判定を行うと共に、外の場合に、当該表示ウィンドウの矩形の外を分割した複数の領域のうちのどの領域かを示す内外領域値を求める領域付き矩形内外判定部と、
前記領域付き矩形内外判定部が求めた前記現頂点の内外領域値と前回取得した頂点の内外領域値の組み合わせに応じて前記現頂点を新点列記憶領域に登録し、前記表示ウィンドウに描画する新点列を作成する点列登録部とを備える描画頂点削除装置。
【請求項５】
領域付き矩形内外判定部は、表示ウィンドウの矩形を構成する４頂点のＸＹ座標と、直線データから取得された現頂点のＸＹ座標の大小関係に基づき、内外判定を行うと共に内外領域値を選択することを特徴とする請求項４記載の描画頂点削除装置。
【請求項６】
領域付き矩形内外判定部が判定した前回取得した頂点の内外領域値と現頂点の内外領域値を、外と外かつ同じ領域、外と外かつ異なる領域、外と内、内と内、内と外のいずれかの組み合わせに分類する内外状態変化判定部を備え、
点列登録部は、前記内外状態変化判定部が分類した組み合わせに応じて、外と外かつ同じ領域の場合は前記現頂点を新点列記憶領域中の登録位置に登録し、外と外かつ異なる領域の場合及び外と内の場合は登録位置を次へ進めた後に前記現頂点を当該次の登録位置に登録して更に当該次の登録位置を次へ進め、内と内の場合及び内と外の場合は前記現頂点を登録位置に登録した後に当該登録位置を次へ進めることを特徴とする請求項４記載の描画頂点削除装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、表示ウィンドウからはみ出る、描画不要の頂点を削除する描画頂点削除装置に関する。
【背景技術】
【０００２】
従来の直線描画装置は、表示ウィンドウから直線がはみ出す場合、表示ウィンドウに対してクリッピングを行うことによって、不要な描画を抑制し、描画処理の高速化を実現していた（例えば、特許文献１参照）。詳細には、描画対象となる直線が表示ウィンドウからはみ出る場合は、表示ウィンドウ枠線と描画直線の交点を算出し、その交点まで直線を描画していた。また、直線が完全に表示ウィンドウ外に位置する場合は、描画を行わないという処理をしていた。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−９７１９号公報
【発明の概要】
【０００４】
従来の直線描画装置は以上のように構成されているので、描画直線のクリッピングのために表示ウィンドウ枠線と描画直線の交点を算出する際、浮動小数点演算が必要であった。そのため、表示ウィンドウ枠線と描画直線の交点数に応じて浮動小数点演算量が多くなり、描画処理が遅くなるという課題があった。
【０００５】
この発明は、上記のような課題を解決するためになされたもので、浮動小数点演算を行うことなく直線をクリッピング処理し、描画を高速化することを目的とする。
【０００６】
この発明の描画頂点削除装置は、頂点を結んだ直線で構成される折れ線を規定する、当該頂点の集合である直線データから、折れ線を構成する順に当該頂点を１つずつ取得する頂点取得部と、頂点取得部が取得した現頂点が、表示ウィンドウの矩形の内か外かの内外判定を行う矩形内外判定部と、矩形内外判定部が判定した現頂点の内外判定結果と前回取得した頂点の内外判定結果の組み合わせに応じて現頂点を新点列記憶領域に登録し、表示ウィンドウに描画する新点列を作成する点列登録部とを備えるものである。
【０００７】
この発明によれば、現頂点の内外判定結果と前回取得した頂点の内外判定結果の組み合わせに応じて現頂点を新点列記憶領域に登録し、表示ウィンドウに描画する新点列を作成することにより、浮動小数点演算を行うことなく直線をクリッピング処理し、描画を高速化することができる。
【０００８】
また、この発明の描画頂点削除装置は、頂点を結んだ直線で構成される折れ線を規定する、当該頂点の集合である直線データから、折れ線を構成する順に当該頂点を１つずつ取得する頂点取得部と、頂点取得部が取得した現頂点が、表示ウィンドウの矩形の内か外かの内外判定を行うと共に、外の場合に、当該表示ウィンドウの矩形の外を分割した複数の領域のうちのどの領域かを示す内外領域値を求める領域付き矩形内外判定部と、領域付き矩形内外判定部が求めた現頂点の内外領域値と前回取得の頂点の内外領域値の組み合わせに応じて現頂点を新点列記憶領域に登録し、表示ウィンドウに描画する新点列を作成する点列登録部とを備えるものである。
【０００９】
この発明によれば、現頂点の内外領域値と前回取得の頂点の内外領域値の組み合わせに応じて現頂点を新点列記憶領域に登録し、表示ウィンドウに描画する新点列を作成することにより、浮動小数点演算を行うことなく直線をクリッピング処理し、描画を高速化することができる。
【図面の簡単な説明】
【００１０】
【図１】この発明の実施の形態１に係る描画頂点削除装置の構成を示すブロック図である。
【図２】実施の形態１に係る描画頂点削除装置の表示ウィンドウと各頂点の位置関係を示す図である。
【図３】実施の形態１に係る描画頂点削除装置の動作を示すフローチャートである。
【図４】図２に示す頂点Ａ〜Ｊを新点列記憶領域７に登録する処理を説明する図である。
【図５】図２に示す頂点Ａ〜Ｊを基にした新点列を用いて描画した折れ線を示す図である。
【図６】折れ線の一例を示す図である。
【図７】この発明の実施の形態２に係る描画頂点削除装置の構成を示すブロック図である。
【図８】実施の形態２に係る描画頂点削除装置の表示ウィンドウと現内外領域値の位置関係を示す図である。
【図９】実施の形態２に係る描画頂点削除装置の領域付き矩形内外判定部８の動作を示すフローチャートである。
【図１０】実施の形態２に係る描画頂点削除装置の動作を示すフローチャートである。
【図１１】図６に示す頂点Ａ〜Ｉを新点列記憶領域７に登録する処理を説明する図である。
【図１２】図６に示す頂点Ａ〜Ｉを基にした新点列を用いて描画した折れ線を示す図である。
【発明を実施するための形態】
【００１１】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態１．
図１は、この発明の実施の形態１に係る描画頂点削除装置の構成を示すブロック図である。図１に示す描画頂点削除装置は、例えば地図表示での道路描画で扱われるような、頂点を結んだ直線で構成される折れ線を規定するための、頂点の集合である直線データ１と、直線データ１から１つずつ順番に頂点を取り出す頂点取得部２と、頂点が表示ウィンドウ内に含まれるかを判定する矩形内外判定部３と、前回の判定した頂点の内外判定結果である前内外フラグ４と今回判定した頂点の内外判定結果とを比較して分岐番号のうちの１つを選択する内外状態変化判定部５と、分岐番号に従って頂点を新点列記憶領域７へ登録する点列登録部６とを備える。
【００１２】
図２に、描画頂点削除装置の表示ウィンドウと各頂点の位置関係を示す。本実施の形態１では、頂点を結んだ直線又は折れ線を描画する表示ウィンドウを矩形形状と定義し、更に、この表示ウィンドウの上下左右に対応する仮想的なＸＹ座標軸を定義する。図２に示すように、表示ウィンドウを、原点を基準にして、右方向（Ｘ軸）に正の幅１００、下方向（Ｙ軸）に正の高さ４０のサイズを持つ領域とする。また、表示ウィンドウの左辺のＸ座標、右辺のＸ座標、上辺のＹ座標、下辺のＹ座標をそれぞれＬＸ，ＲＸ，ＴＹ，ＢＹとする。
【００１３】
また、直線データ１はＡ〜Ｊの１０個の頂点からなり、頂点Ａ〜ＪはＸＹ座標で表される。ここで、頂点Ａ（２０，−２０）、Ｂ（１０，−１０）、Ｃ（１５，１０）、Ｄ（１０，１５）、Ｅ（−１０，１０）、Ｆ（−１５，２０）、Ｇ（−１０，３０）、Ｈ（１５，３０）、Ｉ（２０，５０）、Ｊ（１０，６０）とする。この直線データ１を用いて各頂点Ａ〜Ｊを結ぶ直線を描画すると、図２に示す折れ線となる。
【００１４】
頂点取得部２は、直線データ１から、折れ線を構成する頂点Ａから順番に１つずつ頂点を取得する。
矩形内外判定部３は、頂点取得部２が取得した頂点（現頂点）が表示ウィンドウ内に含まれるか否かを判定する。矩形内外判定部３の内外判定条件を以下に示す。なお、現頂点のＸＹ座標を（ＰＸ，ＰＹ）とする。
【００１５】
［内外判定条件］
（表示ウィンドウの左辺のＬＸ≦現頂点のＰＸ）かつ（現頂点のＰＸ≦表示ウィンドウの右辺のＲＸ）かつ（表示ウィンドウの上辺のＴＹ≦現頂点のＰＹ）かつ（現頂点のＰＹ≦表示ウィンドウの下辺のＢＹ）が満たされるならば現頂点は表示ウィンドウ内、満たされないならば現頂点は表示ウィンドウ外
【００１６】
上記内外判定条件に従うと、頂点Ａは「外」と判定される。なお、矩形内外判定部３は、内外判定結果が「外」の場合に「０」を出力し、「内」の場合に「１」を出力する。
前回取得した頂点が表示ウィンドウの内外どちらにあったかを示すフラグである前内外フラグ４も同様に、「０」であれば「外」、「１」であれば「内」を示す。なお、前内外フラグ４の初期値は「０」とする。
【００１７】
内外状態変化判定部５は、現頂点の内外判定結果と前内外フラグ４とを比較し、この組み合わせに応じて、点列登録部６が行う分岐処理の分岐番号を求める。内外状態変化判定部５は、（前内外フラグ４，現頂点の内外判定結果）が（０，０）ならば分岐番号１とし、（１，０）ならば分岐番号２とし、（０，１）ならば分岐番号３とし、（１，１）ならば分岐番号４とする。
例えば、頂点Ａは（０，０）なので分岐番号１となる。
【００１８】
点列登録部６は、内外状態変化判定部５が求めた分岐番号１〜４に応じた登録処理を行って、現頂点を新点列記憶領域７へ登録する。点列登録部６の詳細は後述する。新点列記憶領域７は、頂点を表すＸＹ座標等の点情報を１００点まで格納できる記憶領域である。
【００１９】
次に、描画頂点削除装置の動作を説明する。図３は、実施の形態１に係る描画頂点削除装置の動作を示すフローチャートである。また、図４は、図２に示す頂点Ａ〜Ｊを新点列記憶領域７に登録する処理を説明する図である。
【００２０】
先ず、ステップＳＴ１において、頂点取得部２が直線データ１から頂点Ａを取得する。
続いて、矩形内外判定部３は、頂点取得部２が頂点Ａを取得したら（ステップＳＴ２“ＹＥＳ”）、上記内外判定条件に従って頂点Ａが表示ウィンドウ外、即ち内外判定結果「０」と判定する（ステップＳＴ３“０”）。続いて、内外状態変化判定部５は、頂点Ａの内外判定結果が「０」、前内外フラグ４が初期値の「０」であるため（ステップＳＴ４“０”）、分岐番号１を選択する（ステップＳＴ５）。
分岐番号１の登録処理の場合、点列登録部６は、新点列記憶領域７のうちの頂点を登録する位置を示す登録ポインタ位置に頂点Ａを登録し（ステップＳＴ６）、前内外フラグ４を「０」にして登録処理を終了する（ステップＳＴ７）。
頂点Ａは、図４（ａ）に示す初期時の登録ポインタ位置に登録されることになるため、登録処理終了時には図４（ｂ）に示すように、新点列記憶領域７の先頭に頂点Ａが登録された状態になる。
【００２１】
処理はステップＳＴ１に戻り、頂点取得部２が直線データ１から次の頂点Ｂを取得する。頂点Ｂは表示ウィンドウ外「０」であり（ステップＳＴ３“０”）、前内外フラグ４も「０」であるため（ステップＳＴ４“０”）、分岐番号１となる（ステップＳＴ５）。なお、点列登録部６は、新点列記憶領域７の登録ポインタ位置に頂点Ｂを登録する際（ステップＳＴ６）、その登録ポインタ位置には既に頂点Ａが登録されているため、この頂点Ａに頂点Ｂを上書きする。頂点Ｂの登録処理終了時の新点列記憶領域７を図４（ｃ）に示す。
このように、新点列記憶領域７の登録ポインタに頂点が上書きされることにより、表示ウィンドウの外にあって描画不要な頂点Ａが削除される。
【００２２】
処理はステップＳＴ１に戻り、頂点取得部２が直線データ１から次の頂点Ｃを取得する。頂点Ｃは表示ウィンドウ内「１」であり（ステップＳＴ３“１”）、前内外フラグ４が「０」であるため（ステップＳＴ１１“０”）、分岐番号３となる（ステップＳＴ１２）。
分岐番号３の登録処理の場合、点列登録部６は、新点列記憶領域７の登録ポインタを１つ進め（ステップＳＴ１３）、進めた先の登録ポインタ位置に頂点Ｃを登録し（ステップＳＴ１４）、更に登録ポインタを１つ進め（ステップＳＴ１５）、前内外フラグ４を「１」にして登録処理を終了する（ステップＳＴ１６）。頂点Ｃの登録処理終了時の新点列記憶領域７を図４（ｄ）に示す。
【００２３】
処理はステップＳＴ１に戻り、頂点取得部２が直線データ１から次の頂点Ｄを取得する。頂点Ｄは表示ウィンドウ内「１」であり（ステップＳＴ３“１”）、前内外フラグ４が「１」であるため（ステップＳＴ１１“１”）、分岐番号４となる（ステップＳＴ１７）。
分岐番号４の登録処理の場合、点列登録部６は、新点列記憶領域７の登録ポインタ位置に頂点Ｄを登録し（ステップＳＴ１４）、登録ポインタを１つ進め（ステップＳＴ１５）、前内外フラグ４を「１」にして登録処理を終了する（ステップＳＴ１６）。頂点Ｄの登録処理終了時の新点列記憶領域７を図４（ｅ）に示す。
【００２４】
処理はステップＳＴ１に戻り、頂点取得部２が直線データ１から次の頂点Ｅを取得する。頂点Ｅは表示ウィンドウ外「０」であり（ステップＳＴ３“０”）、前内外フラグ４が「１」であるため（ステップＳＴ４“１”）、分岐番号２となる（ステップＳＴ８）。
分岐番号２の登録処理の場合、点列登録部６は、新点列記憶領域７の登録ポインタ位置に頂点Ｅを登録し（ステップＳＴ９）、登録ポインタを１つ進め（ステップＳＴ１０）、前内外フラグ４を「０」にして登録処理を終了する（ステップＳＴ７）。頂点Ｅの登録処理終了時の新点列記憶領域７を図４（ｆ）に示す。
【００２５】
描画頂点削除装置は、上記同様に頂点Ｆ，Ｇ，Ｈ，Ｉ，Ｊについて順次処理を行い、内外状態変化判定部５が分岐番号１，１，３，２，１を選択する。点列登録部６はこれらの分岐番号に従ってそれぞれの登録処理を行う（図４（ｇ）〜図４（ｋ））。
【００２６】
全頂点の登録処理が完了して、頂点取得部２が次の頂点を取得しなかった場合（ステップＳＴ２“ＮＯ”）、描画頂点削除装置は登録ポインタの１つ前までの点列を新点列にして（ステップＳＴ１８）、一連の描画頂点削除処理を終了する。従って、新点列は、ＢＣＤＥＧＨＩとなる。この新点列を用いて各頂点を結ぶ直線を描画すると、図５に示す折れ線となる。元の直線データ１を描画した図２の折れ線と比較して、表示ウィンドウに描画される直線の形は変化させずに、描画する頂点数（図示例では頂点Ａ，Ｆ，Ｊの３点）を削除できる。
【００２７】
以上より、実施の形態１によれば、頂点を結んだ直線で構成される折れ線を規定する、当該頂点の集合である直線データ１から、折れ線を構成する順に当該頂点を１つずつ取得する頂点取得部２と、表示ウィンドウの矩形を構成する４頂点のＸＹ座標と直線データから取得された現頂点のＸＹ座標の大小関係に基づいて、頂点取得部２が取得した現頂点が表示ウィンドウの矩形の内か外かの内外判定を行う矩形内外判定部３と、矩形内外判定部３が判定した現頂点の内外判定結果と前内外フラグ４の組み合わせに応じた分岐番号を選択する内外状態変化判定部５と、分岐番号に応じた登録処理を行って現頂点を新点列記憶領域７に登録し、表示ウィンドウに描画する新点列を作成する点列登録部６とを備えるように構成した。
このため、浮動小数点演算を行わず、簡単な比較演算によって、表示ウィンドウに表示される直線の形に変化を与えない頂点のみを削除することにより、従来のような浮動小数点を用いたクリッピング処理に比べて演算処理を早くすることができる。また、不要な直線描画処理が削除できるため、高速に直線描画を行うことができる。
【００２８】
実施の形態２．
図６に、折れ線の一例を示す。上記実施の形態１の描画頂点削除装置を用いて、この折れ線から頂点を削除すると、頂点Ａ，Ｆ，Ｇ，Ｈ，Ｉが削除されて新点列がＢＣＤＥとなる。このように、実施の形態１の描画頂点削除装置では、２つの頂点Ｇ，Ｈが共に表示ウィンドウの外に位置し、かつ、結んだ直線ＧＨが表示ウィンドウ上に重畳するような場合に、表示ウィンドウからこの直線ＧＨが消え、本来表示されるべき直線の一部が表示されない。そこで、本実施の形態２では、表示ウィンドウに直線が重畳する場合に、頂点を削除しない構成の描画頂点削除装置を説明する。
【００２９】
図７は、この発明の実施の形態２に係る描画頂点削除装置の構成を示すブロック図であり、図１と同一又は相当の部分については同一の符号を付し説明を省略する。図７に示す描画頂点削除装置は、図１に示す矩形内外判定部３に代えて領域付き矩形内外判定部８を備えると共に、前内外フラグ４に代えて前内外領域値９を備える。
【００３０】
なお、本実施の形態２の描画頂点削除装置が想定する表示ウィンドウは上記実施の形態１の表示ウィンドウと同じであり、仮想的なＸＹ座標軸の定義をそのまま使用する。
また、本実施の形態２の描画頂点削除装置が扱う直線データ１は図６に示す頂点Ａ〜Ｉとする。各頂点Ａ〜ＩのＸＹ座標（ＰＸ，ＰＹ）は、頂点Ａ（２０，−２０）、Ｂ（１０，−１０）、Ｃ（１５，１０）、Ｄ（１０，１５）、Ｅ（−１０，１０）、Ｆ（−１５，２０）、Ｇ（−１０，３０）、Ｈ（２０，５０）、Ｉ（１０，６０）とする。
【００３１】
領域付き矩形内外判定部８は、頂点取得部２が直線データ１から取得した頂点が表示ウィンドウ内に含まれるかを判定し、外に含まれる場合には外の領域を複数に分割したうちのどの領域に含まれるかも判定する。図８は、描画頂点削除装置の表示ウィンドウと現内外領域値の位置関係を示す図である。本実施の形態２では、表示ウィンドウの矩形の内側領域を現内外領域値「０」とし、矩形の外側領域を現内外領域値「１」〜「８」とする。
【００３２】
領域付き矩形内外判定部８は、現頂点のＸＹ座標ＰＸ，ＰＹと表示ウィンドウの４辺の座標ＬＸ，ＲＸ，ＴＹ，ＢＹの座標を用いて、現内外領域値を算出する。図９に、領域付き矩形内外判定部８の動作を表すフローチャートを示す。領域付き矩形内外判定部８は、現頂点のＸ座標ＰＸが表示ウィンドウ左辺のＬＸより大きく（ステップＳＴ２１“ＹＥＳ”）、表示ウィンドウ右辺のＲＸより小さく（ステップＳＴ２２“ＹＥＳ”）、Ｙ座標ＰＹが表示ウィンドウ上辺のＴＹより大きく（ステップＳＴ２３“ＹＥＳ”）、表示ウィンドウ下辺のＢＹより小さければ（ステップＳＴ２４“ＹＥＳ”）、現内外領域値を「０」とする（ステップＳＴ２５）。また、領域付き矩形内外判定部８は、現頂点のＸ座標ＰＸが表示ウィンドウ左辺のＬＸより大きく（ステップＳＴ２１“ＹＥＳ”）、表示ウィンドウ右辺のＲＸより小さく（ステップＳＴ２２“ＹＥＳ”）、Ｙ座標ＰＹが表示ウィンドウ上辺のＴＹより大きく（ステップＳＴ２３“ＹＥＳ”）、表示ウィンドウ下辺のＢＹ以上であれば（ステップＳＴ２４“ＮＯ”）、現内外領域値を「５」とする（ステップＳＴ２６）。領域付き矩形内外判定部８はその他の現内外領域値も同様に算出する。
例えば、頂点Ａは現内外領域値「４」となる。
【００３３】
内外状態変化判定部５は、現頂点の現内外領域値と前内外領域値９とを比較し、この組み合わせに応じて、点列登録部６が行う分岐処理の分岐番号を求める。内外状態変化判定部５は、（前内外領域値９，現内外領域値）が（１〜８，１〜８）かつ前内外領域値９と現内外領域値が同じ値でないならば分岐番号１とし、（１〜８，１〜８）かつ前内外領域値９と現内外領域値が同じ値ならば分岐番号２とし、（０，１〜８）ならば分岐番号３とし、（１〜８，０）ならば分岐番号４とし、（０，０）ならば分岐番号５とする。なお、前内外領域値９の初期値は「０」とする。
例えば、頂点Ａは（０，４）なので分岐番号３となる。
【００３４】
点列登録部６は、領域付き矩形内外判定部８が求めた分岐番号１〜５に応じた登録処理を行って、現頂点を新点列記憶領域７へ登録する。点列登録部６の詳細は後述する。新点列記憶領域７は、上記実施の形態１と同様に、頂点を表すＸＹ座標等の点情報を１００点まで格納できる記憶領域である。
【００３５】
次に、描画頂点削除装置の動作を説明する。図１０は、実施の形態２に係る描画頂点削除装置の動作を示すフローチャートである。また、図１１は、図６に示す頂点Ａ〜Ｉを新点列記憶領域７に登録する処理を説明する図である。
【００３６】
先ず、ステップＳＴ４１において、頂点取得部２が直線データ１から頂点Ａを取得する。
続いて、領域付き矩形内外判定部８は、頂点取得部２が頂点Ａを取得したら（ステップＳＴ４２“ＹＥＳ”）、図９に示すフローチャートに従って現内外領域値を算出する（ステップＳＴ４３）。
【００３７】
続いて、内外状態変化判定部５は、頂点Ａの現内外領域値が「４」（ステップＳＴ４４“１〜８”）、前内外領域値９が「０」であるため（ステップＳＴ４５“０”）、分岐番号３を選択する（ステップＳＴ５４）。
分岐番号３の登録処理の場合、点列登録部６は、新点列記憶領域７の登録ポインタ位置に頂点Ａを登録し（ステップＳＴ５５）、登録ポインタを１つ進め（ステップＳＴ５６）、前内外領域値９を「４」にして登録処置を終了する（ステップＳＴ５１）。
頂点Ａは、図１１（ａ）に示す初期時の登録ポインタ位置に登録されることになるため、登録処理終了時には図１１（ｂ）に示すように、新点列記憶領域７の先頭に頂点Ａが登録された状態になる。
【００３８】
処理はステップＳＴ４１に戻り、頂点取得部２が直線データ１から次の頂点Ｂを取得する。頂点Ｂは現内外領域値「４」であり（ステップＳＴ４４“１〜８”）、前内外領域値９も「４」であり（ステップＳＴ４５“１〜８”）、現内外領域値と前内外領域値９が同じ値なので（ステップＳＴ４６“ＹＥＳ”）、分岐番号２となる（ステップＳＴ５２）。
分岐番号２の登録処理の場合、点列登録部６は、新点列記憶領域７の登録ポインタ位置に頂点Ａを登録し（ステップＳＴ５３）、前内外領域値９を「４」にして登録処置を終了する（ステップＳＴ５１）。
図１１（ｃ）に示すように、頂点Ｂは既に登録されている頂点Ａに上書きされ、表示ウィンドウの外にあって描画不要な頂点Ａが削除される。
【００３９】
処理はステップＳＴ４１に戻り、頂点取得部２が直線データ１から次の頂点Ｃを取得する。頂点Ｃは現内外領域値「０」であり（ステップＳＴ４４“０”）、前内外領域値９が「４」であるため（ステップＳＴ５７“１〜８”）、分岐番号４となる（ステップＳＴ５８）。
分岐番号４の登録処理の場合、点列登録部６は、登録ポインタを１つ進め（ステップＳＴ５９）、進めた先の登録ポインタ位置に頂点Ｃを登録し（ステップＳＴ６０）、更に登録ポインタを１つ進め（ステップＳＴ６１）、前内外領域値９を「０」にして登録処理を終了する（ステップＳＴ５１）。頂点Ｃの登録処理終了時の新点列記憶領域７を図１１（ｄ）に示す。
【００４０】
処理はステップＳＴ４１に戻り、頂点取得部２が直線データ１から次の頂点Ｄを取得する。頂点Ｄは現内外領域値「０」であり（ステップＳＴ４４“０”）、前内外領域値９が「０」であるため（ステップＳＴ５７“０”）、分岐番号５となる（ステップＳＴ６２）。
分岐番号５の登録処理の場合、点列登録部６は、登録ポインタ位置に頂点Ｄを登録し（ステップＳＴ６０）、登録ポインタを１つ進め（ステップＳＴ６１）、前内外領域値９を「０」にして登録処理を終了する（ステップＳＴ５１）。頂点Ｄの登録処理終了時の新点列記憶領域７を図１１（ｅ）に示す。
【００４１】
描画頂点削除装置は、上記同様に頂点Ｅ，Ｆ，Ｇについて順次処理を行い、内外状態変化判定部５が分岐番号３，２，２を選択する。点列登録部６はこれらの分岐番号に従ってそれぞれの登録処理を行う（図１１（ｆ）〜図１１（ｈ））。
【００４２】
処理はステップＳＴ４１に戻り、頂点取得部２が直線データ１から次の頂点Ｈを取得する。頂点Ｈは現内外領域値「５」であり（ステップＳＴ４４“１〜８”）、前内外領域値９が「２」であり（ステップＳＴ４５“１〜８”）であり、現内外領域値と前内外領域値９が異なる値なので（ステップＳＴ４６“ＮＯ”）、分岐番号１となる（ステップＳＴ４７）。
分岐番号１の登録処理の場合、点列登録部６は、登録ポインタを１つ進め（ステップＳＴ４８）、進めた先の登録ポインタ位置に頂点Ｈを登録し（ステップＳＴ４９）、更に登録ポインタを１つ進め（ステップＳＴ５０）、前内外領域値９を「５」にして登録処理を終了する（ステップＳＴ５１）。
図１１（ｉ）に示すように、頂点Ｈは登録ポインタを１つ進めた位置に登録されるため、表示ウィンドウの外にあっても削除されない。
【００４３】
描画頂点削除装置は、上記同様に頂点Ｉについて処理を行い、内外状態変化判定部５が分岐番号２を選択して、点列登録部６が登録処理を行う（図１１（ｊ））。
【００４４】
全頂点の登録処理が完了して、頂点取得部２が次の頂点を取得しなかった場合（ステップＳＴ４２“ＮＯ”）、登録ポインタの１つ前までの点列を新点列にして（ステップＳＴ６３）、一連の描画頂点削除処理を終了する。従って、新点列は、ＢＣＤＥＧＨとなる。この新点列を用いて各頂点を結ぶ直線を描画すると、図１２に示す折れ線となる。２つの頂点Ｇ，Ｈが共に表示ウィンドウの外に位置し、かつ、結んだ直線ＧＨが表示ウィンドウ上に重畳するような場合でも、直線ＧＨが正常に表示される。よって、元の直線データ１を描画した図６の折れ線と比較して、表示ウィンドウに描画される直線の形は変化させずに、描画する頂点数（図示例では頂点Ａ，Ｆ，Ｉの３点）を削除できる。
【００４５】
以上より、実施の形態２によれば、頂点を結んだ直線で構成される折れ線を規定する、当該頂点の集合である直線データ１から、折れ線を構成する順に当該頂点を１つずつ取得する頂点取得部２と、表示ウィンドウの矩形を構成する４頂点のＸＹ座標と直線データから取得された現頂点のＸＹ座標の大小関係に基づき、頂点取得部２が取得した現頂点が表示ウィンドウの矩形の内か外かの内外判定を行うと共に、外の場合に、当該表示ウィンドウの矩形の外を分割した複数の領域のうちのどの領域かを示す内外領域値を求める領域付き矩形内外判定部８と、領域付き矩形内外判定部８が求めた現頂点の内外領域値と前内外領域値９の組み合わせに応じた分岐番号を選択する内外状態変化判定部５と、分岐番号に応じた登録処理を行って現頂点を新点列記憶領域に登録し、表示ウィンドウに描画する新点列を作成する点列登録部６とを備えるように構成した。
このため、直線の２頂点が共に表示ウィンドウ外に存在し、かつ、その直線が表示ウィンドウに重畳する場合は２頂点を削除しないようにして、表示ウィンドウに表示される直線の形に変化を与えない頂点のみを削除することにより、不要な直線描画処理が削除できるため、高速に直線描画を行うことができる。また、その処理には浮動小数点演算を用いないため、従来のような浮動小数点を用いたクリッピング処理に比べて演算処理を早くすることができる。
【００４６】
なお、描画頂点削除装置をコンピュータで構成する場合、直線データ１、頂点取得部２、矩形内外判定部３、前内外フラグ４（又は前内外領域値９）内外状態変化判定部５（又は領域付き矩形内外判定部８）、点列登録部６、新点列記憶領域７の処理内容を記述している描画頂点削除プログラムをコンピュータのメモリに格納し、コンピュータのＣＰＵがメモリに格納されている描画頂点削除プログラムを実行するようにしてもよい。
【産業上の利用可能性】
【００４７】
以上のように、この発明に係る描画頂点削除装置は、表示ウィンドウに対する頂点の位置と前の頂点の位置の関係に基づいて描画不要の頂点を削除するようにしたので、頂点を結んで道路を描画する地図表示装置等に用いるのに適している。
【図１】
2011030371.tif 000003
【図２】
2011030371.tif 000004
【図３】
2011030371.tif 000005
【図４】
2011030371.tif 000006
【図５】
2011030371.tif 000007
【図６】
2011030371.tif 000008
【図７】
2011030371.tif 000009
【図８】
2011030371.tif 000010
【図９】
2011030371.tif 000011
【図１０】
2011030371.tif 000012
【図１１】
2011030371.tif 000013
【図１２】
2011030371.tif 000014
【国際調査報告】
2011030371.tif 000015
2011030371.tif 000016
2011030371.tif 000017