(57)【要約】【課題】  超平面アレンジメントという概念を使い、従来のアルゴリズムより格段に速く、任意の次元の空間物まで取り扱うことを可能にする。【解決手段】  空間物データに基づいて空間物の境界を構成する全ての凸な要素についてそれぞれ超平面を形成し、この超平面集合を超平面集合記憶手段に記憶し（Ｓ１２１）、超平面集合記憶手段から超平面集合を取り出し、これを用いて多次元空間を分割することにより超平面アレンジメントを構築し、各フェイスの集合を超平面アレンジメントフェイス集合記憶手段に記憶し（Ｓ１２２）、超平面アレンジメントフェイス集合記憶手段に記憶された超平面アレンジメントフェイスの集合の中から空間物の部分にある超平面アレンジメントフェイスを探し出し、この探し出した超平面アレンジメントフェイスの集合を超平面アレンジメントフェイス複体として超平面アレンジメントフェイス複体記憶手段に記憶する（Ｓ１２３）。【選択図】        図１２
2005038204.tif 000002
【特許請求の範囲】
【請求項１】
多次元空間内に存在する空間物をモデル化した空間物データの処理方法であって、
前記空間物データに基づいて前記空間物の境界を構成する全ての凸な要素についてそれぞれ超平面を形成し、この形成された超平面の集合を超平面集合記憶手段に記憶する超平面集合形成ステップ、
前記超平面集合記憶手段から超平面集合を取り出し、この超平面集合を用いて前記多次元空間を分割することにより超平面アレンジメントを構築し、この超平面アレンジメントの各フェイスの集合を超平面アレンジメントフェイス集合記憶手段に記憶する超平面アレンジメントフェイス集合形成ステップ、
前記超平面アレンジメントフェイス集合記憶手段に記憶された超平面アレンジメントフェイスの集合の中から前記空間物の部分にある超平面アレンジメントフェイスを探し出し、この探し出した超平面アレンジメントフェイスの集合を超平面アレンジメントフェイス複体として超平面アレンジメントフェイス複体記憶手段に記憶する超平面アレンジメントフェイス複体形成ステップ
を含む空間物データの処理方法。
【請求項２】
前記超平面集合形成ステップは、前記凸な要素を１つ取り出し、この取り出した凸な要素の次元ｋが前記多次元空間の次元をｄとしたときにｄ−１である場合は、この要素を含む超平面を前記超平面の集合に加え、そうでない場合は、この要素を含む超平面を前記超平面の集合にｄ−ｋ個加え、さらに、前記凸な要素の端が他の凸な要素に含まれない場合は、この凸な要素の端を含む超平面を前記超平面の集合に加える処理を、前記空間物の境界を構成する全ての凸な要素について行うものである請求項１記載の空間物データの処理方法。
【請求項３】
前記超平面アレンジメントフェイス複体形成ステップは、前記超平面アレンジメントフェイスの集合の中から超平面アレンジメントフェイスを１つ取り出し、この取り出した超平面アレンジメントフェイスが前記空間物の外でない場合は前記空間物の部分にある超平面アレンジメントフェイスであると判断する処理を、前記超平面アレンジメントフェイスの集合に含まれる全ての超平面アレンジメントフェイスについて行うものである請求項１または２に記載の空間物データの処理方法。
【請求項４】
請求項１から３のいずれかに記載の空間物データの処理方法により超平面アレンジメントフェイス複体記憶手段に記憶した複数の超平面アレンジメントフェイス複体に基づく空間物データの処理方法であって、
前記超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2との積を構成する空間物に対する新たな超平面アレンジメントフェイス複体Γintersectionを前記超平面集合形成ステップ、超平面アレンジメントフェイス集合形成ステップおよび超平面アレンジメントフェイス複体形成ステップにより求める空間物データの処理方法。
【請求項５】
請求項１から３のいずれかに記載の空間物データの処理方法により超平面アレンジメントフェイス複体記憶手段に記憶した複数の超平面アレンジメントフェイス複体に基づく空間物データの処理方法であって、
前記超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2との差を構成する空間物に対する新たな超平面アレンジメントフェイス複体Γdifferenceを前記超平面集合形成ステップ、超平面アレンジメントフェイス集合形成ステップおよび超平面アレンジメントフェイス複体形成ステップにより求める空間物データの処理方法。
【請求項６】
請求項１から３のいずれかに記載の空間物データの処理方法により超平面アレンジメントフェイス複体記憶手段に記憶した複数の超平面アレンジメントフェイス複体に基づく空間物データの処理方法であって、
前記超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2との和を構成する空間物に対する新たな超平面アレンジメントフェイス複体Γunionを前記超平面集合形成ステップ、超平面アレンジメントフェイス集合形成ステップおよび超平面アレンジメントフェイス複体形成ステップにより求める空間物データの処理方法。
【請求項７】
前記超平面アレンジメントフェイス複体Γintersectionが空でない場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2が交差すると判定する交差判定ステップを含む請求項４記載の空間物データの処理方法。
【請求項８】
前記超平面アレンジメントフェイス複体Γintersectionが空である場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2が離れていると判定する離れ判定ステップを含む請求項４記載の空間物データの処理方法。
【請求項９】
前記超平面アレンジメントフェイス複体Γdifferenceが空である場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2の一方が他方に含まれると判定する含み判定ステップを含む請求項５記載の空間物データの処理方法。
【請求項１０】
請求項１から３のいずれかに記載の空間物データの処理方法により超平面アレンジメントフェイス複体記憶手段に記憶した複数の超平面アレンジメントフェイス複体に基づく空間物データの処理方法であって、
前記超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2とが一致した場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2は等しいと判定する同一判定ステップを含む空間物データの処理方法。
【請求項１１】
前記超平面アレンジメントフェイス複体Γintersectionが超平面アレンジメントフェイス複体Γ1，Γ2の一方の境界に含まれる場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2の一方が他方に接すると判定する接し判定ステップを含む請求項４記載の空間物データの処理方法。
【請求項１２】
多次元空間内に存在する空間物をモデル化した空間物データをコンピュータにより処理するためのプログラムであって、
前記コンピュータに、
前記空間物データに基づいて前記空間物の境界を構成する全ての凸な要素についてそれぞれ超平面を形成し、この形成された超平面の集合を超平面集合記憶手段に記憶する超平面集合形成ステップ、
前記超平面集合記憶手段から超平面集合を取り出し、この超平面集合を用いて前記多次元空間を分割することにより超平面アレンジメントを構築し、この超平面アレンジメントの各フェイスの集合を超平面アレンジメントフェイス集合記憶手段に記憶する超平面アレンジメントフェイス集合形成ステップ、
前記超平面アレンジメントフェイス集合記憶手段に記憶された超平面アレンジメントフェイスの集合の中から前記空間物の部分にある超平面アレンジメントフェイスを探し出し、この探し出した超平面アレンジメントフェイスの集合を超平面アレンジメントフェイス複体として超平面アレンジメントフェイス複体記憶手段に記憶する超平面アレンジメントフェイス複体形成ステップ
を実行させるための空間物データ処理プログラム。
【請求項１３】
前記超平面集合形成ステップは、前記凸な要素を１つ取り出し、この取り出した凸な要素の次元ｋが前記多次元空間の次元をｄとしたときにｄ−１である場合は、この要素を含む超平面を前記超平面の集合に加え、そうでない場合は、この要素を含む超平面を前記超平面の集合にｄ−ｋ個加え、さらに、前記凸な要素の端が他の凸な要素に含まれない場合は、この凸な要素の端を含む超平面を前記超平面の集合に加える処理を、前記空間物の境界を構成する全ての凸な要素について行うものである請求項１２記載の空間物データ処理プログラム。
【請求項１４】
前記超平面アレンジメントフェイス複体形成ステップは、前記超平面アレンジメントフェイスの集合の中から超平面アレンジメントフェイスを１つ取り出し、この取り出した超平面アレンジメントフェイスが前記空間物の外でない場合は前記空間物の部分にある超平面アレンジメントフェイスであると判断する処理を、前記超平面アレンジメントフェイスの集合に含まれる全ての超平面アレンジメントフェイスについて行うものである請求項１２または１３に記載の空間物データ処理プログラム。
【請求項１５】
請求項１２から１４のいずれかに記載の空間物データ処理プログラムを実行したコンピュータにより超平面アレンジメントフェイス複体記憶手段に記憶した複数の超平面アレンジメントフェイス複体に基づいて空間物データを処理するためのプログラムであって、
前記超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2との積を構成する空間物に対する新たな超平面アレンジメントフェイス複体Γintersectionを前記超平面集合形成ステップ、超平面アレンジメントフェイス集合形成ステップおよび超平面アレンジメントフェイス複体形成ステップにより求める空間物データ処理プログラム。
【請求項１６】
請求項１２から１４のいずれかに記載の空間物データ処理プログラムを実行したコンピュータにより超平面アレンジメントフェイス複体記憶手段に記憶した複数の超平面アレンジメントフェイス複体に基づいて空間物データを処理するためのプログラムであって、
前記超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2との差を構成する空間物に対する新たな超平面アレンジメントフェイス複体Γdifferenceを前記超平面集合形成ステップ、超平面アレンジメントフェイス集合形成ステップおよび超平面アレンジメントフェイス複体形成ステップにより求める空間物データ処理プログラム。
【請求項１７】
請求項１２から１４のいずれかに記載の空間物データ処理プログラムを実行したコンピュータにより超平面アレンジメントフェイス複体記憶手段に記憶した複数の超平面アレンジメントフェイス複体に基づいて空間物データを処理するためのプログラムであって、
前記超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2との和を構成する空間物に対する新たな超平面アレンジメントフェイス複体Γunionを前記超平面集合形成ステップ、超平面アレンジメントフェイス集合形成ステップおよび超平面アレンジメントフェイス複体形成ステップにより求める空間物データ処理プログラム。
【請求項１８】
前記超平面アレンジメントフェイス複体Γintersectionが空でない場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2が交差すると判定する交差判定ステップを含む請求項１５記載の空間物データ処理プログラム。
【請求項１９】
前記超平面アレンジメントフェイス複体Γintersectionが空である場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2が離れていると判定する離れ判定ステップを含む請求項１５記載の空間物データ処理プログラム。
【請求項２０】
前記超平面アレンジメントフェイス複体Γdifferenceが空である場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2の一方が他方に含まれると判定する含み判定ステップを含む請求項１６記載の空間物データの処理方法。
【請求項２１】
請求項１２から１４のいずれかに記載の空間物データ処理プログラムを実行したコンピュータにより超平面アレンジメントフェイス複体記憶手段に記憶した複数の超平面アレンジメントフェイス複体に基づいて空間物データを処理するためのプログラムであって、
前記超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2とが一致した場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2は等しいと判定する同一判定ステップを含む空間物データ処理プログラム。
【請求項２２】
前記超平面アレンジメントフェイス複体Γintersectionが超平面アレンジメントフェイス複体Γ1，Γ2の一方の境界に含まれる場合に、前記超平面アレンジメントフェイス複体Γ1，Γ2の一方が他方に接すると判定する接し判定ステップを含む請求項１５記載の空間物データ処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多次元空間内に存在する空間物をモデル化した空間物データの処理方法および空間物データ処理プログラムに関する。
【背景技術】
【０００２】
行政（上下水道や土地台帳などの管理、都市計画、防災）、ビジネス（マーケティング、出店計画、集配送管理、不動産管理など）、自然科学（考古学、生物学、環境学、気象学）などのアプリケーションを持つ空間データベースの重要性は高い。空間データベースでは、例えば多角形や立体などの広がりを持った空間物を含む種々の次元の空間物データを取り扱う。
【０００３】
時間的変化を伴う空間物を取り扱う時空間モデルに関しては種々の提案がなされている。種々の次元（２次元またはそれ以上）の多次元空間内に存在する空間物をデータベース化するための時空間モデルに関する技術には、次のようなものがある。
【０００４】
（１）点（point）、線分（line）、２次元の領域（region）などの基礎となるデータを組み上げて、図形を表現する方法（例えば、非特許文献１，２参照。）。この場合、表現対象となる図形の次元や図形が配置される空間の次元によって、表現の仕方が全く変わる。したがって、データの処理方法も変わる。つまり、表現対象となる図形の次元や図形が配置される空間の次元に特化した表現法である。
【０００５】
（２）制約データベースの考え方を導入し、個々の図形を制約式（１次の連立方程式／不等式）の和として表現する方法。これは次元に汎用性のある表現法である。実装された例としては、非特許文献３に記載のＤＮＦ（Disjunctive Normal Form）モデル、ＣＨＮＦ（Convex with Holes Normal Form）モデルがある（例えば、非特許文献３参照。）。
【０００６】
（３）計算幾何学の分野では、凸胞復体という概念（例えば、非特許文献４参照。）を使って、時空間情報を扱うことの有効性が謳われている。これは、個々の図形を、１個の凸胞複体として表現するものである。これも次元に汎用性のある表現法である。しかし、凸胞復体という概念を使って実際に時空間情報データベースを構成したとの報告はない。
【０００７】
また、時空間情報を超平面アレンジメントという概念を使って取り扱うことの有効性が謳われている（例えば、非特許文献５参照。）。従来、超平面アレンジメントの重要性が認識されながらも、実際には利用されていない。その理由は性能にある。
【０００８】
超平面アレンジメントを用いて実際の問題を解く場合、幾何アルゴリズムの実行時間は、超平面アレンジメントの区画の数（アレンジメントの複雑さ）に応じて増加する。アレンジメントの複雑さは、Ｏ（ｎd）（ｎは超平面数、ｄは次元数）で見積もられる（例えば、非特許文献６参照。）。したがって、現実的には、幾何アルゴリズムの実行時間は許容範囲外であるとされている（非特許文献５参照。）。
【０００９】
ところで、データベースでの検索は、selection（選択）、projection（射影）、join（結合）などの演算子による代数学的アプローチによって行われるのが一般的である（このアイデアは、オラクル（登録商標）等の商用関係データベースシステム等において広く普及している）。一方、図形に対する演算子は、図形同士の幾何オペレーション（union（和）、difference（差）、intersection（積）、intersect（交差）、contain（包含）など）のことである（例えば、非特許文献２参照。）。
【００１０】
【非特許文献１】ルカ・フォルリッチ（Luca Forlizzi）、ラルフ・ハルムート・ギューティング（Ralf Hartmut Guting）、エンリコ・ナルデッリ（Enrico Nardelli）、マーカス・シュナイダ（Markus Schneider）著，“ア・データ・モデル・アンド・データ・ストラクチャーズ・フォー・ムービング・オブジェクツ・データベース（A Data Model and Data Structures for Moving Objects Database）”，エイシーエム・シグモド（ACM SIGMOD），（米国），２０００年
【非特許文献２】アグネス・ヴォイサード（Agnes Voisard）、ベノイト・デーヴィッド（Benoit David）著，“ア・データベース・パースペクティヴ・オン・ジオスペーシャル・データ・モデリング（A Database Perspective on Geospatial Data Modeling）”，アイトリプルイー・トランザクションズ・オン・ナリッジ・アンド・データ・エンジニアリング（IEEE Transactions on Knowledge and Data Engineering），（米国），２００２年，第１４巻，第２号，ｐ．２２６−２４３
【非特許文献３】シュテファン・グルンバッハ（Stephane Grumbach）、フィリップ・リゴー（Philippe Rigaux）、ルーク・セゴウフィン（Luc Segoufin）著，“ザ・ディデイル・システム・フォー・コンプレックス・スペーシャル・クエリーズ（The DEDALE System for Complex Spatial Queries）”，プロシーディングズ・オブ・エイシーエム・シグモド（Proceedings of ACM SIGMOD），（米国），１９９８年，ｐ．２１３−２２４
【非特許文献４】ジェイコブ・イー・グッドマン（Jacob E. Goodman）、ジョセフ・オラルク（Joseph O'Rourke）編，“ハンドブック・オブ・ディスクリート・アンド・コンピューテーショナル・ジオミトリ（Handbook of discrete and computational geometry）”，（米国），シーアールシー・プレス（CRC Press），１９９７年
【非特許文献５】デヴィット・ピー・ドブキン（David P. Dobkin）、エイレット・タル（Ayellet Tal）著，“エフィシエント・アンド・スモール・リプレゼンテーション・オブ・ライン・アレンジメンツ・ウィズ・アプリケーションズ（Efficient and Small Representation of Line Arrangements with Applications）”，エイシーエム・シンポジウム・オン・コンピューテーショナル・ジオミトリ（ACM Symposium on Computational Geometry），（米国），２００１年６月，ｐ．２９３−３０１
【非特許文献６】ハーバート・エデルスブランナー（Herbert Edelsbrunner）著，“アルゴリズムス・イン・コンバイナトリアル・ジオミトリ（Algorithms in Combinatorial Geometry）”，（米国），シュプリンガー・フェアラーク（Springer-Verlag），１９８７年
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上記のように、従来、幾何オペレーションの実装例は、次元に特化しないアルゴリズム（線形計画法(linear programming）、整数計画法）と、次元に特化したアルゴリズムとがある。例えば、非特許文献３では、図形を線形不等式から構成される制約式で表現し、ハーフスペース・インターセクション（Half-space intersection）法を用いて解く方式をとっているが、これは幾何計算のアルゴリズムであり、２次元の図形に特化したアルゴリズムである。つまり、この方式では、３次元の図形や、２次元の図形の動きを扱うことができない。
【００１２】
一方、線形計画法、整数計画法による方法は、図形の交差判定を行うことができるのみで、その他のオペレーション（和、差、積や「接するかどうか」の判定）はできない。
【００１３】
また、現在まで、超平面アレンジメントを使って、実際に時空間情報データベースを実装したとの報告はなされていない。
【００１４】
そこで、本発明においては、超平面アレンジメントという概念を使いながら、従来のアルゴリズムより格段に速く、また、任意の次元の空間物まで取り扱うことが可能な空間物データの処理方法および空間物データ処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明の空間物データの処理方法は、多次元空間内に存在する空間物をモデル化した空間物データの処理方法であって、空間物データに基づいて空間物の境界を構成する全ての凸な要素についてそれぞれ超平面を形成し、この形成された超平面の集合を超平面集合記憶手段に記憶する超平面集合形成ステップ、超平面集合記憶手段から超平面集合を取り出し、この超平面集合を用いて多次元空間を分割することにより超平面アレンジメントを構築し、この超平面アレンジメントの各フェイスの集合を超平面アレンジメントフェイス集合記憶手段に記憶する超平面アレンジメントフェイス集合形成ステップ、超平面アレンジメントフェイス集合記憶手段に記憶された超平面アレンジメントフェイスの集合の中から空間物の部分にある超平面アレンジメントフェイスを探し出し、この探し出した超平面アレンジメントフェイスの集合を超平面アレンジメントフェイス複体として超平面アレンジメントフェイス複体記憶手段に記憶する超平面アレンジメントフェイス複体形成ステップを含む。
【００１６】
また、本発明の空間物データ処理プログラムは、多次元空間内に存在する空間物をモデル化した空間物データをコンピュータにより処理するためのプログラムであって、コンピュータに、空間物データに基づいて空間物の境界を構成する全ての凸な要素についてそれぞれ超平面を形成し、この形成された超平面の集合を超平面集合記憶手段に記憶する超平面集合形成ステップ、超平面集合記憶手段から超平面集合を取り出し、この超平面集合を用いて多次元空間を分割することにより超平面アレンジメントを構築し、この超平面アレンジメントの各フェイスの集合を超平面アレンジメントフェイス集合記憶手段に記憶する超平面アレンジメントフェイス集合形成ステップ、超平面アレンジメントフェイス集合記憶手段に記憶された超平面アレンジメントフェイスの集合の中から空間物の部分にある超平面アレンジメントフェイスを探し出し、この探し出した超平面アレンジメントフェイスの集合を超平面アレンジメントフェイス複体として超平面アレンジメントフェイス複体記憶手段に記憶する超平面アレンジメントフェイス複体形成ステップを実行させるためのものである。
【００１７】
ここで、空間物データとは、空間物の広がりと位置を表現したデータをいう。超平面アレンジメントは、計算幾何学および工学（ロボットの行動計画、コンピュータビジョン、コンピュータグラフィックス）で使用されている概念であり、「有限個の超平面の集まりによる空間の分割」のことをいう。この超平面アレンジメントは、Ｎ次元の空間を０からＮ次元のフェイスに分割する。フェイスとは、超平面によって区切られた区画のことである。また、このフェイスは、互いに重ならないという性質を有する。例えば、図１に示すように、４個の超平面｛ｈ1，ｈ2，ｈ3，ｈ4｝によって形成される超平面アレンジメントフェイスは、σ1からσ33までの３３個である。
【００１８】
このような超平面アレンジメントフェイスの集合をコンピュータ上で形成するため、本発明では、空間物データに基づいて空間物の境界を構成する全ての凸な要素についてそれぞれ超平面を形成し、この形成された超平面の集合を超平面集合記憶手段に記憶し、さらに、この超平面集合記憶手段から超平面集合を取り出し、この超平面集合を用いて多次元空間を分割することにより超平面アレンジメントを構築し、この超平面アレンジメントの各フェイスの集合を超平面アレンジメントフェイス集合記憶手段に記憶する。
【００１９】
本発明に係る超平面アレンジメントフェイス複体は、上記数学的概念である超平面アレンジメントに基づく。超平面アレンジメントフェイス複体では、空間物データを超平面アレンジメントフェイスの集まり（集合）として表現する。この超平面アレンジメントフェイス複体では、Ｋ次元の空間物データは、０からＫまでの次元の超平面アレンジメントフェイスの集まりとして表現される。超平面アレンジメント自体は既知の概念であるが、超平面アレンジメントフェイスの集まりとして空間物データを表した本発明に係る超平面アレンジメントフェイス複体という概念は、本発明者が初めて提案したものである。
【００２０】
ある超平面アレンジメントフェイスσを含むようなｋ次元の線形部分空間があり、かつｋ−１次元の線形部分空間がないときに、超平面アレンジメントフェイスσの次元はｋであると定義する。図１に示す例では、２次元の超平面アレンジメントフェイス（超平面で囲まれた領域の内部）が１１個（３個が有界で、８個が非有界な領域）、１次元の超平面アレンジメントフェイス（超平面の部分）が１６個（８個が直線で、８個が半直線）、０次元の超平面アレンジメントフェイス（超平面の交点）が６個ある。以下、ｋ次元のアレンジメントフェイスのことをｋ−ＨＡ−faceとも表現する。
【００２１】
超平面アレンジメントフェイスには、一意に１個の符号ベクトル（sign vector）が定まる。符号ベクトルの長さは、超平面の数に等しい。また、それぞれの符号は、超平面の表側であるか、超平面上であるか、超平面の裏側にあるかによって、それぞれ＋、０あるいは−の値をとる。図１中の矢印は、超平面の表側を示している。図１の例では、超平面は、ｈ1，ｈ2，ｈ3，ｈ4の４個であり、符号ベクトルの長さは４である。符号ベクトルの長さは、超平面アレンジメントフェイスの次元に関係なく一定である（超平面の数で決まる。）。図１の例では、２次元のσ1の符号ベクトルは［＋＋＋＋］、１次元のσ13の符号ベクトルは［０−＋＋］、０次元のσ28の符号ベクトルは［００＋＋］である。
【００２２】
超平面アレンジメントフェイス複体モデルを定義するために、まず、２つの超平面アレンジメントフェイス間の関係である「インシデント・リレーションシップ（incident relationship）を定義する。「インシデント・リレーションシップ」という表現そのものは、２つの幾何プリミティブ（セル、頂点、辺など）間の関係を表す一般的な言葉であるが、本明細書中においては超平面アレンジメントフェイス間の関係を表すものとして用いる。この超平面アレンジメントフェイスに対するインシデント・リレーションシップの定義は、本発明独自のものである。
【００２３】
２つの超平面アレンジメントフェイスσi，σjがあるとき（但し、σi，σjの両方とも、同じ超平面アレンジメントフェイス集合のフェイスであること）、σjがσiに接していて、かつσjの次元が、σiの次元よりも小さいときに、σjはσiにインシデント（付帯的）であるということにする。例えば、図１では、σ12，σ14，σ16，σ21，σ28，σ30，σ31，σ33の８個が、σ1にインシデントである。インシデント関係は推移的（transitive）であるが、対称ではない（anti-commutative）。例えば、σ12はσ1にインシデントであるが、σ1はσ12にインシデントではない。
【００２４】
以下で説明する「コンプリートネス・オブ・インシデンス（completeness of incidence）」を満足するような超平面アレンジメントフェイスの集合を、超平面アレンジメントフェイス複体と呼ぶ。コンプリートネス・オブ・インシデンスとは、次の通りである。
【００２５】
コンプリートネス・オブ・インシデンス：Σ（Ｈ）＝｛σ1，σ2，…，σn｝を、超平面集合Ｈによってできたすべての超平面アレンジメントフェイスの集合とする。Σ（Ｈ）の部分集合Γについて、次の条件を満たすときに限り、Γを超平面アレンジメントフェイス複体という。
『Γが、Γの任意の要素ｘについて、ｘにインシデントであるようなすべての超平面アレンジメントフェイスを含んでいる。』
【００２６】
つまり、超平面アレンジメントフェイスの集合Γについて、Γが、Γの任意の要素ｋ−ＨＡ−face（ｋ＞０）とインシデント関係にある全ての（ｋ−１）−ＨＡ−faceを含むとき、Γのことを、超平面アレンジメントフェイス複体と呼ぶ。図２は、超平面アレンジメントフェイス複体の例を示している。図２において、Γ＝｛σ1，σ2，…，σ19｝は、６つの超平面の超平面アレンジメントフェイスの集合であるが、この集合Γは上記複体の条件を満たす。例えば、σ1について、σ4，σ5，σ6はσ1とインシデント関係にあるが、これらσ4，σ5，σ6は、すべてΓの要素である。
【００２７】
本来、ｋ次元の超平面アレンジメントフェイスｋ−ＨＡ−face（ｋ＞０）は、定義から有界であることも、非有界であることもある（図３参照。）。但し、０次元の超平面アレンジメントフェイスは必ず有界である。有界の定義は、数学における「有界」の定義と同じであり、ｋ−ＨＡ−face（ｋ＞０）内の任意の点ｐについて、||ｐ||≦を満足するような定数ｒが存在するとき（||ｐ||は、原点から点ｐまでの距離）、そのｋ−ＨＡ−faceは、有界であるという。つまり、有界なｋ−ＨＡ−faceについては、そのｋ−ＨＡ−faceを包含するような半径ｒの超球が存在する。有界なｋ−ＨＡ−faceは、凸図形である。例えば、１−ＨＡ−faceは線分、２−ＨＡ−faceは凸多角形である。超平面アレンジメントフェイス複体は、一般に、有界な超平面アレンジメントフェイスと、非有界な超平面アレンジメントフェイスの集まりである。
【００２８】
このような超平面アレンジメントフェイス複体の特徴は、空間物の表現能力にある。非有界な領域、孤立領域、穴、様々な次元の要素を含むような空間物（図４の（ａ）〜（ｄ）を参照。）も、超平面アレンジメントフェイス複体として表現できる。
【００２９】
ｄ次元空間中のｄ次元の空間物を表現するには、空間物の境界領域を含むような超平面の集まりＨを作り、その超平面の集まりから超平面アレンジメントフェイス複体を作ることで、元の図形を表現できる。図４に示すように、ｄ次元空間中のｋ次元の空間物（但し、ｋ＜ｄ）を表現するには、空間物の境界領域を含むような超平面の集まりだけでなく、余分の（ｄ−ｋ）個以上の超平面を追加することで表現できる。例えば、図４（ｄ）では、１次元の図形（図４では凸多角形につながった線分で、１−ＨＡ−face）を表現するのに端点を通過するような余分な超平面が追加される。また、図４（ｄ）では、２次元空間中の点を表現するのに２つの超平面が使われている。
【００３０】
このような超平面アレンジメントフェイス複体をコンピュータ上で形成するために、本発明では、超平面アレンジメントフェイス集合記憶手段に記憶された超平面アレンジメントフェイスの集合の中から空間物の部分にある超平面アレンジメントフェイスを探し出す。そして、この探し出した超平面アレンジメントフェイスの集合を超平面アレンジメントフェイス複体として超平面アレンジメントフェイス複体記憶手段に記憶する。
【００３１】
ここで、超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2との積を構成する空間物に対する新たな超平面アレンジメントフェイス複体Γintersectionを超平面集合形成ステップ、超平面アレンジメントフェイス集合形成ステップおよび超平面アレンジメントフェイス複体形成ステップにより求めることができる。
【００３２】
また、超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2との差を構成する空間物に対する新たな超平面アレンジメントフェイス複体Γdifferenceを超平面集合形成ステップ、超平面アレンジメントフェイス集合形成ステップおよび超平面アレンジメントフェイス複体形成ステップにより求めることができる。
【００３３】
また、超平面アレンジメントフェイス複体記憶手段から超平面アレンジメントフェイス複体Γ1，Γ2を取り出し、超平面アレンジメントフェイス複体Γ1と超平面アレンジメントフェイス複体Γ2との和を構成する空間物に対する新たな超平面アレンジメントフェイス複体Γunionを超平面集合形成ステップ、超平面アレンジメントフェイス集合形成ステップおよび超平面アレンジメントフェイス複体形成ステップにより求めることができる。
【発明の効果】
【００３４】
空間物データに基づいて空間物の境界を構成する全ての凸な要素についてそれぞれ超平面を形成し、この形成された超平面の集合を超平面集合記憶手段に記憶し、超平面集合記憶手段から超平面集合を取り出し、この超平面集合を用いて多次元空間を分割することにより超平面アレンジメントを構築し、この超平面アレンジメントの各フェイスの集合を超平面アレンジメントフェイス集合記憶手段に記憶し、超平面アレンジメントフェイス集合記憶手段に記憶された超平面アレンジメントフェイスの集合の中から空間物の部分にある超平面アレンジメントフェイスを探し出し、この探し出した超平面アレンジメントフェイスの集合を超平面アレンジメントフェイス複体として超平面アレンジメントフェイス複体記憶手段に記憶することにより、多次元空間中の任意の次元の空間物を超平面アレンジメントフェイスの集まり（超平面アレンジメントフェイス複体）として表現することができる。また、超平面アレンジメントフェイス複体を用いて，３次元以上の任意の次元の空間物同士の種々の空間オペレーションを行うことができるという点で、従来の線形計画法、整数計画法やハーフスペース・インターセクション法を機能的に凌駕する。
【発明を実施するための最良の形態】
【００３５】
図５は本発明の実施の形態における空間物データ処理プログラムを実行したコンピュータの機能ブロック図である。
【００３６】
図５に示すように、本発明の実施の形態におけるコンピュータは、多次元空間内に存在する空間物をモデル化した空間物データを記憶する空間物データ記憶手段１１と、超平面の集合を記憶する超平面集合記憶手段１２と、超平面アレンジメントフェイスの集合を記憶する超平面アレンジメントフェイス集合記憶手段１３と、超平面アレンジメントフェイス複体を記憶する超平面アレンジメントフェイス複体記憶手段１４として機能する。
【００３７】
また、このコンピュータは、空間物データに基づいて超平面集合を形成する超平面集合形成手段２１と、超平面集合を用いて超平面アレンジメントフェイス集合を形成する超平面アレンジメントフェイス集合形成手段２２と、超平面アレンジメントフェイス集合から超平面アレンジメントフェイス複体を形成する超平面アレンジメントフェイス複体形成手段２３と、超平面アレンジメントフェイス複体を用いて各種演算を行う空間オペレーション手段２４として機能する。
【００３８】
超平面集合形成手段２１は、空間物データ記憶手段１１から空間物データを取り出し、この空間物データに基づいて空間物の境界を構成する全ての凸な要素についてそれぞれ超平面を形成し、この形成された超平面の集合Ｈを超平面集合記憶手段１２に記憶するものである。
【００３９】
図６は、この超平面集合形成手段２１による処理の詳細を示している。
図６に示すように、超平面集合形成手段２１は、まず、超平面集合記憶手段１２に格納する超平面集合Ｈを空にし（ステップＳ１０１）、元の空間物の境界を構成する凸な要素を順に１つ取り出して、変数ｆに格納する（ステップＳ１０２）。
【００４０】
次に、超平面集合形成手段１２は、この取り出した凸な要素ｆの次元ｋが多次元空間の次元をｄとしたときにｄ−１であるか否か判別し（ステップＳ１０３）、次元ｋがｄ−１である場合は、この要素ｆを含む超平面を超平面集合Ｈに加え（ステップＳ１０４）、そうでない場合は、この要素ｆを含む超平面を超平面集合Ｈにｄ−ｋ個加える（ステップＳ１０５）。
【００４１】
さらに、超平面集合形成手段１２は、凸な要素ｆの端が他の凸な要素に含まれるか否か判別し（ステップＳ１０６）、含まれない場合は、この凸な要素ｆの端を含む超平面を超平面集合Ｈに加える。そして、超平面集合形成手段１２は、上記処理を空間物の境界を構成する全ての凸な要素について行う（ステップＳ１０７）。これにより、超平面集合記憶手段１２には、空間物の境界を構成する全ての凸な要素について、それぞれ形成された超平面の集合Ｈが格納される。
【００４２】
超平面アレンジメントフェイス集合形成手段２２は、超平面集合記憶手段１２から超平面集合Ｈを取り出し、この超平面集合Ｈを用いて多次元空間を分割することにより超平面アレンジメントＡ（Ｈ）を構築し、この超平面アレンジメントの各フェイスの集合を超平面アレンジメントフェイス集合記憶手段１３に記憶するものである。
【００４３】
超平面アレンジメントフェイス集合形成手段２２が、超平面集合Ｈから超平面アレンジメントＡ（Ｈ）を構築する処理については、非特許文献４，５に記載のように公知であるから詳細な説明を省略する。超平面アレンジメントフェイス集合形成手段２２は、この超平面アレンジメントＡ（Ｈ）の構築の際にできたそれぞれの区画（フェイス）の集合を超平面アレンジメントフェイス集合記憶手段１３に記憶する。
【００４４】
超平面アレンジメントフェイス複体形成手段２３は、超平面アレンジメントフェイス集合記憶手段１３に記憶された超平面アレンジメントフェイスの集合の中から空間物の部分にある超平面アレンジメントフェイスを探し出し、この探し出した超平面アレンジメントフェイスの集合を超平面アレンジメントフェイス複体として超平面アレンジメントフェイス複体記憶手段１４に記憶するものである。
【００４５】
図７は、この超平面アレンジメントフェイス複体形成手段２３による処理の詳細を示している。
図７に示すように、超平面アレンジメントフェイス複体形成手段２３は、まず、超平面アレンジメントフェイス複体記憶手段１４に格納する超平面アレンジメントフェイス集合Γを空にし（ステップＳ１１１）、超平面アレンジメントフェイス集合記憶手段１３に記憶された超平面アレンジメントＡ（Ｈ）のフェイスの集合の中からフェイスσを１つ取り出す（ステップＳ１１２）。
【００４６】
次に、超平面アレンジメントフェイス複体形成手段２３は、この取り出した超平面アレンジメントフェイスσが元の空間物の外か否か判別し（ステップＳ１１３）、空間物の外でない場合は、空間物の部分にある超平面アレンジメントフェイスであると判断して、この超平面アレンジメントフェイスσを超平面アレンジメントフェイス集合Γに加える（ステップＳ１１３）。
【００４７】
そして、超平面アレンジメントフェイス複体形成手段２３は、上記処理を超平面アレンジメントフェイス集合記憶手段１３に記憶された超平面アレンジメントＡ（Ｈ）のフェイスの集合に含まれる全ての超平面アレンジメントフェイスについて行う（ステップＳ１１５）。これにより、超平面アレンジメントフェイス複体記憶手段１４には、超平面アレンジメントフェイス複体としての超平面アレンジメントフェイス集合Γが格納される。
【００４８】
空間オペレーション手段２４は、超平面アレンジメントフェイス複体記憶手段１４から複数の超平面アレンジメントフェイス複体を取り出し、この取り出した超平面アレンジメントフェイス複体を用いて、構造オペレーション（境界（boundary）、内部（interior））、幾何オペレーション（和、差、積などの集合論演算子（２つの空間物から新しい空間物を作る））や、交わる、離れている、含む、等しい、接するなどの位相関係述語（２つの空間物の空間的な関係を判定し、正（true値）あるいは誤（false値）を返す）等の各種空間オペレーションを行うものである。
【００４９】
まず、超平面アレンジメントフェイス複体として表現された空間物の各種空間オペレーションを定義する前に、超平面アレンジメントフェイスの境界（boundary）と閉包（closure）の定義を行う。超平面アレンジメントフェイスの境界と閉包は、超平面アレンジメントフェイスのインシデント関係を使って定義される。
【００５０】
ｋ−ＨＡ−faceσ（ｋ＞０）に対して、σの境界とは、σに対してインシデントであるような全ての超平面アレンジメントフェイスの集まりである。また、ｋ−ＨＡ−faceσ（ｋ＞０）に対して、σの閉包とは、σの境界（これは集合）とσ自身との和集合である。なお、０−ＨＡ−faceについては、０−ＨＡ−faceにインシデントな超平面アレンジメントフェイスは存在しないため、ｋ−ＨＡ−face（ｋ＞０）とは定義が異なる。０−ＨＡ−faceσの境界と閉包は、σ自身であると定義する。
【００５１】
以上の定義をまとめると表１のようになる。なお、Σ（Ｈ）＝｛σ1，σ2，…，σn｝は、超平面集合Ｈによってできた全ての超平面アレンジメントフェイスの集合とする。
【００５２】
【表１】
2005038204.tif 000003
【００５３】
また、図８に超平面アレンジメントフェイスの境界と閉包の例を示す。なお、図中の破線は超平面を表している。
【００５４】
前述のように、超平面アレンジメントフェイス複体として表現された空間物に関するオペレーションには、次の３つの種類がある。
（１）構造オペレーション
（２）幾何オペレーション
（３）位相関係述語
これらのオペレーションの例を図９、図１０および図１１に示す。
【００５５】
（１）構造オペレーション
図９に示すように、境界（boundary）は、元の空間物データの中で、外部に接する点の集まりである。内部（interior）は、元の空間物データの中で、境界に無い点の集まりである。いずれも、超平面アレンジメントフェイスの集合として表現される。超平面アレンジメントフェイス複体Γ＝｛σ1，σ2，…，σn｝の境界と内部の定義は、表２に示すように、超平面アレンジメントフェイスの閉包を使って定義される。
【００５６】
【表２】
2005038204.tif 000004
σi（０≦ｉ≦ｎ）は、超平面アレンジメントフェイス複体Γのフェイスを表している。なお、closure({σ1,σ2,…,σn})＝closure(σ1）∪closure(σ2）∪…∪closure(σn）であり、exterior({σ1,σ2,…,σn})＝Σ（Ｈ）−closure({σ1,σ2,…,σn})とする。Σ（Ｈ）は、超平面集合Ｈによってできた全ての超平面アレンジメントフェイスの集合である。
【００５７】
（２）幾何オペレーション
幾何オペレーションは２項演算である。空間オペレーション手段２４は、超平面アレンジメントフェイス複体記憶手段１４から２つの超平面アレンジメントフェイス複体を取り出す。この取り出した２つの超平面アレンジメントフェイス複体をΓ1，Γ2と表す。幾何オペレーションである積（intersection）と和（union）は、超平面アレンジメントフェイス複体Γ1，Γ2を、点集合として重ね合わせた結果を得る。一方、幾何オペレーションである差（difference）については、２つの空間物の差を取った結果は、単なる差ではなく、境界を含むものと定義する。例えば、図１０では、Γ1，Γ2の差difference（Γ1，Γ2）は交線を含む。
【００５８】
超平面アレンジメントフェイス複体は、ある超平面集合Ｈによってできた全ての超平面アレンジメントフェイスの集合である。超平面アレンジメントフェイス複体Γ1，Γ2に対応する超平面集合を、それぞれＨ1P，Ｈ2Pと表す。Γ1，Γ2の幾何オペレーションの結果は、Ｈ1P，Ｈ2Pの和集合（つまり超平面集合）によってできる超平面アレンジメントフェイスからなる超平面アレンジメントフェイス複体である。
【００５９】
例えば、図１０では、Γ1，Γ2の積intersection（Γ1，Γ2）は、７個の２−ＨＡ−face、２１個の１−ＨＡ−face、１５個の０−ＨＡ−faceからなり、これは１４個の超平面の集合からできた超平面アレンジメントフェイスである。幾何オペレーションの定義を表３に示す。
【００６０】
【表３】
2005038204.tif 000005
【００６１】
（３）位相関係述語（図１１参照。）
位相関係述語は、正（true値）あるいは誤（false値）を返す。
・「交わるintersect（Γ1，Γ2）」は、Γ1，Γ2の積intersection（Γ1，Γ2）が空でないときに限り、true値を返す。
・「離れているdisjoint（Γ1，Γ2）」は、Γ1，Γ2の積の積intersection（Γ1，Γ2）が空であるときに限り、true値を返す。
・「含むcontain（Γ1，Γ2）」は、差difference（Γ2，Γ1）が空であるときに限り、true値を返す。
・「接するmeet（Γ1，Γ2）」は、他の位相関係述語を使って、次のように定義する。
meet（Γ1，Γ2）＝contain（boundary（Γ1），intersection（Γ1，Γ2））
・「等しいequal（Γ1，Γ2）」は、２つの超平面アレンジメントフェイス複体を調べ、次の条件が成り立つときに限りtrue値を返す。
equal（Γ1，Γ2）に対して
{σ∈(Ｈ1P∪Ｈ2P)|Γ1includesσ}＝{σ∈(Ｈ1P∪Ｈ2P)|Γ2includesσ}
が成り立つか。
【００６２】
上記構成の空間物データ処理プログラムを実行したコンピュータによる空間物のオペレーション処理手順について、以下、図１２のフロー図に従って説明する。まず、空間物データ記憶手段１１には２つの空間物Ａ，Ｂの空間物データが記憶されているものとする。
【００６３】
ステップＳ１２１：超平面集合形成手段２１は、空間物データ記憶手段１１から２つの空間物データを取り出し、それぞれの空間物データに基づいて各空間物Ａ，Ｂの境界を構成する全ての凸な要素について超平面を形成し、この形成された超平面集合ＨAP，ＨBPを超平面集合記憶手段１２に記憶する。
【００６４】
ステップＳ１２２：超平面アレンジメントフェイス集合形成手段２２は、超平面集合記憶手段１２から２つの空間物Ａ，Ｂに対する超平面集合ＨAP，ＨBPを取り出し、この超平面集合ＨAP，ＨBPを用いて多次元空間を分割することにより超平面アレンジメントを構築し、この超平面アレンジメントの各フェイスの集合Σ（ＨAP），Σ（ＨBP）を超平面アレンジメントフェイス集合記憶手段１３に記憶する。
【００６５】
ステップＳ１２３：超平面アレンジメントフェイス複体形成手段２３は、超平面アレンジメントフェイス集合記憶手段１３に記憶された超平面アレンジメントフェイスの集合Σ（ＨAP），Σ（ＨBP）の中からそれぞれ空間物Ａ，Ｂの部分にある超平面アレンジメントフェイスを探し出し、この探し出した超平面アレンジメントフェイスの集合ΓA，ΓBをそれぞれ空間物Ａ，Ｂに対する超平面アレンジメントフェイス複体として超平面アレンジメントフェイス複体記憶手段１４に記憶する。
【００６６】
ステップＳ１２４：空間オペレーション手段２４は、超平面アレンジメントフェイス複体記憶手段１４から超平面アレンジメントフェイス複体ΓA，ΓBを取り出し、超平面アレンジメントフェイス複体ΓAと超平面アレンジメントフェイス複体ΓBとの空間オペレーションとして、例えば、積（intersection）、差（difference）や和（union）などを構成する空間物に対する新たな超平面アレンジメントフェイス複体Γintersectionを上記超平面集合形成ステップ（Ｓ１２１）、超平面アレンジメントフェイス集合形成ステップ（Ｓ１２２）および超平面アレンジメントフェイス複体形成ステップ（Ｓ１２３）により求める。
【００６７】
ここで、空間オペレーション手段２４は、上で求めた超平面アレンジメントフェイス複体Γintersectionが空であるか否かを調べ、空でないときは超平面アレンジメントフェイス複体ΓA，ΓBが交差する（intersect）と判定する。一方、超平面アレンジメントフェイス複体Γintersectionが空であるときは、超平面アレンジメントフェイス複体ΓA，ΓBが離れている（disjoint）と判定する。
【００６８】
また、空間オペレーション手段２４は、上で求めた超平面アレンジメントフェイス複体Γdifferenceが空である場合には、超平面アレンジメントフェイス複体ΓA，ΓBの一方が他方に含まれる（contain）と判定する。また、空間オペレーション手段２４は、上で求めた超平面アレンジメントフェイス複体Γintersectionが超平面アレンジメントフェイス複体ΓA，ΓBの一方の境界に含まれる場合に、超平面アレンジメントフェイス複体ΓA，ΓBの一方が他方に接する（meet）と判定する。
【００６９】
また、空間オペレーション手段２４は、空間オペレーションとして同一判定（equal）を行う場合、超平面アレンジメントフェイス複体記憶手段１４から超平面アレンジメントフェイス複体ΓA，ΓBを取り出し、超平面アレンジメントフェイス複体ΓAと超平面アレンジメントフェイス複体ΓBとが一致すると、超平面アレンジメントフェイス複体ΓA，ΓBは等しいと判定する。
【００７０】
このような空間オペレーション手段２４により行う空間オペレーション（幾何オペレーション、位相関係述語など）の用途としては、２つの空間物についての関係を調べるもの（例えば、ロボットのアームと部品との交差、太陽光線や電波の当たり具合）や、空間物データを扱うデータベースがある。空間物データを扱うデータベースでは、データベース内の空間物データに対して点検策（point query）、範囲検索（range queries）、空間ジョイン(spatial join）などの空間質問が行われるが、空間質問を処理して答えを得る過程で、空間オペレーションの実行が行われる。
【００７１】
ここで、空間オペレーション手段２４による空間オペレーションをより速く行うための仕組みについて、以下に説明する。
【００７２】
（Ａ）独立超平面アレンジメントフェイス
超平面アレンジメントフェイス複体のデータをコンパクトに表現し、結果として超平面アレンジメントフェイス複体に関する幾何オペレーション、位相関係述語を速く処理できるようにするために、以下で説明する独立超平面アレンジメントフェイスを使って超平面アレンジメントフェイス複体を表現する。超平面アレンジメントフェイス集合の独立超平面アレンジメントフェイスを次のように定義する。
【００７３】
超平面アレンジメントフェイス集合Σの要素のうち、他のΣの要素にインシデントでない要素を、独立超平面アレンジメントフェイス（independent HA-face）集合という。これを数式で表すと、
independent HA-face of Σ
＝{σ∈Σ|σは、他のΣ内の超平面アレンジメントフェイスにインシデントでない}
例えば、図１３内の空間物は、３つの２次元の独立超平面アレンジメントフェイス集合｛σ1，σ2，σ3｝で表現される。
【００７４】
超平面アレンジメントフェイス複体は、前述の「コンプリートネス・オブ・インシデンス」を満足することから、「他の超平面アレンジメントフェイスにインシデントな超平面アレンジメントフェイスは、データとして記憶しておかなくとも、全て計算で求めることができる」といえる。つまり、超平面アレンジメントフェイス複体については、独立超平面アレンジメントフェイスの集合の閉包が、元の超平面アレンジメントフェイス複体に等しくなる。つまり、超平面アレンジメントフェイス複体は、独立超平面アレンジメントフェイスの集合として、コンパクトに（かつ情報を失うことなく）表現することができる。
【００７５】
表４は、２つの超平面アレンジメントフェイス複体Γ1，Γ2の幾何オペレーションの定義を、独立超平面アレンジメントフェイスを使って表したものである。Σ1I，Σ2Iは、独立超平面アレンジメントフェイス集合を表す。また、Γ1，Γ2の超平面アレンジメントフェイスを作っているそれぞれの超平面集合をＨ1P，Ｈ2Pと表している。
【００７６】
【表４】
2005038204.tif 000006
【００７７】
（Ｂ）２ステップリファインメント
空間オペレーションのうち、幾何オペレーションと、位相関係述語は、２ステップリファインメント（two-step-refinement）で処理する。２ステップリファインメントは、コースリファインメント（coarse-refinement）、イグザクトリファインメント（exact-refinement）の２段階で計算処理を行うことをいう。
【００７８】
最初のステップであるコースリファインメントでは、図形の独立超平面アレンジメントフェイスの個々を調べ、イグザクトリファインメントで精査の必要な独立超平面アレンジメントフェイスの候補を選び出す（この候補のことを、以下「候補集合」と称す。）。候補として選ばれなかった独立超平面アレンジメントフェイスは、イグザクトリファインメントのステップは処理されない。
【００７９】
２ステップリファインメントは、幾何オペレーションと、位相関係述語のためのアルゴリズムである。いずれも２項演算であり、入力は、２つの超平面アレンジメントフェイス複体である。コースリファインメントでは、一方の超平面アレンジメントフェイス複体を包含するような近似図形（例えば、最小包含矩形（minimum bounding rectangle）、最小外接円（minimum bounding circle）、最小外接凸形（minimum bounding convex）など）と、もう一方の超平面アレンジメントフェイス複体を構成する独立超平面アレンジメントフェイスとの交差判定が繰り返される。そして、交差するもののみが候補として選び出され、次のイグザクトリファインメントで処理される。
【００８０】
２ステップリファインメントで、積intersection（Γ1，Γ2）を求める例を図１４に示している。入力となる２つの空間物の独立超平面アレンジメントフェイス集合は、それぞれ｛σ11，σ12，σ13｝と｛σ21，σ22，σ23，σ24，σ25｝である。
【００８１】
積intersection（Γ1，Γ2）を求めるために（図１４（ａ）参照。）、コースリファインメントは、３つの独立超平面アレンジメントフェイス集合｛σ11，σ12，σ13｝（図１４（ｂ）参照。）のそれぞれについて、Γ2を包含するような近似図形（ここでは、最小包含矩形）と交差するかどうかを調べる。この例ではσ11とσ12が交差する。これらが、コースリファインメントで得られる候補集合である。
【００８２】
次のイグザクトリファインメントでは、ペア（σ11，Γ2）と、別のペア（σ12，Γ2）について、交差するかどうかが精査される（この精査は、積intersection（Γ1，Γ2）を求めるのに必要。）。交差するペアは、σ12，Γ2の方のみである（図１４（ｃ）参照。）。
【００８３】
コースリファインメントでは、近似図形データを使って、処理の高速化を行う。使用される近似図形データは次の２種類である。
（１）超平面アレンジメントフェイス複体を包含するような近似図形（例えば、最小包含矩形、最小外接円、最小外接凸形など）
（２）超平面アレンジメントフェイス複体に含まれる０−ＨＡ−face
【００８４】
コースリファインメントの処理手順の詳細は、次の６手順である。
（１）順序の決定
最初は、入力の２つの超平面アレンジメントフェイス複体に、順序を付けるために、その大きさを調べる。超平面アレンジメントフェイス複体の大きさは、独立超平面アレンジメントフェイスの数で数える。以下、入力の２つの超平面アレンジメントフェイス複体のうち、独立超平面アレンジメントフェイスの数の少ない方をΓ1、多い方をΓ2とする。残りの手順では、Γ1の０−ＨＡ−faceと独立超平面アレンジメントフェイスの情報と、Γ2を包含するような近似図形（ここでは、最小包含矩形）の情報を使う。
【００８５】
（２）Γ1の全ての０−ＨＡ−faceについて、Γ2の最小包含矩形との交差判定
Γ1が非有界なら、この手順は飛ばす。Γ1の全ての０−ＨＡ−faceについて、Γ2の最小包含矩形と交差するかどうかを調べる。もし、Γ1の０−ＨＡ−faceが、１つでもΓ2の最小包含矩形と交差するならば、次の出力を出して処理を終える。
intersect（Γ1，Γ2）＝true
disjoint（Γ1，Γ2） ＝false
なお、intersection、difference、union、meet、contain、equalについては、この処理は行わない。
【００８６】
（３）非有界な独立超平面アレンジメントフェイスを、候補集合に挿入
Γ1の独立超平面アレンジメントフェイスのうち、非有界であるものを探し、候補集合（コースリファインメントの出力のこと）に挿入する。以下の（４）（５）（６）の処理では、有界であるものについて、候補集合に挿入すべきかどうかの判断を行う。
【００８７】
（４）独立超平面アレンジメントフェイスの最小包含矩形の構成
Γ1の独立超平面アレンジメントフェイスのうち、有界であるものについて（この独立超平面アレンジメントフェイスをσとおく）、最小包含矩形を構成する。
【００８８】
（５）最小包含矩形による交差判定
前の手順で作った最小包含矩形が、Γ2の最小包含矩形と交差するかどうかを調べる。もし、交差していなければ、最小包含矩形に対応する独立超平面アレンジメントフェイスは、候補集合に含めないことにする（この後の処理は行わない。）。交差していれば、次の処理に進む。空間オペレーションである「等しいequal」を処理している場合には、交差していないものが１つでも見つかれば、結果はfalseとなる。
【００８９】
（６）有界な独立超平面アレンジメントフェイスσ（次元はｋとする）にインシデントなｍ−ＨＡ−face（ｍ＜ｋ）の全てについて、Γ2の最小包含矩形と交差するかどうかを調べる。もし、全てが交差していなければ、候補集合に含めないことにする。１つでも交差していれば、候補集合に含める。空間オペレーションである「等しいequal」を処理している場合には、交差していないものが１つでも見つかれば、結果はfalseとなる。
【００９０】
（Ｃ）積intersectのためのフェイス・オルタネイティブリィ（Face-Alternatively）法
積intersection（Γ1，Γ2）を求める場合、Γ1の独立超平面アレンジメントフェイスと、Γ2の独立超平面アレンジメントフェイスのうち、交差するペアが１つでも見つかれば、その時点で、イグザクトリファインメントの処理は中止できる。このことから、積intersectionの実装には、交差するペアが１つでも見つかれば、その時点で、イグザクトリファインメントの処理を中止するフェイス・オルタネイティブリィ法（以下、「ＦＡ法」と称す。）を提案する。図１５はこのＦＡ法の処理手順を示している。図１６には、処理を中止しないという単純な場合（ギャザリング・キャンディデイツ（Gathering-Candidates）法と呼ぶ。以下、「ＧＣ法」と称す。）の処理手順を示している。
【００９１】
（Ｄ）局所分割統治法（localized divide-and-conquer）
イグザクトリファインメントを高速に行うための手法である局所分割統治法を提案する。局所分割統治法では、「１つの超平面アレンジメントフェイスについて、超平面を（一般に複数個）加えて、さらに細かな超平面アレンジメントフェイスの集まりに分割する」という処理を行う。分割してできた超平面アレンジメントフェイスの集まりは、様々な次元の超平面アレンジメントフェイスを含んでいる。それら超平面アレンジメントフェイスの間のインシデント関係は、グラフ構造（節は１つの超平面アレンジメントフェイス、枝がインシデント関係）で表現する。このグラフのことを、以下、「超平面アレンジメントフェイス束」と呼ぶ。超平面アレンジメントフェイス束を使って、幾何オペレーションと、位相関係述語のイグザクトリファインメントを行う。１つの超平面アレンジメントフェイスについて、超平面を（一般に複数個）加えて、超平面アレンジメントフェイス束を構築するための計算コストは、結果の超平面アレンジメントフェイス束に最終的に含まれる超平面アレンジメントフェイスの数に比例する。
【００９２】
以下、コースリファインメントの出力（つまりイグザクトリファインメントの入力）である候補集合をΣCと表し、もう一方の超平面アレンジメントフェイス複体をΓ2と表す。また、Γ2の超平面アレンジメントフェイスを作る超平面集合をＨと表す。局所分割統治法の手順は次の通りである。
【００９３】
（１）超平面アレンジメントフェイス束の構築
ΣCの要素である独立超平面アレンジメントフェイスσi∈ΣC＝｛σ1，σ2，…，σn｝について、超平面集合Ｈを加えて超平面アレンジメントフェイス束を構築する。できた超平面アレンジメントフェイス束を以下Ｌ（σi）（１≦ｉ≦ｎ）と表す。例えば、図１４（ｃ）では、｛σ11，σ12｝のそれぞれについて、超平面集合を加えて、超平面アレンジメントフェイス束を得る。
【００９４】
（２）超平面アレンジメントフェイス束とΓ2による処理
次に、超平面アレンジメントフェイス束 Ｌ（σi）（１≦ｉ≦ｎ）内の０−ＨＡ−faceについて、Γ2と交差するかを調べる。交差しているものが見つかれば、位相関係述語のうち「交わるintersect」の結果は、直ちにtrueと分かる。それぞれの０−ＨＡ−faceがΓ2と交差しているかの情報は、次のステップ（３）でも使用する。以降の処理は、０−ＨＡ−faceがΓ2と交差するような超平面アレンジメントフェイス束の独立超平面アレンジメントフェイスについてのみ行う。
【００９５】
（３）処理結果の併合
超平面アレンジメントフェイス束Ｌ（σi）を構成する全てのＨＡ−faceについて、Γ2と交差しているかを調べる。Ｌ（σi）の０−ＨＡ−faceについては、前の処理ステップ（２）において、Γ2と交差しているかどうか分かっている。そこで、０−ＨＡ−faceから出発して、より次元が大きくなるような順序で、Ｌ（σi）内のＨＡ−faceをたどりながら、Γ2と交差しているかを調べる。この処理結果を使って、表４の規則に従い、最終的な結果を得る。
【００９６】
一方、逐次添加法や分割統治法などのアレンジメント構築アルゴリズムを使ってイグザクトリファインメントを行うことも可能である。超平面集合Ｈ1P∪Ｈ2Pによってできる超平面アレンジメントフェイスΣ（Ｈ1P∪Ｈ2P）の全てを、これらアレンジメント構築アルゴリズムを使って得た後に、得られた超平面アレンジメントフェイスが、表３に表した条件を満足するかどうかを調べるという手順になる。例えば、「積intersection（Γ1，Γ2）」は、超平面集合Ｈ1P∪Ｈ2Pによってできる超平面アレンジメントフェイス集合Σ（Ｈ1P∪Ｈ2P）のうち、Γ1とΓ2の両方に含まれるものである。
【実施例】
【００９７】
上記本実施形態における空間物データ処理プログラムの性能評価実験を行った。
（Ａ）環境
性能評価実験はサン・マイクロシステムズ（Sun Microsystems）社製ウルトラ（Ultra）１０ワークステーション（ＣＰＵ：UltraSPARC（登録商標）−IIi ４４０ＭＨｚ、実メモリ：１０２４Ｍバイト，ＯＳ：Solaris（商標）８）を使って実施した。プログラムは、Ｃ and Ｃ＋＋（Ｃ／Ｃ＋＋コンパイラ：SUN Forte（商標） 6 Developer Update 2）で作成し、データベースシステムとして「出世魚（ゲ・ユ（G.Yu）、金子邦彦（K.Kaneko）、グアンギ・バイ（G.Bai）、牧之内顕文（A.Makinouchi）著，“トランザクション・マネジメント・フォー・ア・ディストリビューティッド・オブジェクト・ストレージ・システム・ワカシ−デザイン、インプリメンテーション・アンド・パフォーマンス（Transaction Management for a Distributed Object Storage System WAKASHI - Design, Implementation and Performance）”，第１２回アイトリプルイー・データエンジニアリング国際会議（12th IEEE International Conference on Data Engineering），（米国），１９９６年，ｐ．４６０−４６８）」を用いた。
【００９８】
（Ｂ）ランダムデータによるテスト
テスト用のデータとしてＴAN，ＴBN，ＴCN（Ｎ＝５０，１００，２００，３００，４００，５００）と名付けた３種類の２次元図形データをランダムに生成した。手順は次の通りである。
【００９９】
（１）正方形ＳAN，ＳBN，ＳCNを次のように決めた（図１７参照。正方形ＳAN，ＳBN，ＳCNはそれぞれΓA，ΓB，ΓCに対応する。）。
・ＳAN：［（０，０），（１，１）］
・ＳBN：［（０．２，０．２），（１．２，１．２）］
・ＳCN：［（０．９９，０），（１．９９，１）］
（２）ＳA，ＳB，ＳCに重なるような５０個の超平面からなる超平面集合ＨAN，ＨBN，ＨCNをランダムに生成した。
（３）こうしてできた超平面集合について、独立超平面アレンジメントフェイスをランダムに選んで（図１８参照。）、テストデータを作った。選ぶ独立超平面アレンジメントフェイスの数Ｎは、Ｎ＝５０，１００，２００，３００，４００，５００の６通りとした。
（４）以上の手順を５回繰り返して、同じ性質を持った図形を５個得た。
【０１００】
以上の手順で得られたテストデータＴAN，ＴBN，ＴCN（Ｎ＝５０，１００，２００，３００，４００，５００）について、空間オペレーションを実行し、処理にかかった時間の平均を取って、最終的な実験結果を得た。比較結果がはっきりと現れるように、実験は、テストデータがすべて実メモリに載った状態で行った（つまり、ディスクとのＩ／Ｏ（インプット・アウトプット）コストは、測定結果に現れないような実験を実施した）。実験項目は次の３つである。
【０１０１】
（１）ＦＡ法とＧＣ法の比較
「積intersect（ΓAN，ΓBN）」と「積intersect（ΓAN，ΓCN）」を実行して、ＦＡ法（図１５）とＧＣ法（図１６）の比較実験を実施した。図１９が積intersect（ΓAN，ΓBN）（Ｎ＝５０，１００，２００，３００，４００，５００）の結果、図２０と図２１が積intersect（ΓAN，ΓCN）（Ｎ＝５０，１００，２００，３００，４００，５００）の結果である。どの場合も、ＧＣ法よりＦＡ法の法が１．０から２．２倍速い。
【０１０２】
（２）コースリファインメント有り無しの結果
コースリファインメントを行う場合と、行わない場合で「積intersect（ΓAN，ΓBN）」と「積intersect（ΓAN，ΓCN）」を実行して、比較を行った。図２２が積intersect（ΓAN，ΓBN）（Ｎ＝５０，１００，２００，３００，４００，５００）の結果、図２３と図２４が積intersect（ΓAN，ΓCN）（Ｎ＝５０，１００，２００，３００，４００，５００）の結果である。コースリファインメントを行う方が、行わない場合に比べて１０から４０倍速い。
【０１０３】
（３）局所分割統治法の評価
イグザクトリファインメントについて、局所分割統治法と、アレンジメント構築アルゴリズムである逐次添加法と分割統治法で「積intersect（ΓAN，ΓBN）」と「積intersect（ΓAN，ΓCN）」を実行して、比較を行った。つまり、局所分割統治法、逐次添加法、分割統治法の３つの比較である。図２５は積intersect（ΓAN，ΓBN）の結果であり、図２６と図２７が積intersect（ΓAN，ΓCN）の結果である。なお、図中、局所分割統治法はlocalized divide-and-conquer、逐次添加法はincremental、分割統治法はdivide-and-conquerと表している。局所分割統治法は、他の方法と比べて３から２７倍速い。
【０１０４】
（Ｃ）Ｓｅｑｕｏｉａ２０００ポリゴンデータテスト
Ｓｅｑｕｏｉａ２０００ポリゴンデータを使ったウィンドウ・クエリーの実験によって、２ステップリファインメントでウィンドウ・クエリーを行ったときの振る舞いを調べた。Ｓｅｑｕｏｉａ２０００ベンチマークデータベースとは、バークレイ、カリフォルニア大学によって開発されたＧＩＳデータベースで、ポリゴン、グラフ、ポイント、ラスターの４種のデータからなる。実験では、「raw input data for small Sequoia benchmark」を、ウェブページ（http://a2k-ftp.cs.berkelev.edu:8000:/sequoia/benchmark/）からダウンロードし、ダウンロードしたポリゴンデータを使用した。
【０１０５】
表５には、ダウンロードしたＳｅｑｕｏｉａ２０００ポリゴンデータの頂点数の分布を示している。この中から頂点数が１０から５００であるようなポリゴンを、ランダムに２９個選び、超平面アレンジメントフェイス複体として表現して実験を行った。
【０１０６】
【表５】
2005038204.tif 000007
【０１０７】
ウィンドウ・クエリーのウィンドウの大きさと位置は次の手順で、ポリゴンごとにランダムに決めた。ウィンドウの左下の点は、実験で使うポリゴンデータの最小包含矩形内からランダムに選んだ。ウィンドウの幅と高さは、図２８には、実際にポリゴンがウィンドウに交差する場合の結果（処理時間）を、図２９には、実際にはポリゴンがウィンドウに交差しない場合の結果（処理時間）を示している。ウィンドウ・クエリーの処理時間は、おおよそ頂点数に比例することが確かめられた。
【産業上の利用可能性】
【０１０８】
本発明は、例えば多角形や立体などの広がりを持った空間物を含む種々の次元の空間データを扱う空間データベースの構築に有用である。
【図面の簡単な説明】
【０１０９】
【図１】４個の超平面によって形成される超平面アレンジメントフェイスの例を示す図である。
【図２】空間物を超平面アレンジメントフェイス複体として表した例を示す図である。
【図３】ｋ次元の超平面アレンジメントフェイスを示す図である。
【図４】（ａ）は非有界な領域を含む空間物を超平面アレンジメントフェイス複体として表した例を示す図、（ｂ）は孤立領域を含む空間物を超平面アレンジメントフェイス複体として表した例を示す図、（ｃ）は穴を含む空間物を超平面アレンジメントフェイス複体として表した例を示す図、（ｄ）は様々な次元の要素を含む空間物を超平面アレンジメントフェイス複体として表した例を示す図である。
【図５】本発明の実施の形態における空間物データ処理プログラムを実行したコンピュータの機能ブロック図である。
【図６】超平面集合形成手段による処理の詳細を示すフロー図である。
【図７】超平面アレンジメントフェイス複体形成手段による処理の詳細を示すフロー図である。
【図８】超平面アレンジメントフェイスの境界と閉包の例を示す図である。
【図９】構造オペレーションの例を示す図である。
【図１０】幾何オペレーションの例を示す図である。
【図１１】位相関係述語の例を示す図である。
【図１２】本発明の実施の形態における空間物データ処理プログラムを実行したコンピュータによる空間物のオペレーション処理手順を示すフロー図である。
【図１３】空間物を３つの２次元の独立超平面アレンジメントフェイス集合で表現した例を示す図である。
【図１４】２ステップリファインメントの例を示す図である。
【図１５】ＦＡ法の処理手順を示すフロー図である。
【図１６】ＧＣ法の処理手順を示すフロー図である。
【図１７】テスト用のデータを示す図である。
【図１８】ランダムに選んだ独立超平面アレンジメントフェイスを示す図である。
【図１９】ＦＡ法とＧＣ法による積intersect（ΓAN，ΓBN）の比較結果を示す図である。
【図２０】ＦＡ法とＧＣ法による積intersect（ΓAN，ΓCN）の比較結果を示す図である。
【図２１】ＦＡ法とＧＣ法による積intersect（ΓAN，ΓCN）の比較結果を示す図である。
【図２２】コースリファインメントの有無による積intersect（ΓAN，ΓBN）の比較結果を示す図である。
【図２３】コースリファインメントの有無による積intersect（ΓAN，ΓCN）の比較結果を示す図である。
【図２４】コースリファインメントの有無による積intersect（ΓAN，ΓCN）の比較結果を示す図である。
【図２５】局所分割統治法と逐次添加法と分割統治法による積intersect（ΓAN，ΓBN）の比較結果を示す図である。
【図２６】局所分割統治法と逐次添加法と分割統治法による積intersect（ΓAN，ΓCN）の比較結果を示す図である。
【図２７】局所分割統治法と逐次添加法と分割統治法による積intersect（ΓAN，ΓCN）の比較結果を示す図である。
【図２８】Ｓｅｑｕｏｉａ２０００ポリゴンデータテストにおいて実際にポリゴンがウィンドウに交差する場合の結果を示す図である。
【図２９】Ｓｅｑｕｏｉａ２０００ポリゴンデータテストにおいて実際にはポリゴンがウィンドウに交差しない場合の結果を示す図である。
【符号の説明】
【０１１０】
１１  空間物データ記憶手段
１２  超平面集合記憶手段
１３  超平面アレンジメントフェイス集合記憶手段
１４  超平面アレンジメントフェイス複体記憶手段
２１  超平面集合形成手段
２２  超平面アレンジメントフェイス集合形成手段
２３  超平面アレンジメントフェイス複体形成手段
２４  空間オペレーション手段
【図１】
2005038204.tif 000008
【図２】
2005038204.tif 000009
【図３】
2005038204.tif 000010
【図４】
2005038204.tif 000011
【図５】
2005038204.tif 000012
【図６】
2005038204.tif 000013
【図７】
2005038204.tif 000014
【図８】
2005038204.tif 000015
【図９】
2005038204.tif 000016
【図１０】
2005038204.tif 000017
【図１１】
2005038204.tif 000018
【図１２】
2005038204.tif 000019
【図１３】
2005038204.tif 000020
【図１４】
2005038204.tif 000021
【図１５】
2005038204.tif 000022
【図１６】
2005038204.tif 000023
【図１７】
2005038204.tif 000024
【図１８】
2005038204.tif 000025
【図１９】
2005038204.tif 000026
【図２０】
2005038204.tif 000027
【図２１】
2005038204.tif 000028
【図２２】
2005038204.tif 000029
【図２３】
2005038204.tif 000030
【図２４】
2005038204.tif 000031
【図２５】
2005038204.tif 000032
【図２６】
2005038204.tif 000033
【図２７】
2005038204.tif 000034
【図２８】
2005038204.tif 000035
【図２９】
2005038204.tif 000036