(57)【要約】【課題】面同士の接触関係の判定をより適切に行えるようにする。【解決手段】接触面検出システムが、第１多面体の頂点の座標データと第２多面体の頂点の座標データとを取得する座標データ取得部と、前記第１多面体を形成する面から第１面を選択し、前記第２多面体を形成する面から第２面を選択する面選択部と、前記第１面を形成する第１多角形の頂点のうち少なくとも１つの頂点が、前記第２面を形成する第２多角形に内包されているか否かを判定する内包判定部と、前記内包判定部の判定結果に応じて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する接触面検出部と、を具備する。【選択図】図１
2014211822.tif 000002
【特許請求の範囲】
【請求項１】
第１多面体の頂点の座標データと第２多面体の頂点の座標データとを取得する座標データ取得部と、
前記第１多面体を形成する面から第１面を選択し、前記第２多面体を形成する面から第２面を選択する面選択部と、
前記第１面を形成する第１多角形の頂点のうち少なくとも１つの頂点が、前記第２面を形成する第２多角形に内包されているか否かを判定する内包判定部と、
前記内包判定部の判定結果に応じて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する接触面検出部と、
を具備することを特徴とする接触面検出システム。
【請求項２】
前記内包判定部は、
点が凸多角形に内包されるか否かの判定を、当該点と、当該凸多角形の頂点のうち隣り合う２つの頂点の各々とを結ぶ線分と、当該隣り合う２つの頂点を結ぶ辺とで構成される三角形の面積の、当該凸多角形の頂点のうち隣り合う２つの頂点の全ての組み合わせについての合計と、当該凸多角形の面積との比較にて行う面積比較部を具備し、
前記第１多角形の頂点のうち少なくとも１つの頂点と、前記第２多角形または当該第２多角形を分割して得られる凸多角形を前記面積比較部に適用して、前記第１多角形の頂点のうち少なくとも１つの頂点が、前記第２多角形に内包されているか否かを判定する、ことを特徴とする請求項１に記載の接触面検出システム。
【請求項３】
前記第２多角形を、当該第２多角形の１つの頂点と、当該頂点と隣り合う頂点以外の各頂点とを結ぶ線分にて三角形に分割する分割部を具備し、
前記内包判定部は、前記第１多角形の頂点のうち少なくとも１つの頂点と、前記分割部の分割にて得られる三角形のうち少なくとも１つの三角形とを前記面積比較部に適用して、前記第１多角形の頂点のうち少なくとも１つの頂点が、前記第２多角形に内包されているか否かを判定する、ことを特徴とする請求項２に記載の接触面検出システム。
【請求項４】
前記第１多角形の辺と前記第２多角形の辺とが交差するか否かを判定する交差判定部を具備し、
前記接触面検出部は、前記内包判定部の判定結果と前記交差判定部の判定結果とに応じて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する、ことを特徴とする請求項１から３のいずれか一項に記載の接触面検出システム。
【請求項５】
第１構造物の形状に対応した第１多面体と第２構造物の形状に対応した第２多面体とについて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する請求項１から４のいずれか一項に記載の接触面検出システムと、
前記接触面検出システムが検出した接触状況に基づいて、前記第１構造物または前記第２構造物の少なくとも一部について、当該構造物を構成する部材の経時的な状態変化を算出する状態変化算出部と、
を具備することを特徴とする状態変化算出システム。
【請求項６】
ある点の座標データと多角形の頂点の座標データとを取得する座標データ取得部と、
前記ある点と、前記多角形の頂点のうち隣り合う２つの頂点の各々とを結ぶ線分と、当該隣り合う２つの頂点を結ぶ辺とで構成される三角形の面積の、前記多角形の頂点のうち隣り合う２つの頂点の全ての組み合わせについての合計と、前記多角形の面積とが等しいか否かを判定し、判定結果に応じて、前記ある点が、前記多角形に内包されているか否かを判定する内包判定部と、
を具備することを特徴とする内包判定システム。
【請求項７】
接触面検出システムの接触面検出方法であって、
第１多面体の頂点の座標データと第２多面体の頂点の座標データとを取得する座標データ取得ステップと、
前記第１多面体を形成する面から第１面を選択し、前記第２多面体を形成する面から第２面を選択する面選択ステップと、
前記第１面を形成する第１多角形の頂点のうち少なくとも１つの頂点が、前記第２面を形成する第２多角形に内包されているか否かを判定する内包判定ステップと、
前記内包判定ステップでの判定結果に応じて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する接触面検出ステップと、
を具備することを特徴とする接触面検出方法。
【請求項８】
接触面検出システムが備えるコンピュータに、
第１多面体の頂点の座標データと第２多面体の頂点の座標データとを取得する座標データ取得ステップと、
前記第１多面体を形成する面から第１面を選択し、前記第２多面体を形成する面から第２面を選択する面選択ステップと、
前記第１面を形成する第１多角形の頂点のうち少なくとも１つの頂点が、前記第２面を形成する第２多角形に内包されているか否かを判定する内包判定ステップと、
前記内包判定ステップでの判定結果に応じて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する接触面検出ステップと、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、接触面検出システム、状態変化算出システム、内包判定システム、接触面検出方法およびプログラムに関する。
【背景技術】
【０００２】
複数の図形の位置関係の判定について、幾つかの技術が提案されている。例えば、特許文献１に記載の隠れ線・隠れ面演算処理方式では、図形のモデルを形成する平面を三角形に分割する。そして、４行４列の行列式演算を用いて、点が、三角形を含む平面よりも内側にあるか外側にあるかの判定や、辺と辺とが交差するか否かの判定を行って、三角形が他の三角形に隠される部分を判定する。
特許文献１では、これにより、複雑な図形同士の干渉性の判断を４行４列の行列式演算により統一的に処理することができる、とされている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開昭６１−２６５６７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、建築物を構成する個々の部材の経年劣化は、他の建築物との位置関係によって変化し得る。特に、建築物の面と他の建築物の面とが接する場合、部材の経年劣化に影響が生じる。かかる部材の経年劣化の予測では、建築物の前後関係よりも面同士の接触関係が重要となる。
一方、特許文献１に記載の技術は、図形の前後関係に起因する図形同士の干渉に関するものであり、面同士の接触関係の判定に適用した場合、不都合が生じるおそれがある。例えば、特許文献１では、辺と辺との交差を生じない接触関係の判定について十分に示されていない。
【０００５】
本発明は、このような事情を考慮してなされたものであり、その目的は、面同士の接触関係の判定をより適切に行うことができる接触面検出システム、状態変化算出システム、内包判定システム、接触面検出方法およびプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
この発明は上述した課題を解決するためになされたもので、本発明の一態様による接触面検出システムは、第１多面体の頂点の座標データと第２多面体の頂点の座標データとを取得する座標データ取得部と、前記第１多面体を形成する面から第１面を選択し、前記第２多面体を形成する面から第２面を選択する面選択部と、前記第１面を形成する第１多角形の頂点のうち少なくとも１つの頂点が、前記第２面を形成する第２多角形に内包されているか否かを判定する内包判定部と、前記内包判定部の判定結果に応じて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する接触面検出部と、を具備することを特徴とする。
【０００７】
また、本発明の他の一態様による接触面検出システムは、上述の接触面検出システムであって、前記内包判定部は、点が凸多角形に内包されるか否かの判定を、当該点と、当該凸多角形の頂点のうち隣り合う２つの頂点の各々とを結ぶ線分と、当該隣り合う２つの頂点を結ぶ辺とで構成される三角形の面積の、当該凸多角形の頂点のうち隣り合う２つの頂点の全ての組み合わせについての合計と、当該凸多角形の面積との比較にて行う面積比較部を具備し、前記第１多角形の頂点のうち少なくとも１つの頂点と、前記第２多角形または当該第２多角形を分割して得られる凸多角形を前記面積比較部に適用して、前記第１多角形の頂点のうち少なくとも１つの頂点が、前記第２多角形に内包されているか否かを判定する、ことを特徴とする。
【０００８】
また、本発明の他の一態様による接触面検出システムは、上述の接触面検出システムであって、前記第２多角形を、当該第２多角形の１つの頂点と、当該頂点と隣り合う頂点以外の各頂点とを結ぶ線分にて三角形に分割する分割部を具備し、前記内包判定部は、前記第１多角形の頂点のうち少なくとも１つの頂点と、前記分割部の分割にて得られる三角形のうち少なくとも１つの三角形とを前記面積比較部に適用して、前記第１多角形の頂点のうち少なくとも１つの頂点が、前記第２多角形に内包されているか否かを判定する、ことを特徴とする。
【０００９】
また、本発明の他の一態様による接触面検出システムは、上述の接触面検出システムであって、前記第１多角形の辺と前記第２多角形の辺とが交差するか否かを判定する交差判定部を具備し、前記接触面検出部は、前記内包判定部の判定結果と前記交差判定部の判定結果とに応じて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する、ことを特徴とする。
【００１０】
また、本発明の他の一態様による状態変化算出システムは、第１構造物の形状に対応した第１多面体と第２構造物の形状に対応した第２多面体とについて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する請求項１から４のいずれか一項に記載の接触面検出システムと、前記接触面検出システムが検出した接触状況に基づいて、前記第１構造物または前記第２構造物の少なくとも一部について、当該構造物を構成する部材の経時的な状態変化を算出する状態変化算出部と、を具備することを特徴とする。
【００１１】
また、本発明の他の一態様による内包判定システムは、ある点の座標データと多角形の頂点の座標データとを取得する座標データ取得部と、前記ある点と、前記多角形の頂点のうち隣り合う２つの頂点の各々とを結ぶ線分と、当該隣り合う２つの頂点を結ぶ辺とで構成される三角形の面積の、前記多角形の頂点のうち隣り合う２つの頂点の全ての組み合わせについての合計と、前記多角形の面積とが等しいか否かを判定し、判定結果に応じて、前記ある点が、前記多角形に内包されているか否かを判定する内包判定部と、を具備することを特徴とする。
【００１２】
また、本発明の他の一態様による接触面検出方法は、接触面検出システムの接触面検出方法であって、第１多面体の頂点の座標データと第２多面体の頂点の座標データとを取得する座標データ取得ステップと、前記第１多面体を形成する面から第１面を選択し、前記第２多面体を形成する面から第２面を選択する面選択ステップと、前記第１面を形成する第１多角形の頂点のうち少なくとも１つの頂点が、前記第２面を形成する第２多角形に内包されているか否かを判定する内包判定ステップと、前記内包判定ステップでの判定結果に応じて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する接触面検出ステップと、を具備することを特徴とする。
【００１３】
また、本発明の他の一態様によるプログラムは、接触面検出システムが備えるコンピュータに、第１多面体の頂点の座標データと第２多面体の頂点の座標データとを取得する座標データ取得ステップと、前記第１多面体を形成する面から第１面を選択し、前記第２多面体を形成する面から第２面を選択する面選択ステップと、前記第１面を形成する第１多角形の頂点のうち少なくとも１つの頂点が、前記第２面を形成する第２多角形に内包されているか否かを判定する内包判定ステップと、前記内包判定ステップでの判定結果に応じて、前記第１多面体を形成する面のうち前記第２多面体を形成する面に接する面を検出する接触面検出ステップと、を実行させるためのプログラムである。
【発明の効果】
【００１４】
この発明によれば、面同士の接触関係の判定をより適切に行うことができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の第１の実施形態における接触面検出システムの機能構成を示す概略ブロック図である。
【図２】同実施形態における座標データ取得部がデータを取得する多面体の例を示す説明図である。
【図３】同実施形態における分割部が行う多角形の分割の例を示す説明図である。
【図４】同実施形態における面選択部が選択する面の例を示す説明図である。
【図５】同実施形態における面選択部が選択する面の、もう１つの例を示す説明図である。
【図６】２つの三角形の位置関係の例を示す説明図である。
【図７】同実施形態における面積比較部が面積の合計を算出する三角形の例を示す説明図である。
【図８】同実施形態における面積比較部が面積の合計を算出する三角形の、もう１つの例を示す説明図である。
【図９】交差する２つの辺の例を示す説明図である。
【図１０】交差しない２つの辺の例を示す説明図である。
【図１１】交差しない２つの辺の、もう１つの例を示す説明図である。
【図１２】同実施形態における結果出力部による接触面検出部の判定結果の表示例を示す説明図である。
【図１３】同実施形態において、接触面検出システムが多面体の接触面を検出する処理手順の例を示す説明図である。
【図１４】同実施形態において、面選択部が同一平面に含まれる面を検出する処理手順の例を示すフローチャートである。
【図１５】同実施形態において、内包判定部が、２つの面の組み合わせについて、いずれかの面を形成する多角形の頂点の少なくとも１つが、他方の面を形成する多面体に内包されるか否かを判定する処理手順の例を示すフローチャートである。
【図１６】同実施形態において、交差判定部が、２つの面の組み合わせについて、一方の面に含まれる三角形の辺と他方の面に含まれる三角形の辺との交差の有無を判定する処理手順の例を示すフローチャートである。
【図１７】本発明の第２の実施形態における状態変化算出システムの機能構成を示す概略ブロック図である。
【図１８】本発明の第３の実施形態における内包判定システムの機能構成を示す概略ブロック図である。
【発明を実施するための形態】
【００１６】
＜第１の実施形態＞
以下、図面を参照して、本発明の実施の形態について説明する。
図１は、本発明の第１の実施形態における接触面検出システムの機能構成を示す概略ブロック図である。同図において、接触面検出システム１０は、座標データ取得部１１０と、分割部１２０と、面選択部１３０と、接触面検出部１４０と、結果出力部１５０とを具備する。接触面検出部１４０は、内包判定部１４１と、交差判定部１４３とを具備する。内包判定部１４１は、面積比較部１４２を具備する。
【００１７】
接触面検出システム１０は、例えば複数の建築物のモデルなど、複数の多面体における接触面を検出する。
座標データ取得部１１０は、複数の多面体の頂点の座標データを取得する。例えば、座標データ取得部１１０は、建築物のモデルとしての多面体の頂点の座標データを、ＣＡＤ（Computer Aided Design）データまたはＢＩＭ（Building Information Modeling）データにて取得する。
【００１８】
図２は、座標データ取得部１１０がデータを取得する多面体の例を示す説明図である。同図に示す例では、直方体ＡＢＣＤ−ＥＦＧＨと、直方体ａｂｃｄ−ｅｆｇｈとが示されている。座標データ取得部１１０は、これら直方体の各頂点の座標データを取得する。また、図２の例において、面ＡＢＣＤの一部と、面ａｂｃｄの一部とが接している。
以下では、座標データ取得部１１０がデータを取得する多面体のうち２つを、ぞれぞれ、第１多面体、第２多面体と表記する。従って、座標データ取得部１１０は、第１多面体の頂点の座標データと第２多面体の頂点の座標データとを取得する。
なお、座標データ取得部１１０がデータを取得する多面体は直方体に限らない。従って、第１多面体、第２多面体のいずれも直方体に限らない。
【００１９】
分割部１２０は、座標データ取得部１１０がデータを取得した多面体の面を形成する多角形の各々を、当該多角形の１つの頂点と、当該頂点と隣り合う頂点以外の各頂点とを結ぶ線分（対角線）にて三角形に分割する。分割部１２０が分割する多角形には、後述する面選択部１３０が選択する第２面を形成する第２多角形が含まれる。従って、分割部１２０は、第２多角形を、当該第２多角形の１つの頂点と、当該頂点と隣り合う頂点以外の各頂点とを結ぶ線分にて三角形に分割する。
【００２０】
図３は、分割部１２０が行う多角形の分割の例を示す説明図である。同図の例において、分割部１２０は、長方形ＡＢＣＤを対角線ＡＣにて三角形ＡＢＣと三角形ＡＣＤとに分割している。
なお、分割部１２０が行う多角形の分割は、多角形の辺と交差しない線分にて多角形を三角形に分割するものであればよい。従って、分割部１２０が、多角形の１つの頂点と、当該頂点と隣り合う頂点以外の各頂点とを結ぶ線分以外の線分を用いて多角形の分割を行うようにしてもよい。例えば、分割対象の多角形が複雑な形状の凹多角形である場合、分割部１２０が、多角形の辺と交差しない任意の対角線にて多角形を分割する処理を、分割にて得られる図形が全て三角形になるまで繰り返すようにしてもよい。
【００２１】
一方、分割部１２０が１つの頂点と、当該頂点と隣り合う頂点以外の各頂点とを結ぶ対角線にて三角形を分割することで、対角線同士の交差を回避することができ、分割にて得られる三角形の数の増大を防止することができる。また、分割部１２０が１つの頂点と、当該頂点と隣り合う頂点以外の各頂点とを結ぶ対角線にて三角形を分割することで、分割に用いる線分が明確になり、分割部１２０の行う処理の自動化が容易になる。
【００２２】
面選択部１３０は、第１多面体を形成する面から第１面を選択し、第２多面体を形成する面から第２面を選択する。具体的には、面選択部１３０は、第１多面体を形成する各面、および、第２多面体を形成する各面から、同一平面に含まれる面を検出する。例えば、面選択部１３０は、各多角形を形成する各面の３つの頂点を通る平面の方程式の係数を求め、得られた方程式の係数を比較することで、同一平面に含まれる三角形を検出する。面選択部１３０が平面の方程式を求める手法として、当該平面の単位法線ベクトルを算出して方程式の係数を求める方法など、公知の方法を用いることができる。
以下では、面選択部１３０が選択する第１面を形成する多角形を第１多角形と表記し、面選択部１３０が選択する第２面を形成する多角形を第２多角形と表記する。
【００２３】
図４は、面選択部１３０が選択する面の例を示す説明図である。同図では、図２の例における直方体ＡＢＣＤ−ＥＦＧＨと、直方体ａｂｃｄ−ｅｆｇｈとが示されており、さらに平面Ｐ１１が示されている。
図４の例において、図２の場合と同様に、長方形ＡＢＣＤと長方形ａｂｃｄとは同一平面上にある。具体的には、長方形ＡＢＣＤと長方形ａｂｃｄとは、いずれも平面Ｐ１１に含まれている。面選択部１３０は、同一平面上にある長方形ＡＢＣＤと長方形ａｂｃｄとを選択する。なお、上記のように面ＡＢＣＤの一部と、面ａｂｃｄの一部とが接している。
【００２４】
図５は、面選択部１３０が選択する面の、もう１つの例を示す説明図である。同図では、直方体ＡＢＣＤ−ＥＦＧＨと、直方体イロハニ−ホヘトチと、平面Ｐ１１とが示されている。直方体ＡＢＣＤ−ＥＦＧＨと平面Ｐ１１とは、図４の例に示すものと同一である。
図５の例において、長方形ＡＢＣＤと長方形イロハニとは同一平面上にある。具体的には、長方形ＡＢＣＤと長方形イロハニとは、いずれも平面Ｐ１１に含まれている。面選択部１３０は、同一平面上にある長方形ＡＢＣＤと長方形イロハニとを選択する。なお、図５の例の長方形ＡＢＣＤと長方形イロハニとは、互いに接してはいない。
【００２５】
このように、面選択部１３０が選択する面には、互いに接していない面が含まれる。そこで、接触面検出部１４０が、面選択部１３０の選択した面のうち、互いに接している面を検出する。
具体的には、接触面検出部１４０は、面選択部１３０が選択した第１面と第２面について、分割部１２０の分割にて得られた三角形同士が接するか否かを判定することで、第１面と第２面とが接するか否かを判定する。
【００２６】
図６は、２つの三角形の位置関係の例を示す説明図である。同図において、２つの三角形の位置関係のパターンの例としてパターンＰ１１１、Ｐ１２１、Ｐ１３１、および、Ｐ１４１〜Ｐ１４６が示されている。このうち、パターンＰ１１１は、２つの三角形が接していないパターンを示しており、他のパターンは、２つの三角形が接しているパターンを示している。
【００２７】
パターンＰ１１１では、２つの三角形のいずれの頂点も他方の三角形に内包されていない。具体的には、パターンＰ１１１において、頂点Ａ、Ｂ、Ｃのいずれも三角形ａｂｃの外に位置する。なお、ここでいう内包は、内包される点が内包する多角形の辺または頂点と重なっている場合を含む。
また、２つの三角形のいずれの辺も、他方の三角形の辺と交差していない。具体的には、辺ＡＢ、ＢＣ、ＣＡのいずれも、辺ａｂ、ｂｃ、ｃａのいずれとも交差していない。
【００２８】
パターンＰ１２１は、２つの三角形が接しているが、いずれの頂点も他方の三角形に内包されないパターンを示している。具体的には、パターンＰ１２１において、頂点Ａ、Ｂ、Ｃのいずれも三角形ａｂｃの外に位置する。また、頂点ａ、ｂ、ｃのいずれも三角形ＡＢＣの外に位置する。一方、パターンＰ１２１では、２つの三角形の辺と辺とが交差している。例えば、辺ＡＢと、辺ａｂとが交差している
このように、２つの三角形が互いに接しているが、いずれの頂点も他方の三角形に内包されない場合、２つの三角形の辺と辺との交差を検出することで、２つの三角形が互いに接すると判定することが考えられる。
【００２９】
パターンＰ１３１は、２つの三角形が接しているが、いずれの辺も他方の三角形の辺と交差しないパターンを示している。具体的には、パターンＰ１３１において、２つの三角形のいずれの辺も、他方の三角形の辺と交差していない。具体的には、辺ＡＢ、ＢＣ、ＣＡのいずれも、辺ａｂ、ｂｃ、ｃａのいずれとも交差していない。一方、パターンＰ１３１では、一方の三角形の頂点が他方の三角形に内包されている。具体的には、頂点ａ、ｂ、ｃのいずれも、三角形ＡＢＣに内包されている。
このように、２つの三角形が接しているが、いずれの辺も他方の三角形の辺と交差しない場合、他方の三角形に内包される頂点を検出することで、２つの三角形が互いに接すると判定することが考えられる。
【００３０】
パターンＰ１４１は、一方の三角形の１つの頂点（頂点Ｂ）が他方の三角形に内包されるパターンを示している。パターンＰ１４２は、一方の三角形の２つの頂点（頂点ｂおよびｃ）が他方の三角形に内包されるパターンを示している。パターンＰ１４３は、２つの三角形が互いに他方の頂点を内包するパターンを示している。具体的には、三角形ＡＢＣは、頂点ｂおよびｃを内包し、三角形ａｂｃは、頂点Ｂを内包している。
【００３１】
パターンＰ１４４は、２つの三角形が一致しているパターンを示している。パターンＰ１４５は、２つの三角形の２つの頂点がそれぞれ一致し、他の１つの頂点の一方が、他方の三角形に内包されるパターンを示している。パターンＰ１４６は、２つの三角形の２つの頂点がそれぞれ一致し、他の１つの頂点は、いずれも他方の三角形に内包されていないパターンを示す。
【００３２】
パターンＰ１４１〜Ｐ１４６では、いずれも、２つの三角形が互いに接触している。また、パターンＰ１４１〜Ｐ１４６では、いずれも、他方の三角形に内包されている頂点があり、かつ、他方の三角形の辺と交差する辺がある。
以上のように、２つの三角形の辺と辺との交差の検出、および、他方の三角形に内包される頂点の検出の両方を行い、いずれか一方でも検出に成功した場合は、２つの三角形が互いに接触していると判定できる。
【００３３】
接触面検出部１４０は、内包判定部１４１にて、他方の三角形に内包される頂点の有無の判定を行う。また、接触面検出部１４０は、交差判定部１４３にて、２つの三角形の辺と辺との交差の有無の判定を行う。そして、接触面検出部１４０は、内包判定部１４１の判定結果と、交差判定部１４３の判定結果とに応じて、第１多面体を形成する面のうち第２多面体を形成する面に接する面を検出する。
【００３４】
上記のように、内包判定部１４１は、他方の三角形に内包される頂点の有無の判定を行う。この判定により、内包判定部１４１は、第１面を形成する第１多角形の頂点のうち少なくとも１つの頂点が、第２面を形成する第２多角形に内包されているか否かを判定する。
内包判定部１４１において、面積比較部１４２は、点が凸多角形に内包されるか否かの判定を、点と凸多角形の頂点とを結んで得られる三角形の面積の合計と、凸多角形の面積との比較にて行う。より具体的には、面積比較部１４２は、点と、凸多角形の頂点のうち隣り合う２つの頂点の各々とを結ぶ線分と、当該隣り合う２つの頂点を結ぶ辺とで構成される各三角形の面積を算出する。そして、面積比較部１４２は、各三角形の面積の合計を算出する。すなわち、面積比較部１４２は、凸多角形の頂点のうち隣り合う２つの頂点の全ての組み合わせについて、上記の三角形の面積の合計を算出する。さらに、面積比較部１４２は、算出した面積の合計と、凸多角形の面積との比較にて、点が凸多角形に内包されるか否かを判定する。
【００３５】
図７は、面積比較部１４２が面積の合計を算出する三角形の例を示す説明図である。同図において、点ａ、三角形ＡＢＣは、それぞれ、面積比較部１４２が取得する点、凸多角形の一例に該当する。例えば、面積比較部１４２は、第１多角形の１つの頂点と、分割部１２０が第２多角形を分割して得られた三角形とを取得する。
【００３６】
図７の例において、面積比較部１４２は、まず、三角形ａＡＢの面積と、ａＢＣの面積と、ａＣＡの面積とを算出する。面積比較部１４２が三角形の面積を算出する手法として、ベクトルの外積から三角形の面積を算出する手法など公知の手法を用いることができる。例えば、面積比較部１４２は、ベクトルａＡとベクトルａＢとの外積から三角形ａＡＢの面積を算出する。
【００３７】
次に、面積比較部１４２は、三角形ａＡＢ、ａＢＣ、ａＣＡの面積の合計を算出する。
また、面積比較部１４２は、三角形ＡＢＣの面積を算出する。そして、面積比較部１４２は、三角形ａＡＢ、ａＢＣ、ａＣＡの面積の合計と、三角形ＡＢＣの面積とを比較する。
【００３８】
図７の例では、点ａは三角形ＡＢＣに内包されている。この場合、線分ａＡ、ａＢおよびａＣによって、三角形ＡＢＣが三角形ａＡＢ、ａＢＣおよびａＣＡに分割されている。従って、三角形ａＡＢ、ａＢＣ、ａＣＡの面積の合計と、三角形ＡＢＣの面積とが等しくなっている。
このように、点が三角形に内包されている場合、点と、三角形の頂点のうち隣り合う２つの頂点の各々とを結ぶ線分と、当該隣り合う２つの頂点を結ぶ辺とで構成される各三角形の面積と、三角形の面積とが等しくなる。
そこで、面積比較部１４２は、三角形の面積の合計と凸多角形の面積とが等しいと判定した場合、点が多角形に内包されていると判定する。
【００３９】
なお、面積比較部１４２がベクトルの外積から三角形の面積を算出する際、平方根演算における丸め誤差などの誤差が生じることが考えられる。かかる誤差に対応するため、面積比較部１４２が、三角形の面積の合計と凸多角形の面積との比較において、完全一致に限らず、差の大きさが充分小さいと評価し得る場合にも等しいと判定するようにしてもよい。例えば、三角形の面積の合計と凸多角形の面積との差の大きさを凸多角形の面積で除算した値が所定の閾値以下である場合に、面積比較部１４２が、三角形の面積の合計と凸多角形の面積とが等しいと判定するようにしてもよい。
【００４０】
図８は、面積比較部１４２が面積の合計を算出する三角形の、もう１つの例を示す説明図である。図７の場合と同様、点ａ、三角形ＡＢＣは、それぞれ、面積比較部１４２が取得する点、凸多角形の一例に該当する。図７の場合と同様、面積比較部１４２は、三角形ａＡＢ、ａＢＣ、ａＣＡの面積との合計と、三角形ＡＢＣの面積とを比較する。
【００４１】
図８の例では、点ａは三角形ＡＢＣに内包されていない。そして、三角形ａＡＢは、三角形ＡＢＣと重なっていない。また、三角形ａＢＣ、ａＣＡは、いずれも一部が三角形ＡＢＣと重なっていない。このため、三角形ａＡＢ、ａＢＣ、ａＣＡの面積の合計が、三角形ＡＢＣの面積よりも大きくなっている。
このように、点が三角形に内包されていない場合、点と、三角形の頂点のうち隣り合う２つの頂点の各々とを結ぶ線分と、当該隣り合う２つの頂点を結ぶ辺とで構成される各三角形の面積が、三角形の面積よりも大きくなる。
そこで、面積比較部１４２は、三角形の面積の合計と凸多角形の面積とが異なると判定した場合、点が多角形に内包されていないと判定する。
【００４２】
内包判定部１４１は、第１多角形の頂点のうち少なくとも１つの頂点と、第２多角形または当該第２多角形を分割して得られる凸多角形を面積比較部１４２に適用して、第１多角形の頂点のうち少なくとも１つの頂点が、第２多角形に内包されているか否かを判定する。
具体的には、内包判定部１４１は、第１多角形の頂点のうち少なくとも１つの頂点と、分割部１２０の分割にて得られる三角形のうち少なくとも１つの三角形とを面積比較部１４２に適用して、第１多角形の頂点のうち少なくとも１つの頂点が、第２多角形に内包されているか否かを判定する。
【００４３】
ただし、面積比較部１４２は、三角形に限らず凸多角形に点が内包されるか否かの判定を行うことができる。従って、内包判定部１４１が、分割部１２０の分割にて得られた三角形に限らず凸多角形を面積比較部１４２に適用するようにしてもよい。
例えば、座標データ取得部１１０がデータを取得する多面体の面が全て凸多角形である場合、内包判定部１４１が、当該多面体の面を面積比較部１４２に適用するようにしてもよい。この場合、第１多角形の頂点のうち少なくとも１つの頂点が、第２多角形に内包されているか否かの判定に関して、分割部１２０は多角形の分割を行う必要がない。
【００４４】
交差判定部１４３は、第１多角形の辺と第２多角形の辺とが交差するか否かを判定する。交差判定部１４３が線分と線分との交差の有無を判定する手法として、例えばベクトルの外積を用いる手法など公知の手法を用いることができる。
図９は、交差する２つの辺の例を示す説明図である。同図において、線分ａｂは第１多角形の辺の一例に該当し、線分ＡＢは第２多角形の辺の一例に該当する。
【００４５】
図９の例では、線分ＡＢから見て点ａと点ｂとが反対側に位置している。このため、（ベクトルＡＢ）×（ベクトルＡａ）にて得られる法線ベクトルと、（ベクトルＡＢ）×（ベクトルＡｂ）にて得られる法線ベクトルとは逆向きになる。但し「×」はベクトルの外積を示す。
同様に、（ベクトルａｂ）×（ベクトルａＡ）にて得られる法線ベクトルと、（ベクトルａｂ）×（ベクトルａＢ）にて得られる法線ベクトルとは逆向きになる。
このように、いずれの辺を基準にしても法線ベクトルが逆向きになる場合、２つの辺が交差していると判定することができる。
【００４６】
図１０は、交差しない２つの辺の例を示す説明図である。図９の場合と同様、線分ａｂは第１多角形の辺の一例に該当し、線分ＡＢは第２多角形の辺の一例に該当する。
図９の場合と同様、図１０においても、線分ＡＢから見て点ａと点ｂとが反対側に位置している。このため、（ベクトルＡＢ）×（ベクトルＡａ）にて得られる法線ベクトルと、（ベクトルＡＢ）×（ベクトルＡｂ）にて得られる法線ベクトルとは逆向きになる。
一方、線分ａｂから見て点Ａと点Ｂとは同じ側に位置している。このため、（ベクトルａｂ）×（ベクトルａＡ）にて得られる法線ベクトルと、（ベクトルａｂ）×（ベクトルａＢ）にて得られる法線ベクトルとは同じ向きになる。
このように、一方の辺を基準にすると法線ベクトルが逆向きになるが、他方の辺を基準にすると法線ベクトルの向きが同じである場合、２つの辺は交差していないと判定することができる。
【００４７】
図１１は、交差しない２つの辺の、もう１つの例を示す説明図である。図９の場合と同様、線分ａｂは第１多角形の辺の一例に該当し、線分ＡＢは第２多角形の辺の一例に該当する。
図１１の例では、線分ＡＢから見て点ａと点ｂとは同じ側に位置している。このため、（ベクトルＡＢ）×（ベクトルＡａ）にて得られる法線ベクトルと、（ベクトルＡＢ）×（ベクトルＡｂ）にて得られる法線ベクトルとは同じ向きになる。
同様に、（ベクトルａｂ）×（ベクトルａＡ）にて得られる法線ベクトルと、（ベクトルａｂ）×（ベクトルａＢ）にて得られる法線ベクトルとも同じ向きになる。
このように、いずれの辺を基準にしても法線ベクトルの向きが同じである場合、２つの辺は交差していないと判定することができる。
【００４８】
以上より、交差判定部１４３は、いずれの辺を基準にしても法線ベクトルが逆向きになる場合は、２つの辺が交差していると判定し、いずれか一方でも法線ベクトルの向きが同じである場合は、２つの辺が交差していないと判定する。
【００４９】
結果出力部１５０は、接触面検出部１４０の判定結果を出力する。具体的には、結果出力部１５０は、例えば液晶パネル等の表示画面を有し、接触面検出部１４０の判定結果を表示する。
図１２は、結果出力部１５０による接触面検出部１４０の判定結果の表示例を示す説明図である。
同図において、接触面検出部１４０の判定結果を表形式で表示している。行、列のいずれも多面体の面の１つに対応しており、行と列の交差する欄の記載にて、対応する２つの面の接触の有無を示している。
【００５０】
例えば、立体Ｉの面ＡＢＣＤの行において、結果出力部１５０は、同じ立体Ｉの各面については、ハッチングにて接触の有無の判定対象外であることを示している。また、面ＡＢＣＤと面ａｂｃｄとが接触しており、結果出力部１５０は、面ＡＢＣＤの行において面ａｂｃｄの列と交差する欄に「ａｂｃｄ」と表示することで、接触有りを示している。一方、面ＡＢＣＤと他の面とは接触しておらず、結果出力部１５０は、面ＡＢＣＤの行において他の面の列と交差する欄を空欄とすることで、接触無しを示している。
【００５１】
次に、図１３〜図１６を参照して、接触面検出システム１０の動作について説明する。
図１３は、接触面検出システム１０が多面体の接触面を検出する処理手順の例を示す説明図である。
同図の処理において、まず、座標データ取得部１１０が、接触面検出対象としての複数の多面体の頂点の座標データを取得する（ステップＳ１０１）。
次に、分割部１２０は、座標データ取得部１１０がデータを取得した複数の多面体の面を形成する多角形の各々を三角形に分割する（ステップＳ１０２）。
また、面選択部１３０は、座標データ取得部１１０がデータを取得した複数の多面体の面のうち同一平面に含まれる面を検出する（ステップＳ１０３）。
【００５２】
図１４は、面選択部１３０が同一平面に含まれる面を検出する処理手順の例を示すフローチャートである。面選択部１３０は、図１３のステップＳ１０３において図１４の処理を行う。
図１４の処理において、面選択部１３０は、まず、座標データ取得部１１０がデータを取得した複数の多面体の各面について処理を行うループＬ２１を開始する（ステップＳ２０１）。
そして、面選択部１３０は、ループＬ２１において処理対象となっている面に含まれる２つのベクトルを算出する（ステップＳ２０２）。例えば、面選択部１３０は、ループＬ２１において処理対象となっている面を分割部１２０が分割して得られた三角形の１つについて、２つの辺に相当するベクトルを、それぞれ算出する。
【００５３】
次に、面選択部１３０は、ステップＳ２０２で得られた２つのベクトルの外積を算出する（ステップＳ２０３）。この外積は、２つのベクトルを含む平面の法線ベクトルを示している。
そして、面選択部１３０は、ステップＳ２０３で算出した外積に基づいて、平面の方程式の係数を算出する（ステップＳ２０４）。具体的には、面選択部１３０は、ステップＳ２０３で算出した外積を当該外積の大きさで除算して、単位法線ベクトルを算出する。そして、面選択部１３０は、得られた単位法線ベクトルの座標値を、平面の方程式の傾きを示す係数とする。さらに、面選択部１３０は、方程式を求める対象となっている平面に含まれる点の座標値に対して方程式が成立するように、切片の係数を設定する。
【００５４】
例えば、単位法線ベクトルの座標値が（ｖｘ，ｖｙ，ｖｚ）である場合、面選択部１３０は、式（１）に示される平面の方程式の係数を、ａ：＝ｖｘ、ｂ：＝ｖｙ，ｃ：＝ｖｚに設定する。
【００５５】
【数１】
2014211822.tif 000003
【００５６】
但し、ここでの「・」はスカラー積を示す。さらに、点（Ｐｘ，Ｐｙ，Ｐｚ）が当該平面に含まれる場合、面選択部１３０は、平面の方程式の係数を、ｄ：＝−（ａ・Ｐｘ＋ｂ・Ｐｙ＋ｃ・Ｐｚ）に設定する。
【００５７】
ステップＳ２０４の後、面選択部１３０は、座標データ取得部１１０がデータを取得した複数の多面体の全ての面についてループＬ２１の処理を行ったか否かを判定し、判定結果に基づいて分岐を行う（ステップＳ２０５）。未だループＬ２１の処理を行っていない面が存在すると判定した場合、ステップＳ２０１へ戻り、未処理の面に対して引き続きループＬ２１の処理を行う。一方、全ての面に対してループＬ２１の処理を行ったと判定した場合、ループＬ２１を終了する。
【００５８】
ループＬ２１を終了すると、面選択部１３０は、座標データ取得部１１０がデータを取得した複数の多面体のうち２つの多面体に含まれる各１つの面の組み合わせについて処理を行うループＬ２２を開始する（ステップＳ２１１）。
そして、面選択部１３０は、ループＬ２２にて処理対象となっている面の組み合わせについて、係数の絶対値（｜ａ｜、｜ｂ｜、｜ｃ｜および｜ｄ｜）がいずれも等しいか否かを判定する（ステップＳ２１２）。
【００５９】
係数の絶対値がいずれも等しいと判定した場合（ステップＳ２１２：ＹＥＳ）、面選択部１３０は、さらに係数（ａ、ｂ、ｃ、およびｄ）の正負がいずれも同じまたはいずれも逆であるか否かを判定する（ステップＳ２１３）。なお、係数の値が共にゼロの場合は、係数の正負がいずれも同じ、いずれも逆のどちらも成立しているものとして扱う。
係数の正負がいずれも同じまたはいずれも逆であると判定した場合（ステップＳ２１３：ＹＥＳ）、面選択部１３０は、ループＬ２２にて処理対象となっている２つの面が同一平面に含まれると判定する（ステップＳ２２１）。
【００６０】
次に、面選択部１３０は、座標データ取得部１１０がデータを取得した複数の多面体のうち２つの多面体に含まれる各１つの面の全ての組み合わせについてループＬ２２の処理を行ったか否かを判定し、判定結果に基づいて分岐を行う（ステップＳ２４１）。未だループＬ２２の処理を行っていない組み合わせが存在すると判定した場合、ステップＳ２１１へ戻り、未処理の組み合わせに対して引き続きループＬ２２の処理を行う。一方、全ての組み合わせに対してループＬ２２の処理を行ったと判定した場合、ループＬ２２を終了する。
ループＬ２２を終了すると、面選択部１３０は、図１４の処理を終了する。
【００６１】
一方、ステップＳ２１２において、絶対値の等しくない係数があると判定した場合（ステップＳ２１２：ＮＯ）、面選択部１３０は、ループＬ２２にて処理対象となっている２つの面が同一平面に含まれないと判定する（ステップＳ２３１）。
その後、ステップＳ２４１へ進む。
また、ステップＳ２１３において、正負がいずれも同じまたはいずれも逆にはなっていないと判定した場合（ステップＳ２１３：ＮＯ）、ステップＳ２３１へ進む。
【００６２】
なお、面選択部１３０が外積の大きさを算出する際の平方根演算における丸め誤差などの誤差が生じることが考えられる。かかる誤差に対応するため、面選択部１３０が、ステップＳ２１２における係数の絶対値の比較において、完全一致に限らず、差の大きさが充分小さいと評価し得る場合にも等しいと判定するようにしてもよい。例えば、係数の絶対値の差の大きさが所定の閾値以下である場合に、面選択部１３０が、係数の絶対値が等しいと判定するようにしてもよい。
【００６３】
また、面選択部１３０は、判定対象となっている面の各々に含まれる３つの点の座標値を得られれば図１４の処理を行うことができる。従って、図１３の処理において、ステップＳ１０２よりもステップＳ１０３を先に実行するようにしてもよいし、ステップＳ１０２とステップＳ１０３とを並列して実行するようにしてもよい。
【００６４】
図１３の処理に戻って、ステップＳ１０３の後、内包判定部１４１は、ステップＳ１０３において面選択部１３０が選択した２つの面の組み合わせ（同一平面に含まれると判定した２つの面の組み合わせ）の各々について、内包関係の有無を判定する（ステップＳ１０４）。具体的には、内包判定部１４１は、ステップＳ１０３において面選択部１３０が選択した２つの面の組み合わせの各々について、いずれかの面を形成する多角形の頂点の少なくとも１つが、他方の面を形成する多面体に内包されるか否かを判定する。
【００６５】
図１５は、内包判定部１４１が、２つの面の組み合わせについて、いずれかの面を形成する多角形の頂点の少なくとも１つが、他方の面を形成する多面体に内包されるか否かを判定する処理手順の例を示すフローチャートである。内包判定部１４１は、図１３のステップＳ１０４において、面選択部１３０が選択した２つの面の組み合わせの各々について図１５の処理を行う。
【００６６】
図１５の処理において、内包判定部１４１は、まず、分割部１２０の分割にて得られた三角形を、２つの面について１つずつ選択する組み合わせ毎に処理を行うループＬ３１を開始する（ステップＳ３０１）。
さらに、内包判定部１４１は、ステップＳ３０１で選択した２つの三角形の各々について当該三角形と他方の三角形の頂点毎に処理を行うループＬ３２を開始する（ステップ３０２）。
【００６７】
そして、内包判定部１４１は、ループＬ３２で処理対象となっている三角形と頂点とを面積比較部１４２に適用し、面積比較部１４２は、当該三角形の面積を算出する（ステップＳ３０３）。
次に、面積比較部１４２は、図７および図８を参照して説明したのと同様に、ループＬ３２で処理対象となっている頂点と、三角形の頂点のうち隣り合う頂点とで形成される各三角形の面積を算出し、面積の合計を算出する（ステップＳ３０４）。
【００６８】
そして、面積比較部１４２は、ステップＳ３０４で得られた面積の合計と、ステップＳ３０３で得られた面積（元の三角形の面積）とが等しいか否かを判定する（ステップＳ３０５）。
面積の合計が元の三角形の面積に等しいと判定した場合（ステップＳ３０５：ＹＥＳ）、面積比較部１４２は、ループＬ３２で処理対象となっている頂点が、ループＬ３２で処理対象となっている三角形に内包されていると判定する（ステップＳ３１１）。
【００６９】
次に、内包判定部１４１は、ステップＳ３０１で選択した２つの三角形のいずれについても、当該三角形と他方の三角形の頂点との全ての組み合わせについてループＬ３２の処理を行ったか否かを判定し、判定結果に基づいて分岐を行う（ステップＳ３３１）。未だループＬ３２の処理を行っていない組み合わせが存在すると判定した場合、ステップＳ３０２へ戻り、未処理の組み合わせに対して引き続きループＬ３２の処理を行う。一方、全ての組み合わせに対してループＬ３２の処理を行ったと判定した場合、ループＬ３２を終了する。
【００７０】
ループＬ３２を終了すると、内包判定部１４１は、分割部１２０の分割にて得られた三角形を、２つの面について１つずつ選択する全ての組み合わせについてループＬ３１の処理を行ったか否かを判定し、判定結果に基づいて分岐を行う（ステップＳ３３２）。未だループＬ３１の処理を行っていない組み合わせが存在すると判定した場合、ステップＳ３０１へ戻り、未処理の組み合わせに対して引き続きループＬ３１の処理を行う。一方、全ての組み合わせに対してループＬ３１の処理を行ったと判定した場合、ループＬ３１を終了する。
【００７１】
ループＬ３１を終了すると、内包判定部１４１は、面と面との内包関係を判定する（ステップＳ３３３）。ループＬ３２の処理における三角形と頂点との組み合わせのいずれか１つでも、内包されていると判定（ステップＳ３１１）した場合は、内包関係有りと判定する。すなわち、内包判定部１４１は、判定対象となっている２つの面の組み合わせについて、いずれかの面を形成する多角形の頂点の少なくとも１つが、他方の面を形成する多面体に内包されていると判定する。
【００７２】
一方、ループＬ３２の処理における三角形と頂点との組み合わせの全てについて、内包されていないと判定（ステップＳ３２１）した場合は、内包関係無しと判定する。すなわち、内包判定部１４１は、判定対象となっている２つの面の組み合わせについて、いずれの面を形成する多角形の頂点も、他方の面を形成する多面体に内包されていないと判定する。
ステップＳ３３３の後、図１５の処理を終了する。
【００７３】
一方、ステップＳ３０５において、面積の合計と元の三角形の面積とが異なると判定した場合（ステップＳ３０５：ＮＯ）、面積比較部１４２は、ループＬ３２で処理対象となっている頂点が、ループＬ３２で処理対象となっている三角形に内包されていないと判定する（ステップＳ３２１）。
その後、ステップＳ３３１へ進む。
【００７４】
図１３の処理に戻って、ステップＳ１０４の後、交差判定部１４３は、ステップＳ１０３において面選択部１３０が選択した２つの面の組み合わせの各々について、一方の面に含まれる三角形の辺と他方の面に含まれる三角形の辺との交差の有無を判定する（ステップＳ１０５）。
【００７５】
図１６は、交差判定部１４３が、２つの面の組み合わせについて、一方の面に含まれる三角形の辺と他方の面に含まれる三角形の辺との交差の有無を判定する処理手順の例を示すフローチャートである。交差判定部１４３は、図１３のステップＳ１０５において、面選択部１３０が選択した２つの面の組み合わせの各々について図１６の処理を行う。
【００７６】
図１６の処理において、交差判定部１４３は、まず、分割部１２０の分割にて得られた三角形を、２つの面について１つずつ選択する組み合わせ毎に処理を行うループＬ４１を開始する（ステップＳ４０１）。
さらに、交差判定部１４３は、ステップＳ４０１で選択した２つの三角形の各々から１つずつ辺を選択する組み合わせ毎に処理を行うループＬ４２を開始する（ステップ４０２）。
【００７７】
次に、交差判定部１４３は、ループＬ４２で処理対象となっている２つの辺の一方を基準として、図９〜１１を参照して説明したのと同様に、２つの法線ベクトルを算出する（ステップＳ４０３）。
そして、交差判定部１４３は、ステップＳ４０３で得られた２つの法線ベクトルの向きが逆か否かを判定する（ステップＳ４０４）。
【００７８】
法線ベクトルの向きが逆であると判定した場合（ステップＳ４０４：ＹＥＳ）、交差判定部１４３は、さらに、ステップＳ４０３の場合と異なる方の辺を基準として、図９〜１１を参照して説明したのと同様に、２つの法線ベクトルを算出する（ステップＳ４１１）。
そして、交差判定部１４３は、ステップＳ４１１で得られた２つの法線ベクトルの向きが逆か否かを判定する（ステップＳ４１２）。
法線ベクトルの向きが逆であると判定した場合（ステップＳ４１２：ＹＥＳ）、交差判定部１４３は、２つの辺が交差していると判定する（ステップＳ４２１）。
【００７９】
次に、交差判定部１４３は、ステップＳ４０１で選択した２つの三角形の各々から１つずつ辺を選択する全ての組み合わせについてループＬ４２の処理を行ったか否かを判定し、判定結果に基づいて分岐を行う（ステップＳ４４１）。未だループＬ４２の処理を行っていない組み合わせが存在すると判定した場合、ステップＳ４０２へ戻り、未処理の組み合わせに対して引き続きループＬ４２の処理を行う。一方、全ての組み合わせに対してループＬ４２の処理を行ったと判定した場合、ループＬ４２を終了する。
【００８０】
ループＬ４２を終了すると、交差判定部１４３は、分割部１２０の分割にて得られた三角形を、２つの面について１つずつ選択する全ての組み合わせについてループＬ４１の処理を行ったか否かを判定し、判定結果に基づいて分岐を行う（ステップＳ４４２）。未だループＬ４１の処理を行っていない組み合わせが存在すると判定した場合、ステップＳ４０１へ戻り、未処理の組み合わせに対して引き続きループＬ４１の処理を行う。一方、全ての組み合わせに対してループＬ４１の処理を行ったと判定した場合、ループＬ４１を終了する。
【００８１】
ループＬ４１を終了すると、交差判定部１４３は、判定対象となっている２つの面の組み合わせについて、一方の面に含まれる三角形の辺と他方の面に含まれる三角形の辺との交差の有無を判定する（ステップＳ４４３）。ループＬ４２の処理における辺と辺との組み合わせのいずれか１つでも、交差していると判定（ステップＳ４２１）した場合は、一方の面に含まれる三角形の辺と他方の面に含まれる三角形の辺とで、交差しているものがあると判定する。
一方、ループＬ４２の処理における辺と辺との組み合わせの全てについて、交差していないと判定（ステップＳ４３１）した場合は、いずれの辺も交差していないと判定する。
ステップＳ４４３の後、図１６の処理を終了する。
【００８２】
一方、ステップＳ４０４において、法線ベクトルの向きが同じであると判定した場合（ステップＳ４０４：ＮＯ）、交差判定部１４３は、２つの辺が交差していないと判定する（ステップＳ４３１）。
その後、ステップＳ４４１へ進む。
一方、ステップＳ４１２において、法線ベクトルの向きが同じであると判定した場合（ステップＳ４１２：ＮＯ）、ステップＳ４３１へ進む。
【００８３】
なお、ステップＳ４０１において、内包判定部１４１が内包関係有りと判定済みの面の組み合わせを、交差判定部１４３が処理対象から除外するようにしてもよい。
また、図１３の処理において、ステップＳ１０４とステップＳ１０５とを並列して実行するようにしてもよいし、ステップＳ１０５を実行した後、ステップＳ１０４を実行するようにしてもよい。ステップＳ１０５を実行した後、ステップＳ１０４を実行する場合、図１５のステップＳ３０１において、交差判定部１４３が辺の交差ありと判定済みの面の組み合わせを、内包判定部１４１が処理対象から除外するようにしてもよい。
【００８４】
図１３の処理に戻って、ステップＳ１０５の後、接触面検出部１４０は、互いに接触している２つの面の組み合わせを抽出する（ステップＳ１０６）。具体的には、接触面検出部１４０は、面選択部１３０が検出した、同一平面に含まれる２つの面の組み合わせのうち、内包関係ありまたは辺の交差ありのいずれか一方にでも該当する組み合わせを、互いに接触している組み合わせとして抽出する。
一方、接触面検出部１４０は、内包関係無し、かつ、辺の交差無しとされた組み合わせについては、互いに接触していないと判定する。
【００８５】
次に、結果出力部１５０は、接触面検出部１４０がステップＳ１０６で抽出した組み合わせを、接触面検出システム１０の判定結果として出力する（ステップＳ１０７）。例えば、結果出力部１５０は、図１２を参照して説明したように、面と面との接触の有無を表示する。
その後、図１３の処理を終了する。
【００８６】
以上のように、内包判定部１４１は、第１多面体の第１面を形成する第１多角形の頂点のうち少なくとも１つの頂点が、第２多面体の第２面を形成する第２多角形に内包されているか否かを判定する。そして、接触面検出部１４０は、内包判定部１４１の判定結果に応じて、第１多面体を形成する面のうち第２多面体を形成する面に接する面を検出する。
これにより、接触面検出部１４０は、辺と辺との交差を生じない接触関係を、内包関係に基づいて検出することができる。この点において、接触面検出システム１０は、面同士の接触関係の判定をより適切に行うことができる。
【００８７】
また、面積比較部１４２は、点が凸多角形に内包されるか否かの判定を、当該点と、当該凸多角形の頂点のうち隣り合う２つの頂点の各々とを結ぶ線分と、当該隣り合う２つの頂点を結ぶ辺とで構成される三角形の面積の、当該凸多角形の頂点のうち隣り合う２つの頂点の全ての組み合わせについての合計と、当該凸多角形の面積との比較にて行う。
これにより、面積比較部１４２は、三角形の面積を算出することで、点が凸多角形に内包されるか否かの判定を行うことができる。三角形の面積は、例えばベクトルの外積から算出するなど簡単な計算にて算出することができる。従って、面積比較部１４２は、点が凸多角形に内包されるか否かの判定を、簡単な計算にて行うことができる。
【００８８】
また、分割部１２０は、第２多角形を、当該第２多角形の１つの頂点と、当該頂点と隣り合う頂点以外の各頂点とを結ぶ線分にて三角形に分割する。そして、内包判定部１４１は、第１多角形の頂点のうち少なくとも１つの頂点と、分割部１２０の分割にて得られる三角形のうち少なくとも１つの三角形とを面積比較部１４２に適用して、第１多角形の頂点のうち少なくとも１つの頂点が、第２多角形に内包されているか否かを判定する。
これにより、面積比較部１４２は、凸多角形の面積の計算についても、三角形の面積を算出すればよい。従って、面積比較部１４２は、点が凸多角形に内包されるか否かの判定を、簡単な計算にて行うことができる。
【００８９】
また、交差判定部１４３は、第１多角形の辺と第２多角形の辺とが交差するか否かを判定する。そして、接触面検出部１４０は、内包判定部１４１の判定結果と交差判定部１４３の判定結果とに応じて、第１多面体を形成する面のうち第２多面体を形成する面に接する面を検出する。
これにより、接触面検出部１４０は、辺と辺との交差を生じない接触関係と、面を形成す多角形と他方の面を形成する多角形の頂点との内包関係を生じない接触関係とのいずれも検出することができ、面と面との接触関係を漏れなく検出することができる。
【００９０】
＜第２の実施形態＞
図１７は、本発明の第２の実施形態における状態変化算出システムの機能構成を示す概略ブロック図である。同図において、状態変化算出システム２０は、接触面検出システム１１と、状態変化算出部２１０と、結果出力部２５０とを具備する。接触面検出システム１１は、座標データ取得部１１０と、分割部１２０と、面選択部１３０と、接触面検出部１４０とを具備する。接触面検出部１４０は、内包判定部１４１と、交差判定部１４３とを具備する。内包判定部１４１は、面積比較部１４２を具備する。
同図において、図１の各部に対応して同様の機能を有する部分には同一の符号（１１０、１２０、１３０、１４０、１４１、１４２、１４３）を付して説明を省略する。
【００９１】
状態変化算出部２１０は、接触面検出部１４０が検出した面と面との接触状況に基づいて、座標データ取得部１１０がデータを取得する多面体にてモデル化されている構造物の少なくとも一部について、当該構造物を構成する部材の経時的な状態変化を算出する。
状態変化算出部２１０が、構造物を構成する部材の経時的な状態変化を算出する手法として、例えば特開２０１３−０３７３２１号公報に記載されている、部材に対応して定義される領域に代表点を設け、部材間に作用する影響を、影響度を示す変数によって定義する手法を用いることができる。
結果出力部２５０は、状態変化算出部２１０の算出結果を表示する。
【００９２】
以上のように、状態変化算出部２１０は、接触面検出システム１１が検出した、構造物の面の接触状況に基づいて、構造物を構成する部材の経時的な状態変化を算出する。また、接触面検出システム１０の場合と同様、接触面検出システム１１において、内包判定部１４１は、構造物の面を形成する多角形同士の内包関係を判定する。そして、接触面検出部１４０は、内包判定部１４１の判定結果に応じて、構造物を形成する面の接触状況を検出する。
これにより、接触面検出部１４０は、辺と辺との交差を生じない接触関係を、内包関係に基づいて検出することができ、状態変化算出部２１０は、辺と辺との交差を生じない接触関係に対応してより正確に部材の経時的な状況変化を算出することができる。
【００９３】
＜第３の実施形態＞
図１８は、本発明の第３の実施形態における内包判定システムの機能構成を示す概略ブロック図である。同図において、内包判定システム３０は、座標データ取得部３１０と、内包判定部１４１と、結果出力部３５０とを具備する。内包判定部１４１は、面積比較部１４２を具備する。
同図において、図１の各部に対応して同様の機能を有する部分には同一の符号（１４１、１４２）を付して説明を省略する。
【００９４】
座標データ取得部３１０は、凸多角形の頂点の座標データと、当該凸多角形に内包されるか否かの判定対象の点の座標データとを取得する。
結果出力部３５０は、内包判定部１４１による、点が凸多角形に含まれるか否かの判定結果を表示する。
【００９５】
内包判定システム３０において、内包判定部１４１は、点と、多角形の頂点のうち隣り合う２つの頂点の各々とを結ぶ線分と、当該隣り合う２つの頂点を結ぶ辺とで構成される三角形の面積の、多角形の頂点のうち隣り合う２つの頂点の全ての組み合わせについての合計と、多角形の面積とが等しいか否かを判定し、判定結果に応じて、判定対象の点が多角形に内包されているか否かを判定する。
これにより、接触面検出システム１０の場合と同様に、内包判定部１４１（面積比較部１４２）は、三角形の面積を算出することで、点が凸多角形に内包されるか否かの判定を行うことができる。三角形の面積は、例えばベクトルの外積から算出するなど簡単な計算にて算出することができる。従って、内包判定部１４１は、点が凸多角形に内包されるか否かの判定を、簡単な計算にて行うことができる。
【００９６】
なお、接触面検出システム１０や、状態変化算出システム２０や、内包判定システム３０の全部または一部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより各部の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、コンパクトディスク等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００９７】
以上、この発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【符号の説明】
【００９８】
１０  接触面検出システム
２０  状態変化算出システム
３０  内包判定システム
１１０、３１０  座標データ取得部
１２０  分割部
１３０  面選択部
１４０  接触面検出部
１４１  内包判定部
１４２  面積比較部
１４３  交差判定部
１５０、２５０、３５０  結果出力部
２１０  状態変化算出部
【図１】
2014211822.tif 000004
【図２】
2014211822.tif 000005
【図３】
2014211822.tif 000006
【図４】
2014211822.tif 000007
【図５】
2014211822.tif 000008
【図６】
2014211822.tif 000009
【図７】
2014211822.tif 000010
【図８】
2014211822.tif 000011
【図９】
2014211822.tif 000012
【図１０】
2014211822.tif 000013
【図１１】
2014211822.tif 000014
【図１２】
2014211822.tif 000015
【図１３】
2014211822.tif 000016
【図１４】
2014211822.tif 000017
【図１５】
2014211822.tif 000018
【図１６】
2014211822.tif 000019
【図１７】
2014211822.tif 000020
【図１８】
2014211822.tif 000021