線図の圧縮処理プログラム及び閉図形の分割処理プログラム
【課題】線図の精度を保持したまま頂点を間引くことができてデータ量を圧縮可能とする圧縮処理プログラムを提供する。
【解決手段】複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラム１において、互いに異なる一対の線図のうちの一方の線図の頂点と他方の線図の線分との間の最短長さが所定値よりも短い場合に上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする。
【解決手段】複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラム１において、互いに異なる一対の線図のうちの一方の線図の頂点と他方の線図の線分との間の最短長さが所定値よりも短い場合に上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、線図の精度を保持したまま頂点を間引くことができてデータ量を圧縮可能とする圧縮処理プログラム等に関する。
【背景技術】
【０００２】
ＳＶＧ（Ｓｃａｌａｂｌｅ Ｖｅｃｔｏｒ Ｇｒａｐｈｉｃｓ）形式やその他の形式の地図データにおいて、複数の頂点を繋いで生成された線図の頂点を間引いて地図データの容量を圧縮する方法として、Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒアルゴリズム（以下、ＤＰ法という）が知られている（例えば、非特許文献１参照）。
図１６を参照し、ＤＰ法を説明する。間引き処理の対象となる線図、即ち、始点となる頂点から終点となる頂点までの間において複数の頂点を繋いで生成された線図において、始点となる頂点ａ及び終点となる頂点ｚ以外の各頂点ｂ，ｃ，d・・・・ｉには、頂点を間引くことが可能か否かの基準となるしきい値εが設定される。このしきい値εは、ε＝Ａ×Ｂで求めた値である。尚、Ａは対象となる地図の縮尺の母数、Ｂは地図縮尺毎に決められた要求精度である。各頂点Ｔ（ｂ，ｃ，d・・・・ｉ）のそれぞれには、図１６（ａ）；図１７に示すように、頂点Ｔを中心としてしきい値εを半径寸法としたしきい値円Ｒが設定される。即ち、ＤＰ法による線図の圧縮処理プログラムは、線図の各頂点に頂点からの一定距離であるしきい値εが設定され、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させるものである。つまり、図１７に示すように、注目頂点を間引くことができるか否かは、コンピュータが、注目頂点に設定されるしきい値円と注目頂点の両側に位置する頂点同士を繋いだ線分とが交わるか否かを判断し、しきい値円と線分とが交わる場合にはその注目頂点を間引くことが可能であると判定し、しきい値円と線分とが交わらない場合にはその注目頂点を間引くことができないと判定する。
以下、図１６を参照し、ＤＰ法の手順を説明する。まず、図１６（ｂ）のように、線分の始点となる頂点ａと終点となる頂点ｚとを直線ａ１で繋ぐ。線分中の各頂点と直線ａ１とを結ぶ直線ａ１と直交する直交線（垂線）の長さの最長のものを求める。ここで最長の直交線の長さ、つまり、頂点ｃと直線ａ１との間の最短距離が頂点ｃのしきい値εよりも大きく、直線ａ１と頂点ｃのしきい値円Ｒとが交差しないので、頂点ｃは間引かれずに残る。図１６（ｃ）のように、頂点ｃと頂点ａ（始点）とを直線ａ２で繋ぐと共に頂点ｃと頂点ｚ（終点）とを直線ａ３で繋ぐ。頂点ｂと直線ａ２との間の最短距離が頂点ｂのしきい値εよりも大きく、直線ａ２と頂点ｂのしきい値円Ｒとが交差するので、図１６（ｄ）の白丸で示すように、頂点ｂは間引かれる（削除される）。頂点ｃから頂点ｚまでの間の頂点のうち、直線ａ３と直交する直交線の長さの最長の頂点ｅを求める。直線ａ３と頂点ｅのしきい値円Ｒとが交差しないので、図１６（ｄ）に示すように、頂点ｅは間引かれずに残る。頂点ｅと頂点ｃとを直線ａ４で繋ぐと共に頂点ｅと頂点ｚとを直線ａ５で繋ぐ。直線ａ４と頂点ｄのしきい値円Ｒとが交差するので、頂点ｄは図１６（ｅ）のように間引かれる。頂点ｅから頂点ｚまでの間の頂点のうち、直線ａ５と直交する直交線の長さの最長の頂点ｇを求める。直線ａ５と頂点ｇのしきい値円Ｒとが交差しないので、頂点ｇは間引かれずに残る。頂点ｇと頂点ｅとを直線ａ６で繋ぐと共に頂点ｇと頂点ｚとを直線ａ７で繋ぐ。直線ａ５と頂点ｆのしきい値円Ｒとが交差するので、頂点ｆは間引かれる。頂点ｇから頂点ｚまでの間の頂点のうち、直線ａ７と直交する直交線の長さの最長の頂点ｉを求める。直線ａ７と頂点ｉのしきい値円Ｒとが交差しないので、図１６（ｄ）のように、頂点ｉは間引かれずに残る。頂点ｉと頂点ｇとを直線ａ８で繋ぐと共に頂点ｉと頂点ｚとを直線ａ９で繋ぐ。直線ａ８と頂点ｈのしきい値円Ｒとが交差するので、頂点ｈは間引かれる。
また、ＤＰ法では、閉図形のままでは図形の始点と終点とがわからないので間引き処理を行うことができないので、間引き処理の対象が閉図形の場合には、閉図形をいくつかの線図に分割した後にその線図毎に間引き処理を行った後に、間引き処理後の線図を再び連結する。
即ち、ＤＰ法による圧縮処理プログラムの手順は次のとおりである。まず、線分の始点となる頂点と終点となる頂点とを直線で繋いでこの直線と最も離れた頂点を最初の注目頂点としてこの注目頂点のしきい値円と直線とが交差するか否かを判定し、交差する場合は、当該線分の各頂点はすべて間引きされる。すなわち、始点と終点とだけが残り、間引き後の線分は、始点と終点とを繋ぐ直線となる。注目頂点のしきい値円と直線とが交差しない場合には、注目頂点が間引かれずに残る。当該頂点が残ったら、当該頂点と始点とが直線で繋がれ、この直線と最も離れた頂点を注目頂点としてこの注目頂点のしきい値円と直線とが交差するか否かを判定し、交差する場合は、当該注目頂点と始点との間の各頂点はすべて間引きされる。注目頂点のしきい値円と直線とが交差しない場合には、注目頂点が間引かれずに残る。以上のような、注目頂点のしきい値円と直線とが交差するか否かの判断を、注目頂点がなくなるまで行う。
【非特許文献１】Ｄｕｇｌａｓ Ｄ． ａｎｄ Ｐｅｕｃｋｅｒ．Ｔ．，１９７３，Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｒｅｄｕｃｔｉｏｎ ｏｆ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｐｏｉｎｔｓ ｒｅｑｕｉｒｅｄ ｆｏｒ ｒｅｐｒｅｓｅｎｔ ａ ｄｉｇｉｔｚｅｄ ｌｉｎｅ ｏｒ ｃａｒｉｃａｔｕｒｅ， Ｃａｎａｄｉａｎ Ｃａｒｔｏｇｒａｐｈｅｒ，１０，１１２−１２２
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、ＤＰ法によれば、各頂点において一定のしきい値εを用いるために、間引き処理において、図１８に示すように、間引き処理後の線図１１Ａと線図１２Ａとが交差したり、図１９に示すように、線図の角部の頂点５０が除去されてしまうことがあった。例えば、図２０（ａ）に示す閉図形Ｚの場合、形状を維持するために頂点５１；５２を間引きたくはない。しかしななら、図２０（ｂ）〜（ｄ）に示すように、ＤＰ法で間引き処理を行っていくと、分割点６０；６１以外の図形の全ての各頂点のしきい値ε（しきい値円Ｒ）が一定であるため、頂点５１；５２も間引かれてしまい、間引き後の閉図形ＺＡは元の閉図形Ｚの形状を維持できなくなってしまう。即ち、線図の精度を維持したまま線図の頂点を間引いてデータ量を圧縮することが困難であった。
また、閉図形の分割処理は、閉図形の頂点を複数個毎に分けることによって複数の線図に分割しているため、分割の仕方によって、間引き処理後の閉図形が元の閉図形の形状とかけ離れてしまい、元の閉図形の形状が維持されなくなってしまう。
本発明は、上記課題に鑑みてなされたもので、線図の精度を保持したまま頂点を間引くことができてデータ量を圧縮可能とする圧縮処理プログラム、及び、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる閉図形の分割処理プログラムを提供する。
【課題を解決するための手段】
【０００４】
本発明の線図の圧縮処理プログラムは、複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、互いに異なる一対の線図のうちの一方の線図の頂点と他方の線図の線分との間の最短長さが所定値よりも短い場合に上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする。
しきい値調整処理プログラムは、互いに異なる一対の線図の頂点同士を繋いで不等辺三角形網を生成する手段としてコンピュータを機能させる不等辺三角形網生成処理プログラムと、注目頂点と向かい合う三角形の対辺が線図上にある場合には注目頂点とその三角形の対辺との最短長さを修正値として求め、注目頂点と向かい合う三角形の対辺が線図上にない場合には注目頂点を含む三角形において注目頂点と注目頂点を含まない線図上の頂点とを繋ぐ二辺のうち長さの短い辺の長さを修正値として求める手段としてコンピュータを機能させる修正値計算処理プログラムと、上記修正値に０．５以下の係数をかけた修正しきい値を算出する手段としてコンピュータを機能させる修正しきい値算出処理プログラムと、注目頂点の上記しきい値と修正しきい値とを比較して小さい方を注目頂点のしきい値として設定する手段としてコンピュータを機能させるしきい値設定処理プログラムとを備えたことも特徴とする。
本発明の線図の圧縮処理プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする。
本発明の線図の圧縮処理プログラムは、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さと上記しきい値とを比較し、当該線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど上記しきい値を大きくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする。
本発明の線図の圧縮処理プログラムは、注目頂点の上記しきい値に修正係数をかけて算出した修正しきい値を注目頂点のしきい値として設定する手段としてコンピュータを機能させるしきい値調整処理プログラムを備え、しきい値調整処理プログラムは、修正係数算出プログラムを備え、修正係数算出プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど小さく設定された第１修正係数と、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど大きく設定された第２正係数と、を用いて注目頂点の上記修正係数を算出する手段としてコンピュータを機能させることを特徴とする。
本発明の閉図形の分割処理プログラムは、複数の頂点を繋いで生成された閉図形を複数の線図に分割する手段としてコンピュータを機能させる閉図形の分割処理プログラムにおいて、閉図形の各頂点毎にその頂点を分割点とするか否かを決定するための判定要素を算出する手段としてコンピュータを機能させる判定要素算出処理プログラムと、各頂点毎の判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムとを備えたことを特徴とする。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させることも特徴とする。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させることも特徴とする。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段、及び、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の第１判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けする手段、頂点の第２判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段、及び、各頂点に関しての第１判定要素のランク及び第２判定要素のランクを総合して総合ランク上位の頂点を分割点として決定する手段としてコンピュータを機能させることも特徴とする。
【発明の効果】
【０００５】
本発明の線図の圧縮処理プログラムによれば、しきい値調整処理プログラムを備えたので、線図の精度を保持したまま頂点を間引くことができてデータ量を圧縮できる。
しきい値調整処理プログラムが、不等辺三角形網生成処理プログラムと、修正値計算処理プログラムと、修正しきい値算出処理プログラムと、しきい値設定処理プログラムとを備えたので、一方の線図上にある注目頂点と他方の線図とが近い場合、その注目頂点のしきい値を元のしきい値よりも適切に小さくできるので、その注目頂点が間引かれにくくなり、間引き処理後の一方の線図と他方の線図との交差を防止でき、線図の精度を保持したままデータ量を圧縮できる。
本発明の線図の圧縮処理プログラムによれば、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたので、元の線図において形状を維持することが必要な部分の形状を維持できるとともに、データを圧縮できる。特に、各頂点間の長さに差がないような線図を間引き処理する場合に有効である。
本発明の線図の圧縮処理プログラムによれば、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが、上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど上記しきい値を大きくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたので、元の線図において形状を維持することが必要な部分の形状を維持できるとともに、データを圧縮できる。特に、曲線が多くて９０°に近い角部分が少ないような線図を間引き処理する場合に有効である。
本発明の線図の圧縮処理プログラムによれば、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど小さく設定された第１修正係数と、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど大きく設定された第２正係数と、を用いて注目頂点の上記修正係数を算出する手段としてコンピュータを機能させる修正係数算出プログラムを備えたので、元の線図において形状を維持することが必要な部分の形状を適切に維持できるとともに、データを圧縮できる。
本発明の閉図形の分割処理プログラムは、複数の頂点を繋いで生成された閉図形を複数の線図に分割する手段としてコンピュータを機能させる閉図形の分割処理プログラムにおいて、閉図形の各頂点毎にその頂点を分割点とするか否かを決定するための判定要素を算出する手段としてコンピュータを機能させる判定要素算出処理プログラムと、各頂点毎の判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムとを備えたので、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させるので、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる。特に、各頂点間の長さに差がないような閉図形を分割する場合に有効である。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させるので、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる。特に、曲線が多くて９０°に近い角部分が少ないような閉図形を分割する場合に有効である。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段、及び、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の第１判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けする手段、頂点の第２判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段、及び、各頂点に関しての第１判定要素のランク及び第２判定要素のランクを総合して総合ランク上位の頂点を分割点として決定する手段としてコンピュータを機能させるので、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を適切に得ることができる。
【発明を実施するための最良の形態】
【０００６】
最良の形態１
図１乃至図６は本発明の最良の形態１を示す。図１は圧縮処理装置の構成を示し、図２は線図の頂点を繋いで不等辺三角形網を生成した状態を示し、図３は修正値の算出方法を説明し、図４；図５は間引き処理の手順を示し、図６は間引き処理後の線図を示す。
【０００７】
最良の形態１による線図の圧縮処理装置１は、しきい値調整処理手段２、間引き処理手段３を備える。しきい値調整処理手段２は、不等辺三角形網生成処理手段４（以下、ＴＩＮ（Ｔｒｉａｎｇｕｌａｔｅｄ Ｉｒｒｅｇｕｌａｒ Ｎｅｔｗｏｒｋ）生成処理手段という）、修正値算出処理手段５、修正しきい値算出処理手段６、しきい値設定処理手段７を備える。
【０００８】
圧縮処理装置１は、コンピュータと圧縮処理プログラムとにより実現される。間引き処理手段３は、コンピュータと間引き処理プログラムとにより実現される。間引き処理プログラムは、線図上において間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる。ＴＩＮ生成処理手段４は、コンピュータとＴＩＮ生成処理プログラムとにより実現される。ＴＩＮ生成処理プログラムは、互いに異なる一対の線図の頂点同士を繋いで不等辺三角形網を生成する手段としてコンピュータを機能させる。修正値算出処理手段５は、コンピュータと修正値算出処理プログラムとにより実現される。修正値算出処理プログラムは、注目頂点と向かい合う三角形の対辺が線図上にある場合には注目頂点とその三角形の対辺との最短の長さを修正値として求め、注目頂点と向かい合う三角形の対辺が線図上にない場合には注目頂点を含む三角形において注目頂点と注目頂点を含まない線図上の頂点とを繋ぐ二辺のうちの長さの短い辺の長さを修正値として求める手段としてコンピュータを機能させる。修正しきい値算出処理手段６は、コンピュータと修正しきい値算出処理プログラムとにより実現される。修正しきい値算出処理プログラムは、修正値ε１又はε２に０．３以上０．５以下の係数αをかけた修正しきい値εｊを算出する手段としてコンピュータを機能させる。しきい値設定処理手段７は、コンピュータとしきい値設定処理プログラムとにより実現される。しきい値設定処理プログラムは、注目頂点の元しきい値ε０と修正しきい値εｊとを比較して小さい方を注目頂点のしきい値Εとして設定する手段としてコンピュータを機能させる。
【０００９】
尚、本発明で言うコンピュータとは、ＣＰＵ、主記憶装置、外部記憶装置などのハードウエアおよびオペレーティングシステムのような基本ソフトウエアなどからなるコンピュータのことであり、上記各プログラムに基づいて上記各手段を実現する装置を指す。
【００１０】
次に線図の処理方法を説明する。まず、地図において間引き処理の対象となる範囲が指定されると、ＴＩＮ生成処理手段４が、範囲内の互いに異なる一対の線図１１；１２の頂点１３同士を繋いで不等辺三角形網を生成する（図２参照）。次に、修正値算出処理手段５が、注目頂点と向かい合う三角形の対辺が線図１１；１２上にあるか否かを判定した後に、注目頂点と向かい合う三角形の対辺があると判定した場合は、例えば、図３に示すように、注目頂点１３ａと向かい合う三角形の対辺１２ａと直交してかつ注目頂点１３ａに到達する垂線１４を引き、垂線１４の長さｘ１（即ち、注目頂点１３ａとその対辺１２ａとを繋ぐ最短の長さ）を修正値ε１として算出する。そして、修正しきい値算出処理手段６が、修正値ε１に例えば係数α＝０．４をかけた修正しきい値εｊ＝ε１×αを算出する。つぎに、しきい値設定処理手段７が、注目頂点１３ａの元しきい値εと修正しきい値εｊとを比較して小さい方を注目頂点１３ａのしきい値Εとして設定し、その設定された注目頂点１３ａのしきい値Εを半径とするしきい値円１５を注目頂点１３ａを中心として設定する。
尚、修正値算出処理手段５は、注目頂点と向かい合う三角形の対辺が線図１１；１２上にないと判定した場合、注目頂点を含む三角形において注目頂点と注目頂点を含まない線図１１；１２上の頂点とを繋ぐ二辺の長さを求め、二辺の長さのうちの短い辺の長さｘ２を修正値ε２として算出し、修正しきい値算出処理手段６は、修正値ε２に例えば係数α＝０．４をかけた修正しきい値εｊ＝ε２×αを算出する。
【００１１】
図４（ａ）に、しきい値設定処理手段７により設定された各頂点のしきい値Εを半径としたしきい値円１５を各頂点毎に設定した状態を示す。
【００１２】
そして、間引き処理手段３が、従来と同じように間引き処理を行う。この間引き処理を図４（ｂ）〜（ｄ）、図５（ａ）；（ｂ）を参照して説明する。尚、線図１１；１２の頂点の間引き処理は同じなので、以下、線図１１の頂点の間引き処理についてのみ説明する。まず、図４（ｂ）に示すように、線図１１において、始点と終点とを繋ぐ直線１６を引き、この直線１６から最も離れた頂点１７を求める。頂点１７のしきい値円１５と直線１６とが交差しないので、この頂点１７は間引かれない（削除されない）。図４（ｃ）に示すように、頂点１７と始点とを直線１９で繋ぎ、この直線１９から最も離れた頂点２０を求める。この頂点２０のしきい値円１５と直線１９とが交差するので、この頂点２０は間引かれる（削除される）。尚、頂点１７と始点との間の各頂点はすべて間引かれる。また、頂点１７と終点とを直線２３で繋ぎ、この直線２３から最も離れた頂点２４を求める。頂点２４のしきい値円１５は従来の元しきい値εによるしきい値円Ｒよりも小さくなっている。従来、図１８に示すように、頂点２４のしきい値円Ｒと直線２３とが交差していたので、この頂点２４は間引かれ、このため、直線２３が残って、この直線２３と線図１２の頂点２５とが交差してしまっていた。一方、本発明では、頂点２４のしきい値円１５と直線２３とが交差しないので、頂点２４が残り、このため、線図１２の頂点２５と線図１１とが交差しない。以下、図４（ｄ）に示すように、頂点２６のしきい値円１５と直線２６ａとが交差しないので、頂点２６が残り、図５（ａ）；（ｂ）に示すように、頂点２７のしきい値円１５と直線２７ａとが交差しないので、従来、間引きされていた頂点２７も残る。即ち、従来、交差してしまっていた頂点２５と線図１１とが交差せず、しかも、地図データの精度も保たれる間引き処理を行える。図６に間引き処理後の線図１１Ａ；１２Ａを示す。図６に示すように、最良の形態１による間引き処理後は、従来のように、線図１１Ａと線図１２Ａとが交差するようなことがなくなる。
【００１３】
最良の形態１によれば、一方の線図上にある注目頂点と他方の線図とが近い場合、その注目頂点のしきい値Εを元しきい値εよりも小さくしたので、その注目頂点が間引かれにくくなり、間引き処理後の一方の線図と他方の線図との交差を防止できる。例えば、道路を示す線図と家を示す線図との交差を防止できる。よって、地図データの精度を保持したまま地図データを圧縮できる。
【００１４】
最良の形態２
互いに異なる一対の線図のうちの一方の線図の頂点と他方の線図の線分との間の最短長さが所定値よりも短い場合に元しきい値εを小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムでもよい。地図の縮尺の違いによってそれぞれ異なる所定値を決めておけば、最良の形態１と同様に、地図データの精度を保持したまま地図データを圧縮できる。
【００１５】
最良の形態３
閉図形のままでは図形の始点と終点とがわからないので間引き処理を行うことができない。そこで、始点と終点とを出すために、閉図形をいくつかの線図に分割した後に、上述したように線図の始点と終点とを線で繋いで線図の間引き処理を開始し、間引き処理が終了した後の線図の終点及び始点を連結して閉図形に戻すことにより、閉図形の間引き処理が行われる。従来、この閉図形の分割処理は、閉図形をｎ個に分割する場合に、閉図形を構成する頂点の数をｎで割った数の頂点で形成されるｎ個の線図に分割する。例えば、１６個の頂点を繋いで形成された閉図形を４つに分割する場合、ある任意の頂点を分割点と決めて、その任意の頂点から一方向に向かって４番目、８番目、１２番目の頂点を分割点と決めることによって、４つの線図に分割する。つまり、４個の頂点を繋いで形成される線図を４つ形成し、１つ１つの線図に対して間引き処理を行い、間引き処理後の４つの線図の終点及び始点を連結して閉図形に戻す。しかしながら、このような分割処理の場合、間引き処理後の閉図形が元の閉図形の形状とかけ離れてしまい、元の閉図形において形状を維持することが必要な部分の形状を維持できない。
【００１６】
最良の形態３では、元の閉図形において形状を維持することが必要な部分の形状を維持できるようにした閉図形の分割処理プログラムについて説明する。図７乃至図９は本発明の最良の形態３を示す。図７は分割処理装置の構成を示し、図８は分割手順を示し、図９は判定要素の説明図である。
【００１７】
閉図形の分割処理装置３０は、判定要素算出処理手段３１、分割点決定処理手段３２を備える。分割処理装置３０は、コンピュータと分割処理プログラムとにより実現される。判定要素算出処理手段３１は、コンピュータと判定要素算出処理プログラムとにより実現される。分割点決定処理手段３２は、コンピュータと分割点決定処理プログラムとにより実現される。
【００１８】
判定要素算出処理プログラムは、閉図形の各頂点毎にその頂点を分割点とするか否かを決定するための判定要素を算出する手段としてコンピュータを機能させるプログラムである。この判定要素算出処理プログラムは、図９に示すように、判定要素を算出する対象となる注目頂点Ｔ１から一方の頂点Ｔ２に繋がれた一方線分Ｌ１と注目頂点Ｔ１から他方の頂点Ｔ３に繋がれた他方線分Ｌ２とのなす角度θを第１判定要素として算出する手段、及び、判定要素を算出する対象となる注目頂点Ｔ１から一方の頂点Ｔ２に繋がれた一方線分Ｌ１の長さl１及び注目頂点Ｔ１から他方の頂点Ｔ３に繋がれた他方線分Ｌ２の長さl２のうち長さの短い方の線分の長さを第２判定要素として算出する手段としてコンピュータを機能させる。分割点決定処理手段３２は、コンピュータと分割点決定処理プログラムとにより実現される。分割点決定処理プログラムは、各頂点毎の判定要素に基づいて分割点を決定する手段としてコンピュータを機能させるプログラムである。この分割点決定処理プログラムは、頂点の第１判定要素としての角度θが９０°に近いほどその頂点を分割点候補として上位にランク付けする手段、頂点の第２判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段、及び、各頂点に関しての第１判定要素のランク及び第２判定要素のランクを総合して総合ランク上位の頂点を分割点として決定する手段としてコンピュータを機能させる。
【００１９】
図８では、分割点を「３」に設定して総合ランク上位３位までの頂点が分割された例を示す。尚、図８（ｂ）の各頂点の傍に付した番号が総合ランクの順番であり、ここでは、図８（ｃ）に示すように、閉図形Ｚの４つの角部にある頂点のうち３つの頂点Ｔｘ；Ｔｙ；Ｔｚが分割点に決定される。分割点とならなかった角部にある総合ランク４位の頂点Ｔｅは、分割点となった角部にある頂点に比べて、総合ランク８位の頂点と繋がれた線分長さが短く、かつ、角度が９０°に遠いため、総合ランクが低くなっている。
【００２０】
図８（ｃ）に示すように、分割された３つの線図Ｙ１；Ｙ２；Ｙ３毎にそれぞれ上述した間引き処理を行う。ここでは、線図は、始点と終点とを繋ぐ直線となるよう間引き処理され、線図もよりＬ字状に近い状態に間引き処理され、これら線図が、分割点となった頂点同士で再び連結されることによって、より長方形に近い閉図形になる。つまり、元の閉図形の形状である長方形状の形状を崩すことなく間引きされた閉図形を得ることができる。よって、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる。
【００２１】
最良の形態４
分割点決定処理プログラムは、各頂点毎の第１判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムであってもよい。つまり、この分割点決定処理プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほどその頂点を分割点候補として上位にランク付けする手段としてコンピュータを機能させる。この分割点決定処理プログラムを用いた場合であっても、例えば、各頂点間の長さに差がないような閉図形を分割する場合に有効である。
【００２２】
最良の形態５
分割点決定処理プログラムは、各頂点毎の第２判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムであってもよい。つまり、この分割点決定処理プログラムは、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段としてコンピュータを機能させる。この分割点決定処理プログラムを用いた場合であっても、例えば、曲線が多くて９０°に近い角部分が少ないような閉図形を分割する場合に有効である。
【００２３】
最良の形態６
図１０乃至図１４は本発明の最良の形態６を示す。図１０は圧縮処理装置の構成を示し、図１１は間引き処理の手順を示し、図１２は間引き後の閉図形を示し、図１３は第１修正係数β１を求める関数式及び関数グラフの一例を示し、図１４は第２修正係数β２を求める関数式及び関数グラフの一例を示す。
【００２４】
最良の形態６による、線図の圧縮処理手段１は、しきい値調整処理手段２、間引き処理手段３を備える。しきい値調整処理手段２は、修正係数算出処理手段３５、しきい値設定処理手段３６を備える。
修正係数算出処理手段３５は、コンピュータと修正係数算出プログラムとにより実現される。修正係数算出プログラムは、注目頂点の元しきい値εに修正係数をかけて算出した修正しきい値を注目頂点のしきい値として設定する手段としてコンピュータを機能させる。更に詳細には、修正係数算出プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど小さく設定された第１修正係数β１と、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さくかつその差が大きいほど大きく設定された第２修正係数β２と、を用いて注目頂点の修正係数βを算出する手段としてコンピュータを機能させる。しきい値設定処理手段３６は、コンピュータとしきい値設定処理プログラムとにより実現される。しきい値設定処理プログラムは、注目頂点の修正係数β×元しきい値εにより求めたしきい値Εを注目頂点のしきい値Εとして設定する手段としてコンピュータを機能させる。
【００２５】
第１修正係数β１や第２修正係数β２は上述した条件に合うように設定すればよい。例えば、第１修正係数β１は、以下に示す関数Ｐ（ｘ）で求める。
ここで、
ｘ：頂点の角度（０度から１８０度）
ａ：傾き係数
ｘ０：角度フィルタ係数（Ｐ（ｘ０）＝０．５となるときの角度）
例えば、第２修正係数β２は、以下に示す関数Ｐ（ｌ´）で求める。
Ｐ（ｌ´）＝１−ｃ×ｌ´
ここで、
ｌ´：正規化辺長、ｌ´＝ｌ／ε（０＜ｌ＜ε、ｌ≧εならば、ｌ´＝ｌ）
ｃ：傾き係数（一般に、１−ｃ＝０．２が標準値）
そして、修正係数βを、√β１×√β２で求める。
【００２６】
図１１（ａ）に、しきい値設定処理手段３６により設定された各頂点のしきい値Εを半径としたしきい値円１５Ａを各頂点毎に設定した状態を示す。
【００２７】
そして、間引き処理手段が、従来と同じように間引き処理を行う。この間引き処理を図１１（ｂ）〜（ｄ）を参照して説明する。尚、この例では、閉図形を例にしているので、間引き処理の前に、上述した分割処理手段で閉図形を分割してから間引き処理を行う。図１１（ｂ）〜（ｄ）では閉図形が頂点Ｔｃ；Ｔｄで分割された後に、分割された頂点同士を繋いだ線図ＸＡと線図ＸＢとで別々に間引き処理を行っている。間引き処理の手法は、最良の形態１と同じである。しきい値設定処理手段８により設定された線図ＸＡの各頂点Ｔ１１；Ｔ１２；Ｔ１３のしきい値Εは、いずれも修正係数βによって小さくなっており、このため、線図ＸＡの間引き処理により、図１１（ｂ）のように、直線Ｍ１と頂点Ｔ１１のしきい値円１５Ａとが交差しないので、頂点Ｔ１１が残り、図１１（ｃ）のように、直線Ｍ２と頂点Ｔ１２のしきい値円１５Ａとが交差しないので、頂点Ｔ１２が残り、図１１（ｄ）のように、直線Ｍ３と頂点Ｔ１３のしきい値円１５Ａとが交差しないので、頂点Ｔ１３が残る。しきい値設定処理手段３６により設定された線図ＸＢの各頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４のしきい値Εは、第２修正係数β２が大きいために大きくなっており、線図ＸＢの間引き処理により、各頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４は間引きされる。図１２に間引き後の線図ＸＡ；ＸＢを連結した閉図形を示す。
【００２８】
最良の形態６の圧縮処理装置１によれば、間引き処理後の閉図形は、各頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４のみが間引きされ、元の閉図形の元の閉図形において形状を維持することが必要な部分の形状を維持できる。よって、最良の形態１と同様に、地図データの精度を保持したまま地図データを圧縮できる。つまり、元の線図において形状を維持することが必要な部分の形状を維持できるとともに、データを圧縮できる。また、第１修正係数β１と第２修正係数β２とを用いて修正係数βを算出しているため、特に図１１に示すような、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近くても、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さい頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４を間引くことができる。つまり、第１修正係数β１を用いただけでは、頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４が残ってしまう場合があるが、第１修正係数β１と第２修正係数β２とを用いることで、形状維持に不要な頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４を間引くことができる。
【００２９】
最良の形態７
しきい値調整処理プログラムとして、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを用いても良い。このしきい値調整処理プログラムを用いた場合であっても、例えば、各頂点間の長さに差がないような線図を間引き処理する場合に有効である。
【００３０】
最良の形態８
しきい値調整処理プログラムとして、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さと上記しきい値とを比較し、当該線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど上記しきい値を大きくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを用いても良い。このしきい値調整処理プログラムを用いた場合であっても、例えば、曲線が多くて９０°に近い角部分が少ないような線図を間引き処理する場合に有効である。
【００３１】
最良の形態９
最良の形態１；６の圧縮処理手段１と最良の形態３の分割処理手段とを備えた地図データ圧縮処理装置による処理の流れを図１５を参照して説明する。地図データ圧縮処理装置は、圧縮対象となる地図の範囲を指定するコマンドを入力して、その指定された範囲のデータを読み込む（ステップＳ１）。最良の形態１によるしきい値修正処理を行う（ステップＳ２）。最良の形態６によるしきい値修正処理を行う（ステップＳ３）。最良の形態３による分割処理を行う（ステップＳ４）。間引き処理を行う（ステップＳ５）。尚、ステップＳ２〜ステップＳ４までの処理の順序は変わっても良い。
【産業上の利用可能性】
【００３２】
本発明は、地図データ以外の線図の間引き処理、及び、地図データ以外の閉図形の分割処理にも使用できる。
【図面の簡単な説明】
【００３３】
【図１】圧縮処理装置を示すブロック構成図（最良の形態１）。
【図２】不等辺三角形網を示す図（最良の形態１）。
【図３】修正値算出方法の説明図（最良の形態１）。
【図４】間引き処理の手順を示す図（最良の形態１）。
【図５】間引き処理の手順を示す図（最良の形態１）。
【図６】間引き処理後の線図を示す図（最良の形態１）。
【図７】分割処理装置を示すブロック構成図（最良の形態３）。
【図８】分割手順を示す図（最良の形態３）。
【図９】判定要素の説明図（最良の形態３）。
【図１０】圧縮処理装置を示すブロック構成図（最良の形態６）。
【図１１】間引き処理の手順を示す図（最良の形態６）。
【図１２】間引き後の閉図形を示す図（最良の形態６）。
【図１３】第１修正係数β１を求める関数式及び関数グラフの一例を示す図（最良の形態６）。
【図１４】第２修正係数β２を求める関数式及び関数グラフの一例を示す図（最良の形態６）。
【図１５】地図データ圧縮処理装置による処理の流れ図（最良の形態９）。
【図１６】従来の間引き処理の手順を示す図。
【図１７】従来の間引き処理のしきい値の説明図。
【図１８】従来の間引き処理結果を示す図。
【図１９】従来の間引き処理結果を示す図。
【図２０】従来の間引き処理結果を示す図。
【符号の説明】
【００３４】
１ 圧縮処理装置、２ しきい値調整処理手段、３ 間引き処理手段、
４ ＴＩＮ生成処理手段、５ 修正値算出処理手段、６ 修正しきい値算出処理手段、
７ しきい値設定処理手段、３０ 分割処理装置、３１ 判定要素算出処理手段、
３２ 分割点決定処理手段、３５ 修正係数算出処理手段、３６ しきい値設定処理手段。
【技術分野】
【０００１】
本発明は、線図の精度を保持したまま頂点を間引くことができてデータ量を圧縮可能とする圧縮処理プログラム等に関する。
【背景技術】
【０００２】
ＳＶＧ（Ｓｃａｌａｂｌｅ Ｖｅｃｔｏｒ Ｇｒａｐｈｉｃｓ）形式やその他の形式の地図データにおいて、複数の頂点を繋いで生成された線図の頂点を間引いて地図データの容量を圧縮する方法として、Ｄｏｕｇｌａｓ−Ｐｅｕｃｋｅｒアルゴリズム（以下、ＤＰ法という）が知られている（例えば、非特許文献１参照）。
図１６を参照し、ＤＰ法を説明する。間引き処理の対象となる線図、即ち、始点となる頂点から終点となる頂点までの間において複数の頂点を繋いで生成された線図において、始点となる頂点ａ及び終点となる頂点ｚ以外の各頂点ｂ，ｃ，d・・・・ｉには、頂点を間引くことが可能か否かの基準となるしきい値εが設定される。このしきい値εは、ε＝Ａ×Ｂで求めた値である。尚、Ａは対象となる地図の縮尺の母数、Ｂは地図縮尺毎に決められた要求精度である。各頂点Ｔ（ｂ，ｃ，d・・・・ｉ）のそれぞれには、図１６（ａ）；図１７に示すように、頂点Ｔを中心としてしきい値εを半径寸法としたしきい値円Ｒが設定される。即ち、ＤＰ法による線図の圧縮処理プログラムは、線図の各頂点に頂点からの一定距離であるしきい値εが設定され、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させるものである。つまり、図１７に示すように、注目頂点を間引くことができるか否かは、コンピュータが、注目頂点に設定されるしきい値円と注目頂点の両側に位置する頂点同士を繋いだ線分とが交わるか否かを判断し、しきい値円と線分とが交わる場合にはその注目頂点を間引くことが可能であると判定し、しきい値円と線分とが交わらない場合にはその注目頂点を間引くことができないと判定する。
以下、図１６を参照し、ＤＰ法の手順を説明する。まず、図１６（ｂ）のように、線分の始点となる頂点ａと終点となる頂点ｚとを直線ａ１で繋ぐ。線分中の各頂点と直線ａ１とを結ぶ直線ａ１と直交する直交線（垂線）の長さの最長のものを求める。ここで最長の直交線の長さ、つまり、頂点ｃと直線ａ１との間の最短距離が頂点ｃのしきい値εよりも大きく、直線ａ１と頂点ｃのしきい値円Ｒとが交差しないので、頂点ｃは間引かれずに残る。図１６（ｃ）のように、頂点ｃと頂点ａ（始点）とを直線ａ２で繋ぐと共に頂点ｃと頂点ｚ（終点）とを直線ａ３で繋ぐ。頂点ｂと直線ａ２との間の最短距離が頂点ｂのしきい値εよりも大きく、直線ａ２と頂点ｂのしきい値円Ｒとが交差するので、図１６（ｄ）の白丸で示すように、頂点ｂは間引かれる（削除される）。頂点ｃから頂点ｚまでの間の頂点のうち、直線ａ３と直交する直交線の長さの最長の頂点ｅを求める。直線ａ３と頂点ｅのしきい値円Ｒとが交差しないので、図１６（ｄ）に示すように、頂点ｅは間引かれずに残る。頂点ｅと頂点ｃとを直線ａ４で繋ぐと共に頂点ｅと頂点ｚとを直線ａ５で繋ぐ。直線ａ４と頂点ｄのしきい値円Ｒとが交差するので、頂点ｄは図１６（ｅ）のように間引かれる。頂点ｅから頂点ｚまでの間の頂点のうち、直線ａ５と直交する直交線の長さの最長の頂点ｇを求める。直線ａ５と頂点ｇのしきい値円Ｒとが交差しないので、頂点ｇは間引かれずに残る。頂点ｇと頂点ｅとを直線ａ６で繋ぐと共に頂点ｇと頂点ｚとを直線ａ７で繋ぐ。直線ａ５と頂点ｆのしきい値円Ｒとが交差するので、頂点ｆは間引かれる。頂点ｇから頂点ｚまでの間の頂点のうち、直線ａ７と直交する直交線の長さの最長の頂点ｉを求める。直線ａ７と頂点ｉのしきい値円Ｒとが交差しないので、図１６（ｄ）のように、頂点ｉは間引かれずに残る。頂点ｉと頂点ｇとを直線ａ８で繋ぐと共に頂点ｉと頂点ｚとを直線ａ９で繋ぐ。直線ａ８と頂点ｈのしきい値円Ｒとが交差するので、頂点ｈは間引かれる。
また、ＤＰ法では、閉図形のままでは図形の始点と終点とがわからないので間引き処理を行うことができないので、間引き処理の対象が閉図形の場合には、閉図形をいくつかの線図に分割した後にその線図毎に間引き処理を行った後に、間引き処理後の線図を再び連結する。
即ち、ＤＰ法による圧縮処理プログラムの手順は次のとおりである。まず、線分の始点となる頂点と終点となる頂点とを直線で繋いでこの直線と最も離れた頂点を最初の注目頂点としてこの注目頂点のしきい値円と直線とが交差するか否かを判定し、交差する場合は、当該線分の各頂点はすべて間引きされる。すなわち、始点と終点とだけが残り、間引き後の線分は、始点と終点とを繋ぐ直線となる。注目頂点のしきい値円と直線とが交差しない場合には、注目頂点が間引かれずに残る。当該頂点が残ったら、当該頂点と始点とが直線で繋がれ、この直線と最も離れた頂点を注目頂点としてこの注目頂点のしきい値円と直線とが交差するか否かを判定し、交差する場合は、当該注目頂点と始点との間の各頂点はすべて間引きされる。注目頂点のしきい値円と直線とが交差しない場合には、注目頂点が間引かれずに残る。以上のような、注目頂点のしきい値円と直線とが交差するか否かの判断を、注目頂点がなくなるまで行う。
【非特許文献１】Ｄｕｇｌａｓ Ｄ． ａｎｄ Ｐｅｕｃｋｅｒ．Ｔ．，１９７３，Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｒｅｄｕｃｔｉｏｎ ｏｆ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｐｏｉｎｔｓ ｒｅｑｕｉｒｅｄ ｆｏｒ ｒｅｐｒｅｓｅｎｔ ａ ｄｉｇｉｔｚｅｄ ｌｉｎｅ ｏｒ ｃａｒｉｃａｔｕｒｅ， Ｃａｎａｄｉａｎ Ｃａｒｔｏｇｒａｐｈｅｒ，１０，１１２−１２２
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、ＤＰ法によれば、各頂点において一定のしきい値εを用いるために、間引き処理において、図１８に示すように、間引き処理後の線図１１Ａと線図１２Ａとが交差したり、図１９に示すように、線図の角部の頂点５０が除去されてしまうことがあった。例えば、図２０（ａ）に示す閉図形Ｚの場合、形状を維持するために頂点５１；５２を間引きたくはない。しかしななら、図２０（ｂ）〜（ｄ）に示すように、ＤＰ法で間引き処理を行っていくと、分割点６０；６１以外の図形の全ての各頂点のしきい値ε（しきい値円Ｒ）が一定であるため、頂点５１；５２も間引かれてしまい、間引き後の閉図形ＺＡは元の閉図形Ｚの形状を維持できなくなってしまう。即ち、線図の精度を維持したまま線図の頂点を間引いてデータ量を圧縮することが困難であった。
また、閉図形の分割処理は、閉図形の頂点を複数個毎に分けることによって複数の線図に分割しているため、分割の仕方によって、間引き処理後の閉図形が元の閉図形の形状とかけ離れてしまい、元の閉図形の形状が維持されなくなってしまう。
本発明は、上記課題に鑑みてなされたもので、線図の精度を保持したまま頂点を間引くことができてデータ量を圧縮可能とする圧縮処理プログラム、及び、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる閉図形の分割処理プログラムを提供する。
【課題を解決するための手段】
【０００４】
本発明の線図の圧縮処理プログラムは、複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、互いに異なる一対の線図のうちの一方の線図の頂点と他方の線図の線分との間の最短長さが所定値よりも短い場合に上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする。
しきい値調整処理プログラムは、互いに異なる一対の線図の頂点同士を繋いで不等辺三角形網を生成する手段としてコンピュータを機能させる不等辺三角形網生成処理プログラムと、注目頂点と向かい合う三角形の対辺が線図上にある場合には注目頂点とその三角形の対辺との最短長さを修正値として求め、注目頂点と向かい合う三角形の対辺が線図上にない場合には注目頂点を含む三角形において注目頂点と注目頂点を含まない線図上の頂点とを繋ぐ二辺のうち長さの短い辺の長さを修正値として求める手段としてコンピュータを機能させる修正値計算処理プログラムと、上記修正値に０．５以下の係数をかけた修正しきい値を算出する手段としてコンピュータを機能させる修正しきい値算出処理プログラムと、注目頂点の上記しきい値と修正しきい値とを比較して小さい方を注目頂点のしきい値として設定する手段としてコンピュータを機能させるしきい値設定処理プログラムとを備えたことも特徴とする。
本発明の線図の圧縮処理プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする。
本発明の線図の圧縮処理プログラムは、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さと上記しきい値とを比較し、当該線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど上記しきい値を大きくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする。
本発明の線図の圧縮処理プログラムは、注目頂点の上記しきい値に修正係数をかけて算出した修正しきい値を注目頂点のしきい値として設定する手段としてコンピュータを機能させるしきい値調整処理プログラムを備え、しきい値調整処理プログラムは、修正係数算出プログラムを備え、修正係数算出プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど小さく設定された第１修正係数と、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど大きく設定された第２正係数と、を用いて注目頂点の上記修正係数を算出する手段としてコンピュータを機能させることを特徴とする。
本発明の閉図形の分割処理プログラムは、複数の頂点を繋いで生成された閉図形を複数の線図に分割する手段としてコンピュータを機能させる閉図形の分割処理プログラムにおいて、閉図形の各頂点毎にその頂点を分割点とするか否かを決定するための判定要素を算出する手段としてコンピュータを機能させる判定要素算出処理プログラムと、各頂点毎の判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムとを備えたことを特徴とする。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させることも特徴とする。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させることも特徴とする。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段、及び、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の第１判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けする手段、頂点の第２判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段、及び、各頂点に関しての第１判定要素のランク及び第２判定要素のランクを総合して総合ランク上位の頂点を分割点として決定する手段としてコンピュータを機能させることも特徴とする。
【発明の効果】
【０００５】
本発明の線図の圧縮処理プログラムによれば、しきい値調整処理プログラムを備えたので、線図の精度を保持したまま頂点を間引くことができてデータ量を圧縮できる。
しきい値調整処理プログラムが、不等辺三角形網生成処理プログラムと、修正値計算処理プログラムと、修正しきい値算出処理プログラムと、しきい値設定処理プログラムとを備えたので、一方の線図上にある注目頂点と他方の線図とが近い場合、その注目頂点のしきい値を元のしきい値よりも適切に小さくできるので、その注目頂点が間引かれにくくなり、間引き処理後の一方の線図と他方の線図との交差を防止でき、線図の精度を保持したままデータ量を圧縮できる。
本発明の線図の圧縮処理プログラムによれば、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたので、元の線図において形状を維持することが必要な部分の形状を維持できるとともに、データを圧縮できる。特に、各頂点間の長さに差がないような線図を間引き処理する場合に有効である。
本発明の線図の圧縮処理プログラムによれば、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが、上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど上記しきい値を大きくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたので、元の線図において形状を維持することが必要な部分の形状を維持できるとともに、データを圧縮できる。特に、曲線が多くて９０°に近い角部分が少ないような線図を間引き処理する場合に有効である。
本発明の線図の圧縮処理プログラムによれば、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど小さく設定された第１修正係数と、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど大きく設定された第２正係数と、を用いて注目頂点の上記修正係数を算出する手段としてコンピュータを機能させる修正係数算出プログラムを備えたので、元の線図において形状を維持することが必要な部分の形状を適切に維持できるとともに、データを圧縮できる。
本発明の閉図形の分割処理プログラムは、複数の頂点を繋いで生成された閉図形を複数の線図に分割する手段としてコンピュータを機能させる閉図形の分割処理プログラムにおいて、閉図形の各頂点毎にその頂点を分割点とするか否かを決定するための判定要素を算出する手段としてコンピュータを機能させる判定要素算出処理プログラムと、各頂点毎の判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムとを備えたので、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させるので、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる。特に、各頂点間の長さに差がないような閉図形を分割する場合に有効である。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させるので、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる。特に、曲線が多くて９０°に近い角部分が少ないような閉図形を分割する場合に有効である。
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段、及び、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の第１判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けする手段、頂点の第２判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段、及び、各頂点に関しての第１判定要素のランク及び第２判定要素のランクを総合して総合ランク上位の頂点を分割点として決定する手段としてコンピュータを機能させるので、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を適切に得ることができる。
【発明を実施するための最良の形態】
【０００６】
最良の形態１
図１乃至図６は本発明の最良の形態１を示す。図１は圧縮処理装置の構成を示し、図２は線図の頂点を繋いで不等辺三角形網を生成した状態を示し、図３は修正値の算出方法を説明し、図４；図５は間引き処理の手順を示し、図６は間引き処理後の線図を示す。
【０００７】
最良の形態１による線図の圧縮処理装置１は、しきい値調整処理手段２、間引き処理手段３を備える。しきい値調整処理手段２は、不等辺三角形網生成処理手段４（以下、ＴＩＮ（Ｔｒｉａｎｇｕｌａｔｅｄ Ｉｒｒｅｇｕｌａｒ Ｎｅｔｗｏｒｋ）生成処理手段という）、修正値算出処理手段５、修正しきい値算出処理手段６、しきい値設定処理手段７を備える。
【０００８】
圧縮処理装置１は、コンピュータと圧縮処理プログラムとにより実現される。間引き処理手段３は、コンピュータと間引き処理プログラムとにより実現される。間引き処理プログラムは、線図上において間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる。ＴＩＮ生成処理手段４は、コンピュータとＴＩＮ生成処理プログラムとにより実現される。ＴＩＮ生成処理プログラムは、互いに異なる一対の線図の頂点同士を繋いで不等辺三角形網を生成する手段としてコンピュータを機能させる。修正値算出処理手段５は、コンピュータと修正値算出処理プログラムとにより実現される。修正値算出処理プログラムは、注目頂点と向かい合う三角形の対辺が線図上にある場合には注目頂点とその三角形の対辺との最短の長さを修正値として求め、注目頂点と向かい合う三角形の対辺が線図上にない場合には注目頂点を含む三角形において注目頂点と注目頂点を含まない線図上の頂点とを繋ぐ二辺のうちの長さの短い辺の長さを修正値として求める手段としてコンピュータを機能させる。修正しきい値算出処理手段６は、コンピュータと修正しきい値算出処理プログラムとにより実現される。修正しきい値算出処理プログラムは、修正値ε１又はε２に０．３以上０．５以下の係数αをかけた修正しきい値εｊを算出する手段としてコンピュータを機能させる。しきい値設定処理手段７は、コンピュータとしきい値設定処理プログラムとにより実現される。しきい値設定処理プログラムは、注目頂点の元しきい値ε０と修正しきい値εｊとを比較して小さい方を注目頂点のしきい値Εとして設定する手段としてコンピュータを機能させる。
【０００９】
尚、本発明で言うコンピュータとは、ＣＰＵ、主記憶装置、外部記憶装置などのハードウエアおよびオペレーティングシステムのような基本ソフトウエアなどからなるコンピュータのことであり、上記各プログラムに基づいて上記各手段を実現する装置を指す。
【００１０】
次に線図の処理方法を説明する。まず、地図において間引き処理の対象となる範囲が指定されると、ＴＩＮ生成処理手段４が、範囲内の互いに異なる一対の線図１１；１２の頂点１３同士を繋いで不等辺三角形網を生成する（図２参照）。次に、修正値算出処理手段５が、注目頂点と向かい合う三角形の対辺が線図１１；１２上にあるか否かを判定した後に、注目頂点と向かい合う三角形の対辺があると判定した場合は、例えば、図３に示すように、注目頂点１３ａと向かい合う三角形の対辺１２ａと直交してかつ注目頂点１３ａに到達する垂線１４を引き、垂線１４の長さｘ１（即ち、注目頂点１３ａとその対辺１２ａとを繋ぐ最短の長さ）を修正値ε１として算出する。そして、修正しきい値算出処理手段６が、修正値ε１に例えば係数α＝０．４をかけた修正しきい値εｊ＝ε１×αを算出する。つぎに、しきい値設定処理手段７が、注目頂点１３ａの元しきい値εと修正しきい値εｊとを比較して小さい方を注目頂点１３ａのしきい値Εとして設定し、その設定された注目頂点１３ａのしきい値Εを半径とするしきい値円１５を注目頂点１３ａを中心として設定する。
尚、修正値算出処理手段５は、注目頂点と向かい合う三角形の対辺が線図１１；１２上にないと判定した場合、注目頂点を含む三角形において注目頂点と注目頂点を含まない線図１１；１２上の頂点とを繋ぐ二辺の長さを求め、二辺の長さのうちの短い辺の長さｘ２を修正値ε２として算出し、修正しきい値算出処理手段６は、修正値ε２に例えば係数α＝０．４をかけた修正しきい値εｊ＝ε２×αを算出する。
【００１１】
図４（ａ）に、しきい値設定処理手段７により設定された各頂点のしきい値Εを半径としたしきい値円１５を各頂点毎に設定した状態を示す。
【００１２】
そして、間引き処理手段３が、従来と同じように間引き処理を行う。この間引き処理を図４（ｂ）〜（ｄ）、図５（ａ）；（ｂ）を参照して説明する。尚、線図１１；１２の頂点の間引き処理は同じなので、以下、線図１１の頂点の間引き処理についてのみ説明する。まず、図４（ｂ）に示すように、線図１１において、始点と終点とを繋ぐ直線１６を引き、この直線１６から最も離れた頂点１７を求める。頂点１７のしきい値円１５と直線１６とが交差しないので、この頂点１７は間引かれない（削除されない）。図４（ｃ）に示すように、頂点１７と始点とを直線１９で繋ぎ、この直線１９から最も離れた頂点２０を求める。この頂点２０のしきい値円１５と直線１９とが交差するので、この頂点２０は間引かれる（削除される）。尚、頂点１７と始点との間の各頂点はすべて間引かれる。また、頂点１７と終点とを直線２３で繋ぎ、この直線２３から最も離れた頂点２４を求める。頂点２４のしきい値円１５は従来の元しきい値εによるしきい値円Ｒよりも小さくなっている。従来、図１８に示すように、頂点２４のしきい値円Ｒと直線２３とが交差していたので、この頂点２４は間引かれ、このため、直線２３が残って、この直線２３と線図１２の頂点２５とが交差してしまっていた。一方、本発明では、頂点２４のしきい値円１５と直線２３とが交差しないので、頂点２４が残り、このため、線図１２の頂点２５と線図１１とが交差しない。以下、図４（ｄ）に示すように、頂点２６のしきい値円１５と直線２６ａとが交差しないので、頂点２６が残り、図５（ａ）；（ｂ）に示すように、頂点２７のしきい値円１５と直線２７ａとが交差しないので、従来、間引きされていた頂点２７も残る。即ち、従来、交差してしまっていた頂点２５と線図１１とが交差せず、しかも、地図データの精度も保たれる間引き処理を行える。図６に間引き処理後の線図１１Ａ；１２Ａを示す。図６に示すように、最良の形態１による間引き処理後は、従来のように、線図１１Ａと線図１２Ａとが交差するようなことがなくなる。
【００１３】
最良の形態１によれば、一方の線図上にある注目頂点と他方の線図とが近い場合、その注目頂点のしきい値Εを元しきい値εよりも小さくしたので、その注目頂点が間引かれにくくなり、間引き処理後の一方の線図と他方の線図との交差を防止できる。例えば、道路を示す線図と家を示す線図との交差を防止できる。よって、地図データの精度を保持したまま地図データを圧縮できる。
【００１４】
最良の形態２
互いに異なる一対の線図のうちの一方の線図の頂点と他方の線図の線分との間の最短長さが所定値よりも短い場合に元しきい値εを小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムでもよい。地図の縮尺の違いによってそれぞれ異なる所定値を決めておけば、最良の形態１と同様に、地図データの精度を保持したまま地図データを圧縮できる。
【００１５】
最良の形態３
閉図形のままでは図形の始点と終点とがわからないので間引き処理を行うことができない。そこで、始点と終点とを出すために、閉図形をいくつかの線図に分割した後に、上述したように線図の始点と終点とを線で繋いで線図の間引き処理を開始し、間引き処理が終了した後の線図の終点及び始点を連結して閉図形に戻すことにより、閉図形の間引き処理が行われる。従来、この閉図形の分割処理は、閉図形をｎ個に分割する場合に、閉図形を構成する頂点の数をｎで割った数の頂点で形成されるｎ個の線図に分割する。例えば、１６個の頂点を繋いで形成された閉図形を４つに分割する場合、ある任意の頂点を分割点と決めて、その任意の頂点から一方向に向かって４番目、８番目、１２番目の頂点を分割点と決めることによって、４つの線図に分割する。つまり、４個の頂点を繋いで形成される線図を４つ形成し、１つ１つの線図に対して間引き処理を行い、間引き処理後の４つの線図の終点及び始点を連結して閉図形に戻す。しかしながら、このような分割処理の場合、間引き処理後の閉図形が元の閉図形の形状とかけ離れてしまい、元の閉図形において形状を維持することが必要な部分の形状を維持できない。
【００１６】
最良の形態３では、元の閉図形において形状を維持することが必要な部分の形状を維持できるようにした閉図形の分割処理プログラムについて説明する。図７乃至図９は本発明の最良の形態３を示す。図７は分割処理装置の構成を示し、図８は分割手順を示し、図９は判定要素の説明図である。
【００１７】
閉図形の分割処理装置３０は、判定要素算出処理手段３１、分割点決定処理手段３２を備える。分割処理装置３０は、コンピュータと分割処理プログラムとにより実現される。判定要素算出処理手段３１は、コンピュータと判定要素算出処理プログラムとにより実現される。分割点決定処理手段３２は、コンピュータと分割点決定処理プログラムとにより実現される。
【００１８】
判定要素算出処理プログラムは、閉図形の各頂点毎にその頂点を分割点とするか否かを決定するための判定要素を算出する手段としてコンピュータを機能させるプログラムである。この判定要素算出処理プログラムは、図９に示すように、判定要素を算出する対象となる注目頂点Ｔ１から一方の頂点Ｔ２に繋がれた一方線分Ｌ１と注目頂点Ｔ１から他方の頂点Ｔ３に繋がれた他方線分Ｌ２とのなす角度θを第１判定要素として算出する手段、及び、判定要素を算出する対象となる注目頂点Ｔ１から一方の頂点Ｔ２に繋がれた一方線分Ｌ１の長さl１及び注目頂点Ｔ１から他方の頂点Ｔ３に繋がれた他方線分Ｌ２の長さl２のうち長さの短い方の線分の長さを第２判定要素として算出する手段としてコンピュータを機能させる。分割点決定処理手段３２は、コンピュータと分割点決定処理プログラムとにより実現される。分割点決定処理プログラムは、各頂点毎の判定要素に基づいて分割点を決定する手段としてコンピュータを機能させるプログラムである。この分割点決定処理プログラムは、頂点の第１判定要素としての角度θが９０°に近いほどその頂点を分割点候補として上位にランク付けする手段、頂点の第２判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段、及び、各頂点に関しての第１判定要素のランク及び第２判定要素のランクを総合して総合ランク上位の頂点を分割点として決定する手段としてコンピュータを機能させる。
【００１９】
図８では、分割点を「３」に設定して総合ランク上位３位までの頂点が分割された例を示す。尚、図８（ｂ）の各頂点の傍に付した番号が総合ランクの順番であり、ここでは、図８（ｃ）に示すように、閉図形Ｚの４つの角部にある頂点のうち３つの頂点Ｔｘ；Ｔｙ；Ｔｚが分割点に決定される。分割点とならなかった角部にある総合ランク４位の頂点Ｔｅは、分割点となった角部にある頂点に比べて、総合ランク８位の頂点と繋がれた線分長さが短く、かつ、角度が９０°に遠いため、総合ランクが低くなっている。
【００２０】
図８（ｃ）に示すように、分割された３つの線図Ｙ１；Ｙ２；Ｙ３毎にそれぞれ上述した間引き処理を行う。ここでは、線図は、始点と終点とを繋ぐ直線となるよう間引き処理され、線図もよりＬ字状に近い状態に間引き処理され、これら線図が、分割点となった頂点同士で再び連結されることによって、より長方形に近い閉図形になる。つまり、元の閉図形の形状である長方形状の形状を崩すことなく間引きされた閉図形を得ることができる。よって、間引き処理後に、元の閉図形において形状を維持することが必要な部分の形状を維持した閉図形を得ることができる。
【００２１】
最良の形態４
分割点決定処理プログラムは、各頂点毎の第１判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムであってもよい。つまり、この分割点決定処理プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほどその頂点を分割点候補として上位にランク付けする手段としてコンピュータを機能させる。この分割点決定処理プログラムを用いた場合であっても、例えば、各頂点間の長さに差がないような閉図形を分割する場合に有効である。
【００２２】
最良の形態５
分割点決定処理プログラムは、各頂点毎の第２判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムであってもよい。つまり、この分割点決定処理プログラムは、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段としてコンピュータを機能させる。この分割点決定処理プログラムを用いた場合であっても、例えば、曲線が多くて９０°に近い角部分が少ないような閉図形を分割する場合に有効である。
【００２３】
最良の形態６
図１０乃至図１４は本発明の最良の形態６を示す。図１０は圧縮処理装置の構成を示し、図１１は間引き処理の手順を示し、図１２は間引き後の閉図形を示し、図１３は第１修正係数β１を求める関数式及び関数グラフの一例を示し、図１４は第２修正係数β２を求める関数式及び関数グラフの一例を示す。
【００２４】
最良の形態６による、線図の圧縮処理手段１は、しきい値調整処理手段２、間引き処理手段３を備える。しきい値調整処理手段２は、修正係数算出処理手段３５、しきい値設定処理手段３６を備える。
修正係数算出処理手段３５は、コンピュータと修正係数算出プログラムとにより実現される。修正係数算出プログラムは、注目頂点の元しきい値εに修正係数をかけて算出した修正しきい値を注目頂点のしきい値として設定する手段としてコンピュータを機能させる。更に詳細には、修正係数算出プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど小さく設定された第１修正係数β１と、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さくかつその差が大きいほど大きく設定された第２修正係数β２と、を用いて注目頂点の修正係数βを算出する手段としてコンピュータを機能させる。しきい値設定処理手段３６は、コンピュータとしきい値設定処理プログラムとにより実現される。しきい値設定処理プログラムは、注目頂点の修正係数β×元しきい値εにより求めたしきい値Εを注目頂点のしきい値Εとして設定する手段としてコンピュータを機能させる。
【００２５】
第１修正係数β１や第２修正係数β２は上述した条件に合うように設定すればよい。例えば、第１修正係数β１は、以下に示す関数Ｐ（ｘ）で求める。
ここで、
ｘ：頂点の角度（０度から１８０度）
ａ：傾き係数
ｘ０：角度フィルタ係数（Ｐ（ｘ０）＝０．５となるときの角度）
例えば、第２修正係数β２は、以下に示す関数Ｐ（ｌ´）で求める。
Ｐ（ｌ´）＝１−ｃ×ｌ´
ここで、
ｌ´：正規化辺長、ｌ´＝ｌ／ε（０＜ｌ＜ε、ｌ≧εならば、ｌ´＝ｌ）
ｃ：傾き係数（一般に、１−ｃ＝０．２が標準値）
そして、修正係数βを、√β１×√β２で求める。
【００２６】
図１１（ａ）に、しきい値設定処理手段３６により設定された各頂点のしきい値Εを半径としたしきい値円１５Ａを各頂点毎に設定した状態を示す。
【００２７】
そして、間引き処理手段が、従来と同じように間引き処理を行う。この間引き処理を図１１（ｂ）〜（ｄ）を参照して説明する。尚、この例では、閉図形を例にしているので、間引き処理の前に、上述した分割処理手段で閉図形を分割してから間引き処理を行う。図１１（ｂ）〜（ｄ）では閉図形が頂点Ｔｃ；Ｔｄで分割された後に、分割された頂点同士を繋いだ線図ＸＡと線図ＸＢとで別々に間引き処理を行っている。間引き処理の手法は、最良の形態１と同じである。しきい値設定処理手段８により設定された線図ＸＡの各頂点Ｔ１１；Ｔ１２；Ｔ１３のしきい値Εは、いずれも修正係数βによって小さくなっており、このため、線図ＸＡの間引き処理により、図１１（ｂ）のように、直線Ｍ１と頂点Ｔ１１のしきい値円１５Ａとが交差しないので、頂点Ｔ１１が残り、図１１（ｃ）のように、直線Ｍ２と頂点Ｔ１２のしきい値円１５Ａとが交差しないので、頂点Ｔ１２が残り、図１１（ｄ）のように、直線Ｍ３と頂点Ｔ１３のしきい値円１５Ａとが交差しないので、頂点Ｔ１３が残る。しきい値設定処理手段３６により設定された線図ＸＢの各頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４のしきい値Εは、第２修正係数β２が大きいために大きくなっており、線図ＸＢの間引き処理により、各頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４は間引きされる。図１２に間引き後の線図ＸＡ；ＸＢを連結した閉図形を示す。
【００２８】
最良の形態６の圧縮処理装置１によれば、間引き処理後の閉図形は、各頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４のみが間引きされ、元の閉図形の元の閉図形において形状を維持することが必要な部分の形状を維持できる。よって、最良の形態１と同様に、地図データの精度を保持したまま地図データを圧縮できる。つまり、元の線図において形状を維持することが必要な部分の形状を維持できるとともに、データを圧縮できる。また、第１修正係数β１と第２修正係数β２とを用いて修正係数βを算出しているため、特に図１１に示すような、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近くても、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さい頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４を間引くことができる。つまり、第１修正係数β１を用いただけでは、頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４が残ってしまう場合があるが、第１修正係数β１と第２修正係数β２とを用いることで、形状維持に不要な頂点Ｔ２１；Ｔ２２；Ｔ２３；Ｔ２４を間引くことができる。
【００２９】
最良の形態７
しきい値調整処理プログラムとして、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを用いても良い。このしきい値調整処理プログラムを用いた場合であっても、例えば、各頂点間の長さに差がないような線図を間引き処理する場合に有効である。
【００３０】
最良の形態８
しきい値調整処理プログラムとして、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さと上記しきい値とを比較し、当該線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど上記しきい値を大きくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを用いても良い。このしきい値調整処理プログラムを用いた場合であっても、例えば、曲線が多くて９０°に近い角部分が少ないような線図を間引き処理する場合に有効である。
【００３１】
最良の形態９
最良の形態１；６の圧縮処理手段１と最良の形態３の分割処理手段とを備えた地図データ圧縮処理装置による処理の流れを図１５を参照して説明する。地図データ圧縮処理装置は、圧縮対象となる地図の範囲を指定するコマンドを入力して、その指定された範囲のデータを読み込む（ステップＳ１）。最良の形態１によるしきい値修正処理を行う（ステップＳ２）。最良の形態６によるしきい値修正処理を行う（ステップＳ３）。最良の形態３による分割処理を行う（ステップＳ４）。間引き処理を行う（ステップＳ５）。尚、ステップＳ２〜ステップＳ４までの処理の順序は変わっても良い。
【産業上の利用可能性】
【００３２】
本発明は、地図データ以外の線図の間引き処理、及び、地図データ以外の閉図形の分割処理にも使用できる。
【図面の簡単な説明】
【００３３】
【図１】圧縮処理装置を示すブロック構成図（最良の形態１）。
【図２】不等辺三角形網を示す図（最良の形態１）。
【図３】修正値算出方法の説明図（最良の形態１）。
【図４】間引き処理の手順を示す図（最良の形態１）。
【図５】間引き処理の手順を示す図（最良の形態１）。
【図６】間引き処理後の線図を示す図（最良の形態１）。
【図７】分割処理装置を示すブロック構成図（最良の形態３）。
【図８】分割手順を示す図（最良の形態３）。
【図９】判定要素の説明図（最良の形態３）。
【図１０】圧縮処理装置を示すブロック構成図（最良の形態６）。
【図１１】間引き処理の手順を示す図（最良の形態６）。
【図１２】間引き後の閉図形を示す図（最良の形態６）。
【図１３】第１修正係数β１を求める関数式及び関数グラフの一例を示す図（最良の形態６）。
【図１４】第２修正係数β２を求める関数式及び関数グラフの一例を示す図（最良の形態６）。
【図１５】地図データ圧縮処理装置による処理の流れ図（最良の形態９）。
【図１６】従来の間引き処理の手順を示す図。
【図１７】従来の間引き処理のしきい値の説明図。
【図１８】従来の間引き処理結果を示す図。
【図１９】従来の間引き処理結果を示す図。
【図２０】従来の間引き処理結果を示す図。
【符号の説明】
【００３４】
１ 圧縮処理装置、２ しきい値調整処理手段、３ 間引き処理手段、
４ ＴＩＮ生成処理手段、５ 修正値算出処理手段、６ 修正しきい値算出処理手段、
７ しきい値設定処理手段、３０ 分割処理装置、３１ 判定要素算出処理手段、
３２ 分割点決定処理手段、３５ 修正係数算出処理手段、３６ しきい値設定処理手段。
【特許請求の範囲】
【請求項１】
複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、互いに異なる一対の線図のうちの一方の線図の頂点と他方の線図の線分との間の最短長さが所定値よりも短い場合に上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする線図の圧縮処理プログラム。
【請求項２】
しきい値調整処理プログラムは、互いに異なる一対の線図の頂点同士を繋いで不等辺三角形網を生成する手段としてコンピュータを機能させる不等辺三角形網生成処理プログラムと、注目頂点と向かい合う三角形の対辺が線図上にある場合には注目頂点とその三角形の対辺との最短長さを修正値として求め、注目頂点と向かい合う三角形の対辺が線図上にない場合には注目頂点を含む三角形において注目頂点と注目頂点を含まない線図上の頂点とを繋ぐ二辺のうち長さの短い辺の長さを修正値として求める手段としてコンピュータを機能させる修正値計算処理プログラムと、上記修正値に０．５以下の係数をかけた修正しきい値を算出する手段としてコンピュータを機能させる修正しきい値算出処理プログラムと、注目頂点の上記しきい値と修正しきい値とを比較して小さい方を注目頂点のしきい値として設定する手段としてコンピュータを機能させるしきい値設定処理プログラムとを備えたことを特徴とする請求項１に記載の線図の圧縮処理プログラム。
【請求項３】
複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする線図の圧縮処理プログラム。
【請求項４】
複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さと上記しきい値とを比較し、当該線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど上記しきい値を大きくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする線図の圧縮処理プログラム。
【請求項５】
複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、注目頂点の上記しきい値に修正係数をかけて算出した修正しきい値を注目頂点のしきい値として設定する手段としてコンピュータを機能させるしきい値調整処理プログラムを備え、しきい値調整処理プログラムは、修正係数算出プログラムを備え、修正係数算出プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど小さく設定された第１修正係数と、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど大きく設定された第２正係数と、を用いて注目頂点の上記修正係数を算出する手段としてコンピュータを機能させることを特徴とする線図の圧縮処理プログラム。
【請求項６】
複数の頂点を繋いで生成された閉図形を複数の線図に分割する手段としてコンピュータを機能させる閉図形の分割処理プログラムにおいて、閉図形の各頂点毎にその頂点を分割点とするか否かを決定するための判定要素を算出する手段としてコンピュータを機能させる判定要素算出処理プログラムと、各頂点毎の判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムとを備えたことを特徴とする閉図形の分割処理プログラム。
【請求項７】
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させることを特徴とする請求項６に記載の閉図形の分割処理プログラム。
【請求項８】
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させることを特徴とする請求項６に記載の閉図形の分割処理プログラム。
【請求項９】
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段、及び、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の第１判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けする手段、頂点の第２判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段、及び、各頂点に関しての第１判定要素のランク及び第２判定要素のランクを総合して総合ランク上位の頂点を分割点として決定する手段としてコンピュータを機能させることを特徴とする請求項６に記載の閉図形の分割処理プログラム。
【請求項１】
複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、互いに異なる一対の線図のうちの一方の線図の頂点と他方の線図の線分との間の最短長さが所定値よりも短い場合に上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする線図の圧縮処理プログラム。
【請求項２】
しきい値調整処理プログラムは、互いに異なる一対の線図の頂点同士を繋いで不等辺三角形網を生成する手段としてコンピュータを機能させる不等辺三角形網生成処理プログラムと、注目頂点と向かい合う三角形の対辺が線図上にある場合には注目頂点とその三角形の対辺との最短長さを修正値として求め、注目頂点と向かい合う三角形の対辺が線図上にない場合には注目頂点を含む三角形において注目頂点と注目頂点を含まない線図上の頂点とを繋ぐ二辺のうち長さの短い辺の長さを修正値として求める手段としてコンピュータを機能させる修正値計算処理プログラムと、上記修正値に０．５以下の係数をかけた修正しきい値を算出する手段としてコンピュータを機能させる修正しきい値算出処理プログラムと、注目頂点の上記しきい値と修正しきい値とを比較して小さい方を注目頂点のしきい値として設定する手段としてコンピュータを機能させるしきい値設定処理プログラムとを備えたことを特徴とする請求項１に記載の線図の圧縮処理プログラム。
【請求項３】
複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど上記しきい値を小さくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする線図の圧縮処理プログラム。
【請求項４】
複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さと上記しきい値とを比較し、当該線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど上記しきい値を大きくするよう修正する手段としてコンピュータを機能させるしきい値調整処理プログラムを備えたことを特徴とする線図の圧縮処理プログラム。
【請求項５】
複数の頂点を繋いで生成された線図の頂点を間引いてデータ量を圧縮するに際し、線図の各頂点に頂点からの一定距離であるしきい値を設定し、間引き可能か否かの判定対象とする注目頂点の両側に位置する頂点同士を繋いだ線と注目頂点との間の最短長さがしきい値よりも小さい場合にその注目頂点を間引く手段としてコンピュータを機能させる線図の圧縮処理プログラムにおいて、注目頂点の上記しきい値に修正係数をかけて算出した修正しきい値を注目頂点のしきい値として設定する手段としてコンピュータを機能させるしきい値調整処理プログラムを備え、しきい値調整処理プログラムは、修正係数算出プログラムを備え、修正係数算出プログラムは、注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度が９０°に近いほど小さく設定された第１修正係数と、注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さが上記しきい値よりも小さくかつ当該線分の長さと上記しきい値との差が大きいほど大きく設定された第２正係数と、を用いて注目頂点の上記修正係数を算出する手段としてコンピュータを機能させることを特徴とする線図の圧縮処理プログラム。
【請求項６】
複数の頂点を繋いで生成された閉図形を複数の線図に分割する手段としてコンピュータを機能させる閉図形の分割処理プログラムにおいて、閉図形の各頂点毎にその頂点を分割点とするか否かを決定するための判定要素を算出する手段としてコンピュータを機能させる判定要素算出処理プログラムと、各頂点毎の判定要素に基づいて分割点を決定する手段としてコンピュータを機能させる分割点決定処理プログラムとを備えたことを特徴とする閉図形の分割処理プログラム。
【請求項７】
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させることを特徴とする請求項６に記載の閉図形の分割処理プログラム。
【請求項８】
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けして、上位にランク付けされた頂点を分割点として決定する手段としてコンピュータを機能させることを特徴とする請求項６に記載の閉図形の分割処理プログラム。
【請求項９】
判定要素算出処理プログラムは、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分と注目頂点から他方の頂点に繋がれた他方線分とのなす角度を判定要素として算出する手段、及び、判定要素を算出する対象となる注目頂点から一方の頂点に繋がれた一方線分及び注目頂点から他方の頂点に繋がれた他方線分のうち長さの短い方の線分の長さを判定要素として算出する手段としてコンピュータを機能させ、分割点決定処理プログラムは、頂点の第１判定要素としての角度が９０°に近いほどその頂点を分割点候補として上位にランク付けする手段、頂点の第２判定要素としての長さが長いほどその注目頂点を分割点候補として上位にランク付けする手段、及び、各頂点に関しての第１判定要素のランク及び第２判定要素のランクを総合して総合ランク上位の頂点を分割点として決定する手段としてコンピュータを機能させることを特徴とする請求項６に記載の閉図形の分割処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２００８−２９９５０６（Ｐ２００８−２９９５０６Ａ）
【公開日】平成２０年１２月１１日（２００８．１２．１１）
【国際特許分類】
【出願番号】特願２００７−１４３６１５（Ｐ２００７−１４３６１５）
【出願日】平成１９年５月３０日（２００７．５．３０）
【出願人】（５９１０７４１６１）アジア航測株式会社 (48)
【Ｆターム（参考）】
【公開日】平成２０年１２月１１日（２００８．１２．１１）
【国際特許分類】
【出願日】平成１９年５月３０日（２００７．５．３０）
【出願人】（５９１０７４１６１）アジア航測株式会社 (48)
【Ｆターム（参考）】
[ Back to top ]