"入力された領域データの2次元領域の重複を判定するための領域情報重複判定演算装置であって、前記入力された領域データのメッシュIDの集合の各メッシュIDの組をシンボルの組合せに変換し、記憶手段に格納するZDD変換処理手段と、前記領域データに対する演算命令を前記記憶手段に格納されている前記シンボルの組合せに適用して実行する領域演算処理手段と、前記領域演算処理手段の実行結果を前記入力された領域データと同様の形式に変換して出力する出力手段と、を有することを特徴とする領域情報重複判定演算装置。入力された領域データの2次元領域の重複を判定するための装置における領域情報重複判定演算方法であって、ZDD変換処理手段が、前記入力された領域データのメッシュIDの集合の各メッシュIDの組をシンボルの組合せに変換し、記憶手段に格納するZDD変換処理ステップと、領域演算処理手段が、前記領域データに対する演算命令を前記記憶手段に格納されている前記シンボルの組合せに適用して実行する領域演算処理ステップと、出力手段が、前記領域演算処理手段の実行結果を前記入力された領域データと同様の形式に変換して出力する出力ステップと、を行うことを特徴とする領域情報重複判定演算方法。コンピュータを、請求項1に記載の領域情報重複判定演算装置の各手段として機能させるための領域情報重複判定演算プログラム。しかしながら、上記の従来の技術は、メッシュによる表現方法は近似的なものであり、一つ一つのメッシュのサイズを大きくとると、近似誤差が大きくなるという問題があった。一方、メッシュを小さくとると、ある領域を表すために必要なメッシュの個数が増大し、それに伴って計算回数及び記憶容量が膨大になるという問題があった。本発明は、上記の点に鑑みなされたもので、2次元領域を表すメッシュデータを保持するメモリ量を削減し、かつ、領域に対する演算を高速に実行することが可能な重複判定演算装置及び方法及びプログラムを提供することを目的とする。上記の課題を解決するため、本発明は、入力された領域データの2次元領域の重複を判定するための領域情報重複判定演算装置であって、前記入力された領域データのメッシュIDの集合の各メッシュIDの組をシンボルの組合せに変換し、記憶手段に格納するZDD変換処理手段と、前記領域データに対する演算命令を前記記憶手段に格納されている前記シンボルの組合せに適用して実行する領域演算処理手段と、前記領域演算処理手段の実行結果を前記入力された領域データと同様の形式に変換して出力する出力手段と、を有する。本発明は、ゼロサプレス型二分決定グラフと呼ばれるデータ構造を用いて領域を表現する。ZDDは組み合わせ集合を効率的に保持することが可能なデータ構造であり、メッシュの集合を既存手法よりもより少ないメモリ量で保持することができる。さらに、領域に対する集合演算を、メッシュの集合を表現するZDD間での集合演算によって効率的に実行できるため、演算に必要な計算量も削減することができる。これにより、2次元領域を表すメッシュデータを省メモリで保持し、かつ領域に対する演算が高速に実行できるという効果が得られる。以下図面と共に、本発明の実施の形態を説明する。図2は、本発明の一実施の形態における重複判定演算装置の構成を示す。重複判定演算装置は、領域データ入力部1、ZDDゼロサプレス型二分決定グラフ変換処理部2、ZDD記憶部3、演算入力部4、領域演算処理部5、演算結果出力部6から構成される。領域データ入力部1は、外部から入力データを受け取り、ZDD変換処理部2へと渡す。ZDD変換処理部2では、領域データ入力部1からデータを受け取り、それをZDDに変換して、ZDD記憶部3に記録する。ZDD記憶部3には、ZDD変換処理部2によって変換されたZDDが記録される。記録したデータは領域演算処理部5で処理される。演算入力部4には、領域データ入力部1から与えられる領域データに対する演算命令を入力する。演算命令の一覧を図3に示す。入力される演算は、図3の演算もしくはその組み合わせとなっている。入力された演算命令は領域演算処理部5に渡される。領域演算処理部5では、演算入力部4から受け取った演算命令を、ZDD記憶部3に格納されているZDDに対して実行し、その結果を演算結果出力部6に出力、もしくはZDD記憶部3に格納する。演算結果出力部6では、領域演算処理部5から受け取ったZDDデータを、入力データと同様の形式に変換して出力する。次に、ZDDについて説明する。ZDDは、組み合わせ集合を2分グラフの形で保持するデータ構造である。ここで、組み合わせ集合とは、あるアイテムの集合Aa1,a2,...,に対して、e⊆Aであるようなeを要素とする集合のことである。例えば、集合Ba,b,cに対し、集合ac,b,cはBの組み合わせ集合である。ZDDによって組み合わせ集合を表した例を図4に示す。ZDDは指向性をもったグラフ構造であり、ノードは0または1のラベルをもった終端ノードと、各ノードが対応するアイテムのラベルをもった中間ノードとの2種類がある。各中間ノードは0枝、1枝と呼ばれる2つの子ノードを指すリンクを持つ。また、ひとつのZDDには先頭のノードを表すポインタがある。図4は組み合わせ集合{ac,b,c}を表すZDDである。図中では、終端ノードは四角のノード、中間ノードは丸いノード、1枝は実線の矢印、0枝は点線の矢印、先頭ノードを表すポインタは実線の矢印でそれぞれ表現される。各ノード中の文字は、ノードのラベルを表す。ある組み合わせeが、ZDDが表す組み合わせ集合に含まれるかどうかは、以下の手続きによって知ることができる。まず、ZDDの先頭ノードを表すポインタに沿って、先頭ノードに遷移する。そこで、先頭ノードのラベルが表すアイテムがeに含まれているなら1枝が指すノードに遷移し、そうでないなら0枝が指すノードに遷移する。以上の手続きを最終的に終端ノードにたどり着くまで実行し、最終的にラベル1をもつ終端ノードに遷移し、かつeに含まれるすべてのアイテムに対応するノードを遷移してきているなら、eは組み合わせ集合に含まれる。そうでないならeは組み合わせ集合に含まれない。図4のZDDは、計算機上では、図4のように、ノードIDをインデックスとする配列として表現される。配列の一つの要素には、ノードのラベル、0枝の指すノードID、1枝の先のノードIDが格納されている。ある組み合わせ集合をZDDとして表すときには、アイテム間に予め順序を定められており、ZDD中ではあるノードのラベルであるアイテムとその子ノードのラベルであるアイテムとを比較したときに、必ず子ノードのアイテムの方が、順序が後になるという制約がある。図4のZDDでは、アイテムa,b,cの間にa,b,cの順で順序が定められているものとする。次に、処理の流れを説明する。図5は、本発明の一実施の形態における処理のフローチャートである。ステップ1まず、領域データを領域データ入力部1より入力する。入力として受け取るデータは、2次元平面での領域情報をメッシュ化したものである。図6は入力データの例で、図7は図6の入力データをメッシュ化したときの概念図である。図7の図形は、図7において灰色で塗りつぶされているメッシュの集合として表される。メッシュの集合は、図8のように、メッシュを一意に識別できるIDの集合として表される。図8では、メッシュの縦方向の位置と横方向の位置の組によって、一意なIDとなっている。領域データ入力部1では、図8の形式で領域データを受け取る。なお、メッシュ化するときの縦横のメッシュの個数は予め決まっているものとする。以下では横のメッシュの個数をN、縦のメッシュの個数をMとする。ステップ2受け取った領域データをZDD変換処理部2でZDDに変換する。この処理を図9の詳細フローを用いて説明する。ステップ11まず、メッシュIDの集合を受け取る。各メッシュIDは、横方向の番号i0≦i≦N-1と、縦方向の番号jとの組i,jによって表される。ステップ12次に、メッシュIDの集合に含まれている各メッシュIDの組を、それぞれシンボルの組み合わせに変換する。いま、NとMのそれぞれが、2の階乗、つまり正の整数p,qに対して、N=2p、M=2q、であるとする。この条件のもとで、i,jをそれぞれp桁、q桁の2進数として表し、それを連結したpq個の0または1の列をつくる。例えばN=4,M=4だったとすると、i=2,j=3のときは、それぞれ10,11となり、長さ4の0または1の列1011として表現される。こうして得られた長さpqの列を、pq個のシンボル{s1,s2,...,spq}の組み合わせによって表現する。具体的には、列のうち、k番目の値が1ならばskを含む、そうでないなら含まないとして、シンボルの集合を作る。列が1011であったら、対応するシンボル集合は{s1,s3,s4}となる。図10は、図8のメッシュIDの集合からシンボルの組み合わせの集合を得る例を示している。図中の灰色の各メッシュについて、メッシュの外枠の0または1に基づいてシンボル{a,b,c,d}の組み合わせが対応付けられている。最終的に得られる組み合わせ集合を図11に示す。なお、組合せ集合には、いずれのシンボルも含まない組合せが要素として含まれてもよい。そのような組合せをφとして表す。図10では左上のメッシュが含まれた場合、組合せ集合の要素としてφが含まれることになる。ステップ13組み合わせ集合が得られたら、それをZDDに変換する。組み合わせ集合からZDDを得るには、文献1ShinichiMinatoZeroSuppressedBDDsforSetManipulationinCombinatorialProblemsDAC93pp272277に記されているZDDの演算を適切な順序で実行すればよい。図11の組み合わせ集合については、図12のようなZDDと、そのテーブルでの表現が得られる。ここで、シンボルa,b,c,dには、順序a<b<c<dが成り立つとしている。順序は任意であり、変数順序によってZDDの性質が変化することはない。構成されたZDDのノード数は10個であり、もとのメッシュの総数よりも少なくなっている。これは、ZDDとして表現することでメッシュ集合を圧縮して表現できることを示している。構成されたZDDをZDD記憶部3に記憶し、処理を終了する。入力された各領域データは、すべてZDDとしてZDD記憶部3に蓄積される。ステップ3演算入力部4から演算命令を受け取る。演算命令は図3に示す演算のいずれかであるとする。ステップ4次に、領域演算処理部5にて、ZDD記憶部3のZDDに対して演算を実行する。各演算は、ZDDに対する典型的な演算であり、その詳細は上記の文献1に記載がある。図13は、例として2つのZDDの差集合を求めた例である。なお、ZDD同士の演算では、その出力もZDDとなる。ZDD同士の演算は、ZDDの節点数に比例する計算回数で効率的に実行することが可能であるため、メッシュ集合をコンパクトに表現することができたならば、効率的に集合演算を実行することが可能である。ステップ5領域演算処理部5は、演算の結果得られたZDDを、再度メッシュIDの集合の形に変更して、演算結果出力部6より出力する。ZDDからメッシュIDの集合を得るには、文献2RandalEBryantGraphBasedAlgorithmsforBooleanFunctionManipulationIEEETransactionsonComputersC356776911986にあるZDDから組み合わせ集合を得る手順によって得られたシンボル列を2進数として解釈し、メッシュIDの組に再度置き換えればよい。上記のように、領域データ地図をメッシュとして、縦横の位置を2進数で表現してシンボルに対応させ、地図領域をメッシュの集合で表現し、ZDD変換し、ZDDに対する演算処理を行うことで、高速に2次元領域の重複判定を行うことが可能となる。上記の図2に示す重複判定演算装置の各構成要素の動作をプログラムとして構築し、重複判定演算装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更応用が可能である。"