(57)【要約】  ＣＡＤシステムおよび対応する方法およびコンピュータプログラム製品。方法は、交差するカーブの組を受け付けるステップと、交差するカーブの組からのソースカーブおよびデスティネーションカーブの選択を受け付けるステップとを含む。該方法は選択意図規則を受け付けるステップと、選択意図規則に従って、交差するカーブの組から、ソースカーブを含むカーブの第１のチェーンを計算するステップとを含む。該方法は、選択された経路を保存するステップを含み、該選択された経路は、選択意図規則から最小数のずれを有する、デスティネーションカーブとソースカーブとの間のカーブのチェーンである。
2013530443.tif 000002
【特許請求の範囲】
【請求項１】
ＣＡＤシステムにおける自動経路決定のための方法であって、
ＣＡＤシステムが、交差するカーブの組を受け付けるステップと、
ＣＡＤシステムが、前記交差するカーブの組からのソースカーブおよびデスティネーションカーブの選択を受け付けるステップと、
ＣＡＤシステムが、選択意図規則を受け付けるステップと、
ＣＡＤシステムが、前記選択意図規則に従って、前記交差するカーブの組から、前記ソースカーブを含むカーブの第１のチェーンを計算するステップと、
ＣＡＤシステムが、選択された経路を保存するステップであって、該選択された経路は、前記選択意図規則から最小数のずれを有する、前記デスティネーションカーブと前記ソースカーブとの間のカーブのチェーンである、ステップと、
を含む、ことを特徴とする方法。
【請求項２】
前記選択意図規則に従って、前記交差するカーブの組から、前記デスティネーションカーブを含むカーブの第２のチェーンをさらに計算する、請求項１記載の方法。
【請求項３】
前記カーブの第１のチェーンと前記カーブの第２のチェーンとが同じであるか否かを判別する、請求項２記載の方法。
【請求項４】
前記カーブの第１のチェーンと前記カーブの第２のチェーンとが同じでない場合、その後、前記選択意図規則からの１以上のずれを有するソースカーブを含む、少なくとも１つの付加的なカーブのチェーンを計算する、請求項２記載の方法。
【請求項５】
前記カーブの第１のチェーンと前記カーブの第２のチェーンとが同じでない場合、その後、前記ソースカーブと、前記カーブの第１のチェーンと前記カーブの第２のチェーンの両方に共通する少なくとも１つの付加的なカーブとを含む、カーブの少なくとも１つの付加的なチェーンを計算する、請求項２記載の方法。
【請求項６】
複数の選択された経路が保存され、該複数の選択された経路のうちの最短の経路を同定する、請求項１記載の方法。
【請求項７】
前記選択され、保存された経路は、前記選択意図規則から同じ最小数のずれを有する複数の経路のうちの、前記ソースカーブと前記デスティネーションカーブとの間の最短の経路である、請求項１記載の方法。
【請求項８】
プロセッサとアクセス可能メモリとを備えたＣＡＤシステムであって、該ＣＡＤシステムは有利には以下のステップ、すなわち、
交差するカーブの組を受け付けるステップと、
前記交差するカーブの組からのソースカーブおよびデスティネーションカーブの選択を受け付けるステップと、
選択意図規則を受け付けるステップと、
前記選択意図規則に従って、前記交差するカーブの組から、前記ソースカーブを含むカーブの第１のチェーンを計算するステップと、
選択された経路を保存するステップであって、該選択された経路は、前記選択意図規則から最小数のずれを有する、前記デスティネーションカーブと前記ソースカーブとの間のカーブのチェーンである、ステップと、
を実行するように構成されている、ことを特徴とするＣＡＤシステム。
【請求項９】
前記選択意図規則に従って、前記交差するカーブの組から、前記デスティネーションカーブを含むカーブの第２のチェーンを計算するステップを実行するようにさらに構成されている、請求項８記載のＣＡＤシステム。
【請求項１０】
前記カーブの第１のチェーンと前記カーブの第２のチェーンとが同じであるか否かを判別するステップを実行するようにさらに構成されている、請求項９記載のＣＡＤシステム。
【請求項１１】
前記カーブの第１のチェーンと前記カーブの第２のチェーンとが同じでない場合、その後、前記選択意図規則からの１以上のずれを有するソースカーブを含む、カーブの少なくとも１つの付加的なチェーンを計算するステップを実行するようにさらに構成されている、請求項９記載のＣＡＤシステム。
【請求項１２】
前記カーブの第１のチェーンと前記カーブの第２のチェーンとが同じでない場合、その後、前記ソースカーブと、前記カーブの第１のチェーンと前記カーブの第２のチェーンの両方に共通する少なくとも１つの付加的なカーブとを含む、カーブの少なくとも１つの付加的なチェーンを計算するステップを実行するようにさらに構成されている、請求項９記載のＣＡＤシステム。
【請求項１３】
複数の選択された経路が保存され、該複数の選択された経路のうちの最短の経路を同定するように構成されている、請求項８記載のＣＡＤシステム。
【請求項１４】
前記選択され、保存された経路は、前記選択意図規則から同じ最小数のずれを有する複数の経路のうちの、前記ソースカーブと前記デスティネーションカーブとの間の最短の経路である、請求項８記載のＣＡＤシステム。
【請求項１５】
コンピュータ実行可能命令がコード化されたコンピュータ読み取り可能記録媒体であって、該命令は、実行時に、ＣＡＤデータ処理システムに以下のステップ、すなわち、
交差するカーブの組を受け付けるステップと、
前記交差するカーブの組からのソースカーブおよびデスティネーションカーブの選択を受け付けるステップと、
選択意図規則を受け付けるステップと、
前記選択意図規則に従って、前記交差するカーブの組から、前記ソースカーブを含むカーブの第１のチェーンを計算するステップと、
選択された経路を保存するステップであって、該選択された経路は、前記選択意図規則から最小数のずれを有する、前記デスティネーションカーブと前記ソースカーブとの間のカーブのチェーンである、ステップと、
を行わせる、ことを特徴とするコンピュータ読み取り可能記録媒体。
【請求項１６】
前記選択意図規則に従って、前記交差するカーブの組から、前記デスティネーションカーブを含むカーブの第２のチェーンを計算するステップを、実行時に、ＣＡＤデータ処理システムに行わせるコンピュータ実行可能命令がさらにコード化された、請求項１５記載のコンピュータ読み取り可能記録媒体。
【請求項１７】
前記カーブの第１のチェーンと前記カーブの第２のチェーンとが同じであるか否かを判別するステップを、実行時に、ＣＡＤデータ処理システムに行わせるコンピュータ実行可能命令がさらにコード化された、請求項１６記載のコンピュータ読み取り可能記録媒体。
【請求項１８】
前記カーブの第１のチェーンと前記カーブの第２のチェーンとが同じでない場合、その後、前記選択意図規則からの１以上のずれを有するソースカーブを含む、カーブの少なくとも１つの付加的なチェーンを計算するステップを、実行時に、ＣＡＤデータ処理システムに行わせるコンピュータ実行可能命令がさらにコード化された、請求項１６記載のコンピュータ読み取り可能記録媒体。
【請求項１９】
前記カーブの第１のチェーンと前記カーブの第２のチェーンとが同じでない場合、その後、前記ソースカーブと、前記カーブの第１のチェーンと前記カーブの第２のチェーンの両方に共通する少なくとも１つの付加的なカーブと、を含む少なくとも１つの付加的なカーブのチェーンを計算するステップを、実行時に、ＣＡＤデータ処理システムに行わせるコンピュータ実行可能命令がさらにコード化された、請求項１６記載のコンピュータ読み取り可能記録媒体。
【請求項２０】
複数の選択された経路が保存され、該複数の選択された経路のうちの最短の経路を同定する、請求項１５記載のコンピュータ読み取り可能記録媒体。
【請求項２１】
前記選択され、保存された経路は、前記選択意図規則から同じ最小数のずれを有する複数の経路のうちの、前記ソースカーブと前記デスティネーションカーブとの間の最短の経路である、請求項１５記載のコンピュータ読み取り可能記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、コンピュータベースの設計、製造、エンジニアリング、モデリングおよび視覚化（それぞれまたはまとめて「ＣＡＤ」および「ＣＡＤシステム」）、ならびに、プロダクトライフサイクルマネジメント（「ＰＬＭ」）および他のシステムにおける使用のためのシステムおよび方法に関する。
【背景技術】
【０００２】
多くの工業製品は最初にＣＡＤシステムで設計およびモデルリングされ、製造業者、小売業者、消費者および他のユーザにより、様々な製品の設計、使用および廃棄を管理するためにＰＬＭシステムが用いられる。改善されたシステムが望まれている。
【発明の概要】
【課題を解決するための手段】
【０００３】
種々の開示の実施形態には、ＣＡＤシステムおよび対応する方法およびコンピュータプログラム製品が含まれる。方法は、交差するカーブの組を受け付けるステップと、交差するカーブの組からのソースカーブおよびデスティネーションカーブの選択を受け付けるステップとを含む。該方法は選択意図規則を受け付けるステップと、選択意図規則に従って、交差するカーブの組から、ソースカーブを含むカーブの第１のチェーンを計算するステップとを含む。該方法は、選択された経路を保存するステップを含み、該選択された経路は、選択意図規則から最小数のずれを有する、デスティネーションカーブとソースカーブとの間のカーブのチェーンである。付加的な中間カーブが特定されてもよく、これにより現在の経路が再ルーティングされる。
【０００４】
上記は、当業者が以下の詳細な説明をより良く理解できるように本発明の特徴および技術的な利点をかなり大雑把に述べたものである。特許請求の範囲の対象を成す本発明の付加的な特徴及び利点を以下において説明する。当業者であれば、本発明の変更又は本発明と同一の目的を達成するための構造を設計するための基礎として、開示された着想及び特定の実施の形態を容易に使用することができるであろう。また、当業者であれば、そのような等価物はその最も広い形態においても、本発明の精神及び範囲から逸脱するものではないことが分かるであろう。
【０００５】
以下の詳細な説明の前に、本明細書にわたり使用される幾つかの用語又は語句の定義を明確にすることは有利であると思われる。「含む」及び「有する」という語、またそれらから派生した語は限定的でない包含を意味する。「又は」という語は包含的な語であり、すなわち「及び／又は」を意味する。「関連した」及び「それと関連した」ならびにそれらから派生した語は「含む」、「中に含まれる」、「相互に接続されている」、「有する」、「中に有する」、「〜に、又は〜と接続する」、「〜に、又は〜と結合する」、「〜と通信可能である」、「〜と協働する」、「交互配置する」、「近接して並置する」、「〜に近接している」、「〜に、又は〜と結び付けられている」、「持つ」、「〜の性質を有する」等を意味する。また「コントローラ」という語は、ハードウェア、ファームウェア、ソフトウェア、又はそれらのうちの少なくとも２つの組合せによって実施されていようと、少なくとも１つの動作を制御する任意のデバイス、システム又はその一部を意味する。任意の特定のコントローラに関連した機能は中央に集中していてもよいし、局所的であれ遠隔的であれ分散していても良いことを言及しておく。本願明細書全体にわたり幾つかの語及び語句の定義が示されるが、当業者であれば、そのような定義は、殆どではないにしろ、多くの場合、このように定義された語及び語句の以前の用法及び将来の用法にも当てはまることを理解するであろう。幾つかの語は多様な実施の形態を含んでいるが、添付の特許請求の範囲における記載はこれらの語を特定の実施の形態に明示的に限定している。
【０００６】
本明細書及び本発明の利点をより完璧に理解するために、以下では、添付の図面を参照しながら本発明を説明する。図面において、同一の参照番号は同一の対象を表している。
【図面の簡単な説明】
【０００７】
【図１】一実施形態が実現可能なデータ処理システムのブロック図を示す。
【図２】本明細書に記載の技術を用いる選択によるカーブのコレクションの例を示す。
【図３】開示の実施形態における高レベル処理のフローチャートを示す。
【図４】開示の実施形態における処理のフローチャートを示す。
【図５】開示の実施形態における図４の処理を示す出力ツリー図を示す。
【図６】開示の実施形態における処理のフロー図を示す。
【図７】開示の実施形態における図６の処理を示す出力ツリー図を示す。
【図８】開示の実施形態におけるツリー図の非限定的な例を示す。
【図９】開示の実施形態におけるリンクリストツリー構造の非限定的な例を示す。
【発明を実施するための形態】
【０００８】
本願書類において本発明の主旨を記載するために用いられる図１〜９（後述）および種々の実施形態は例示に過ぎず、本発明の範囲を何ら限定するものと理解されるべきではない。本発明の基本構成が任意に適切に構成された装置において実施可能であることは当業者には理解されるであろう。本願の多くの革新的な教示について、例示的な非限定の実施形態に関連して記載される。
【０００９】
従来のＣＡＤシステムにおいて、カーブまたはエッジのコレクション、または、カーブおよびエッジの混ざったものが種々の処理への入力として用いられる。複数の用語を避けるため、本明細書においては、ＣＡＤの分野で知られている「カーブ」および「エッジ」のいずれも「カーブ」を意味するものとする。本明細書中で用いられるとき、以下に示されるように、「チェーン」は連結したカーブのコレクションであり、「経路」はソースカーブからデスティネーションカーブとの間（それ自身を含む）の、一連の連結したカーブのコレクションである。
【００１０】
ユーザはしばしば、交差したカーブの非常に複雑なネットワークから、カーブのサブセットおよびカーブの一部をコレクションしようとする。従来のシステムでは、一つずつまたは小グループでカーブの一部を非効率的に選択しなければならない。
【００１１】
「選択意図（Selection Intent）」とは、開示の実施形態において用いられる既存の機能および技術を意味する。選択意図はカーブをコレクションするための種々の方法を提供する。
【００１２】
選択意図規則は、起点となるカーブが明示的に選択されたときに、カーブを自動的にコレクションされる基準である。このような規則の例は、「連結カーブ」、「正接カーブ」および「シングルカーブ」である。
【００１３】
「連結カーブ」の規則が選択されると、１つのカーブの明示的な選択により、たとえば、その端点に特有に接続されているカーブがすべて自動的に選択され、これらのカーブに特有に連結しているカーブが自動的に選択される。この連鎖選択処理のため、カーブのコレクションは「チェーン」と呼ばれる。
【００１４】
カーブのコレクションは連結したカーブのチェーンとして存在し、記憶される。後にカーブが基本カーブに加えられる場合、これらのカーブは選択意図規則を満たすものであり、これらは自動的にコレクションに加えられる。
【００１５】
カーブまたはラインが「正接カーブ」の選択意図規則を用いて選択された場合、正接接続されているカーブが自動的に選択される。カーブまたはラインが「シングルカーブ」の選択意図規則を用いて選択された場合、ユーザにより明示的に選択された１つのカーブのみがコレクションに入る。他のカーブは自動的に入らない。
【００１６】
本明細書中に開示される実施形態は、たとえば、「連結カーブ」、「正接カーブ」および「シングルカーブ」の選択意図規則を用いて実現される。
【００１７】
いくつかのオプションが使用可能であり、これらはカーブのコレクションの際に付加的なコントロールを提供する。選択意図規則は、特定のカーブが選択されたときにコレクションに自動的に加えられるカーブの種類を決定する。「交差で停止」オプションは「連結カーブ」、「正接カーブ」および「シングルカーブ」の規則にのみ関連する。このオプションは、ユーザが自動的またはマニュアルでカーブの交差により制約されるべきカーブの選択を望む際に特定される。特定された場合、「交差で停止」オプションによって、カーブ全体よりむしろ、（交差の間の）カーブの部分の選択が可能となる。
【００１８】
「交差で停止」オプションとともに「正接カーブ」の選択意図規則を用いてラインが選択された場合、結果得られるコレクションは交差するカーブにより制約される。コレクションは完全な正接チェーンを含まず、チェーンの交差の間にあるチェーンの部分のみを含む。
【００１９】
カーブの密なネットワークに関し、これはしばしば所望の選択意図規則およびオプションの組み合わせを用いて所望のカーブのコレクションを定めるためには面倒なものとなる。所望のコレクションを決定するには通常、画面上で多数回選択する必要があるが、これは頻繁な画面の拡大縮小操作を伴い、これにより誤った選択をすることが非常に多くなってしまう。これらは全て、ユーザの生産性に直接影響する。
【００２０】
たとえば、交差するカーブの密なネットワークについて、「シングルカーブ」規則および「交差で停止」オプションを用いてコレクションを定めるには、画面上で１２回選択しなければならない。開示の実施形態によれば、システムまたはユーザが画面上で非常に少ない選択により所望のコレクションを定めることができるシステムおよび方法が提供される。開示の実施形態によれば、ユーザおよびシステムがより望ましいコレクションへ現在のコレクションを容易に修正可能なシステムおよび方法が提供される。開示の実施形態は、複雑なカーブのネットワークからカーブのコレクションを定める際の生産性を大きく改善する。
【００２１】
図１は、一つの実施形態を実施することができる、例えばＣＡＤシステムとしてのデータ処理システムのブロック図を示す。図示されているデータ処理システムはプロセッサ１０２を含んでおり、このプロセッサ１０２は２次キャッシュ／ブリッジ１０４に接続されている。２次キャッシュ／ブリッジ１０４はさらにローカルシステムバス１０６に接続されている。ローカルバスシステム１０６は、例えば、ＰＣＩ（peripheral component interconnect）アーキテクチャバスである。図示されている実施例におけるローカルバスシステムには、メインメモリ１０８及びグラフィックアダプタ１１０も接続されている。グラフィックアダプタ１１０をディスプレイ１１１に接続することもできる。
【００２２】
他の周辺装置、例えばローカルエリアネットワーク（ＬＡＮ）／ワイドエリアネットワーク／ワイヤレス（例えばＷｉＦｉ）アダプタ１１２もローカルバスシステム１０６に接続することができる。拡張バスインタフェース１１４は、ローカルバスシステム１０６を入力／出力（Ｉ／Ｏ）バス１１６に接続させる。Ｉ／Ｏバス１１６にはキーボード／マウスアダプタ１１８、ディスクコントローラ１２０及びＩ／Ｏアダプタ１２２が接続されている。ディスクコントローラ１２０を記録装置１２６に接続することができ、この記録装置１２６は機械使用可能又は機械読み出し可能なあらゆる適切な記憶媒体で良く、不揮発性のハードコーディングタイプの媒体、例えば読み出し専用メモリ（ＲＯＭ）又は電気的に消去及びプログラミング可能な読み出し専用メモリ（ＥＥＰＲＯＭ）、磁気タイプの記録装置及びユーザ記録可能なタイプの媒体、例えばフロッピーディスク、ハードディスクドライブ及びコンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）又はディジタル多目的ディスク（ＤＶＤ）及び他の公知の光学的、電気的又は磁気的な記録装置がこれに含まれるが、記憶媒体はこれらの例に限定されるものではない。
【００２３】
図示されている例におけるＩ／Ｏバス１１６にはオーディオアダプタ１２４も接続されており、このオーディオアダプタ１２４には音声を再生するためにスピーカ（図示せず）を接続することができる。キーボード／マウスアダプタ１１８は、例えばマウス、トラックボール、トラックポインタ等のポインティングデバイス（図示せず）のためのコネクションを提供する。
【００２４】
当業者には、図１に図示されているハードウェアを特定の実施の形態のために変更できることは明らかである。例えば、他の周辺装置、例えば光学ディスクドライブ等も付加的に使用することができるか、又は、図示されているハードウェアの代わりに使用することができる。図示されている実施例は説明を目的としたものに過ぎず、本発明に関する構造的な制約を暗示することを意図したものではない。
【００２５】
本発明の実施の形態によるデータ処理システムは、グラフィカルユーザインタフェースを使用するオペレーティングシステムを含んでいる。オペレーティングシステムは複数のディスプレイウィンドウをグラフィカルユーザインタフェースにおいて同時に表示することができ、各ディスプレイウィンドウは種々のアプリケーションへのインタフェース又は同一のアプリケーションの種々のインスタンスへのインタフェースを提供する。ユーザはポインティングデバイスを介してグラフィカルユーザインタフェースにおけるカーソルを操作することができる。カーソルの位置を変更することができる、及び／又は、カーソルの位置として所望のレスポンスを起動させるために行なわれたイベント、例えばマウスボタンのクリックが考えられる。
【００２６】
商用の種々のオペレーティングシステムの内の一つ、例えばＭｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）のバージョン（レドモンド（ワシントン州）に位置するＭｉｃｒｏｓｏｆｔ社の製品）を、適切に変更されている場合には使用することができる。オペレーティングシステムは、本明細書において説明する本発明に従い修正又は作成されている。
【００２７】
ＬＡＮ／ＷＡＮ／ワイヤレスアダプタ１１２を（データ処理システム１００の一部ではない）ネットワーク１３０に接続することができ、このネットワーク１３０として、当業者には周知であるような、公共又は私用のあらゆるデータ処理システムネットワーク、又は、ネットワークの組み合わせが考えられ、例えばインターネットが含まれる。データ処理システム１００はネットワーク１３０を介してサーバシステム１４０と通信することができ、このサーバシステム１４０もまたデータ処理システム１００の一部ではないが、例えば、別個のデータ処理システム１００として実施することができる。
【００２８】
開示の実施形態により、複雑なカーブのネットワークから、カーブのコレクションを定める際の生産性が大きく向上される。上述のように、多くのＣＡＤシステムおよび機能はカーブのコレクションを入力として必要とする。
【００２９】
図２は本明細書に記載の技術を用いた選択によるカーブのコレクションの例を示す。強調されたカーブのコレクション（経路２０５）の選択には、本明細書に開示の技術によれば、画面上で２回の選択しか必要とされない。画面上での２回の必要な選択は、２１０と２１５で示されている。
【００３０】
従来の技術によれば、所望の選択意図規則およびオプションの組み合わせによりカーブの同じコレクションを同定するためには、ユーザはマニュアルで１２回選択する必要がある。必要な選択回数を減らす（この例では、１２回から２回に）ことにより、ＣＡＤ設計処理の効率が大きく向上される。
【００３１】
開示の実施形態には、カーブのコレクションを定めるための新たな対話モデルと、最小量のユーザ入力で所望のコレクションを探索するためのシステムおよび方法が含まれる。
【００３２】
開示の実施形態における基本的な対話は、システムが、コレクションが含むべき一連の入力カーブのユーザ選択を受け付けることである。システムは、その後、これらの入力カーブを接続するカーブを決定し、これらをコレクションに加える。本明細書で用いられるとき、カーブのコレクションは「経路」と呼ばれる。経路を探索するための詳細な基準および主要な基準は本明細書中に記載されている。
【００３３】
種々の実施形態において、カーソルが候補となる入力カーブの上にあるときに、対話モデルによってさらにリアルタイムの視覚的な経路のフィードバックが提供される。このフィードバックにより、ユーザは、カーソルの下のカーブが選択された場合に生じる正確な経路を見ることができる。システムがカーブの一部の上にカーソルを動かすユーザ入力を受け付けたとき、たとえば、システムは、本明細書中に記載のような処理を自動的に実行し、リアルタイムで全体の経路を選択し、表示する。
【００３４】
たとえば、図２中、カーブ２１０が入力として選択されたとすると、カーソルはカーブ２１５の上に置かれる。本明細書中に記載の処理は、予め定められた基準に従って、これらの２つのカーブの間の経路を探索する。これはリアルタイムで行われ、「経路」は特徴的な色で表示される、カーブ２１５が選択されると、経路２０５が形成される。
【００３５】
種々の実施形態では、経路の計算のための少なくとも２つの基準が考慮される。第１の基準は、最良の「経路」は、それが特定の選択意図（ＳＩ）「規則」からずれる回数を最小化しなければならない、というものである。例として、目標の（destination）道に至るために元の（source）道に沿って旅する人の例を考えることができる。理想のルートは常にＳＩに完全に従うものであろう。他の全てのルートについて理想ルートからのずれが考慮される。種々の実施形態では、第１の基準は、この基準が最短の経路長（非常に多くの経路探索アルゴリズムに非常に共通する）に基づいていないという点において、一般的なアプローチと異なっている。これは、システムがルーティング規則に違反する回数を最小化することに基づいている。
【００３６】
以下の例はこの基準を示す。ユーザは「正接カーブ」規則を特定しかつ２つのカーブを選択することにより、経路を形成したい。システムが計算した経路は、大きい数の規則のずれを有するいかなるより短い経路よりも、むしろ、正接カーブ規則からの最小数のずれを有する経路である。
【００３７】
第２の基準は、同数のずれを持つ複数の「経路」が見いだされた場合に、最短の長さを有する経路が選択される、というものである。たとえば、ユーザが２つのカーブおよび「連結カーブ」規則を選択した場合、同数のずれを有する複数の経路が存在しうる。このような場合、システムはこれらの経路のうちの最短の経路を選択する。なお、本明細書に記載されるとき、ユーザ入力またはユーザ選択へのいかなる記載も、適切な入力装置を介したこのような入力または選択を受け付けるシステムを含むことが理解される。
【００３８】
対話を通じて、さらに、全ての明示的に選択された入力カーブの削除、明示的に選択された入力カーブの別のカーブとの置換、および、２つの従前に選択された入力カーブの間で選択される新たな入力カーブを通る経路の再ルーティングが可能である。影響された経路はそれに応じて修正される。
【００３９】
開示の処理は現在のアプローチに対する大きな利点を有する。たとえば、種々の実施形態では、最良の経路への非常に速い収束速度が可能となる。収束基準のロバストな設計により、さらなるコンピューティングによって常により大きい数のずれを有する経路が確実に得られる。
【００４０】
さらに、理想から同数のずれを有する複数の経路が存在する場合、これらのすべてが同じ深度の反復において見いだされる。本明細書の処理のパフォーマンスはモデル全体の複雑さに依存しない。パフォーマンスはソースカーブとデスティネーションカーブの近くにおける局所的な複雑さに依存する。
【００４１】
また、開示の処理により、さらに、すでにコレクションの一部であるいかなるカーブも経路検索処理に寄与しないことが保証される。
【００４２】
このアルゴリズムは、ソースカーブとデスティネーションカーブとから同時にスタートする双方向検索アルゴリズムである。高速の収束の鍵となるものは反復深度の考えである。全ての反復深度において、起こりうる最少数のずれが既知である。
【００４３】
図３は、開示の実施形態における高レベルの処理のフローチャートを示す。なお、種々のステップが同時に行われてもよい。特に（限定するものではないが）、後述の、ソースカーブおよびデスティネーションカーブからの経路計算が好適には同時に行われる。
【００４４】
システムは、経路を探索すべき一組のカーブを受け付ける（ステップ３０５）。本明細書において用いられるとき、「受け付ける」には、記録媒体からのロード、ユーザにより入力された、ネットワークなどを介した別のシステムからの受信、当業者に知られたその他のものが含まれる。カーブの組は、任意の２Ｄまたは３Ｄモデルの一部あるいはＣＡＤシステムにおける他の構造であってよい。
【００４５】
システムは、カーブの組のうちからソースカーブおよびデスティネーションカーブの選択を受け付ける（ステップ３１０）。
【００４６】
システムはオプションで、選択意図規則の選択を受け付け、他のオプションを受け付けることができる（ステップ３１５）。
【００４７】
システムは選択された選択意図規則に従って、ソースカーブから始まる（または少なくともこれを含む）第１のチェーン（カーブのコレクション）を計算する（ステップ３２０）。このチェーンはソースカーブからデスティネーションカーブへの経路の一部または全体を形成する。
【００４８】
システムは、任意の選択された選択意図規則に従って、デスティネーションカーブから始まる（または少なくともこれを含む）第２のチェーン（カーブのコレクション）を計算する（ステップ３２５）。このチェーンはデスティネーションカーブからソースカーブへの経路の一部または全体を形成する。
【００４９】
システムは第１のチェーンと第２のチェーンとを比較して、これらのチェーンが同じであるか否かを判別する（ステップ３３０）。２つが同じである場合、システムはこのチェーンをソースカーブとデスティネーションカーブとの間の選択された経路として記録し（ステップ３３５）、それを保存し、これはずれゼロを有する。
【００５０】
２つが同じでない場合（ステップ３３０において）、システムは第１のチェーンおよび第２のチェーンに交差する、複数の共通するカーブを同定する（ステップ３４０）。これらの共通カーブは経路がずれうる唯一の道である。交差は、これらのカーブが、完全な経路を形成するために、第１のチェーンと第２のチェーンとの両方に共通しうることを示す。
【００５１】
システムは第１および第２の基準ならびに任意の選択された選択意図規則に従って、少なくとも１つの共通するカーブを含む、ソースカーブにおいて始まる第３のチェーンを計算する（ステップ３４５）。
【００５２】
システムは、第１および第２の基準ならびに任意の選択された選択意図規則に従って、少なくとも１つの共通するカーブを含む、デスティネーションカーブにおいて始まる第４のチェーンを計算する（ステップ３５０）。
【００５３】
システムは第３および第４のチェーンを比較し、これらが同じであるか否かを判別するか（ステップ３５５）、または、次の反復における他の経路と比較する。これらのいずれかが一致する場合、システムは、このチェーンを選択された経路またはチェーンとして記録し（ステップ３３５）、これはずれ１を有する。
【００５４】
経路が一致しない場合（ステップ３５５において）、選択された経路が同定され、記録される（ステップ３３５において）まで、処理は、別の共通するカーブを用いるステップ３４５へと戻る。
【００５５】
同数の最小ずれを有する複数の選択された経路が見いだされた場合（ステップ３６０）、システムは本明細書に記載の技術を用いてこれらの経路のうち最短の経路を探索し、保存する（ステップ３６５）。複数の選択された経路がない場合、または、選択された経路のうちの最短の経路が見いだされ、保存された後、処理は終了する（ステップ３７０）。
【００５６】
上記処理によって、チェーンが探索され、与えられた入力カーブについての関連データをコンパクトフォーマットで保存する。第１のチェーンおよび第２のチェーンが同じでない場合、ソースカーブとデスティネーションカーブとの間の経路を探索するために、選択意図規則から１以上のずれを有する、少なくとも１つの付加的なチェーンが計算される。場合により、保存された選択経路は、選択意図規則から同一の最小数のずれを有する複数の経路のうちの、ソースカーブとデスティネーションカーブとの間の最短の経路である。
【００５７】
ダイクストラ法は、最短経路の探索のための技術として当業者によく知られている。本明細書中に記載の他の技術は既知のアプローチとは大きく異なっており、大きな利点がある。
【００５８】
１つの開示されるアプローチは、単一のアクティブノードは存在しないが、代わりに、「レベル」と呼ばれる、同時処理される複数のアクティブノードが存在する２つのチェーン間の最小数のチェーンを見いだすための処理を含む。１つのチェーンから他のチェーンに移るコストは常に同じであるため、この場合同時処理が可能である。
【００５９】
このアプローチの処理では、スタートチェーンをＣ１とする。このアプローチでは、システムは、このチェーンの、受け付けたカーブの組の中の他のカーブとの全ての交差を処理する。これらの交差は、その後、次のレベルのチェーンを生成するために用いられる。このアプローチでは、２番目のチェーンが特定のレベルに達した時に処理は停止する。このレベルは２つの入力チェーンを接続するために必要な最小数のチェーンを示す。
【００６０】
図４は、開示の実施形態に関連する１つの開示の処理に関するフローチャートを示す。種々のステップは同時にまたは異なる順序で行われてよい。
【００６１】
システムは２つの入力チェーンを受け付ける（ステップ４０５）。これらはたとえば図３の処理に記載された第３の経路および第４の経路に対応する。
【００６２】
システムは２つの入力チェーンが同じであるか否か判別する（ステップ４１０）。同じ場合、これはシステムが所望のチェーンを見いだしたことを示し、処理は停止する（ステップ４３０）。
【００６３】
システムは、これらのチェーンのうちの最初のものについて全ての交差を探索する（ステップ４１５）。
【００６４】
第１の処理レベルにおいて、システムはチェーン１の全ての交差から新たな連続（untrimmed）チェーンを生成する（ステップ４２０）。このステップの一部として、システムはさらにすべての新たに生成されたチェーンについて交差を探索してもよい。本明細書中で用いられるとき、「連続（untrimmed）」チェーンとは、交差にて停止しないカーブのチェーンである。
【００６５】
第１の処理レベルにおいて、システムは新たに生成されたチェーンが所望のチェーン２のものと同じであるか否か判別する（ステップ４２５）。同じである場合、これはシステムが所望のチェーンを見いだしたことを示し、処理は停止する（ステップ４３０）。
【００６６】
同じでない場合、システムは第２の処理レベルを行い、第１の処理レベルにおいて探索された全てのチェーンの交差から新たなチェーンを生成する（ステップ４３５）。このステップの一部として、システムは新たに生成されたチェーンについての交差を探索してもよい。
【００６７】
第２の処理レベルにおいて、システムは新たに生成されたチェーンが所望のチェーン２のものと同じであるか否かチェックする（ステップ４４０）。同じである場合、これはシステムが所望のチェーンを見いだしたことを示し、処理は停止する（ステップ４３０）。
【００６８】
同じでない場合、システムはさらなる処理レベルについてステップ４３５の処理を繰り返す（ステップ４３５に戻る）。（処理が終了する点において（図示せず））次のレベルについて新たなチェーンを生成するために、システムが所望のチェーン２に至る（そしてステップ４３０で終了する）まで、または、特定のレベルにおける任意のチェーンのさらなる交差が存在しなくなるまで、処理は繰り返される。
【００６９】
図５は、開示の実施形態に関連する図４の処理を示す出力ツリー図を示す。図中には、ノードまたはリーブとして示されているチェーン５０５、および、各チェーンの間の交差５１０が示されている。処理の３つのレベル、すなわち、第１レベル０、第２レベル１および次のレベル２がここに示されている。
【００７０】
図６は開示の実施形態に関連する現在好ましい処理のための処理のフローチャートを示す。この処理では、処理の各レベルはソースカーブからの「前半」作業とデスティネーションカーブからの「後半」作業に分けられる。種々のステップは同時にまたは異なる順序で行われてよい。
【００７１】
システムは２つの入力チェーンを受け付ける（ステップ６０５）。これらはたとえば図３の処理に記載された第３のチェーンおよび第４のチェーンに対応する。好ましい実施形態では、これらの入力チェーンはそれぞれソースカーブおよびデスティネーションカーブを元とするチェーンである。
【００７２】
システムは２つの入力チェーンが同じであるか否か判別する（ステップ６１０）。同じ場合、これはシステムが所望のチェーンを見いだしたことを意味し、処理は停止する（ステップ６３０）。これはずれがゼロの場合である。
【００７３】
システムはこれらのチェーンのうちの最初の２つ（チェーン１およびチェーン２と呼ぶ）について全ての交差を探索する（ステップ６１５）。これらはたとえばソースカーブを含むチェーンと、デスティネーションカーブを含むチェーンである。
【００７４】
第１の処理レベルの前半に関し、システムはチェーン１の全ての交差から新たな連続（untrimmed）チェーンを生成する（ステップ６２０）。このステップの一部として、システムはさらに全ての新たに生成されたチェーンについて交差を探索する。
【００７５】
第１の処理レベルの前半に関し、システムは新たに生成されたチェーンが所望のチェーン２のものと同じであるか否かチェックする（ステップ６２５）。同じ場合、これはシステムが所望のチェーンを見いだしたことを意味し、処理は停止する（ステップ６３０）。
【００７６】
第１の処理レベルの後半に関し、システムはチェーン２の全ての交差から新たな連続（untrimmed）チェーン（交差における停止が「ない」チェーン（chains with stop at intersection 'off'））を生成する（ステップ６３５）。この処理の一部として、システムは全ての新たに生成されたチェーンについて交差をさらに探索する。
【００７７】
第１の処理レベルの後半に関し、システムは、新たに生成されたチェーンがレベル１の処理の「前半」において生成されたチェーンのいずれかと一致するか否かチェックする（ステップ６４０）。一致する場合、これはシステムが所望のチェーンを見いだしたことを意味し、処理は停止する（ステップ６３０）。
【００７８】
第１の処理レベルの前半に関し、システムはレベル１の「前半」の処理において探索された全てのチェーンのすべての交差から新たなチェーンを生成する（ステップ６４５）。このステップの一部として、システムはさらに全ての新たに生成されたチェーンについて交差を探索してもよい。
【００７９】
第２の処理レベルの前半に関し、システムは新たに生成されたチェーンのいずれかがレベル１の「後半」において生成されたチェーンのいずれかと一致するか否かチェックする（ステップ６５０）。一致する場合、これはシステムが所望のチェーンを見いだしたことを示し、処理は停止する（ステップ６３０）。
【００８０】
第２の処理レベルの後半に関し、システムはレベル１の「後半」の処理において探索された全てのチェーンの全ての交差から新たなチェーンを生成する（ステップ６５５）。このステップの一部として、システムはさらに全ての新たに生成されたチェーンについて交差を探索してもよい。
【００８１】
第２の処理レベルの後半に関し、システムは新たに生成されたチェーンがレベル２の「前半」において生成されたチェーンのいずれかと一致するか否かチェックする（ステップ６６０）。一致する場合、これはシステムが所望のチェーンを見いだしたことを示し、処理は停止する（ステップ６３０）。
【００８２】
（処理が終了する時点において（図示せず））次のレベルについて新たなチェーンを生成するために、（ステップ６５０へ繰り返して）一致が見いだされるまで、または、特定のレベルにおいて前後半いずれかにおいてチェーンのいずれについても使用可能なさらなる交差がなくなるまで、システムは処理を繰り返す。
【００８３】
図７は開示の実施形態による図６の処理を示す出力ツリー図を示し、これは前半７４０と後半７５０に分かれ、それぞれが独自のツリーを形成している。ここには、ノードまたはリーフとして示されたチェーン７０５と、各チェーンの間の交差７１０が示されている、処理の３つのレベルすなわち第１レベル０、第２レベル１および次のレベル２がここに示されている。
【００８４】
上記のように、いくつかの実施形態の処理の結果は、ツリー状構造であり、これより、すべての候補解がツリーを進むことにより展開される。
【００８５】
ツリー構造から最短の経路を探索するための処理への入力は、処理の終わりにおいて一致するノードである。各ノードはチェーンおよび１つ前のノードとともにモデルのその他の要素とのその交差に関する情報、ならびに、現在のチェーンが形成された１つ前のノードからの交差情報を含む。
【００８６】
終端ノードから、終端ノードが形成された交差情報とともに１つ前のノードが検索され、保存される。この交差情報は終端ノードの制約の１つである。
【００８７】
１つ前のノードから、１つ前のチェーンおよびその交差情報の検索処理が、再度、ツリーの最初のチェーンに達するまで、繰り返される。
【００８８】
ツリーリストにおける任意の点において、特定のノードにおいて、複数の１つ前のノードが、その交差情報と共に存在しうる。複数の１つ前のノードは、現在のチェーンが形成されうる複数のチェーンが存在することを暗示する。この状態は最小経路長に基づいて解決される必要がある。
【００８９】
図８は、開示の実施形態にかかる例示的な、非限定的なツリー構造の例を示し、これはノードまたはリーフとしてのチェーン８０５、および、各チェーンの間の交差８１０を示す。レベルＮ＋１  ８２０から戻る際、レベルＮ＋１におけるノード（ＣＮ１１）はレベルＮ  ８３０の、２つの先行ノード（ＣＮ１およびＣＮ２）を有する。これはレベルＮ＋１におけるチェーンがレベルＮにおける２つのチェーンから形成されることを暗示する。これは複数の経路がレベルＮ＋１まで存在し、解決を必要とすることを意味する。
【００９０】
解決のため、レベルＮにおけるノードから再び共通のチェーンに戻る。上述の例において、共通ノードはレベルＮ−１  ８４０の強調されたノード（ノード８４０）である。Ｎ−１のノードは最小チェーンの解の一部であり、ただ１つの交差を有する（これがその１つ前のレベルからのただ１つのチェーンの交差から形成されたことを意味する）ため、最小経路長はレベルＮ−１  ８４０から計算される必要がある。
【００９１】
経路長の計算に関し、チェーンの長さは以下のように計算される。
【００９２】
レベルＮのノードＣＮ１について、チェーンの長さは、ノードＣＮとノードＣＮ１の交差と、ＣＮ１１とノードＣＮ１の交差との間の部分（trimmed）チェーンの長さである。
【００９３】
したがって、チェーン長さ｛ＣＮ１｝＝｛１つ前のノードおよび次のノード（すなわちノードＣＮおよびＣＮ１１）にそれぞれ交差するＣＮ１チェーンの長さ｝である。
【００９４】
最小経路長＝
｛チェーン長さ［ＣＮ］＋チェーン長さ［ＣＮ１］＋チェーン長さ［ＣＮ１１］｝と｛チェーン長さ［ＣＮ］＋チェーン長さ［ＣＮ２］＋チェーン長さ［ＣＮ１１］｝とのうちの最小値
【００９５】
複数性リゾルバにより、リンクリスト構造を形成するように修正されたツリー構造が得られる。
【００９６】
図９は開示の実施形態におけるリンクリストツリー構造の非限定的な例を示す。リンクリストにおける各ノードは、リスト内の次のノードを差し、同様に交差情報とともに１つ前のノードの情報を有する。
【００９７】
チェーンレシピが以下のようにリンクリストから展開される。レベル（Ｎ＋１）  ９２０におけるノードＣＮ２から上に進み、ＣＮ１の交差情報が利用可能であり、レベル（Ｎ）  ９３０のノード（ＣＮ１）におけるチェーンの制約の１つとして保存される。この交差情報は、ノードＣＮ１についての他の制約として用いられる。この交差情報はチェーンＣＮ１の１つ前のチェーンについての制約の１つとしても用いられる。このようにして、全てのノードがレベル（Ｎ１１）  ９４０のノードへの入力チェーンまで上に進む。
【００９８】
当業者であれば、単純且つ明確にするために、本発明を用いた使用に適した全てのデータ処理システムの完全な構造及び動作は本明細書において図示又は説明していないことが分かる。その代わりに、本発明に固有のデータ処理システム又は本発明の理解のために必要なデータ処理システムのみを図示及び説明している。データ処理システム１００のその他の部分の構造及び動作は、当業者には公知である現行の種々の任意の実施の形態に従うもので良い。
【００９９】
本明細書には完全に機能的なシステムの文脈での記述が含まれているが、当業者であれば、本発明のメカニズムの少なくとも一部は種々の任意の形態の機械使用可能、コンピュータ使用可能又はコンピュータ読み出し可読な媒体に記録された命令の形態で配布できること、また本発明はその配布物を実際に実行するために使用される特定のタイプの命令又は信号が記録されている媒体又は記憶媒体に関係なく同様に適用されることを理解するであろうということを言及することは重要である。それらの命令は、実行されれば、データ処理システムに本明細書において説明した方法を実施させることができる。機械使用可能／機械読み出し可能又はコンピュータ使用可能／コンピュータ読み出し可能な媒体の例には、不揮発のハードコーディングタイプの媒体、例えば読み出し専用メモリ（ＲＯＭ）又は電気的に消去及びプログラミング可能な読み出し専用メモリ（ＥＥＰＲＯＭ）及びユーザ記録可能なタイプの媒体、例えばフロッピーディスク、ハードディスクドライブ及びコンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）又はディジタル多目的ディスク（ＤＶＤ）が含まれる。
【０１００】
本発明の実施例を詳細に説明してきたが、当業者であれば、本明細書に記載した実施例の種々の変更、置換、バリエーション及び改良はその最も広い形態においても本発明の精神及び範囲から逸脱することなく可能であることが分かるであろう。
【０１０１】
本明細書における説明は、いずれかの特定の要素、ステップ又は機能も特許請求の範囲に含まれていなければならない不可欠の要素であることを意図したものではないと解するべきである。すなわち、本発明が対象とする範囲は明示された特許請求の範囲の記載によってのみ定義される。さらには、いずれの請求項も、「〜のための手段（means for）」という語の後に分詞が続かないかぎり、３５ＵＳＣ§１１２の第６パラグラフに訴えることを意図するものではない。
【図１】
2013530443.tif 000003
【図２】
2013530443.tif 000004
【図３】
2013530443.tif 000005
【図４】
2013530443.tif 000006
【図５】
2013530443.tif 000007
【図６】
2013530443.tif 000008
【図７】
2013530443.tif 000009
【図８】
2013530443.tif 000010
【図９】
2013530443.tif 000011
【国際調査報告】
2013530443.tif 000012
2013530443.tif 000013
2013530443.tif 000014