(57)【要約】【課題】３次元モデル化オブジェクトを設計するためのコンピュータ実施方法を提供する。【解決手段】方法は、幾何学要素を提供するステップ（Ｓ１０）を含み、幾何学要素は、モデル化オブジェクトを表し、幾何学要素がその中で互いのコピーである組を含む。方法は、グラフを定義するステップ（Ｓ２０）と、グラフの最大の部分グラフを決定するステップ（Ｓ３０）と、最多の弧を有し、かつ弧によって表される剛体運動がすべて同一基準を順守する連結成分の組を、決定された部分グラフ内において識別するステップ（Ｓ４０）も含む。  そのような方法は、３Ｄモデル化オブジェクトの設計を改善する。【選択図】図１
2014130601.tif 000002
【特許請求の範囲】
【請求項１】
３次元モデル化オブジェクトを設計するためのコンピュータ実施方法であって、
幾何学要素を提供するステップ（Ｓ１０）であって、前記幾何学要素は、前記モデル化オブジェクトを表し、前記幾何学要素がその中で互いのコピーである組を含む、ステップ、
各々が前記組の幾何学要素を表すノードと、各々がノードのペアを連結し、前記ペアの一方のノードによって表される前記幾何学要素を前記ペアの他方のノードによって表される前記幾何学要素に変換する剛体運動を表す弧とを有するグラフを定義するステップ（Ｓ２０）、
前記弧によって表される剛体運動がすべて所定の類似基準を順守する、前記グラフの最大の部分グラフを決定するステップ（Ｓ３０）であって、前記類似基準は、所定の同一基準よりも弱い、ステップ、および
最多の弧を有し、前記弧によって表される剛体運動がすべて前記同一基準を順守する連結成分の組を、前記決定された部分グラフ内において識別するステップ（Ｓ４０）
を含むことを特徴とするコンピュータ実施方法。
【請求項２】
前記識別された組の連結成分のうちの各連結成分の前記ノードを折り畳むことによって、前記グラフを変更するステップと、
前記変更されたグラフ上で前記決定するステップ（Ｓ３０）および前記識別するステップ（Ｓ４０）を繰り返すステップと
を反復するステップをさらに含むことを特徴とする請求項１に記載のコンピュータ実施
方法。
【請求項３】
前記折り畳むステップは、
前記識別された組の連結成分のうちの任意の連結成分の任意のノードに連結されたすべての弧を削除するステップと、
各それぞれの連結成分について、前記それぞれの連結成分のすべてのノードを単一のノードに置き換えるステップと、
等大の連結成分を表すノードのペア間に弧を追加するステップであって、追加される各弧は、前記ペアの一方のノードによって表される前記連結成分を前記ペアの他方のノードによって表される前記連結成分に変換する剛体運動を表す、ステップと
を含むことを特徴とする請求項２に記載のコンピュータ実施方法。
【請求項４】
前記識別するステップ（Ｓ４０）は、
最多の弧を有する前記部分グラフを、前記決定された部分グラフ内において選択するステップ（Ｓ４１０）と、
前記選択された部分グラフの前記連結成分の各々の前記弧によって表される剛体運動がどれも前記同一基準を順守するかどうかをテストするステップ（Ｓ４２０）と
を含むことを特徴とする請求項１〜３のいずれかに記載の方法。
【請求項５】
前記識別するステップ（Ｓ４０）は、前記テストするステップ（Ｓ４２０）の結果として、
前記テストするステップ（Ｓ４２０）の結果が肯定的である場合は、連結成分の組を前記選択された部分グラフの前記連結成分として識別するステップ（Ｓ４３０）と、
前記テストするステップ（Ｓ４２０）の結果が否定的である場合は、前記選択された部分グラフを分割するステップ（Ｓ４４０）と、前記選択するステップ（Ｓ４１０）および前記テストするステップ（Ｓ４２０）を再実行するステップと
をさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記分割するステップ（Ｓ４４０）は、
前記選択された部分グラフのうちのすべての部分グラフの中で、最多の弧を有し、前記弧によって表される剛体運動がすべて前記同一基準を順守する、前記選択された部分グラフのうちの前記部分グラフの前記弧を、前記選択された部分グラフから切り取るステップと、
前記切り取られた弧を用いて新しい部分グラフを生成するステップと
を含むことを特徴とする請求項５に記載の方法。
【請求項７】
データ記憶媒体上に記録されるように適合され、請求項１乃至６のいずれかに記載の方法を実行するための命令を含むことを特徴とするコンピュータプログラム。
【請求項８】
請求項７に記載のコンピュータプログラムを記録していることを特徴とするデータ記憶媒体。
【請求項９】
メモリに結合されたプロセッサと、グラフィカルユーザインタフェースとを備え、前記メモリは、請求項７に記載のコンピュータプログラムを記録していることを特徴とするＣＡＤシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムおよびシステムの分野に関し、より詳細には、３次元（３Ｄ）モデル化オブジェクトを設計するための方法、システム、およびプログラムに関する。
【背景技術】
【０００２】
オブジェクトの設計、エンジニアリング、および製造のための数々のシステムおよびプログラムが、市場で提供されている。ＣＡＤは、コンピュータ支援設計（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ）の頭字語であり、例えば、オブジェクトを設計するためのソフトウェアソリューションに関する。ＣＡＥは、コンピュータ支援エンジニアリング（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｅｎｇｉｎｅｅｒｉｎｇ）の頭字語であり、例えば、将来の製品の物理的挙動をシミュレートするためのソフトウェアソリューションに関する。ＣＡＭは、コンピュータ支援製造（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｍａｎｕｆａｃｔｕｒｉｎｇ）の頭字語であり、例えば、製造プロセスおよび操作を定義するためのソフトウェアソリューションに関する。そのようなシステムでは、技法の効率性に関して、グラフィカルユーザインタフェース（ＧＵＩ）が重要な役割を演じる。これらの技法は、製品ライフサイクル管理（ＰＬＭ：Ｐｒｏｄｕｃｔ  Ｌｉｆｅｃｙｃｌｅ  Ｍａｎａｇｅｍｅｎｔ）システム内に組み込むことができる。ＰＬＭとは、製品の開発のために、構想から耐用期限が尽きるまで、拡大された事業の構想の全般にわたって、製品データを共有し、共通プロセスを適用し、企業知識を活用する際に企業の助けとなるビジネス戦略のことである。
【０００３】
（ＣＡＴＩＡ、ＥＮＯＶＩＡ、およびＤＥＬＭＩＡという商標の下で）Ｄａｓｓａｕｌｔ  Ｓｙｓｔｅｍｅｓによって提供されたＰＬＭソリューションは、製品エンジニアリング知識を編成するエンジニアリングハブ（Ｅｎｇｉｎｅｅｒｉｎｇ  Ｈｕｂ）、製造エンジニアリング知識を管理するマニュファクチャリングハブ（Ｍａｎｕｆａｃｔｕｒｉｎｇ  Ｈｕｂ）、ならびに、事業統合、およびエンジニアリングハブおよびマニュファクチャリングハブ両方との接続を可能にするエンタープライズハブ（Ｅｎｔｅｒｐｒｉｓｅ  Ｈｕｂ）を提供する。すべてが一緒になって、システムは、最適化された製品定義、製造準備、生産、およびサービスを推進する、動的な知識ベースの製品創造および決定支援を可能にするための、製品、プロセス、リソースを結び付けるオープンオブジェクトモデルを提供する。
【０００４】
現在、多くのＣＡＤシステムは、ユーザが、３Ｄモデル化オブジェクトを、ユーザに提供されたモデル化オブジェクトの境界表現（ｂｏｕｎｄａｒｙ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）（Ｂ−Ｒｅｐ）に基づいて設計することを可能にする。Ｂ−Ｒｅｐは、各々がそれぞれのサポート面（ｓｕｐｐｏｒｔｉｎｇ  ｓｕｒｆａｃｅ）の有界な部分として定義される１組の面分（ｆａｃｅ）を含む、データ形式である。ユーザは、既存の面分を変更すること、新しい面分を生成すること、いくつかの面分を削除すること、ならびに／または面分に対する制約および／もしくは面分の間の制約を定義すること、あるいは使用するＣＡＤシステムによって提供された任意のアクションなどによって、１組の面分に働きかけることができる。そのような場合、効率性のため、立体（ｓｏｌｉｄ）の履歴は、一般にユーザから利用可能ではない。
【０００５】
開発下にあるそのような３Ｄ設計の一側面は、「パターン認識」として知られている。「パターン」という用語は、同じ幾何学的特徴の規則的なレイアウトのコピーを指している。パターンの認識は、設計中にそのようなパターンを単一の要素として処理することを可能にし、それによって、一連の設計の可能性を広げる。例えば、パターンの要素を１つずつ変更する代わりに、パターンの事前認識のおかげで、ユーザは、パターンの変更を、例えば単一のアクションで、全体的に実行することができる。パターン認識は、機械設計、消費財、建造物建築、航空宇宙、または他の領域など、ＣＡＤの様々な領域にも関連する。
【０００６】
パターン認識は、特徴認識に関連することができる。特徴認識は、所与の３Ｄオブジェクト（通常は機械部品を表す立体）における特徴的な形状を認識するのに有益である。機械設計において関心のある特徴的な形状は、例えば、ホール（ｈｏｌｅ）、押出パッド（ｅｘｔｒｕｄｅｄ  ｐａｄ）、押出ポケット（ｅｘｔｒｕｄｅｄ  ｐｏｃｋｅｔ）、フィレット（ｆｉｌｌｅｔ）もしくはラウンド（ｒｏｕｎｄ）、外旋パッド（ｒｅｖｏｌｕｔｅ  ｐａｄ）、および／または外旋ポケット（ｒｅｖｏｌｕｔｅ  ｐｏｃｋｅｔ）を含む。特徴的な形状の認識は、例えば、押出もしくは外旋形状の輪郭、外旋形状の回転軸、ラウンドおよびフィレットの半径値、押出方向、ならびに／または押出深さなど、その仕様を、より良い意味レベルで識別することにつながる。この情報は、例えば押出の輪郭を編集することによって、形状を変更するために、または例えば機械加工プロセスなど、下流のプロセスを供給するために使用される。
【０００７】
特徴認識機能は、以下の手順を通して、商用ＣＡＤシステムにおいて利用可能である。ユーザは、認識する特徴のタイプを選択することができる。その後、任意選択で、ユーザは、探索を初期化するために、立体上の特徴の１つまたは複数の面分を選択する。システムは、認識を実行し、認識された特徴の仕様を生成する。
【０００８】
入力された立体の形状を局所的に変更することが意図される場合、「直接編集」機能も利用可能である。「履歴なしモデリング（ｈｉｓｔｏｒｙ  ｆｒｅｅ  ｍｏｄｅｌｉｎｇ）」とも呼ばれるこの技術は、履歴設計の代替として、ＣＡＤエディタによって促進される。目標は、Ｂ−Ｒｅｐだけを使用して、立体の形状を容易に変更することである。ユーザの観点から見て編集を簡潔にするために、「直接編集」技術は、立体の局所形状を認識しなければならない。例えば、システムは、ホールの円筒形状を維持すること（および円筒を自由形式面（ｆｒｅｅ  ｆｏｒｍ  ｓｕｒｆａｃｅ）に変更しないこと）、ポケットの壁の垂直方向を維持すること、ならびに／または形状の外旋性もしくは押出性を維持することを行わなければならない。結果として、「直接編集」分野であっても、特徴認識は不可避である。
【０００９】
従来の特徴認識は、一度に１つの特徴を扱う。それは、所与の特徴の複数のコピーを識別せず、これらのコピーのレイアウトを識別しない。パターン認識に関して、この主題は、未だ開発下にあるが、既存の解決策には、多くのユーザ介入が必要であると思われる。
【００１０】
したがって、既存の解決策は、特にユーザ利用の観点および網羅性の観点から見て、効率性を欠いている。これに関連して、３Ｄモデル化オブジェクトを設計するための改善された解決策が未だ必要とされている。
【発明の概要】
【００１１】
したがって、一態様によれば、３Ｄモデル化オブジェクトを設計するためのコンピュータ実施方法が提供される。方法は、幾何学要素を提供するステップを含み、幾何学要素は、モデル化オブジェクトを表し、幾何学要素がその中で互いのコピーである組を含む。方法は、各々が前記組の幾何学要素を表すノードと、各々がノードのペアを連結し、ペアの一方のノードによって表される幾何学要素をペアの他方のノードによって表される幾何学要素に変換する剛体運動を表す弧とを有するグラフを定義するステップも含む。方法は、弧によって表される剛体運動がすべて所定の類似基準（ｓｉｍｉｌａｒｉｔｙ  ｃｒｉｔｅｒｉｏｎ）を順守する、グラフの最大の部分グラフを決定するステップも含み、類似基準は、所定の同一基準（ｉｄｅｎｔｉｔｙ  ｃｒｉｔｅｒｉｏｎ）よりも弱い。また、方法は、最多の弧を有し、かつ弧によって表される剛体運動がすべて同一基準を順守する、連結成分（ｃｏｎｎｅｃｔｅｄ  ｃｏｍｐｏｎｅｎｔ）の組を、決定された部分グラフ内において識別するステップを含む。
【００１２】
方法は、以下のうちの１つまたは複数を含むことができる：
−  方法は、以下のステップ：識別された組の連結成分のうちの各連結成分のノードを折り畳む（ｃｏｌｌａｐｓｅ）ことによって、グラフを変更するステップ；変更されたグラフ上で決定するステップおよび識別するステップを繰り返すステップ；を反復するステップをさらに含み、
−  折り畳むステップは、識別された組の連結成分のうちの任意の連結成分の任意のノードに連結されたすべての弧を削除するステップと、各それぞれの連結成分について、それぞれの連結成分のすべてのノードを単一のノードに置き換えるステップと、等大（ｉｓｏｍｅｔｒｉｃ）の連結成分を表すノードのペア間に弧を追加するステップとを含み、追加される各弧は、ペアの一方のノードによって表される連結成分をペアの他方のノードによって表される連結成分に変換する剛体運動を表し、
−  識別するステップは、最多の弧を有する部分グラフを、決定された部分グラフ内において選択するステップと、選択された部分グラフの連結成分の各々の弧によって表される剛体運動がどれも同一基準を順守するかどうかをテストするステップとを含み、
−  識別するステップは、テストするステップの結果として、テストするステップの結果が肯定的である場合は、連結成分の組を選択された部分グラフの連結成分として識別するステップと、テストするステップの結果が否定的である場合は、選択された部分グラフを分割し、選択するステップおよびテストするステップを再実行するステップとをさらに含み、ならびに／または
−  分割するステップは、選択された部分グラフのうちのすべての部分グラフの中で、最多の弧を有し、かつ弧によって表される剛体運動がすべて同一基準を順守する、選択された部分グラフのうちの部分グラフの弧を、選択された部分グラフから切り取るステップと、切り取られた弧を用いて新しい部分グラフを生成するステップとを含む。
【００１３】
上述の方法を実行するための命令を含むコンピュータプログラムがさらに提案される。コンピュータプログラムは、コンピュータ可読記憶媒体に記録されるように適合される。
【００１４】
上述のコンピュータプログラムを記録しているコンピュータ可読記憶媒体がさらに提案される。
【００１５】
メモリに結合されたプロセッサと、グラフィカルユーザインタフェースとを備えるＣＡＤシステムがさらに提案され、メモリは、上述のコンピュータプログラムを記録している。
【図面の簡単な説明】
【００１６】
次に、本発明の実施形態を、非限定的な例によって、添付の図面を参照しながら説明する。
【図１】方法の一例のフローチャートである。
【図２】グラフィカルユーザインタフェースの一例を示す図である。
【図３】クライアントコンピュータシステムの一例を示す図である。
【図４】方法の例を示す図である。
【図５】方法の例を示す図である。
【図６】方法の例を示す図である。
【図７】方法の例を示す図である。
【図８】方法の例を示す図である。
【図９】方法の例を示す図である。
【図１０】方法の例を示す図である。
【図１１】方法の例を示す図である。
【図１２】方法の例を示す図である。
【図１３】方法の例を示す図である。
【図１４】方法の例を示す図である。
【図１５】方法の例を示す図である。
【図１６】方法の例を示す図である。
【図１７】方法の例を示す図である。
【図１８】方法の例を示す図である。
【図１９】方法の例を示す図である。
【図２０】方法の例を示す図である。
【図２１】方法の例を示す図である。
【図２２】方法の例を示す図である。
【図２３】方法の例を示す図である。
【図２４】方法の例を示す図である。
【図２５】方法の例を示す図である。
【図２６】方法の例を示す図である。
【図２７】方法の例を示す図である。
【図２８】方法の例を示す図である。
【図２９】方法の例を示す図である。
【図３０】方法の例を示す図である。
【発明を実施するための形態】
【００１７】
図１は、３Ｄモデル化オブジェクトを設計するためのコンピュータ実施方法のフローチャートを示している。方法は、幾何学要素を提供するステップＳ１０を含む。幾何学要素は、モデル化オブジェクトを表す。Ｓ１０において提供される幾何学要素は、幾何学要素がその中で互いのコピーである組を含む。方法は、ノードと、各々がノードのペアを連結する弧とを有するグラフを定義するステップＳ２０も含む。各ノードは、組の幾何学要素を表す。各弧は、ペアの一方のノードによって表される幾何学要素をペアの他方のノードによって表される幾何学要素に変換する剛体運動を表す。方法は、グラフの最大の部分グラフを決定するステップＳ３０も含む。Ｓ３０において決定された最大の部分グラフは、弧によって表される剛体運動がすべて所定の類似基準を順守する部分グラフの中にある。類似基準は、所定の同一基準よりも弱い。方法は、最多の弧を有し、かつ弧によって表される剛体運動がすべて同一基準を順守する連結成分の組を、（Ｓ３０において決定された）決定された部分グラフ内において識別するステップＳ４０も含む。
【００１８】
そのような方法は、３Ｄモデル化オブジェクトを設計するための改善された解決策を構成する。弧によって表される剛体運動がすべて同一基準を順守する連結成分を識別するステップＳ４０によって、方法は、幾何学パターンを決定し、それによって、パターンベースの設計機能をユーザに開放する。弧によって表される剛体運動がすべて同一基準よりも弱い所定の類似基準を順守する、グラフの最大の部分グラフ内において、これらのパターンを識別するステップＳ４０によって、方法は、意図されたパターンをより良く把握し、設計をより一層容易にするための、適切な識別を実行する。特に、Ｓ３０の特定の基準に従って、最大の部分グラフを決定することによって、またＳ４０において、Ｓ４０の特定の基準に従って、最多の弧を有する１組の連結成分をこれらの部分グラフ内において識別することによって、方法は、認識されたパターン内の弧の総数に従って、パターン認識を最適化し、したがって、最も意図されたパターンを認識する。方法は、類似基準および同一基準の使用を特定の方法で混ぜ合わせるので、方法は、「パターンからなるパターン（ｐａｔｔｅｒｎ  ｏｆ  ｐａｔｔｅｒｎｓ）」の構造自体に属する可能性の高いパターンを認識する。したがって、方法は、反復的パターン認識に寄与する第１のステップを構成し、それによって、そのような反復的パターン認識のためのデータを準備する。方法は、グラフ定義Ｓ２０および幾何学計算に依存するので、方法は、容易に実施することができ、したがって、自動化することができ、それによって、網羅的で迅速な方法で有意味なパターンを識別することができる。これは、すべて以下の説明において詳述される。
【００１９】
モデル化オブジェクトは、コンピュータシステムのメモリ内に記憶されたデータによって定義される、任意のオブジェクトである。拡大解釈される場合、「モデル化オブジェクト」という表現は、データ自体も指す。「３Ｄモデル化オブジェクトを設計する」とは、３Ｄモデル化オブジェクトを精巧に作り上げるプロセスの少なくとも一部である、任意のアクションまたは一連のアクションのことを指す。したがって、方法は、３Ｄモデル化オブジェクトをゼロから作成するステップを含むことができる。あるいは、方法は、先に生成された３Ｄモデル化オブジェクトを提供するステップと、その後、その３Ｄモデル化オブジェクトを変更するステップとを含むことができる。
【００２０】
３Ｄモデル化オブジェクトは、ＣＡＤモデル化オブジェクト、またはＣＡＤモデル化オブジェクトの一部とすることができる。いずれの場合も、方法によって設計される３Ｄモデル化オブジェクトは、例えば、ＣＡＤモデル化オブジェクトによって占有される３Ｄ空間など、ＣＡＤモデル化オブジェクトまたは少なくともそれの一部を表すことができる。ＣＡＤモデル化オブジェクトは、ＣＡＤシステムのメモリ内に記憶されたデータによって定義される、任意のオブジェクトである。システムのタイプによって、モデル化オブジェクトは、異なる種類のデータによって定義することができる。ＣＡＤシステムは、ＣＡＴＩＡなど、モデル化オブジェクトのグラフィカル表現に基づいて少なくともモデル化オブジェクトを設計するのに適した任意のシステムである。したがって、ＣＡＤモデル化オブジェクトを定義するデータは、モデル化オブジェクトの表現を可能にするデータ（例えば、空間内の相対位置を含む幾何学データ）を含む。
【００２１】
方法は、製造プロセスに含めることができ、製造プロセスは、方法を実行した後、例えば、方法によって認識された幾何学パターンに従って、モデル化オブジェクトに対応する物理的製品を生産することを含むことができる（そのような場合、製造プロセスには、幾何学パターンについての情報が供給され得る）。いずれの場合も、方法によって設計されたモデル化オブジェクトは、製造オブジェクトを表すことができる。したがって、モデル化オブジェクトは、モデル化立体（すなわち、立体を表すモデル化オブジェクト）とすることができる。製造オブジェクトは、部品または部品の組立品などの、製品とすることができる。方法は、モデル化オブジェクトの設計を改善するので、製品の製造も改善し、したがって、製造プロセスの生産性を向上させる。方法は、ＤＥＬＭＩＡなどの、ＣＡＭシステムを使用して実施することができる。ＣＡＭシステムは、少なくとも製造プロセスおよび操作の定義、シミュレーション、および制御を行うのに適した、任意のシステムである。
【００２２】
方法は、コンピュータで実施される。これは、方法が、少なくとも１つのコンピュータ、または任意の同様のシステム上で実行されることを意味する。例えば、方法は、ＣＡＤシステム上で実施することができる。したがって、方法のステップ（例えば、ユーザによってトリガされるステップ、および／もしくはユーザ対話を伴うステップ）は、おそらくは完全に自動的にまたは半自動的に、コンピュータによって実行される。特に、提供ステップＳ１０および／または定義ステップＳ２０は、ユーザがトリガすることができる。決定ステップＳ３０および／または識別ステップＳ４０は、自動的に（すなわち、いかなるユーザ介入もなしに）、または半自動的に（すなわち、例えば、結果を確認するための、もしくはユーザが決定した要素を部分グラフおよび／もしくは連結成分の組に追加する／連結成分の組から削除するための、例えば、僅かなユーザ介入を伴って）、実行することができる。
【００２３】
方法のコンピュータ実施の典型的な例は、この目的に適したシステムを用いて方法を実行することである。システムは、方法を実行するための命令を記録したメモリを備えることができる。言い換えると、ソフトウェアは、直ちに使用できるように、メモリ上にすでに準備されている。したがって、システムは、他のいかなるソフトウェアもインストールすることなしに、方法を実行するのに適している。そのようなシステムは、メモリに結合された、命令を実行するための少なくとも１つのプロセッサも備えることができる。言い換えると、システムは、プロセッサに結合されたメモリ上に符号化された命令であって、方法を実行するための手段を提供する命令を含む。そのようなシステムは、３Ｄモデル化オブジェクトを設計するための効率的なツールである。
【００２４】
そのようなシステムは、ＣＡＤシステムとすることができる。システムは、ＣＡＥおよび／またはＣＡＭシステムとすることもでき、ＣＡＤモデル化オブジェクトは、ＣＡＥモデル化オブジェクトおよび／またはＣＡＭモデル化オブジェクトとすることもできる。実際、モデル化オブジェクトは、これらのシステムの任意の組合せに対応するデータによって定義できるので、ＣＡＤ、ＣＡＥ、およびＣＡＭシステムは、一方が他方にとって排他的とはならない。
【００２５】
システムは、例えばユーザによって命令の実行を開始するための、少なくとも１つのＧＵＩを備えることができる。特に、ＧＵＩは、ユーザが、提供ステップＳ１０をトリガし、その後、ユーザがそうすることを決定した場合、例えば、（例えば「再帰的パターン認識」と称される）特定の機能を起動することによって、定義ステップＳ２０をトリガすることを可能にすることができる。その後、決定ステップＳ３０と、それに続いて、識別ステップＳ４０を、自動的または半自動的に実行することができる。
【００２６】
３Ｄモデル化オブジェクトは、３Ｄ（すなわち３次元）である。これは、モデル化オブジェクトが３Ｄ表現を可能にするデータによって定義されることを意味する。特に、Ｓ１０において提供される幾何学要素は、３Ｄである（すなわち、それらは、３Ｄにおいて定義され、したがって、すべての幾何学要素の結合体が平面内に包含可能でないこともある）。３Ｄ表現は、すべての角度から表現物を見ることを可能にする。例えば、モデル化オブジェクトは、３Ｄ表現された場合、その軸のいずれかの周りで、または表現が表示された画面内の任意の軸の周りで処理し、回転させることができる。これは、特に、３Ｄモデル化されていない２Ｄアイコンを、それらが２Ｄパースペクティブにおいて何かを表現する場合であっても、除外する。３Ｄ表現の表示は、設計を容易にする（すなわち、設計者が統計的に仕事を成し遂げるスピードを速める）。製品の設計は製造プロセスの一部であるので、これは、製造業における製造プロセスをスピードアップする。図のいくつかの例が２Ｄで表現されていても、方法の３Ｄ特徴に関する説明が成り立つことに留意されたい。これらの例は方法を理解するためのものであることが理解されなければならない。
【００２７】
図２は、典型的なＣＡＤシステムのＧＵＩの一例を示している。
【００２８】
ＧＵＩ２１００は、標準的なメニューバー２１１０、２１２０、ならびに下部および側部ツールバー２１４０、２１５０を有する、典型的なＣＡＤタイプのインタフェースとすることができる。そのようなメニューおよびツールバーは、１組のユーザ選択可能なアイコンを含み、各アイコンは、当技術分野で知られるように、１つまたは複数の操作または機能に関連付けられる。これらのアイコンのいくつかは、ＧＵＩ２１００内に表示された３Ｄモデル化オブジェクト２０００に対して編集および／または作業を行うように適合された、ソフトウェアツールに関連付けられる。ソフトウェアツールは、ワークベンチにグループ化することができる。各ワークベンチは、ソフトウェアツールのサブセットを含む。特に、ワークベンチの１つは、モデル化製品２０００の幾何学的特徴を編集するのに適した、編集ワークベンチである。操作中、設計者は、例えば、オブジェクト２０００の一部を事前選択し、その後、適切なアイコンを選択することによって、操作（例えば、造形操作、もしくは寸法、色などを変更するような他の任意の操作）を開始すること、または幾何学的制約を編集することができる。例えば、典型的なＣＡＤ操作は、画面上に表示された３Ｄモデル化オブジェクトの穴開けまたは折り曲げのモデル化である。
【００２９】
ＧＵＩは、例えば、表示された製品２０００に関連するデータ２５００を表示することができる。図２の例では、「特徴ツリー」として表示されたデータ２５００と、それらの３Ｄ表現２０００は、ブレーキキャリパ（ｂｒａｋｅ  ｃａｌｉｐｅｒ）およびディスクを含むブレーキ組立体に関する。ＧＵＩは、例えば、オブジェクトの３Ｄ方向付けを容易にするための、編集された製品の動作のシミュレーションをトリガするための、または表示された製品２０００の様々な属性を表すための、様々なタイプのグラフィックツール２１３０、２０７０、２０８０をさらに示すことができる。カーソル２０６０は、触覚デバイスによってコントロールすることができ、ユーザがグラフィックツールと対話することを可能にする。
【００３０】
図３は、例えば、ユーザのワークステーションなど、クライアントコンピュータシステムとしてのシステムのアーキテクチャの一例を示している。
【００３１】
クライアントコンピュータは、内部通信バス１０００に接続された中央処理装置（ＣＰＵ）１０１０と、やはりバスに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを備える。クライアントコンピュータには、バスに接続されたビデオランダムアクセスメモリ１１００に関連付けられた、グラフィックス処理ユニット（ＧＰＵ）１１１０がさらに設けられる。ビデオＲＡＭ１１００は、当技術分野において、フレームバッファとしても知られている。大容量記憶デバイスコントローラ１０２０は、ハードドライブ１０３０などの大容量メモリデバイスへのアクセスを管理する。コンピュータプログラム命令およびデータを有形に具体化するのに適した大容量メモリデバイスは、例を挙げると、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイスなどの半導体メモリデバイス、内蔵ハードディスクおよび着脱可能ディスクなどの磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭディスク１０４０を始めとする、すべての形態の不揮発性メモリを含む。上記のいずれも、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補うこと、またはその中に組み込むことができる。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータは、カーソル制御デバイスまたはキーボードなどの、触覚デバイス１０９０も含むことができる。カーソル制御デバイスは、図２を参照して言及されたように、画面１０８０上の任意の所望の位置にユーザがカーソルを選択的に配置することを可能にするために、クライアントコンピュータにおいて使用される。画面によって、コンピュータモニタなど、その上で表示が実行され得る任意のサポートが意味される。加えて、カーソル制御デバイスは、ユーザが、様々なコマンドを選択し、制御信号を入力することを可能にする。カーソル制御デバイスは、制御信号をシステムに入力するための、数々の信号発生デバイスを含む。典型的には、カーソル制御デバイスは、マウスとすることができ、信号を発生させるために、マウスのボタンが使用される。
【００３２】
システムに方法を実行させるため、コンピュータによって実行するための命令を含むコンピュータプログラムが提供され、命令は、この目的のための手段を含む。プログラムは、例えば、デジタル電子回路で、もしくはコンピュータハードウェア、ファームウェア、ソフトウェアで、またはそれらの組合せで実施することができる。本発明の装置は、プログラム可能プロセッサによって実行するための、機械可読記憶デバイスに有形に具体化されるコンピュータプログラム製品で実施することができ、本発明の方法ステップは、入力データの操作および出力の生成によって本発明の機能を実行するために、命令からなるプログラムを実行するプログラム可能プロセッサによって実行することができる。命令は、データ記憶システムからデータおよび命令を受け取り、データ記憶システムにデータおよび命令を送るように結合された、少なくとも１つのプログラム可能プロセッサと、少なくとも１つの入力デバイスと、少なくとも１つの出力デバイスとを含む、プログラム可能システムにおいて実行可能な、１つまたは複数のコンピュータプログラムで有利に実施することができる。アプリケーションプログラムは、高水準手続き型もしくはオブジェクト指向プログラミング言語で、または望ましければアセンブリ言語もしくは機械語で実施することができ、いずれの場合も、言語は、コンパイル言語またはインタプリタ言語とすることができる。プログラムは、完全インストールプログラムまたは更新プログラムとすることができる。後者の場合、プログラムは、方法を実行するのに適したシステムになった状態に、既存のＣＡＤシステムを更新する。
【００３３】
提供ステップＳ１０が、次に説明される。
【００３４】
方法は、モデル化オブジェクトを表す幾何学要素を提供するステップＳ１０を含む。したがって、幾何学要素は、モデル化オブジェクトの幾何学形状の一部である。幾何学要素は、任意のタイプとすることができる。例えば、幾何学要素は、基本的な立体、基本的な曲線、および／または基本的な面（ｓｕｒｆａｃｅ）を含むことができる。ＣＡＤにおいて広く使用され、以下で主に説明される一例では、幾何学要素は、Ｓ１０において提供されるモデル化オブジェクトの境界表現（Ｂ−Ｒｅｐ）の（例えばすべての）面分とすることができる。幾何学要素は、Ｂ−Ｒｅｐの面分の幾何学パターンとすることもできる。そのような場合、方法は、パターンからなるパターンの認識を直接的に実行する。
【００３５】
提供ステップＳ１０は、モデル化オブジェクト（例えば、その境界表現）上で作業する設計者に起因し、または例えば既存のライブラリ内で検索された、Ｂ−Ｒｅｐなどすでに存在するモデルに方法を適用できるということに、例えば起因することができる。いずれの場合も、モデル化オブジェクトは、Ｓ１０においてＢ−Ｒｅｐとして提供され得る。境界表現は、３Ｄオブジェクトをそのエンベロープ（すなわち、その外表面）の観点からモデル化するための、広く知られた形式である。したがって、Ｂ−Ｒｅｐは、幾何学データおよび位相データを含むことができる、特定の形式のデータを指す。幾何学データは、３Ｄ位置の観点から記述される実体である、幾何学的実体を提供するデータである。位相データは、幾何学的実体との関連性、および／または例えば相対的な位置決めなど、他の位相的実体との関係の観点から記述される実体である、位相的実体を提供するデータである。典型的には、関係は、位相的実体を他の位相的実体に関連付ける、「によって境界付けされる（ｉｓ  ｂｏｕｎｄｅｄ  ｂｙ）」関係を含むことができ、それによって、それらは、位相的に境界付けされる。
【００３６】
提供ステップＳ１０は、いずれの履歴データも排除することができる。言い換えると、Ｓ１０において提供されるモデル化オブジェクトは、履歴なしとすることができる。これは、モデル化オブジェクトが、その設計の履歴を示すいかなるデータにも関連付けられておらず、例えばＢ−Ｒｅｐを含む宣言的データのみによっていることを意味する。したがって、方法は、設計者がモデル化オブジェクトの履歴を所有していない状況において機能でき、このことは、モデル化オブジェクト上で設計される幾何学パターンが、Ｓ１０において提供されるデータ内でそのようなものとして定義されないことを特に暗示する。
【００３７】
この方法の場合、（例えば幾何学）データは、いわゆる「サポート面」、例えば、パラメトリック曲面（ｐａｒａｍｅｔｒｉｃ  ｓｕｒｆａｃｅ）（すなわち、２Ｄ領域を定義するパラメータに関連付けられた３Ｄ位置の観点からモデル化された３Ｄ表面）を含む。サポート面は、典型的には、ナーブス曲面（Ｎｕｒｂｓ  ｓｕｒｆａｃｅ）とすることができるが、平面、標準曲面（ｃａｎｏｎｉｃａｌ  ｓｕｒｆａｃｅ）、または手続き型曲面（ｐｒｏｃｅｄｕｒａｌ  ｓｕｒｆａｃｅ）とすることもできる。（例えば位相）データは、少なくとも１組の面分を含むことができ、各面分は、（幾何学データで提供される）それぞれのサポート面の有界な部分として定義される。したがって、面分は、切り取られた面に対応する。したがって、サポート面は、何らかの切り取り操作によって面分がその上に定められる（それによって面分を「サポート」する）面である。したがって、Ｓ１０において提供される幾何学要素は、全データで定義される、そのような面分とすることができる。
【００３８】
Ｂ−Ｒｅｐの概念は、広く知られているが、Ｓ１０において提供され得るモデル化オブジェクトの一例を通して、次にさらに説明される。しかし、例えば、少なくともいくつかの位相的実体に対して、「によって境界付けされる」関係とは異なる関係を用いる、Ｂ−Ｒｅｐの他の例も、方法によって企図され得る。また、非Ｂ−Ｒｅｐ表現も、方法によって企図され得る。
【００３９】
すでに言及したように、モデル化オブジェクトのＢ−Ｒｅｐは、位相的実体および幾何学的実体を含むことができる。幾何学的実体は、面（ｓｕｒｆａｃｅ）（例えば平面（ｐｌａｎｅ））、曲線（ｃｕｒｖｅ）（例えば線（ｌｉｎｅ））、および／または点（ｐｏｉｎｔ）である、３Ｄオブジェクトを含むことができる。面は、２つのパラメータの関数として提供することができる。曲線は、単純に１つのパラメータの関数として提供することができる。点は、３Ｄ位置として提供することができる。位相的実体は、面分、稜線、および／または頂点を含むことができる。その定義によって、面分は、「サポート面」と呼ばれる、それぞれの面の有界な部分に対応する。したがって、「面分」という用語は、面のそのような有界な部分、または２Ｄ領域の対応する有界な部分を区別せずに指すことができる。同様に、稜線は、例えばサポート曲線（ｓｕｐｐｏｒｔｉｎｇ  ｃｕｒｖｅ）と呼ばれる、曲線の有界な部分に対応する。したがって、「稜線」という用語は、曲線またはその領域のそのような有界な部分を指すことができる。頂点は、３Ｄ空間内の点との結び付きとして定義することができる。これらの実体は、以下のように互いに関連する。曲線の有界な部分は、曲線上にある２つの点（頂点）によって定義される。面の有界な部分は、その境界によって定義され、この境界は、面上にある１組の稜線である。面分の境界の稜線は、共有する頂点によって一緒に接続される。面分は、共有する稜線によって一緒に接続される。定義によって、２つの面分は、それらが稜線を共有する場合、隣接する。同様に、２つの稜線は、それらが頂点を共有する場合、隣接する。面、曲線、および点は、それらのパラメータ化を介して、一緒に結び付けることができる。例えば、境界の頂点を定義するために、曲線を定義するパラメトリック関数のパラメータの値が提供され得る。同様に、境界の稜線を定義するために、曲線のパラメータを面の２つのパラメータに結び付ける関数が提供され得る。しかし、Ｂ−Ｒｅｐのそのような位相データの非常に詳細な構造は、本説明の範囲外にある。
【００４０】
図４および図５は、Ｓ１０において提供されたものとすることができ、図において１、２、３の番号が付された３つの面分、すなわち、上部平面面分１と、２つの側面円筒面分２、３とから作成される、円筒スロット８０のＢ−ｒｅｐモデルを示している。図４は、スロット８０の斜視図を示している。図５は、すべての面分の分解図を示している。重複する番号は、共有の稜線および頂点を示している。面分１は、平面の有界な部分である。面分１の境界は、稜線４、５を含み、それらの各々は、頂点１０と頂点１１によって境界付けされる。それらはともに、同じサポート円を有する。面分２は、稜線６、８、５、１３によって境界付けされ、そのすべては、無限円筒曲面（すなわち、面分２のサポート面）上にある。面分１、２は、それらが稜線５を共有するので、隣接している。面分２、３は、それらが稜線８、１３を共有するので、隣接している。面分１、３は、それらが稜線４を共有するので、隣接している。
【００４１】
図６は、スロット８０のＢ−ｒｅｐモデルの「によって境界付けされる」位相関係を示している。高位レイヤ１０１のノードは、面分であり、中位レイヤ１０３のノードは、稜線であり、低位レイヤ１０５のノードは、頂点である。図７および図８は、位相的実体（面分、稜線、頂点）とサポート幾何学形状（無限円筒、無限平面、無限直線、点）の間の関係を示している。ＣＡＤシステムでは、Ｂ−ｒｅｐモデルは、「によって境界付けされる」関係と、位相的実体とサポート幾何学形状の間の関係と、サポート幾何学形状の数学的記述とを適切なデータ構造で収集する。言い換えると、図６および図７に示されるデータ構造は、この例の位相データの一部であり、それは、幾何学データの幾何学的実体との結び付き（これは図７である）、および位相的実体の間の結び付き（これは図６である）を含む。
【００４２】
（ステップＳ２０〜Ｓ４０を含む）方法の他のアクションが、次に説明される。
【００４３】
Ｓ１０において提供される幾何学要素は、幾何学要素がその中で互いのコピーである、または言い換えると、互いに幾何学的に同一である、もしくは一方が他方の幾何学的レプリカである、組（例えば、少なくとも１組）を含む。方法は、これらの幾何学要素に基づいて、グラフを定義するステップＳ２０を含む。これのために、方法は、組の事前決定を提供するステップ、またはあるいは、組を決定するステップを含むことができる（例えば、方法は、組の要素を一緒に結び付ける特定のデータを決定する）。これは、定義ステップＳ２０をより迅速に実行することを可能にする。例えば、幾何学要素がＢ−Ｒｅｐの１組の面分である場合、方法は、例えば、ユーザがトリガしたときに、面分が互いのコピーであることを目的として、境界表現の面分のすべてのサブセットを決定するステップを含む。Ｓ１０の組は、当業者が望む任意の実装形態に従って、決定することができる。例えば、方法は、面分のペアの間で比較を実行するステップを含むことができ、面分は、任意の順序に従ってブラウズされる。そのような比較は、任意の方法で実行することができる。例が、後で提供される。また、ＣＡＤの分野から分かるように、数値計算を伴う任意の決定は、システムによって適用される必要な数値近似の影響を受ける。本ケースでは、面分は、それらが理論的には僅かに異なるとしても、互いのコピーであると決定されることがある。したがって、方法は、実際には、実質的に互いのコピーである面分の組を決定することができる。しかし、近似が実施される方法は、本説明の主題ではないので、以下では、「実質的に互いのコピー」と「互いのコピー」とは区別されない。実際のところ、方法は、２つの幾何学要素、例えば面分が互いのコピーであるかどうかを判別するための所定の基準に従うとしか見なされない。あるいは、方法は、互いのコピーである幾何学要素の組を事前に決定することなく、グラフを直接的に定義できる（Ｓ２０）とも理解されなければならない。
【００４４】
方法は、後で方法によって拡張的に使用される特定のグラフを定義するステップＳ２０を含む。グラフ理論から分かるように、グラフは、ノードと、各々がノードのペアを連結する弧とを有する、数学的対象である。したがって、方法は、おそらくは、（方法によって決定できる、またはそのようなものとして提供できる）互いのコピーである１組の幾何学要素を識別した後、Ｓ１０において提供されたデータから開始して、コンピュータデータに関するそのような構造を定義する（Ｓ２０）。ここで、そのような組のいくつかが決定される場合、Ｓ２０において同じだけ多くのグラフがそれぞれ定義され得ることに留意されたい。または、方法は、最初の反復において処理されなかった組を後の反復において処理することができる。これらは、実施上の詳細である。グラフは、コピーの組全体において、またはそれの部分において定義できることにも留意されたい。これも、実装形態の内容である。第１の手法では、パターン認識を網羅的に実行するため、定義ステップＳ２０は、組全体において実行することができる。
【００４５】
ここで、Ｓ２０において定義されるグラフは、（当業者には分かるように）Ｓ２０において方法によって生成されるデータを形式化する特定の構造を有する。各ノードは、コピーの組の幾何学要素（例えば面分）を表す。例えば、各ノード名が、例えばポインタを介して、幾何学要素の参照に結び付けられる。同様に、各弧は、ペアの一方のノードによって表される幾何学要素をペアの他方のノードによって表される幾何学要素に変換する剛体運動を表す。面分を含む任意の幾何学要素は、点集合と見ることができ（それによって、そのようなものとして方法によって処理することができ）、すなわち、３次元空間
【００４６】
【数１】
2014130601.tif 000003
【００４７】
の部分集合と見ることができる。剛体運動は、Ｄ（ｘ）＝Ｒｘ＋Ｔによって、２つの点集合の間で定義される写像
【００４８】
【数２】
2014130601.tif 000004
【００４９】
であり、ここで、Ｒは、回転であり、Ｔは、並進ベクトルである（それらの一方はヌルの可能性あり）。剛体運動Ｄは、簡潔にＤ＝（Ｒ，Ｔ）と表記することができる。ｙ＝Ｄ（ｘ）は、ｘ＝Ｄ−１（ｙ）と等価であり、ここで、Ｄ−１（ｙ）＝Ｒ−１ｙ−Ｒ−１Ｔであるので、剛体運動は、可逆的である。３次元剛体運動のグループは、従来、ＳＥ（３）と表記される。Ｓ１０において提供される組の幾何学要素は、互いのコピーであるので、組の２つの幾何学要素を与えた場合、一方は、剛体運動を適用することによって、他方の幾何学要素から導出することができる。
【００５０】
グラフは、そのような導出（または変換）を記述するデータを収集する。剛体運動および関連する幾何学形状は、実際には、有向な連結されたグラフＢ（Ｘ，Ｕ，α，ω）に記憶することができ、ここで、ノードＸは、幾何学形状であり、弧Ｕは、剛体運動でラベル付けされる。ラベル付けは、写像ｍ：Ｕ→ＳＥ（３）である。より正確には、弧ｕ∈Ｕは、ノードα（ｕ）＝ｘ∈Ｘで開始し、ノードω（ｕ）＝ｙ∈Ｘで終了するという記述は、幾何学形状ｘと幾何学形状ｙが、互いのコピーであること、および剛体運動ｍ（ｕ）が、ｘをｙに変更し、それは、ｙ＝ｍ（ｕ）ｘと表記されることを意味する。ここで、弧ｖ∈Ｕが、ｘとｚ∈Ｘとを連結し、それが、α（ｖ）＝ｘ、ω（ｖ）＝ｚと記述されると仮定する。ｘをｚに変更する剛体運動は、ｚ＝ｍ（ｖ）ｘである。その場合、ｚは、ｙのコピーでもあり、ｙをｚに変更する剛体運動は、ｚ＝ｍ（ｖ）ｍ（ｕ）−１ｙである。反対に、ｚをｙに変更する剛体運動は、ｙ＝ｍ（ｕ）ｍ（ｖ）−１ｚである。
【００５１】
ここで、弧の方向付けに関連する問題は、単なる実施上の問題であるので、当業者によって任意の方法で扱うことができることに留意されたい。例えば、弧が与えられ、その弧によって連結される２つのノードが与えられた場合、剛体運動を決定するための開始ノードの問題は、任意の方法で扱うことができる（他方のノードが開始点として使用される場合は、剛体運動は逆向きになることが分かる）。実施の一例が、包括的理解のために後で提供される。
【００５２】
Ｓ１０において提供される組の幾何学要素は、互いのコピーであるので、この組上でＳ２０において定義されるグラフは、完全とすることができ、すべての弧は、上述のように定義される。しかし、効率性のため、方法は、Ｓ２０において、任意の所定の基準に従って完全グラフの弧のいくつか（例えば、他の任意の剛体運動との類似性を有さない剛体運動を表す弧）を取り除いた、完全ではないグラフを定義することができる。
【００５３】
その後、方法は、いくつかの制約を順守する、グラフの最大の部分グラフを決定するステップＳ３０を含む。言い換えると、方法は、何らかの所定の制約の下で、グラフの最大の部分グラフ（すなわち、部分グラフは、グラフのすべてのノードおよび弧の集合の部分集合である）、すなわち、最多の要素を有する部分グラフを計算する。所定の制約は、以下のものであり、すなわち、Ｓ３０において決定される部分グラフは、弧によって表される剛体運動がすべて所定のいわゆる「類似」基準を順守する部分グラフでなければならない。ここで、Ｓ３０において決定される部分グラフは、いくつかのノードが同時にいくつかの異なる最大の部分グラフに属することがあるので、後で例示されるように、必ずしも互いに素ではないことに留意されたい。
【００５４】
類似基準は、２つの剛体運動が、幾何学的対象に作用する方法において類似していることを示す基準である。類似基準は、同一基準よりも弱く、同一基準は、２つの剛体運動が（数値計算に内在する上述の近似を法として）同一であることを示すためのものである。類似基準および同一基準はともに、事前に決定され、すなわち、システムは、剛体運動のペアがこれらの基準のいずれかまたは両方を順守するかどうかを調べる方法を記憶している。したがって、方法は、最大の部分グラフを決定するために、任意の方法／順序で、所定の類似基準に基づいて、コンピュータサイエンスの分野で知られているような、比較を実行することができる。
【００５５】
機械設計の分野に特によく適合された類似基準の例および特性が、次に提供される。
【００５６】
類似の目標は、剛体運動が必ずしも等しくないにも係わらず、また剛体物体が３Ｄ空間内に任意に配置されているにも係わらず、２つの剛体運動、およびそれらの逆が、それぞれ、２つの幾何学的対象に同じ方法で作用することを識別することである。
【００５７】
明瞭にするため、以下では２つのステップに従って、類似を説明する。第１のステップは、２つの弧のいわゆる「類似性（ａｎａｌｏｇｙ）」を定義することであり、代数的特性を提供する。この第１の定義は、弧の方向付けを含むので、第２のステップは、弧の方向付けが関連しないような方法で、「類似性」を再使用することによって、「類似」を定義する。
【００５８】
ｕｉ、ｉ＝１、２をグラフＢの２つの弧とし、Ｄｉ＝ｍ（ｕｉ）を弧ｕｉにそれぞれ関連付けられた剛体運動とする。ｘｉ＝α（ｕｉ）を弧ｕｉの始点における幾何学的対象とし、ｙｉ＝ω（ｕｉ）を弧ｕｉの終点における幾何学的対象とする。そのため、定義によって、ｙｉ＝Ｄｉ（ｘｉ）、ｉ＝１、２である。
【００５９】
定義によって、以下の２つの条件が検証されるような剛体運動Ｍが存在する場合、弧ｕ１は、弧ｕ２に類似し、ｕ１〜ｕ２と表記される。
【００６０】
１．
【００６１】
【数３】
2014130601.tif 000005
【００６２】
２．  ｘ２＝Ｍ（ｘ１）
よりコンパクトな表記を使用して、これは、
【００６３】
【数４】
2014130601.tif 000006
【００６４】
およびα（ｕ２）＝Ｍ（α（ｕ１））と書くことができる。
【００６５】
実際には、定義は、弧ｕｉの始点ｘｉの選択には依存せず、むしろ終点ｙｉに依存する。より正確には、先の定義におけるような剛体運動Ｍが存在する場合、
【００６６】
【数５】
2014130601.tif 000007
【００６７】
および
ｙ２＝Ｓ（ｙ１）であるような、別の剛体運動Ｓが存在する。証明は、以下の通りである。
【００６８】
最初に、
【００６９】
【数６】
2014130601.tif 000008
【００７０】
である。
【００７１】
次に、
【００７２】
【数７】
2014130601.tif 000009
【００７３】
であることを
【００７４】
【数８】
2014130601.tif 000010
【００７５】
を用いて、チェックすれば十分である。
【００７６】
【数９】
2014130601.tif 000011
【００７７】
以下で「反転特性（ｉｎｖｅｒｓｉｏｎ  ｐｒｏｐｅｒｔｙ）」と呼ばれる別の重要な特性は、２つの弧が類似している場合、反転された弧も同様に類似していることである。形式的に、ｕ１〜ｕ２であれば、ｕ１−１〜ｕ２−１であり、ここで、表記ｕｉ−１は、ｙｉで開始し、ｘｉで終了する、反転剛体運動Ｄｉ−１に関連付けられた、反転された弧である。証明は、以下の通りである。ｕ１〜ｕ２である場合、一方では、
【００７８】
【数１０】
2014130601.tif 000012
【００７９】
であり、そのため、
【００８０】
【数１１】
2014130601.tif 000013
【００８１】
である。定義ｘ２＝Ｍ（ｘ１）の他方の点は、弧ｕｉ−１の終了ノードにおいて表現され、それは、先の所見に従って有効である。これが、ｕ１−１〜ｕ２−１であることを証明している。
【００８２】
「類似性」は、弧の集合における同値関係である。これを証明するために、以下の特性が立証される。
【００８３】
第１の特性は、反射性であり、すなわち、任意の弧は、それ自身に類似しており、ｕ〜ｕであり、これは、Ｍを同一の剛体運動として選択することによって明らかである。
【００８４】
第２の特性は、対称性であり、ｕ１〜ｕ２であれば、ｕ２〜ｕ１である。これは、Ｄ１＝Ｍ−１Ｄ２Ｍであれば、Ｄ２＝ＭＤ１Ｍ−１であり、ｘ２＝Ｍ（ｘ１）であれば、ｘ１＝Ｍ−１（ｘ２）であるためである。これは、「２つの弧は類似している」と言うことを、それらの一方が他方に類似していると言う代わりに、可能にする。
【００８５】
第３の最後の特性は、推移性であり、ｕ１〜ｕ２およびｕ２〜ｕ３であれば、ｕ１〜ｕ３である。実際、ｕ２〜ｕ３であるならば、Ｄ２＝Ｎ−１Ｄ３Ｎおよびｘ３＝Ｎ（ｘ２）であるような剛体運動Ｎが存在する。しかし、Ｄ１＝Ｍ−１Ｄ２Ｍおよびｘ２＝Ｍ（ｘ１）であるので、それぞれ、
Ｄ１＝Ｍ−１Ｄ２Ｍ
＝Ｍ−１Ｎ−１Ｄ３ＮＭ
＝（ＮＭ）−１Ｄ３（ＮＭ）
および
ｘ３＝Ｎ（ｘ２）
＝ＮＭ（ｘ１）
を得る。
【００８６】
これが、ｕ１〜ｕ３であること、剛体運動がＮＭであることを証明している。
【００８７】
そのため、類似関係は、弧の集合上における同値関係である。難点は、ｕ１〜ｕ２である場合、関係ｕ１−１〜ｕ２は成り立たないので、それが、弧の方向付けに依存することである。これは、Ｄ２＝Ｄ２−１でない限り、Ｄ１＝Ｍ−１Ｄ２Ｍが、概して、Ｄ１−１＝Ｍ−１Ｄ２Ｍを含意しないためである。
【００８８】
そのため、類似の定義は、以下のように定めることができる。定義によって、弧ｕ１が弧ｕ２に類似するならば、または弧ｕ１−１が弧ｕ２に類似するならば、弧ｕ１は、弧ｕ２に類似し、
【００８９】
【数１２】
2014130601.tif 000014
【００９０】
と表記される。要するに、ｕ１〜ｕ２またはｕ１−１〜ｕ２であれば、
【００９１】
【数１３】
2014130601.tif 000015
【００９２】
である。
【００９３】
関係
【００９４】
【数１４】
2014130601.tif 000016
【００９５】
は、以下で証明されるように、やはり同値関係である。
【００９６】
反射性、すなわち、すべてのｕについて
【００９７】
【数１５】
2014130601.tif 000017
【００９８】
は、同様に、すべてのｕについてｕ〜ｕであるので立証される。ｕ−１は、概して、ｕに類似しないことに留意されたい。
【００９９】
対称性、すなわち、
【０１００】
【数１６】
2014130601.tif 000018
【０１０１】
ならば、
【０１０２】
【数１７】
2014130601.tif 000019
【０１０３】
は、以下のように立証される。
ｕ１〜ｕ２ならば、〜は対称的であるので、ｕ２〜ｕ１であり、その場合、
【０１０４】
【数１８】
2014130601.tif 000020
【０１０５】
である。ｕ１−１〜ｕ２ならば、反転特性によって、ｕ２−１〜ｕ１であり、これは、
【０１０６】
【数１９】
2014130601.tif 000021
【０１０７】
であることを意味する。
【０１０８】
推移性、すなわち、
【０１０９】
【数２０】
2014130601.tif 000022
【０１１０】
および
【０１１１】
【数２１】
2014130601.tif 000023
【０１１２】
であれば、
【０１１３】
【数２２】
2014130601.tif 000024
【０１１４】
は、以下のように立証される。言明「
【０１１５】
【数２３】
2014130601.tif 000025
【０１１６】
」は、４つの可能性をまとめたものであり、各可能性が、
【０１１７】
【数２４】
2014130601.tif 000026
【０１１８】
を含意することをチェックしなければならない。
１．  ｕ１〜ｕ２およびｕ２〜ｕ３
２．  ｕ１〜ｕ２およびｕ２−１〜ｕ３
３．  ｕ１−１〜ｕ２およびｕ２〜ｕ３
４．  ｕ１−１〜ｕ２およびｕ２−１〜ｕ３
関係〜は推移的であるので、ケース１は、ｕ１〜ｕ３をもたらし、その場合、
【０１１９】
【数２５】
2014130601.tif 000027
【０１２０】
である。
【０１２１】
ケース２は、反転特性によって、ｕ１〜ｕ２およびｕ２〜ｕ３−１と等価である。〜は推移的であるので、やはり反転特性によって、ｕ１〜ｕ３−１は、ｕ１−１〜ｕ３と等価であり、すなわち、
【０１２２】
【数２６】
2014130601.tif 000028
【０１２３】
である。
【０１２４】
〜は推移的であるので、ケース３は、ｕ１−１〜ｕ３をもたらし、すなわち、
【０１２５】
【数２７】
2014130601.tif 000029
【０１２６】
である。
【０１２７】
ケース４は、ｕ１−１〜ｕ２およびｕ２〜ｕ３−１と等価である。〜は推移的であるので、反転特性によって、ｕ１−１〜ｕ３−１は、ｕ１〜ｕ３であることを意味し、その場合、
【０１２８】
【数２８】
2014130601.tif 000030
【０１２９】
である。
【０１３０】
基本的な代数によれば、類似関係は、弧の集合を、以下では「同値類」と呼ばれることがある、最大かつ互いに素の部分集合に分類する。弧によって連結されたノードを用いて拡張される場合、これらの同値類は、Ｓ３０において決定される部分グラフを構成することができる。
【０１３１】
上で説明したように、Ｓ３０において最大の部分グラフが決定された後、方法は、決定された部分グラフ内において、少なくとも１つの幾何学パターンを識別するステップＳ４０を含み、Ｓ４０において識別された組の各連結成分は、実際には、方法によって幾何学パターンとして宣言的に見られる。Ｓ４０において、連結成分の組が、Ｓ３０において決定された部分グラフ内において識別されるという事実は、最大の部分グラフのうちの１つの特定の部分部分グラフ（ｓｕｂ−ｓｕｂ−ｇｒａｐｈ）（すなわち、連結成分の組）、場合によっては、最大の部分グラフ全体（極端なケースでは、または後で説明するように、方法が反復される場合の反復の終りでは、ヌルグラフの可能性もあるが、概して、ヌルグラフではない）が、いくつかの条件に従って識別されることを意味する。
【０１３２】
１組の連結成分を「識別する」によって、連結成分の存在、およびいわゆる連結成分を形成する幾何学要素の間の連結を示すために、データがモデル化オブジェクトに追加されることが意味される。例えば、グループ名が生成され、幾何学要素または幾何学要素のグループとグループ名との間の結び付きが、モデル化オブジェクト（を定義するデータ）に追加される。要素を一緒に結び付けるこの方法は、決定ステップＳ３０のために実施することもできる新しいデータは、おそらくは、永続メモリ上に記憶すること、または少なくともユーザが幾何学パターン上で作業を行えるだけ十分に長く記憶することができる。これらは、当業者に知られた単なる実施の問題である。
【０１３３】
さらに、方法は、幾何学パターンを識別する。「幾何学パターン」という表現は、幾何学パターンに属する要素が幾何学形状を構成し、その要素（例えば、面分または面分の組）が、予測可能な方法で、すなわち、所定の規則に従って配置され、それによって、完全なランダム性を排除していることを意味する。いわゆる「連結成分」は、単純に連結されたグラフである。この方法の場合、企図される連結成分は、いくつかの基準を順守する、Ｓ３０において決定された最大の部分グラフの連結された部分部分グラフである。すなわち、連結成分の弧は、同一基準を順守する剛体運動を表さなければならない（すなわち、１つの連結成分のすべての剛体運動は、方法のために定義された所定の同一基準によって同一である）。したがって、連結成分のノードによって表される幾何学要素は、ノードの１つによって表される１つの初期幾何学構成要素に１つの同じ剛体運動を適用することによって、すべて獲得可能である（幾何学パターンは、実際には、例えば別のユーザによって、方法に先立って、そのようなものとして設計されていることがある）。これは、幾何学パターンの定義に入る。
【０１３４】
さらに、連結成分の組は、類似の剛体運動を有する１組の幾何学パターンであり、Ｓ４０において識別された組の１つの連結成分の同一の剛体運動は、Ｓ４０において識別された組の別の連結成分の同一の剛体運動と類似している。したがって、そのような「連結成分の組」の構造を出力することによって、方法は、「パターンからなるパターン」の認識を開始する。実際に、使用される類似基準の性質のおかげで、Ｓ４０において、いくつかの連結成分が組内において識別される場合（入力データに応じて、Ｓ４０において識別される組は、ただ１つの連結成分しか含まないことがあるが、いくつかの状況では、２つ以上を含む）、連結成分は、おそらくは、剛体運動を用いて１つから他を獲得可能とすることができる。したがって、後で例示されるように、パターンからなるパターンが認識され得る。
【０１３５】
幾何学パターンの幾何学要素は、互いのコピーであるように最初に選択されるので、方法は、設計意図に従って意味を有する幾何学パターンを認識する。また、連結成分の組は、Ｓ３０において決定された部分グラフ内において、弧によって表される剛体運動がすべて同一基準を順守する連結成分のすべての可能な組の中から、（連結成分の組のすべての弧をカウントした合計で、すなわち、組のすべての連結成分について、各連結成分の弧の総数を合算した合計で）最多の弧を有するものとして選択される。これは、任意の方法で実施することができるが、いわゆる「分割」を含む可能性のある一例が、後で説明される。いくつかのそのような組が存在するケースは、当業者が望む任意の方法で扱うことができる。そのような選択、またはＳ４０において識別される連結成分の組は、ユーザ意図の良好な把握を可能にする。言い換えると、方法によって認識されるパターン構造は、ユーザにとって統計的に最も有意である。特に、これは、方法がすでに説明されたように適用され得る機械設計の分野において特に当てはまることが分かっている。
【０１３６】
したがって、識別Ｓ４０は、より容易な設計を可能にする。まず第一に、これは、幾何学パターン構造（すなわち、連結成分の組の構造）を後でユーザに提示することを可能にする。したがって、ユーザは、設計者の意図を把握することができる。これは、先に言及したように、後で設計アクションを幾何学パターン構造上で全体的に（すなわち、自動的な統一された方法で）実行することも可能にする。例えば、ユーザは、連結成分全体または１組全体の連結成分を単一の「ドラッグアンドドロップ」アクションを用いて変換することができる。または、ユーザは、組の連結成分のいずれかまたはすべての、すべての要素のサイズを、それを選択し、その後、その要素の新しいサイズを一度だけ入力することによって、大きくすることができる。これらは、単なる例である。方法は、識別ステップＳ４０の結果を含む、そのような後の設計アクションのいずれかまたはいくつかを含むことができる。方法は、幾何学パターンを含むいくつかの特定の設計をより僅かなユーザアクションで達成することを可能にするので、これは、概して、ＣＡＤの分野で有益である。これは、モデル化オブジェクトが製品を表す場合、機械設計の分野で特に有益であり、そのような場合、方法は、そのすべてのフェーズの時間最適化を必要とする全体的な工業プロセスに属する。方法は、認識された連結成分の組を製造プロセスに供給するステップも含むことができる。
【０１３７】
したがって、例えば面分定義に基づいた、簡単な幾何学的計算を実行することによって、また限定されたグラフベースの計算を実行することによって、方法は、識別を助けるためにユーザがモデル化オブジェクト上の任意の特定の幾何学要素または位置を識別（すなわち事前選択）する必要なしに、複雑であり得る（単一の連結成分に対応する単一のパターンよりも入り組んでいる）１組の連結成分の形態で幾何学パターン構造を効率的に識別する。方法は、実際に、ユーザによって行われるそのような識別を排除することができる。したがって、方法は、例えば、モデル化オブジェクトの境界表現に適合された、パターンの効率的な識別を可能にすることができる。方法は、ユーザが行う幾何学形状のいかなる視覚的分析も必要としない。方法は、入力された幾何学形状をシステマティックに分析することによって、重複する幾何学形状の配置に集中する。ユーザはそのプロセスに直接的には係わらないので、他の仕事のための時間が確保される。さらに、後で説明するように、モデル化オブジェクトのパターンからなるパターンの全体構造をもたらすために、方法を使用することができる。これは、１回限りのプロセスである。結果として、本発明は、パターン認識のために費やされる時間を短縮し、可能な限り最良の結果を提供する。
【０１３８】
方法は、何らかの形で、反復できることに留意されたい。基本的に、各反復において、先行する反復のＳ４０において識別された連結成分は、そのような幾何学要素と見なされる。このように、方法は、提供されたモデルのパターンからなるパターンの全体構造を反復的に決定することができ、Ｓ４０の最初の反復において決定される連結成分は、Ｓ４０の次の反復において決定されるより高レベルの連結成分のおそらくは部分である。
【０１３９】
より正確には、方法は、以下のアクションを反復するステップをさらに含むことができる。最初に、方法の先行する反復の識別ステップＳ４０の後、方法は、識別された連結成分の組のうちの各連結成分のノードを折り畳むことによって、（第２の反復のときは最初の反復のＳ２０において定義された、またはその後の反復のときは先行する反復においてすでに変更された）グラフを変更することができる。これは、「連結成分による連結成分（ｃｏｎｎｅｃｔｅｄ  ｃｏｍｐｏｎｅｎｔ  ｂｙ  ｃｏｎｎｅｃｔｅｄ  ｃｏｍｐｏｎｅｎｔ）」という方法で、組の各連結成分のノードを一緒にマージすることによって、グラフの縮小をもたらす。その後、方法は、変更されたグラフにおいて、決定ステップＳ３０および識別ステップＳ４０を実行する。言い換えると、Ｓ２０において定義されたグラフは維持され、それは方法の反復を通して変更されるので、その変更されたバージョンが、その後の各反復の決定ステップＳ３０および識別ステップＳ４０のための入力として使用される。このように、方法は、Ｓ１０において提供された１組の幾何学要素内のすべてのパターンを網羅的および反復的に認識する。連結成分は、方法の各反復によって、そのようなものとして処理されるので、方法は、任意の反復順序で、パターンからなるパターンを認識することができる。さらに、方法が実行される方法は、相対的に低い計算量で、そうすることを可能にする。
【０１４０】
ここで、潰し（ｃｏｌｌａｐｓｉｎｇ）は、単純に以下のアクションを含むことによって、実行することができる。潰しは、識別された連結成分の組のうちの任意の連結成分の任意のノードに連結されたすべての弧を削除することを含むことができる。言い換えると、連結成分は、それらのノードに縮小され、ノードの１つに連結されていた、（識別ステップＳ４０の前に）グラフ内に存在した弧はどれも、維持されない。その場合、潰しは、各それぞれの連結成分について、それぞれの連結成分のすべてのノードを単一のノードによって置き換えることができる。これは、データ処理の観点から見て、単純な参照管理の問題である。最後に、潰しは、そのように追加されたノードのペア間に弧を追加することを含むことができる。特に、追加される弧は、等大の連結成分を表すノード（すなわち、それらは先行するステップにおける等大の連結成分に由来する）の間に追加される。したがって、連結成分は、幾何学的に剛体運動を法として同一である。追加された各弧は、実際には、ペアの一方のノードによって表される連結成分をペアの他方のノードによって表される連結成分に変換する剛体運動を表す。やはり、方向付けの扱いは、実施上の問題である。したがって、Ｓ２０において定義されるグラフの全体的な構造は、維持される。これは、決定ステップＳ３０および識別ステップＳ４０を、同じアルゴリズムブロックを用いて、したがって、効率的な方法で、実行することを可能にする。
【０１４１】
次に、いくつかの定義を行った後、方法の例を説明する。例では、提供ステップＳ１０は、モデル化オブジェクトのＢ−Ｒｅｐを提供するステップを含む。幾何学要素は、最初は、Ｂ−Ｒｅｐにおいて定義された面分である。特に、適用例は、機械設計とすることができ、モデル化オブジェクトは、パターン認識が特に有益な、部品または部品の組立品などの製品を表す。
【０１４２】
点集合Ｘを与えた場合、簡潔にはＹ＝Ｄ（Ｘ）と表記される、Ｙ＝｛Ｄ（ｘ），ｘ∈Ｘ｝であるような、剛体運動Ｄが存在する場合、点集合Ｙは、Ｘの「レプリカ」である。
【０１４３】
「方向付けされた点集合（ｏｒｉｅｎｔｅｄ  ｐｏｉｎｔ−ｓｅｔ）」は、２つ組（Ｘ，ｕＸ）であり、ここで、
【０１４４】
【数２９】
2014130601.tif 000031
【０１４５】
は、点集合であり、ｕＸは、写像ｕＸ：Ｘ→Ｓ２であり、ここで、Ｓ２は、
【０１４６】
【数３０】
2014130601.tif 000032
【０１４７】
の１組の単位ベクトルである。言い換えると、任意の点ｘ∈Ｘにおいて、単位ベクトルｕＸ（ｘ）が定義される。
【０１４８】
方向付けされた点集合（Ｙ，ｕＹ）は、Ｙが方向付けを保ったＸのレプリカである場合、方向付けされた点集合（Ｘ，ｕＸ）の「コピー」である。より正確には、すべてのｘ∈Ｘについて、レプリカ上の対応する点Ｄ（ｘ）の単位ベクトルは、点ｘにおけるＸの単位ベクトルを回転したものである。形式的に、すべてのｘ∈Ｘについて、ｕＹ（Ｄ（ｘ））＝ＲｕＸ（ｘ）であり、これは、以下のダイアグラムが可換であることを意味する。
【０１４９】
【数３１】
2014130601.tif 000033
【０１５０】
定義ステップＳ２０が依存し得る、点集合上の関係「コピーである」は、同値関係である。それを証明するには、以下の特性をチェックすれば十分であり、それは難しくない。（１）点集合はそれ自体のコピーである、（２）ＹがＸのコピーであるならば、ＸはＹのコピーである、（３）ＹがＸのコピーであり、ＺがＹのコピーであるならば、ＺはＸのコピーである。
【０１５１】
基本的な代数によれば、点集合の有限集合Ｇ（すなわち、Ｇの要素が点集合である）が与えられた場合、同値関係「コピーである」は、Ｇを、コピーからなる互いに素かつ最大の部分集合Ｇｉに分類する。これは、ｉ≠ｊならば、Ｇｉ∩Ｇｊ＝φであること、Ｇ＝∪ｉＧｉであること、Ｘ、Ｙ∈Ｇｉならば、ＹはＸのコピーであること、およびＸ∈Ｇｉかつ
【０１５２】
【数３２】
2014130601.tif 000034
【０１５３】
ならば、ＹはＸのコピーでないことを意味する。部分集合Ｇｉは、実際、同値関係の同値類を参照することによって、点集合の「類」となる。
【０１５４】
先の理論は、立体（すなわち、この例におけるモデル化オブジェクトは立体である）の面分に適用される（しかし、それに限定されない）。面分は、点集合の役割を演じ、立体のＢ−Ｒｅｐは、集合Ｇである。言い換えると、定義ステップＳ２０のために互いのコピーである面分の組を決定するため、当業者は、面分を点集合として、またＳ１０において提供されるＢ−Ｒｅｐを上で定義されたような集合Ｇとして表すことができる。
【０１５５】
互いのコピーであるＢ−Ｒｅｐの面分の組を決定する一例が、次に説明される。
【０１５６】
例えば、立体を表すモデル化オブジェクトを与えた場合、Ｓ１０において提供される立体のＢ−Ｒｅｐは、１組の独立した面分と見なされる。すなわち、Ｇ＝｛ｆ１、…、ｆｎ｝であり、ここで、ｆｉは、立体の第ｉの面分である。まさに最初のステップは、「コピーである」関係に従って、Ｇの部分集合を計算することである。全体的なアルゴリズムは、以下の通りであり得る。
For i = 1 to n do begin
If fi is not already used in a subset then
Create a new subset Gi := {fi}
For j := i + 1 to n do begin
If fj is not already used in a subset then
If fj is a copy of fj then
Gi := Gi∪{fｊ}
Store the rigid motion that
changes fi into fｊ
End if
End if
End for
End if
End for
【０１５７】
面分に対して「コピーである」関係をいかに実施するかについての例が、次に説明される。
【０１５８】
先に説明したように、立体の面分は、サポート面（例えば平面）と、境界稜線とによって定義される。一例では、面分は、立体の外向きの法線ベクトルを備える。境界稜線は、この法線ベクトルに従って方向付けされる。境界稜線は、共有頂点によって接続される。
【０１５９】
比較を実行して、剛体運動を見つけるため、各面分は、いくつかの軸系（ａｘｉｓ  ｓｙｓｔｅｍ）を備える。面分の各頂点ｖでは、軸系は、以下のように生成される。原点Ｐの座標は、頂点ｖの座標である。Ｕで表される第１のベクトルは、ｖの入力境界稜線の接線であり、−Ｕは、境界稜線と同じに方向付けされる。Ｖで表される第２のベクトルは、ｖの出力境界稜線の接線であり、境界稜線の方向に方向付けされる。「入力」および「出力」という語は、面分の法線ベクトルに従った、境界稜線の位相的方向付けに関連する。第３のベクトルは、頂点ｖにおいて計算される、面分の外向きの法線ベクトルＮである。Ｎは常にＵおよびＶに対して垂直であるにも係わらず、軸系（Ｐ，Ｕ，Ｖ，Ｎ）は、概して、有向でなく、直交しないことに留意されたい。
【０１６０】
図９〜図１１は、半円筒面分９０の軸系を示している。図９は、面分９０と、その法線ベクトル９２とを示している。図１０は、法線ベクトル９２によって誘導される境界稜線９４の位相的方向付けを示している。境界稜線ａは、頂点ｖの入力稜線である。境界稜線ｂは、頂点ｖの出力稜線である。図１１は、各境界頂点における軸系のベクトルＵ、Ｖ、Ｎを表示している。
【０１６１】
ここで、方法は、一例では、コピー面分の組の決定において、２つの面分が互いのコピーであるかどうかを、存在するならば、（後で定義ステップＳ２０において使用できる）それらの間の剛体運動を直接的に探索することによって判定することができる。ｆ、ｇを、（同数の）局所軸系
【０１６２】
【数３３】
2014130601.tif 000035
【０１６３】
および
【０１６４】
【数３４】
2014130601.tif 000036
【０１６５】
をそれぞれ備える、２つの面分とする。面分ｆ、ｇが、同数の局所軸系を有さない場合、それは、それらが、同数の境界頂点を有さないことを意味し、そのため、それらは互いのコピーではないと判定され、剛体運動探索は開始されない。
【０１６６】
別の場合では、第１のステップは、面分ｆの第ｉの軸系を面分ｇの第ｊの軸系に変更する剛体運動Ｄｉ，ｊをそれぞれ計算することである。ｉ、ｊ＝１、…、ｍであるので、最大でｍ２個のそのような剛体運動が存在する。形式的に、剛体運動は、
【０１６７】
【数３５】
2014130601.tif 000037
【０１６８】
のようになる。
【０１６９】
【数３６】
2014130601.tif 000038
【０１７０】
、
【０１７１】
【数３７】
2014130601.tif 000039
【０１７２】
、およびＤｉ，ｊ（ｘ）＝Ｒｉ，ｊｘ＋Ｔｉ，ｊであり、これは、未知数が、行列Ｒｉ，ｊの係数と、ベクトルＴｉ，ｊの座標であることに留意して、最初に、以下の線形システムを解くことによって獲得されることに留意されたい。
【０１７３】
【数３８】
2014130601.tif 000040
【０１７４】
第２に、行列Ｒｉ，ｊが回転であることを保証するために、以下の２つの条件が、チェックされなければならない。
Ｒｉ，ｊＲｉ，ｊＴ＝Ｉ
ｄｅｔ（Ｒｉ，ｊ）＝１
【０１７５】
これらが満たされない場合、Ｒｉ，ｊは回転ではないので、Ｄｉ，ｊは剛体運動ではない。
【０１７６】
その後、ｆをｇに変更する剛体運動Ｄ＊が、存在するならば、先に計算されたＤｉ，ｊの中から見出される。ここでの問題は、ｆ、ｇ、および剛体運動Ｄが与えられた場合、Ｄ（ｆ）＝ｇは真か？という質問に答えることである。これは、３Ｄ点ｘｋ、ｋ＝１、…、ｑの集まりで面分ｆをサンプリングし、点Ｄ（ｘｋ）と面分ｇの間の距離が、同一のオブジェクトについての所定の閾値数値と比較して、十分に小さいことをチェックすることによって、行うことができる。Ｄｉ，ｊの中のいくつかの剛体運動がｆをｇに変更できる場合、可能なときは、純粋な並進が選択される。これは、コピー面分の組を決定するステップを実行する効率的な方法であり、ユーザの意図に沿った結果をもたらす。
【０１７７】
決定されたコピー面分の組（すなわち、上述の「部分集合」）のためのデータ構造の一例が、次に説明される。
【０１７８】
剛体運動および関連する点集合は、（所与の面分に対応する）所与の点集合のコピーと、関連する剛体運動とを取り出すために、次に説明される適切なデータ構造内に記憶することができる。概念的に、このデータ構造は、有向グラフＷ＝（Ｐ，Ａ，α，ω）を含み、ここで、ノードＰは、点集合であり、弧Ａは、剛体運動によってラベル付けされる。ラベル付けは、写像ｍ：Ａ→ＳＥ（３）であり、ここで、ＳＥ（３）は、３次元剛体運動のグループである。より正確には、弧ｕ∈Ａは、ノードα（ｕ）＝ｘ∈Ｐで開始し、ノードω（ｕ）＝ｙ∈Ｐで終了するという記述は、点集合ｘと点集合ｙが、互いのコピーであること、および剛体運動ｍ（ｕ）が、ｘをｙに変更し、それは、ｙ＝ｍ（ｕ）ｘと表記されることを意味する。ここで、弧ｖ∈Ａが、ｘとｚ∈Ｐとを接続し、それが、α（ｖ）＝ｘ、ω（ｖ）＝ｚと記述されると仮定する。ｘをｚに変更する剛体運動は、ｚ＝ｍ（ｖ）ｘである。その場合、ｚは、ｙのコピーでもあり、ｙをｚに変更する剛体運動は、ｚ＝ｍ（ｖ）ｍ（ｕ）−１ｙである。反対に、ｚをｙに変更する剛体運動は、ｙ＝ｍ（ｕ）ｍ（ｖ）−１ｚである。この情報はすべて、データ構造によって保存することができる。
【０１７９】
性質上、初期サブセットを計算するアルゴリズムは、それらの各々がサブセットである、深度１の木グラフから作成される、グラフを生成する。定義上、深度１の木は、入力弧のない１つのノード（根ノード）と、出力弧のない他のすべてのノード（葉ノード）とを有する木グラフである。言い換えると、すべての非根ノードは、根ノードに接続される。結果として、深度１の木グラフ内の任意の２つのノードを与えた場合、それらを連結する弧からなる経路がただ１つ存在し、この一意的な経路は、ただ２つの弧を含む。
【０１８０】
図１２〜図１３は、初期サブセットを計算するアルゴリズム（コピー面分の組を決定するステップＳ２０）からもたらされる、グラフデータ構造を示している。図１２は、面分に１から１２までの番号が付された、一列に並んだ４つの円筒スロットからなる、モデル化オブジェクトのＢ−Ｒｅｐ１２０を示している。それらには、位相的データ構造内におけるある任意の記憶に従って、番号が付されている。図１３は、２つの深度１の木１３２を含む、グラフ１３０を示している。
【０１８１】
したがって、１つの点集合を他の任意の点集合に変更する剛体運動は、２つの点集合を連結する弧からなる経路に沿って剛体運動を組み合わせることによって計算される。この経路は２つの弧を含むので、ただ２つの剛体運動が組み合わされる。サブセット内の任意の２つの点集合に関連する剛体運動を計算するこの機能は、方法のこの例において広く使用される。したがって、コピー面分の任意のペア間の剛体運動は、グラフ１３０などのグラフから簡単に取り出す／決定することができるので、そのようなグラフから、方法は、定義ステップＳ２０を非常に容易に実行することができる。
【０１８２】
したがって、この時点で、方法は、すべての重複する幾何学形状と、関連する剛体運動とを、Ａと表記され得るグラフに収集していることがある。グラフＡのノードは、幾何学形状を表し、グラフＡの弧は、剛体運動を表す。グラフＡ（Ｓ２０において定義されたグラフ）の各連結成分Ｂは、同じ幾何学形状のコピーを集め、複雑な構造である可能性がある。
【０１８３】
方法の次のステップの例は、以下の通りである。
１．グラフＡの各連結成分Ｂ内において、弧は、類似基準クラスに従って、別々のサブセットにグループ化される。これは、決定ステップＳ３０の一例である。
２．その後、最多の弧を含むサブセットが、最も重複する基本構造を獲得するための最良の候補になる。これは、識別ステップＳ４０の開始の一例である。
３．弧のこの最大のサブセットに対応するＢの部分グラフＣが考察され、Ｃの連結成分Ｃｉが計算される。これは、識別ステップＳ４０の次のフェーズの一例である。
４．各連結成分Ｃｉのすべての弧が、同じ剛体運動を表す場合、基本パターンが認識される。これは、識別ステップＳ４０の終了の一例である。
５．グラフＢは、各連結成分Ｃｉのノードを単一のノードにマージし、無用な弧を廃棄することによって、新しいグラフＢ’に簡略化される。これは、識別された連結成分の組の各連結成分のノードを折り畳むことによって、グラフを変更する一例である。
【０１８４】
ステップ１および２の目標は、基本パターンを獲得する可能性のある部分グラフの収集を可能にする、適切な条件を提供することである。プロセスは、新しいパターンが認識されなくなるまで、グラフＢの一連の簡略化バージョンに反復的に適用することができる。初期グラフＡの各連結成分は、後で詳述されるように、このようにしてさらに処理することができる。ステップ４において、必ずしもすべての連結成分Ｃｉが同じ剛体運動を備えるとは限らない場合、サブセットＣは分割される。この分割プロセスは、弧のサブセットを可能な限り大きく維持しながら、類似基準を改善するためのものである。
【０１８５】
この例における方法は、主に反復プロセスである。例におけるアルゴリズムのコアは、「基本パターンレコグナイザ（ｅｌｅｍｅｎｔａｒｙ  ｐａｔｔｅｒｎ  ｒｅｃｏｇｎｉｚｅｒ）」であり、「パターンからなるパターンのレコグナイザ（ｐａｔｔｅｒｎ  ｏｆ  ｐａｔｔｅｒｎｓ  ｒｅｃｏｇｎｉｚｅｒ）」内に反復的に含まれる。基本パターンが認識されると、入力グラフが簡略化され、認識が再び実行される。パターンからなるパターンのレコグナイザは、図１４の図に示されるように動作することができる。基本パターンレコグナイザは、図１５の図で説明されるように動作することができる。
【０１８６】
Ｂ−Ｒｅｐの一例を用いる方法の一例が、次に説明される。
【０１８７】
例のＢ−Ｒｅｐ１６０は、図１６に示されるように、（方法の簡単な理解のために）平面内に配置された１組の１８個の円を含む（すなわち、互いのコピーであり、Ｓ１０において提供される面分は、図の平面に対応する平面によってサポートされ、円によって境界付けされた円盤である）。円には、１から１８までの番号が付されている。円１、２、３は、円環（ｃｒｏｗｎ）の周囲に配置され得たことが分かる。その後、この円環は、２回並進され、その全体が、１回回転され得た。これが、少なくとも機械設計の分野においては、ユーザ意図に従っている可能性が最も高い、図１６の例のＢ−Ｒｅｐの設計の履歴である。方法の目標は、この反復的な回転−並進−回転のパターン構造を、幾何学形状と剛体運動との入力グラフから取り出すことである。
【０１８８】
図１６の例に対応する幾何学形状および剛体運動を集めた、例えば、図９〜図１３を参照して上で説明したような、Ｓ２０において定義されたグラフＢが、図１７に示されている。簡潔にするため、図では、弧には番号が付されていないが、それらは終了ノード番号によって識別することができるからである。弧は、剛体運動を用いてラベル付けされる。記号Ｔｉは、並進を示し、記号Ｒｉは、回転を示す。例えば、並進Ｔ１を介して、円４は、円１のコピーであり、同様に、円１４は、円５のコピーである。回転Ｒ１を介して、円２は、円１のコピーである。円１０は、回転Ｒ５を介して、円１２のコピーである。回転Ｒ１とＲ５は、同じ角度２π／３を有するにも係わらず、それらは、同じ中心を有さないので、同一ではない。また、明瞭にするため、出現が３回未満の剛体運動も、図では排除されている。
【０１８９】
基本パターン認識のまさに最初のステップの一例は、グラフＢの弧をいわゆる「クラス」にグループ化することである（これは決定ステップＳ３０である）。クラスは、関連する剛体運動と幾何学的対象とに関係する類似基準に従って、弧を集める。上で説明したように、類似基準は、剛体運動の厳格な同等性よりも弱い。
【０１９０】
図１７のグラフから開始する決定ステップＳ３０の実施の一例が、次に説明される。
【０１９１】
準備的な定義が役に立つ。ｕｉ、ｉ＝１、２を、２つの弧とし、Ｄｉ＝（Ｒｉ，Ｔｉ）、ｉ＝１、２を、それぞれ弧ｕｉに関連付けられた剛体運動とする。形式的に、Ｄｉ＝ｍ（ｕｉ）とする。θｉを、回転Ｒｉの角度とし、Ａｉを、回転Ｒｉの軸とする。ｘｉ＝α（ｕｉ）を、弧ｕｉの始点における幾何学的対象とし、ｇ（ｘｉ）を、重心とする。
【０１９２】
定義によって、ｕｉの半径は、ｇ（ｘｉ）とＡｉの間の距離ｄｉである。図１８〜図１９に示されるように、ｘｉの代わりに、弧ｕｉの終点における幾何学的対象であるｙｉ＝ω（ｕｉ）を考えることによっても、同じ値ｄｉが獲得される。
【０１９３】
先に提供された類似基準の例によれば、以下の条件の１つが成り立つ場合、弧ｕ１およびｕ２は、類似している。
１．Ｄ１およびＤ２は、純粋な並進であり、それらの並進ベクトルが、同じ長さを有する。形式的に、θ１＝θ２＝０、および｜Ｔ１｜＝｜Ｔ２｜である。
２．Ｄ１およびＤ２は、純粋な並進ではない。それらの回転は、同じ絶対角度を有し、形式的に、｜θ１｜＝｜θ２｜≠０である。弧ｕ１およびｕ２の半径は、等しく、形式的に、ｄ１＝ｄ２である。
【０１９４】
これ以外の場合、弧ｕ１およびｕ２は、類似していない。
【０１９５】
例の方法は、決定ステップＳ３０を実行するために、適切なテストを実行して、類似する剛体運動を決定することができる。
【０１９６】
基本的な代数によれば、すでに説明したように、類似関係は、弧の集合上の同値関係であり、それは、（定理によって）弧の集合を最大の互いに素の部分集合に分類し、それは、「同値類」と呼ばれることがある。
【０１９７】
例に戻ると、グラフＢ上で実行されるクラス計算および部分グラフ抽出は、Ｓ３０において、図２０〜図２２に示される３つの最大の部分グラフをもたらす。図２０の部分グラフＣは、回転Ｒｉ、ｉ＝１、…、６が、すべて同じ角度および同じ半径を有するという事実によっている（それらは、同じ中心を有さないので、同一ではない）。それは、１８本の弧を含む。図２１の部分グラフ２１０は、回転Ｒ７に由来する。それは、９本の弧を含む。図２２の部分グラフ２２０は、並進Ｔ１およびＴ２が、同一でないにも係わらず、同じ長さを有するという事実に由来する。それは、１２本の弧を含む。
【０１９８】
図２０〜図２２の最大の部分グラフＣ、２１０、２２０の決定ステップＳ３０の後に実行される、識別ステップＳ４０の一例が、次に説明される。
【０１９９】
次のステップは、最多の弧を備える部分グラフを選択することであり、それは、例では、１８本の弧を含むためにグラフＣである。グラフＣは、６個の連結成分Ｃｉ＝１．．．６を含む。成分Ｃ１は、ノード１、２、３を含み、成分Ｃ２は、ノード４、５、６を含み、成分Ｃ３は、ノード７、８、９を含み、成分Ｃ４は、ノード１０、１１、１２を含み、成分Ｃ５は、ノード１３、１４、１５を含み、成分Ｃ６は、ノード１６、１７、１８を含む。各連結成分のすべての弧は、同じ剛体運動によってラベル付けされ、成分Ｃ１の弧は、すべて回転Ｒ１によってラベル付けされ、成分Ｃ２の弧は、すべて回転Ｒ２によってラベル付けされるなどである。結果として、例のアルゴリズムは、各連結成分が、基本パターンであり、それは、３つの円からなる小さな円環であることを認識することができる。これは、識別ステップＳ４０である。
【０２００】
その後、方法を反復して行うことができる。グラフＢは、先に提供された潰しの例を用いて説明したように、各連結成分Ｃｉのノードを単一のノードにマージすることによって、グラフＢ’に簡略化される。１つの成分から別の成分にノードを連結するグラフＢの弧は、例えば、以下のように管理することができる。ＣｉおよびＣｊを、２つの異なる成分とする。ノードＣｉとノードＣｊの間に１対１写像が存在し、この写像のすべての弧が同じ剛体運動Ｄを用いてラベル付けされる場合、簡略化されたグラフＢ’は、単一のノードＣｉと単一のノードＣｊとを連結する１つの弧を備え、それは、剛体運動Ｄを用いてラベル付けされる。他の場合、Ｃｉの幾何学形状は、Ｃｊの幾何学形状と全体的には等大でなく、簡略化されたグラフにおいて、弧は生成されない。
【０２０１】
例では、これは、図２３の簡略化されたグラフＢ’をもたらす。読み易いように、マージングからもたらされるノードの名前は、図における最初のノード番号に基づいている。
【０２０２】
今度は、簡略化されたグラフＢ’を、例のアルゴリズムの次の反復の入力グラフとすることができる。Ｂ’の弧上で実行される同値類計算は、図２４〜図２５に示されるように、２つのサブセットＣ’および２５０をもたらす。Ｃ’と表記される部分グラフは、｜Ｔ１｜＝｜Ｔ２｜であるので、４本の弧を含み、一方、部分グラフ２５０は、３本の弧を含む。
【０２０３】
その場合、部分グラフＣ’上で上述のような基本パターン認識を実行することを選択することができ、それは、それが最多の弧を含むからである。これは、連結成分ごとに１つの、２つの基本パターンをもたらす。その場合、グラフＢ’は、図２６に示されるように、グラフＢ”に簡略化される。
【０２０４】
例のまさに最後の反復は、グラフＢ”上において、回転Ｒ７を介する２つのコピーからなる基本パターンを認識することである。この反復は、詳述しない。
【０２０５】
最終的に、例の方法によって認識される反復的なパターン構造のロジック２７０は、階層的グラフのグラフィカルシンタックスを使用して、図２７に示されるようなものとすることができる。したがって、方法は、Ｓ１０において提供されたＢ−Ｒｅｐ１６０の１組の面分が、ロジック２７０に従うことを示すデータを出力することができ、ロジックは、Ｂ−Ｒｅｐのパターンからなるパターンの完全な構造を表す階層的データである。
【０２０６】
図１６〜図２７を参照して提供された例では、識別ステップＳ４０は、Ｓ３０において決定された部分グラフ内において、最多の弧を有する部分グラフを単純に選択することによって、常に実行される。実際に、この例では、（Ｃｉ＝１．．．６、図２４のグラフＣ’の連結成分、次に図２６のＢ”の単一の連結成分を含む）選択された部分グラフの連結成分は、常にすべて同一基準を順守する。
【０２０７】
しかし、概括的なケースでは、これは必ずしも真であるとは限らない。したがって、方法は、これが真ではない特別なケースを考慮することによって、改良することができ、「誤った結果」の出力をより少なくすることができる。これは、以下のように行うことができる。
【０２０８】
識別ステップＳ４０は、上述したように、最多の弧を有する部分グラフを、決定された部分グラフ内において選択するステップを含むことができる。しかし、識別ステップＳ４０は、選択された部分グラフの各連結成分の弧によって表される剛体運動がどれも同一基準を順守するかどうかをテストするステップも含むことができる。言い換えると、最多の弧を有する部分グラフの連結成分が考察される（したがって、すべての弧は「類似」しており、すなわち、類似する剛体運動を表す）。方法は、実際には、そのように個別に（すなわち１つずつ）考察される各連結成分が、実際に同一である弧のみからなる（すなわち、同一の剛体運動を表す）かどうかを（コンピュータサイエンスの分野において旧知の方法で）テストする。
【０２０９】
テストの結果として、異なる戦略に従って、正しい連結成分の組を識別し、それによって、方法を終了させることができる。実施が簡単な１つの方法は、以下で説明するような分割手順を実行することである。
【０２１０】
分割手順では、識別ステップＳ４０は、テストの結果として、以下のアクションをさらに含む。テストの結果が肯定的である（すなわち、選択された部分グラフのすべての連結成分が各々同一基準を順守する）場合、方法は、選択された部分グラフの連結成分として連結成分の組を識別する（すなわち、選択された部分グラフの連結成分は、識別ステップＳ４０によって出力される組を形成する）。これが、実際には常に、図１６〜図２７の例における状況である。しかし、そうではない、すなわち、テストの結果が否定的である場合、方法は、選択された部分グラフの分割を実行し、選択およびテストを再実行する。分割は、再実行した場合にテスト手順の結果が肯定的である可能性がより高まる状態になるように、選択された部分グラフを割ることによって、選択された部分グラフを変更することからなる。これは、最終的に、反復を終了させることを可能にする。
【０２１１】
迅速に収束し、設計を順守する例では、分割は、選択された部分グラフ内の部分グラフの弧を、選択された部分グラフから切り取ることを含み、これは、便宜的に、「部分グラフを切り取る」と言われることがある。切り取られる部分グラフは、選択された部分グラフ内のすべての部分グラフのうちで、最多の弧を有し、弧によって表される剛体運動がすべて同一基準を順守する部分グラフである。そのような部分グラフがいくつか存在する（すなわち、弧の数が等しい）ケースは、任意の方法で扱うことができる。その後、分割は、切り取られた弧を用いて、新しい部分グラフを生成することも含む。
【０２１２】
これは、例によって、以下で詳述される。
【０２１３】
例の分割プロセスは、以下の条件で実行される。グラフＢを、入力グラフＡの連結成分とする。クラス計算が、Ｓ３０において、Ｂの弧をサブセットに区分する区分を決定する。グラフＣは、最大のサブセットによって定義されるＢの部分グラフである。部分グラフＣｉは、Ｃの連結成分である。Ｃ０と表記される、これらの少なくとも１つと、関連する剛体運動ｍ（ｕ）およびｍ（ｖ）が等しくないような、Ｃ０の２つの弧ｕ、ｖとが存在する。
【０２１４】
その後、例の分割プロセスは、以下のように動作する。先に定義されたようなＣ０を与えた場合、第１のステップは、Ｄｉ、ｉ＝１、…、ｎと表記される、Ｃ０の弧に関連付けられたすべての異なる剛体運動を識別することである。概して、剛体運動の数ｎは、Ｃ０内の弧の数よりも少なく、それは、いくつかの弧が、同じ剛体運動に関連付けられることがあるからである。第２のステップは、共有される剛体運動に従って、Ｃ０の弧をグループ化することである。形式的に、ｉ＝１、…、ｎである場合、Ｕｉは、すべてのｕ∈Ｕｉについて、ｍ（ｕ）＝Ｄｉであるような、Ｃ０の弧の部分集合であり、要するに、Ｕｉ＝ｍ−１（Ｄｉ）である。ここで、Ｇ（Ｕｉ）を、Ｕｉ内の弧によって定義されるＣ０の部分グラフとする。次のステップは、これらの部分グラフのすべての組合せを考察することである。各部分集合Ｑ⊂｛１、…、ｎ｝は、
【０２１５】
【数３９】
2014130601.tif 000041
【０２１６】
によって、そのような組合せを定義する。
【０２１７】
次のステップは、すべてのＱ⊂｛１，…，ｎ｝のうちから、最多の弧を有し、Ｋ（Ｑ）の各連結成分については、すべての弧が同じ剛体運動に関連付けられる、組合せＫ（Ｑ）を選択することである。この特性を備える｛１，…，ｎ｝の部分集合をＱ＊と表記する。分割操作は、部分集合の区分において、Ｃ０の弧の部分集合を、部分集合
【０２１８】
【数４０】
2014130601.tif 000042
【０２１９】
と、それとは相補的な部分集合
【０２２０】
【数４１】
2014130601.tif 000043
【０２２１】
とによって置き換えることである。
【０２２２】
言い換えると、分割は、選択された部分グラフから、同一基準を順守する剛体運動を表す弧を有する、それの最大（弧の数に関して「最大」）の部分部分グラフ（ｓｕｂ−ｓｕｂ−ｇｒａｐｈ）を切り取る。その後、再び、Ｓ３０において最初に決定された１組の最大の部分グラフの変更バージョンにおいて、選択が実行され、その後、再び、テストも実行されるので、再び、分割が実行されることがある。最終的に、必ず、結果は、アルゴリズムが収束するように、同一の弧を有する連結成分のみを有する、選択された部分グラフになる。もちろん、分割の結果は、方法が反復されるとき、決定（Ｓ３０）および識別（Ｓ４０）の次回以降の反復において、入力要素が同じ（例えば、分割される部分グラフが同じ）であれば、より迅速に分割を実行できるように、記憶することができる。
【０２２３】
図２８は、分割操作が好ましく、誤った結果を回避する助けになる状況を例示している。この例ではＳ１０において提供されるＢ−Ｒｅｐは、等間隔に配置された（８から１４の番号が付された）７個の円から作られる部分円環と、（１から６の番号が付された）６個の円からなるグリッドと、グリッドと整列していない（７の番号が付された）追加の円とを含む。
【０２２４】
この幾何学形状に対応する、Ｓ２０において定義されるグラフＢが、図２９に提供されている。頂点の番号付けは、一目瞭然である。弧は、文字「ａ」から「ｎ」によって名付けられ、関連する剛体運動を用いてラベル付けされている。並進ベクトルは、同じ長さ｜Ｔ１｜＝｜Ｔ２｜＝｜Ｔ３｜を有する。
【０２２５】
明らかに、グラフＢは、図２９に示されるように、２つの連結成分２９２、２９４を備える。グラフＢの弧上で実行されるクラス計算は、２つの部分集合｛ｉ，ｊ，ｋ，ｌ，ｍ，ｎ｝および｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ｝をもたらし、最大の部分集合は、第２のものである。そのため、部分グラフＣは、頂点１から７と、弧ａからｈとによって定義される。この部分グラフは連結であるので、それはＣ０に等しい。
【０２２６】
Ｃ０のすべての弧が同じ剛体運動に関連付けられているわけではないので、分割プロセスが必要とされる。例えば、弧ａは、並進Ｔ１に関連付けられ、一方、弧ｂは、Ｔ１と等しくない並進Ｔ２に関連付けられる。これは、ｍ（ａ）＝Ｔ１≠Ｔ２＝ｍ（ｂ）と書かれる。第１の分割するステップは、Ｃ０の弧に関連付けられたｎ＝３個の剛体運動を識別し、それらは、Ｔ１、Ｔ２、Ｔ３である。剛体運動による弧のグループ化は、
Ｕ１＝ｍ−１（Ｔ１）＝｛ａ，ｄ，ｇ｝
Ｕ２＝ｍ−１（Ｔ２）＝｛ｂ，ｃ，ｅ，ｆ｝
Ｕ３＝ｍ−１（Ｔ３）＝｛ｈ｝
をもたらす。
【０２２７】
ここで、すべての部分集合Ｑ⊂｛１，２，３｝の調査は、部分グラフ
Ｋ（｛１、２｝）＝Ｇ（Ｕ１∪Ｕ２）＝Ｇ（｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ｝）
Ｋ（｛１、３｝）＝Ｇ（Ｕ１∪Ｕ３）＝Ｇ（｛ａ，ｄ，ｇ，ｈ｝）
Ｋ（｛２、３｝）＝Ｇ（Ｕ２∪Ｕ３）＝Ｇ（｛ｂ，ｃ，ｅ，ｆ，ｈ｝）
Ｋ（｛１｝）＝Ｇ（Ｕ１）＝Ｇ（｛ａ，ｄ，ｇ｝）
Ｋ（｛２｝）＝Ｇ（Ｕ２）＝Ｇ（｛ｂ，ｃ，ｅ，ｆ｝）
Ｋ（｛３｝）＝Ｇ（Ｕ３）＝Ｇ（｛ｈ｝）
をチェックすることである。
【０２２８】
グラフＫ（｛１，２，３｝）は、Ｃ０自体であるので、関係がない。グラフＫ（φ）は、空であるので、関係がない。図３０は、部分グラフＫ（Ｑ）を示している。明らかに、特性（各連結成分のすべての弧は同じ剛体運動に関連付けられる）は、グラフＫ（｛１｝）、Ｋ（｛２｝）、およびＫ（｛３｝）によっては満たされるが、他のいずれのグラフによっても満たされない。（弧の数に関して）最大のものは、Ｋ（｛２｝）である。そのため、分割は、部分集合｛ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇ，ｈ｝を、｛ｂ，ｃ，ｅ，ｆ｝および｛ａ，ｄ，ｇ，ｈ｝に分離する。
【０２２９】
次のステップは、この新しい部分集合を再区分するための反復であり、この場合、｛ｉ，ｊ，ｋ，ｌ，ｍ，ｎ｝である、最大の部分集合を見つける。対応する部分グラフのすべての弧は、同じ剛体運動Ｒ１に関連付けられているので、アルゴリズムは、対応する基本パターンを識別する。残りの最大の部分集合は、｛ｂ，ｃ，ｅ，ｆ｝であり、ノードを潰した後、次の反復において扱われる。実際に、潰しは、分割の後、先に説明したのと同じ方法で、実行することができる。
【図１】
2014130601.tif 000044
【図２】
2014130601.tif 000045
【図３】
2014130601.tif 000046
【図４】
2014130601.tif 000047
【図５】
2014130601.tif 000048
【図６】
2014130601.tif 000049
【図７】
2014130601.tif 000050
【図８】
2014130601.tif 000051
【図９】
2014130601.tif 000052
【図１０】
2014130601.tif 000053
【図１１】
2014130601.tif 000054
【図１２】
2014130601.tif 000055
【図１３】
2014130601.tif 000056
【図１４】
2014130601.tif 000057
【図１５】
2014130601.tif 000058
【図１６】
2014130601.tif 000059
【図１７】
2014130601.tif 000060
【図１８】
2014130601.tif 000061
【図１９】
2014130601.tif 000062
【図２０】
2014130601.tif 000063
【図２１】
2014130601.tif 000064
【図２２】
2014130601.tif 000065
【図２３】
2014130601.tif 000066
【図２４】
2014130601.tif 000067
【図２５】
2014130601.tif 000068
【図２６】
2014130601.tif 000069
【図２７】
2014130601.tif 000070
【図２８】
2014130601.tif 000071
【図２９】
2014130601.tif 000072
【図３０】
2014130601.tif 000073
【外国語明細書】
2014130601000001.pdf