(57)【要約】【課題】従来の宣言型モデリングＣＡＤシステムでは、一部分の宣言素性が修正されると入力バケットのアップデートが必要となり、多大なアップデート時間を要していた。【解決手段】基本ボリュームを表す葉ノードと、２項可換演算組合せボリュームを表す非葉ノードと、を持つ二分木を用いてモデル化される工業製品を設計するためのコンピュータ実装方法であって、葉ノードの追加または除去をトリガする設計動作を実行するステップと、二分木を理想化するステップであって、すなわち、二分木を修正し、一方で、弱い葉ノードの個数を最小化することにより、木の最適性を維持する、ステップであって、弱い葉ノードは、除去されると、結果として得られる二分木がもはや最適ではなくなるような葉ノードである、ステップと、を含むことを特徴とする方法。【選択図】図２８
2015064876.tif 000002
【特許請求の範囲】
【請求項１】
基本ボリュームを表す葉ノード（ＬＮ）と、２項可換演算組合せボリュームを表す非葉ノードと、を持つ二分木を用いてモデル化される工業製品を設計するためのコンピュータ実装方法であって、
葉ノード（ＬＮ）の追加または除去をトリガする設計動作を実行するステップと、
前記二分木を理想化するステップであって、すなわち、前記二分木を修正し、一方で、弱い葉ノード（ＷＬＮ）の個数を最小化することにより前記木の最適性を維持する、ステップであって、弱い葉ノード（ＷＬＮ）は、除去されると、結果として得られる二分木がもはや最適ではなくなるような葉ノードであり、最適二分木は、任意の２個の葉ノード（ＬＮ）間の深さの差の絶対値が０または１に等しい、ステップと、
を含むことを特徴とする方法。
【請求項２】
前記設計動作が新しい葉ノード（ＬＮ）の追加であるとき、
最小数の葉ノード（ＬＮ）を持つ部分木を定義する次のノードを反復して選択することによって、前記二分木を、根ノード（ＲＮ）から既存の葉ノード（ＬＮ）にトラバースすることによりノードの経路を判定するステップと、
前記新しい葉ノード（ＬＮ）を、経路の終わりの前記既存の葉ノード（ＬＮ）に追加するステップと
を含むことを特徴とする請求項１に記載のコンピュータ実装方法。
【請求項３】
前記設計動作が葉ノード（ＬＮ）の前記除去であるとき、
前記二分木上で、もはや最適ではない前記非最適葉ノード（ＬＮ）を判定するステップであって、前記葉ノード（ＬＮ）は最小の深さを持つ、ステップと、
前記非最適葉ノード（ＬＮ）から前記根ノード（ＲＮ）への前記経路において、部分木が非最適である第１のノードであるピボットノード（ＰＮ）を判定するステップと、
前記ピボットノード（ＰＮ）の前記非最適部分木において、最深の深さを持つＶ部分木を判定するステップであって、前記Ｖ部分木は２個の葉ノード（ＬＮ）を持つ部分木である、ステップと、
前記非最適葉ノード（ＬＮ）と前記Ｖ部分木を入れ替えるステップと、
を含むことを特徴とする請求項１に記載のコンピュータ実装方法。
【請求項４】
特定の工業製品を設計することに適合される二分木を入力するための既定義の木を提供するステップをさらに含むことを特徴とする請求項１から３のいずれか一項に記載のコンピュータ実装方法。
【請求項５】
前記二分木の各ノードについて、その部分木の最大の深さがメモリに格納されることを特徴とする請求項１から４のいずれか一項に記載のコンピュータ実装方法。
【請求項６】
前記二分木の各ノードについて、その部分木の最小の深さがメモリに格納されることを特徴とする請求項１から５のいずれか一項に記載のコンピュータ実装方法。
【請求項７】
前記二分木の各ノードについて、その部分木の葉ノード（ＬＮ）の個数がメモリに格納されることを特徴とする請求項１から６のいずれか一項に記載のコンピュータ実装方法。
【請求項８】
前記二分木が、非最適二分木を最適二分木（ＯＢＴ）に変換することにより取得されることを特徴とする請求項１から７のいずれか一項に記載のコンピュータ実装方法。
【請求項９】
基本ボリュームを表す葉ノード（ＬＮ）の線形リストを、理想二分木（ＩＢＴ）に変換することにより、工業製品を表す任意の二分木を理想化する準備ステップさらに含み、前記葉ノード（ＬＮ）は前記基本ボリュームであることを特徴とする請求項８に記載のコンピュータ実装方法。
【請求項１０】
葉ノード（ＬＮ）個数の関連する範囲に従って、予め計算された理想二分木のライブラリを使用し、かつ、前記二分木の線形リストの基本ボリュームを表す葉ノード（ＬＮ）の個数を読み込んで、前記葉ノード個数に対応する前記予め計算された理想二分木（ＩＢＴ）をロードし、かつ、前記予め計算された二分木の前記葉ノード（ＬＮ）を前記線形リストの前記基本ボリュームに設定することにより、工業製品を表す任意の二分木を理想化する準備ステップさらに含むことを特徴とする請求項８に記載のコンピュータ実装方法。
【請求項１１】
請求項１から１０のいずれか一項に記載の二分木を用いてモデル化される工業製品を設計するための方法を、コンピュータシステムに実行させるコンピュータ実行可能命令を有するコンピュータ可読媒体。
【請求項１２】
二分木を用いてモデル化される工業製品を設計するための、コンピュータ可読媒体に格納されるコンピュータプログラム製品であって、システムに請求項１から１０のいずれか一項に記載の方法の前記ステップを行わせるためのコード手段を含むことを特徴とするコンピュータプログラム製品。
【請求項１３】
二分木を用いてモデル化される工業製品を設計するため装置であって、請求項１から１０のいずれか一項に記載の方法の前記ステップを実装するための手段を含むことを特徴とする装置。
【請求項１４】
請求項１から１０のいずれか一項に記載の方法を用いて設計される工業製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムの分野に関し、より詳細には、例えば、コンピュータ支援設計ＣＡＤにおける、二分木を用いてモデル化される工業製品を設計するためのコンピュータ実装方法の分野に関する。
【背景技術】
【０００２】
本発明は、コンピュータ支援設計ＣＡＤを扱い、より正確には宣言型モデリング（機能モデリングとも呼ばれる）を扱う。宣言型モデリングＣＡＤシステムは、所定のヒストリ木を宣言素性（ｄｅｃｌａｒａｔｉｖｅ  ｆｅａｔｕｒｅ）と共に含む。ＣＡＤシステムのユーザが宣言素性をインスタンス化した後、結果として得られるソリッド（立体）をサポートするデータ構造は、和集合または共通集合などの可換演算を介して基本ボリュームを組み合わせた多くの部分木を含む、ヒストリ木となる。本発明は、この特別な状況を利用して、ユーザが変更を要求した後のソリッドのアップデート性能を向上させる。
【０００３】
図１の左図に示すように、宣言型モデリングシステムの所定のヒストリ木を考え、また、所定のヒストリ木の入力バケットを考えると、宣言素性は、インスタンス化されると、基本ボリュームを入力バケット間に展開させる。その結果、いくつかの素性がインスタンス化された後、各入力バケットが可換演算（主に、「＋」で示されるブール演算和）を介して複数の基本ボリュームを組み合わせる。現在、基本ボリュームの各組み合わせは、図１の右図に示すように、ボリュームが作成シーケンスに従って格納される番号付きリストによって、実装される。図において、根ノードがＲＮで示され、葉ノードがＬＮで示され、内部ノードがＩＮで示され、弧（ａｒｃ）または辺（ｅｄｇｅ）がノードをつなぐ。
【０００４】
宣言型ソリッドのアップデートには２つのステップが含まれることに留意されたい。第１のステップは、入力バケット（基本ボリュームの集合のリスト）をアップデートすることであり、第２のステップは、所定のヒストリ木をアップデートすることであり、ヒストリ木において、可換演算および非可換演算が格納される。工業試験によると、宣言的モデリング技法の初めての実装により、全体の計算時間が主に所定のヒストリ木のアップデート（入力バケットのアップデート時間ではなく）に費やされることが示されている。しかし、本分野における最近の性能向上（継続中のダッソーシステムズの特許：ＥＰ２４７４９２８、ＥＰ２４７４９２９、およびＥＰ２４７４９３０による）では、所定のヒストリ木のアップデート時間を減少させて、目下、基本ボリュームのアップデート時間が有意であるようにされ、従って最適化を行うに相応しい。
【０００５】
以下で定義されるように、本発明は、「最適二分木」の概念を集中的に使用する。この概念は、辞書内の番号付けされたデータ（「レコード」と呼ばれる）をソートおよび探索する技術において周知である。ソートと探索の技術によると、新しいレコードが辞書に追加される度に、いわゆる「二分探索木」がアップデートされ、その構造は所与のレコードの探索を円滑にするべく設計される。探索の効率は二分木の均衡に基づく。そのため、新しいレコードが辞書に追加される度にこの均衡を維持するための精緻なアルゴリズムが存在する。探索の技術は、データベース管理のみならず計算幾何学にも使用される。著名な文献としては、Ｄ．Ｋｎｕｔｈの「Ｓｏｒｔｉｎｇ  ａｎｄ  ｓｅｒａｃｈｉｎｇ」がある。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記で説明したように、所定のヒストリ木の各入力バケットは、番号付きリストを介して基本ボリュームを組み合わせる。ユーザが、一部分の宣言素性を修正すると、基本ボリューム修正（削除、大きさの変更、位置変更．．．）が実行され、入力バケットのアップデートが必要となる。この結果、多大なアップデート時間を要することになり、何故なら、各リストのアップデートが、修正されるボリュームの世代（ａｇｅ）に比例する。アップデート時間の観点から、番号付きリストが最高の構造ではないことは、ソリッドモデリングの技術により周知である。
【０００７】
従来の技術の別の問題は、以下の通りである。宣言的モデリング技法は、素性作成順序とは無関係に動作するべく設計される。ダッソーシステムズの特許ＥＰ１５０１０２６では、結果として得られるソリッドの形状が、素性作成順序とは無関係であることが保証される。しかし、入力バケットのリスト実装により、先の素性のアップデートが、後の素性のアップデートより長くなってしまい、これは、宣言動作が何であるべきなのかについてのユーザの予測と明らかに相反する。
【０００８】
探索の技術では、二分探索木の均衡が維持される。二分探索木のトポロジでは、葉ノードが番号付きレコードである、という事実に極めて関連する構造が獲得される。例えば、典型的な要件は、左の部分木の全てのノードが、（レコードの番号付けに従うと）右の部分木の全てのノードより低いことである。これが、均衡アルゴリズムの複雑性の源である。
【０００９】
本発明の目的は、上記で言及した問題を克服するコンピュータ実装方法およびシステムを提供することである。
【課題を解決するための手段】
【００１０】
本発明の一態様によると、基本ボリュームを表す葉ノード（ＬＮ）と、２項可換演算組合せボリュームを表す非葉ノードと、弧でつながるノードと、を持つ二分木を用いてモデル化される工業製品を設計するためのコンピュータ実装方法が提案され、該方法は、
葉ノードの追加または除去をトリガする設計動作を実行するステップと、
二分木を理想化するステップであって、すなわち、二分木を修正し、一方で、弱い葉ノードの個数を最小化することにより、木の最適性を維持する、ステップであって、弱い葉ノードは、除去されると、結果として得られる二分木がもはや最適ではなくなるような葉ノードであり、最適二分木は、任意の２個の葉ノード（ＬＮ）間の深さの差の絶対値が、０または１に等しい、ステップと
を含む。
【００１１】
そのような理想的な木を保持することにより、ユーザが変更を要求した後に、宣言型ＣＡＤシステムがソリッドの新しい形状を計算するのに必要な時間を短縮することができる。さらに、宣言型ＣＡＤシステムの応答時間が、より平滑になり、これは、素性のアップデート時間がその作成日時に左右されないということである。換言すると、任意の素性のアップデート時間が略同一となり、平均的に、従来技術の状態よりも短縮される。
【００１２】
迅速なアップデートは、有益な向上であり、何故なら、ＣＡＤ産業においては、設計時間の８０％が修正に費やされ、対照的に、設計時間の２０％が新しいモデルを一から作成することに費やされる。性能の向上により時間が確保されることで、新しい製品の商品化までの時間を短縮させることができ、または、代替の設計の研究に時間を使うことができる。
【００１３】
アップデート時間全体を短縮することにより、また、素性間で不均衡なアップデート時間を平滑にすることにより、本発明は、宣言型ＣＡＤシステムをより快適に使用できるものにする。
【００１４】
本発明にて、最適二分木を使用するのは、辞書内の番号付きレコードを探索することよりも優れてシンプルであるという文脈においてである。実際、二分木の全ての非葉ノードは、同一の可換演算（主に、ブール演算和）であり、また、全ての葉ノードが基本ボリュームである。これにより、状況が非常にシンプルとなり、本発明のアルゴリズムの効率は、その単純さの結果である。
【００１５】
一実施形態によると、コンピュータ実装方法は、設計動作が新しい葉ノードの追加であるとき、
最小数の葉ノードを持つ部分木を定義する次のノードを反復して選択することによって、二分木を、根ノード（ＲＮ）から既存の葉ノードにトラバース（巡回）することによりノードの経路を定義するステップと、
新しい葉ノード（ＬＮ）を、経路の終わりの既存の葉ノードに追加するステップと
を含む。
【００１６】
従って、新しい葉ノードの追加により、木の構造を、その深さに比例する計算コストで、保存または向上させる。
【００１７】
別の実施形態において、コンピュータ実装方法は、設計動作が葉ノードの除去であるとき、
二分木上で、もはや最適ではない非最適葉ノードを判定するステップであって、葉ノード（ＬＮ）は最小の深さを持つ、ステップと、
非最適葉ノードから根ノードへの経路において、部分木が非最適である第１のノードである、ピボットノードを判定するステップと、
ピボットノードの非最適部分木において、最深深さを持つＶ部分木を判定するステップであって、Ｖ部分木は、２個の葉ノードを持つ部分木である、ステップと、
非最適葉ノードとＶ部分木を入れ替えるステップと
を含む。
【００１８】
従って、ノード除去後の最適性の回復が、木の深さに比例する計算コストで実行される。
【００１９】
一実施形態によると、コンピュータ実装方法は、特定の工業製品を設計することに適合される二分木を入力するための所定の木を提供するステップさらに含む。
従って、ＣＡＤシステムは、宣言動作を特徴とし、ユーザに高レベルの設計特徴を提供する。
【００２０】
一実施形態によると、二分木の各ノードについて、その部分木の最大の深さがメモリに格納される。
これにより、計算を制限することができる。
【００２１】
一実施形態によると、二分木の各ノードについて、その部分木の最小の深さがメモリに格納される。
これにより、計算を制限することができる。
【００２２】
一実施形態によると、二分木の各ノードについて、その部分木の葉ノードの個数がメモリに格納される。
これにより、計算を制限することができる。
換言すると、メモリは非一時的なコンピュータ可読媒体である。
【００２３】
一実施形態によると、二分木が、非最適二分木を最適二分木に変換することにより取得される。
従って、本発明の方法によらずに作成された、工業製品または物体の二分木を使用することが可能である。
【００２４】
例えば、該方法は、基本ボリュームを表す葉ノードの線形リストを、理想二分木に変換することにより、工業製品を表す任意の二分木を理想化する準備ステップさらに含み、葉ノードは基本ボリュームである。
【００２５】
従って、本発明の方法によらずに作成された、工業製品または物体の二分木を使用することが可能である。
【００２６】
例えば、該方法は、葉ノード個数の関連する範囲に従って、予め計算した理想二分木のライブラリを使用し、かつ、二分木の線形リストの基本ボリュームを表す葉ノードの個数を読み込んで、葉ノード個数に対応する予め計算された理想二分木をロードし、かつ、線形リストの基本ボリュームを予め計算された二分木の葉ノードに設定する、ことにより、工業製品を表す任意の二分木を理想化する準備ステップさらに含む。
【００２７】
従って、本発明の方法によらずに作成された、工業製品または物体の二分木を使用することが可能である。
【００２８】
また、本発明の別の態様によると、上述の二分木を用いてモデル化される工業製品を設計するための方法を、コンピュータシステムに実行させるコンピュータ実行可能命令を有するコンピュータ可読媒体が提案される。
【００２９】
また、本発明の別の態様によると、二分木を用いてモデル化される工業製品を設計するための、コンピュータ可読媒体に格納されるコンピュータプログラム製品であって、システムに上述の方法のステップを行わせるためのコード化手段を含むことを特徴とする製品が提案される。
【００３０】
また、本発明の別の態様によると、二分木を用いてモデル化される工業製品を設計するため装置であって、上述の方法のステップを実装するための手段を含むことを特徴とする装置が提案される。
【００３１】
また、本発明の別の態様によると、上述の方法を用いて設計される工業製品が提案される。
【００３２】
非制限的な例を用いて説明され、かつ、添付の図面により例示されるいくつかの実施形態を検討することにより、本発明がより良く理解されるであろう。
【図面の簡単な説明】
【００３３】
【図１】従来の技術により、木構造の例を示す図である。
【図２】本発明の態様に係るコンピュータ実装方法を示す図である。
【図３】本発明の態様に係るコンピュータ実装方法を示す図である。
【図４】本発明の態様に係るコンピュータ実装方法を示す図である。
【図５】本発明の態様に係るコンピュータ実装方法を示す図である。
【図６】本発明の態様に係るコンピュータ実装方法を示す図である。
【図７】本発明の態様に係るコンピュータ実装方法を示す図である。
【図８】本発明の態様に係るコンピュータ実装方法を示す図である。
【図９】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１０】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１１】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１２】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１３】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１４】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１５】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１６】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１７】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１８】本発明の態様に係るコンピュータ実装方法を示す図である。
【図１９】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２０】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２１】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２２】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２３】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２４】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２５】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２６】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２７】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２８】本発明の態様に係るコンピュータ実装方法を示す図である。
【図２９】本発明の態様に係るコンピュータ実装方法を示す図である。
【図３０】本発明の態様に係るコンピュータ実装方法を示す図である。
【図３１】本発明を実装することができるコンピュータネットワークまたは同様のデジタル処理環境を示す図である。
【図３２】コンピュータの内部構造の図である。
【発明を実施するための形態】
【００３４】
以下の図面により、本発明の機能がさらに詳細に説明される。
【００３５】
図２に示すように、本発明では、図１の右図に示すような既存の番号付リストではなく、均衡のとれた二分木を介して、入力バケットの基本ボリュームの組み合わせが実装される。そして、各入力バケットのアップデート時間は、その基本ボリュームの個数の対数に比例するのであり、番号付きリストのアップデート時間がその基本ボリュームの対数に比例することとは対照的である。さらに、各均衡二分木は、その形状が、基本ボリュームの作成および削除を通じて最適に保たれるように、操作される。
【００３６】
本発明の説明は、１個の二分木の操作に着目して行う。もちろん、宣言的ＣＡＤシステムにおいて本発明を実装することにより、所定のヒストリ木構造に応じて必要な数の二分木がサービスに導入され、各二分木は本説明に従って操作される。
【００３７】
使用する図式の定義は以下の通りである。
【００３８】
木は、図３に示すように、非輪状の図形である。木には、厳密には弧の個数より１つ多いノードが含まれる。図３の最左の図形は木ではない（多くの輪が見られる）。図３の最右の図形は木である。
【００３９】
二分木は、図４に示すように、２個の弧を持つ根ノードＲＮという１個のノード、３個の弧を持つ内部ノードＩＮという複数のノード、１個の弧を持つ葉ノードＬＮという複数のノード、を特徴とする木である。従来、図４に示すように、製図においては、根ノードＲＮが最下位置に配置され、葉ノードＬＮが最上位置に配置される。
【００４０】
本願全体を通して、ｐは葉ノードＬＮの個数であり、ｐ＝２ｑ＋ｒと表され、ここでｑおよびｒは０≦ｒ＜２ｑとなる整数である。数値ｑはｑ＝ｌｏｇ２ｐと表されることが多い。グラフ理論により周知であるように（オイラーの公式を二分木に適用することにより）ノードの総数および弧の個数が、葉ノードＬＮの個数により完全に定義される。
【００４１】
慣例により、図５に示すように、二分木の弧は葉ノードＬＮから根ノードＲＮに向くように、図面においては上部から下部に向くように、配置される。図５に示すように、根ノードＲＮは出力弧を持たず２個の入力弧を持ち、葉ノードＬＮは入力弧を持たず１個の出力弧を持ち、内部ノードＩＮは１個の出力弧と２個の入力弧を持つ。この従来的な配置向きは、本発明の文脈において、二分木により獲得されるデータフローに従って選択される。図面においては暗黙的なことである。
【００４２】
図６に示すように、ノードｘにより定義される部分木は、ノードｘの出力弧を切りとることにより取得される。その結果、ノードｘは、その部分木の根ノードとなる。葉ノードは部分木としてとらえることができる。
【００４３】
定義によると、２個の兄弟ノードが同一の出力ノードを持つ。図７では、点線の輪郭で、同一の出力ノードｘを持つ２個の兄弟部分木が囲まれている。
【００４４】
ノードの深さは、当該ノードから根ノードＲＮまでの経路の弧の個数である。木の深さは、最大の葉ノード深さである。根ノードＲＮの深さはゼロである。図８において、ノードｘの深さは３であり、葉ノードｙの深さは３であり、葉ノードｚの深さは５である。
【００４５】
葉ノード以外の各ノードは、従来的に「左」および「右」と呼ばれる２つの入力ノードを持つ。定義によると、葉ノード以外の所与のノードの左部分木は、その左入力ノードにより定義される部分木であり、同様に、右部分木は、その右入力ノードにより定義される部分木である。定義によると、均衡二分木では、葉ノード以外の各ノードについて、その左と右の部分木間の深さの差の絶対値が１より小さいかまたは１に等しい。図９の最左の木は不均衡であるが、最右の木は均衡である（ノードにはノードのそれぞれの部分木の深さが記されている）。
【００４６】
最適二分木ＯＢＴは特別な均衡二分木である。定義によると、最適二分木の任意の２個の葉ノードＬＮ間の深さの差の絶対値が、０または１に等しい。換言すると、図１０に示すように、葉ノードＬＮについて最大で２つの深さレベルが存在する。図９の均衡二分木は、最適ではないが、図１０の最左の均衡二分木は最適である。
【００４７】
定義により、図１０の最右に示すように、完全二分木の全ての葉ノードＬＮは、同じ深さを持つ。完全二分木も葉ノードＬＮの個数は、常に２の整数乗でありｐ＝２ｑを意味する。その結果、ｐ＝２ｑ＋ｒ個の葉ノードＬＮを有する最適二分木の任意の葉ノードＬＮの深さは、ｑまたはｑ＋１である。以下の特性は先行技術により周知である。最適二分木は、同じ個数の葉ノードＬＮを持つ全ての二分木の中で、最小の深さであることを特徴とする。
【００４８】
二分木に対して実行され、かつ、本発明において使用される演算は、「新しい葉ノードの追加」および「既存の葉ノードの除去」である。追加の演算は、以下のように行われる。象徴的に基本ボリュームを表す既存の葉ノードａを考え、また、ｃという新しい基本ボリュームを考えると、追加の演算は、図１１に示すように、葉ノードａを、根ノード＋と、葉ノードａおよびｃとで定義される部分木で置き換えることである。
【００４９】
明らかに、葉ノードの追加により、二分木の深さを増加させることができる。
【００５０】
除去の演算は、以下のように行われる。二分木の葉ノードＬＮの除去は、その出力ノードをその兄弟部分木の根ノードＲＮで置き換えることである。例えば、図１２において、葉ノードｂを除去することは、ノードｂの出力ノード＋を、葉ノードｂの兄弟部分木ａ＋ｃの根ノード＋で置き換えることである。
【００５１】
明らかに、葉ノードＬＮの除去により、二分木の深さを減少させることができる。
【００５２】
今までのところ、全ての定義および特性は先行技術により周知である。それらは、参照するものによって異なり、何故ならそれらが厳密に呼び出されるからである。我々の知識では、次の定義は本発明に独創的なものである。
【００５３】
ここで、最適二分木の弱い葉ノードＷＬＮの考え方を定義する。最適二分木を考えると、弱い葉ノードは、定義によると、除去されると、結果として得られる二分木がもはや最適ではなくなるような葉ノードである。例えば、図１３において、葉ノードｘの除去により、最適性が壊されない
逆に、図１４において、ノードｙを除去することにより、実際に最適性が壊され、ノードｙが弱い葉ノードＷＬＮとなる。最右の木は最適ではなく、何故なら、３つの葉ノードの深さ値２、３、および４が存在するからである。
【００５４】
弱い葉ノードは以下のように特徴付けられる。その深さはｑ、兄弟ノードは葉ノードＬＮ（部分木ではない）であり、二分木のどこかに深さｑ＋１のノードが存在する。
【００５５】
ここで、理想的な二分木ＩＢＴを定義する。定義によると、理想的な二分木ＩＢＴは、弱い葉ノードの個数が最小であることを特徴とする最適な二分木ＯＢＴである。図１５に示すように、全ての最適二分木ＯＢＴが理想的であるというわけではない。最左の二分木は最適であるが理想的ではなく、一方、最右の二分木は理想的である。それら双方は１０個の葉ノードＬＮを持ち、最左の二分木が個の弱い葉ノードＷＬＮを持ち、最右の二分木が４個の弱い葉ノードＷＬＮを持つ。弱い葉ノードＷＬＮは白の正方形である。
【００５６】
ｐ＝２ｑ＋ｒ個の葉ノードＬＮを有する最適二分木ＯＢＴの弱い葉ノードの個数φの、下方の境界は弱い葉ノードの最小個数φｍｉｎであり、かつ、上方の境界は弱い葉ノードの最大個数φｍａｘであり、すなわち、φｍｉｎ≦φ≦φｍａｘであり、このとき、ｒ＝０ならばφｍｉｎ＝０、ｒ≠０ならばφｍｉｎ＝ｍａｘ｛０，２ｑ−２ｒ｝、また、このとき、ｒ＝０ならばφｍａｘ＝０、ｒ≠０ならばφｍａｘ＝２ｑ−２ｄｉｖ（ｒ＋１，２）、である。
ｄｉｖ（ａ，ｂ）という表記は、整数ｂによる整数ａのユークリッド除法の商を表す。
【００５７】
本発明の文脈において、葉ノードＬＮはボリュームであり、非葉ノードは二項可換演算の組み合わせボリューム全体である。さらに、各非葉ノードは、その２個の入力ソリッドを組み合わせて得られるソリッド形状を格納する。ユーザが宣言素性を作成または削除する度に、新しい葉ノードＬＮが二分木に対して追加または除去される。以下では、任意の版のシーケンスで二分木の最適性または理想性を維持するアルゴリズムについて説明する。理想的な二分木の概念は、葉ノード削除の際の最適性の喪失を減少させるのに有用である。弱い葉ノードＷＬＮの個数を減らすことは、二分木が最適性を喪失して、システムが最適性を回復させる可能性を減らすことにもなる。
【００５８】
既存の二分木を考え、また、当該二分木に追加される新しい葉ノードＬＮを考えると、「理想的な成長アルゴリズム」が、新しい葉ノードを追加すべき最良の既存の葉ノードＬＮを計算する。データ構造は、各ノードについて、その部分木の葉ノードＬＮの個数を保存する。換言すると、各ノードｘは、その部分木の葉ノードＬＮの個数を知っており、λ（ｘ）で表され、ｘが１個の葉ノードＬＮならばλ（ｘ）＝０である。アルゴリズムは、根ノードＲＮで開始され、最小個数λを有する現在ノードの入力ノードを参照して、ある葉ノードＬＮに達するまで繰り返される。
【００５９】
x:=根ノード
While xが葉ノードでない do begin
y:=xの左入力ノード
z:=zの右入力ノード
If λ(y)≦λ(z) then
x:=y
Else
x:=z
End if
End while
Return x
【００６０】
図１６において、新しい葉ノードの最良の場所が矢印で指し示される。アルゴリズムが参照したノードに、それぞれのλ数が付されている。
【００６１】
明らかに、新しい葉ノードＬＮの最良の場所を見つけるための計算コストは、二分木の深さに比例する。
【００６２】
二分木が理想的でない場合でも、先のアルゴリズムが働くことに留意されたい。理想的でない木から開始して、有限個数の追加葉ノードの後に理想性に達する。理想木ＩＢＴで開始され、新しい葉ノードＬＮをアルゴリズムにより規定される場所に追加することにより、新しい理想木ＩＢＴが与えられる。
【００６３】
図１７には、最適性の回復について示される。
【００６４】
弱い葉ノードＷＬＮを最適二分木ＯＢＴから除去すると、生じる二分木はもはや最適ではない。実際、除去演算により、いわゆる「非最適葉ノード」が作成され、これは、深さｑ−１の一意的な葉ノードＬＮであり、二分木内の他のとこかに、深さｑの少なくとも１個の葉ノードＬＮ、および、深さｑ＋１の少なくとも１つの葉ノードＬＮが存在するということに留意されたい。
【００６５】
最適性回復アルゴリズムの入力データは、
・適切なデータ構造（後述される）を備える二分木である、と共に
・ｘで示される、その一意的な非最適葉ノード（へのポインタ）、である。
【００６６】
アルゴリズムには、３つのステップが含まれる。すなわち、第１のノードであってその部分木が非最適である、ピボットノードＰＮを見つけること、「Ｖ」部分木（Ｖ部分木は、２個の葉ノードと１個の根ノードとを含む部分木である）を見つけること、および、非最適葉ノードＬＮをＶ部分木で入れ替えること、である。
【００６７】
以下のデータ構造が使用される。各ノードｓに２つの整数が付される。その部分木の最大の深さｄｍａｘ（ｓ）、および、その部分木の最小の深さｄｍｉｎ（ｓ）である。二分木が最適であるならば、任意のノードｔについて、以下のｃ（ｔ）で示す最適性条件が真となる。
【００６８】
０≦ｄｍａｘ（ｕ）−ｄｍｉｎ（ｖ）かつ０≦ｄｍａｘ（ｖ）−ｄｍｉｎ（ｕ）≦１
ここで、ｕ、ｖはノードｔの入力ノードである。ノードｔが葉ノードならば、ｄｍａｘ（ｔ）＝ｄｍｉｎ（ｔ）＝０である。
【００６９】
ピボットノードＰＮを見つけるステップは、以下のように実現される。ピボットノードファインダアルゴリズムは、非最適葉ノードｘで開始され、根ノードＲＮに向かって進み、ｙで示すいわゆるピボットノードＰＮを見つける。ピボットノードＰＮは、偽の最適条件を特徴とする経路上にある第１のノードである。
【００７０】
s:=ｘの出力ノード
While ｃ（ｓ）が真 do begin
s:=sの出力ノード
End if
End while
y:=s
【００７１】
図１８は、ピボットノードＰＮ発見処理を示す。見つかったピボットノードはｙである。アルゴリズムが参照したノードには、（ｄｍａｘ，ｄｍｉｎ）値が付されている。
【００７２】
最深深さを有するＶ部分木を見つけるステップは、以下のように実現される。アルゴリズムは、ピボットノードｙで開始され、葉ノードに向かい、最深のＶ部分木を見つける。この最深Ｖ部分木の根ノードには、ｚが付される。
【００７３】
アルゴリズムは以下の通りである。
s:=y 
While sが葉ノードでない do begin
u:=sの左入力ノード
v:=sの右入力ノード
If dmax(u)≧dmax(v) then
s:=u
Else
s:=v
End if
End while
z:=sの出力ノード
【００７４】
図１９は、Ｖ部分木探索を示す。アルゴリズムが参照するノードにそれぞれのｄｍａｘ値が付されている。
【００７５】
入れ替えのステップが、図２０に示され、ｚで示すＶ部分木の根ノードが非最適葉ノードＬＮで入れ替えられ、これにより、最適性が回復される。
【００７６】
図２１は、可能性のある最悪の場合を示す。ピボットノードＰＮが根ノードＰＮであるということがあり得る。これは、除去された葉ノードが最深葉ノードから「遠く」に位置する場合に起こる。図２１では、木の左側で葉ノードが先に除去され、非最適葉ノードｘが生み出される。最深葉ノードが木の右側に位置するため、ピボットノードｙが根ノードとなる。この最悪の場合においても、最適性回復の計算コストは、二分木の深さに比例する。
【００７７】
最適性回復では、いくつかのソリッドモデリングのアップデートが要求されて、新しいソリッド形状が得られる、という方法で二分木が認識される。繰り返される演算は、修正されたノードから根ノードＲＮへの経路上に位置される。これらの演算は、図２２では四角で囲んだ「＋」である。換言すると、四角で囲んだ「＋」で表されるノードは、変化に追随して再計算すべきノードである。
【００７８】
図２３は、最悪の場合の最適性回復を表す。明らかに、繰り返される「＋」演算の個数が、二分木の深さの２倍を超えることは不可能である。ここでもまた、計算の複雑性が二分木の深さに比例する。
【００７９】
本発明の核心は、二分木の理想性を回復することである。
【００８０】
弱い葉ノードＷＬＮを理想二分木ＩＢＴから除去し、かつ、先のアルゴリズムを介して最適性を回復することにより、理想二分木ＩＢＴを生み出すことができる（理想二分木は最適二分木ＯＢＴより良好である、すなわち、最適二分木では、弱い葉ノードの個数が最小で、弱い葉ノードとは、除去されると得られる二分木がもはや最適ではなくなるという葉ノードである）。
【００８１】
ここで、本発明の裏付けを行う。
【００８２】
ｖを、ｐ＝２ｑ＋ｒ個の葉ノード有する最初の理想二分木ＩＢＴの弱い葉ノードＷＬＮとする。次に、３つの事実に気づかなければならない。第１に、葉ノードｖの深さはｑである。第２に、ノードｖの兄弟部分木は実際に、ｘで示す別の葉ノードである（深さは同様にｑ）。そうでなければ、ｖのＶ形状の兄弟部分木は、ｖが除去された後に最適性を保存することになる。第３に、最初の二分木のどこかに、深さｑ＋１の少なくとも１個の葉ノードＬＮが存在する。このことを、図２４に示す。
【００８３】
葉ノードｖを除去した後、その前の兄弟葉ノードｘは深さがｑ−１に下がり、そのため、最適性が壊れる。このことを、図２５に示す。
【００８４】
最適性を回復するために、アルゴリズムはＶ部分木を見つけ、その根ノードＲＮにｚが付され、ノードｚとｘを入れ替える。重要な点は、ｚの兄弟木がｗで示される葉ノードであり、別のＶ部分木ではないことである。（そうでなければ、最初の二分木は最適でないことになる。実際、我々は、ノードｚの兄弟部分木がＶ部分木であると想定することができる。そして、このＶ部分木を、最初の二分木上の葉ノードｖまたはｘで入れ替えることにより、弱い葉ノードＷＬＮの個数は減り、一方で、葉ノードＬＮの総数が保存され、これは最初の二分木の理想性の仮説と相反する。）従って、弱い葉ノードｖが除去され、かつ、ノードｘとｚが入れ替えられた後、２つの状況が可能となる。深さｑ＋１の葉ノードＬＮがもはや存在しない場合、結果として得られる二分木は完全であり、何故なら全ての葉ノードＬＮが同じ深さを持つからであり、これは特別な理想二分木である。木のどこかに深さｑ＋１の他の葉ノードＬＮが存在する場合、２個の新しい弱い葉ノードＷＬＮが作成される。これは、２個の最初の弱い葉ノードｘとｖが、今度は４個の弱い葉ノードで置き換えられるからであり、この４個は、図面においては図２６に示すように、ｘ、ｗ、および、Ｖ部分木の、ｃ、ｄで示す２個の葉ノードである。
【００８５】
ここで、葉ノードＬＮの総数がｐ−１であるため、結果として得られる最適二分木ＯＢＴは理想ＩＢＴである。実際、この文脈において、最初（かつ理想的）の二分木ＩＢＴの弱い葉ノードＷＬＮの個数は、φｍｉｎ（ｐ）＝２ｑ−２ｒである。弱い葉ノードＷＬＮの除去および最適回復の後、結果として得られる最適二分木ＯＢＴの弱い葉ノードＷＬＮの個数は、φｍｉｎ（ｐ）＋２である。しかし、
φｍｉｎ（ｐ）＋２＝２ｑ−２ｒ＋２
＝２ｑ−２（ｒ−１）
＝φｍｉｎ（ｐ−１）
これは、結果として得られる最適二分木ＯＢＴは、ｐ−１個の葉ノードＬＮを持つので、理想ＩＢＴであるということを意味し、裏付けは終了する。
【００８６】
図２７に示すように、理想二分木ＩＢＴの弱い葉ノードではないノードを削除すると、最適性が喪失する（最適性は保存される）ことに留意されたい。最左の二分木の指し示される葉ノードを削除することにより、中央の木が生み出される。この木の弱い葉ノードは、白い正方形である。これは最適であるが、理想的ではなく、何故なら、同じ個数の葉ノードを持つ理想二分木は、弱い葉ノードＷＬＮを持たないからである。
【００８７】
理想的な成長アルゴリズムでは、十分な個数の葉ノードが追加された後に、理想性が回復される。さらに、従前には最適であったが理想的ではなかった二分木の最適性を回復することにより、概して、理想二分木ＩＢＴは生み出されない。換言すると、本発明では、二分木の最適性を保存する。理想性は成長および最適性の回復を通じて保存される。
【００８８】
図２８は、二分木の全ての可能性のあるステータスを捕えたものであり、理想二分木、最適（理想的ではない）二分木、および、非最適二分木、が含まれる。また、二分木に対して行われる演算を介した全ての可能性のあるステータスの変化も合わせて描かれ、葉ノードＬＮの追加（理想的な成長アルゴリズムによる）、弱い葉ノードＷＬＮの除去、弱い葉ノード以外の葉ノード除去、および、最適性の回復、が含まれる。非最適のステータスは、一時的、であり、最適性が喪失するとすぐにアルゴリズムが最適性を瞬時に回復することを意味する。
【００８９】
先の説明によると、最適二分木ＯＢＴに対して行われる全ての演算は、葉ノードＬＮの個数の対数である、木の深さに比例する。これらの演算は、葉ノードの除去、葉ノードの追加、最適性の回復、またはソリッドのアップデート、である。反対に、線形リストに対して行われる演算は、葉ノードの総数に主に比例する。全ての基本ボリュームが、修正または削除される確立が同一である、という工業的な仮説の下で、以下の図では、最適二分木と番号付きリストとの間の平均計算成長を比較する。図２９に示すように、二分木を選択する方が、番号付きリストに比べて明らかに有利である。
【００９０】
葉ノードＬＮの個数とｐ＝２ｑ＋ｒで示すと、最適二分木ＯＢＴの平均深さは以下の通り。
【００９１】
【数１】
2015064876.tif 000003
【００９２】
番号付きリストの平均深さは以下の通り。
【００９３】
【数２】
2015064876.tif 000004
【００９４】
適切なデータ構造は、二分木が各ノードに追加的な情報を格納しているものである。二分木のデータ構造、ポインタ、およびナビゲーション機能は、当該技術において標準的である。これを超えて、本発明では、各ノードが以下の数値データを提供することができる、ことを必要とする。すなわち、ノードの部分木の最大の深さ、ノードの部分木の最小の深さ、およびノードの部分木の葉ノードＬＮの個数、である。これらのデータは、演算（葉ノードの除去、葉ノードの追加、最適性の回復）により、最大でも深さに比例する程度のコストで、最新に維持される。アルゴリズムの全体的な対数計算の複雑性は保持される。換言すると、データ構造操作は複雑性を上昇させない。
【００９５】
最適二分木ＯＢＴの以下の特性は、実装を支援することができる。第１の点として、最適二分木の全ての部分木が、同様に最適二分木である。第２の点として、ｐ＝２ｑ＋ｒを最適二分木の葉ノードＬＮの個数、０≦ｒ＜２ｑ、とすると、深さｑの葉ノードの個数は２ｑ−ｒ、深さｑ＋１の葉ノードの個数は２ｒである。よって、最適二分木の最大の深さおよび最小の深さは、葉ノードの個数から簡単に計算することができる。ｐを与えて、ｑおよびｒを、ｐ＝２ｑ＋ｒかつ０≦ｒ＜２ｑ、となるように計算する。ｒ＝０ならば、ｄｍｉｎ：＝ｑかつｄｍａｘ：＝ｑかつｄｍａｘ：＝ｑ＋１である。
【００９６】
この節では、図３０に示すように、従来技術の記載に従って設計されたある一部分を（各入力バケットが線形リストを用いて入力される。図３０の左図）、本発明のデータ形式に変換する（各入力バケットが理想二分木ＩＢＴを用いて入力される。図３０の右図）ことについて説明する。
【００９７】
コンバータが、各入力バケットに対して、理想化アルゴリズムを実行し、これは、基本ボリュームの線形リストを、葉ノードＬＮが当該基本ボリュームである理想二分木ＩＢＴに変換することである。そして、コンバータは、その一部分のソリッドモデリングのアップデートを実行し、これにより、同一のソリッド形状が生み出される。
【００９８】
理想化アルゴリズムでは、理想二分木を以下のように段階的に作成する：
新しい二分木を起動（根ノードまで縮小された空の二分木）
For 線形リストの各基本ボリュームｖ do begin
新しい葉ノードｖを二分木に追加
End for
別のさらに速い理想化アルゴリズムでは、葉ノード個数の関連する範囲、典型的には、ｐ＝２の葉ノードからｐ＝５０の葉ノードまで、に従って予め計算した理想二分木ＩＢＴのライブラリが含まれる。各入力バケットに対して、本方法では、その線形リストの基本ボリュームの個数を読み込む、この葉ノード個数に対応する理想二分木の構造をロードする、および、線形リストの基本ボリュームを二分木の葉ノードに設定する、ことが含まれる。
【００９９】
アルゴリズムの選択は、変換がどの程度大きいか、および、どの程度の頻度か、で決まる。
【０１００】
データ変換の第１の使用は、以前のバージョンのＣＡＤシステム（本発明を実装していない）を使用して設計されたモデルを、本発明を実装するＣＡＤシステムのバージョンと互換性のあるモデルに変換することである。その場合、二分木は、非最適二分木を最適二分木ＯＢＴに変換することにより得られる。
【０１０１】
データ変換の別の使用は、作成後の性能を向上させることである。
【０１０２】
図３１は、本発明を実装することができるコンピュータネットワークまたは同様のデジタル処理環境を示す。
【０１０３】
クライアントコンピュータ／装置ＣＬおよびサーバコンピュータＳＶが、アプリケーションプログラム等を実行する処理装置、記憶装置、および、入出力装置を提供する。クライアントコンピュータ／装置ＣＬはまた、通信ネットワークＣＮＥＴを介して、他のクライアント装置／処理ＣＬおよびサーバコンピュータＳＶを含む他のコンピューティング装置にリンクされる。通信ネットワーク７０は、リモートアクセスネットワーク、グローバルネットワーク（例えば、インターネット）、世界規模のコンピュータ収集、ローカルエリアネットワークまたはワイドエリアネットワーク、およびゲートウェイの一部であってよく、これらはそれぞれのプロトコルを現下で使用してお互いに通信を行う。他の電子装置／コンピュータネットワークアーキテクチャも適切である。
【０１０４】
図３２は、図３１のコンピュータシステムにおける、コンピュータ（例えば、クライアントプロセッサ／装置ＣＬまたはサーバコンピュータＳＶ）の内部構造の図である。各コンピュータＣＬ、ＳＶは、システムバスＳＢを含み、バスは、コンピュータまたは処理システムの構成要素間でデータ転送に使用されるハードウェアの線のセットである。バスＳＢは、本質的には、コンピュータシステム異なる要素（例えば、プロセッサ、ディスク記憶装置、メモリ、入出力ポート、ネットワークポートなど）を接続する共有導管であり、要素間の情報の転送を可能にするものである。
【０１０５】
システムバスＳＢに付随するものには、種々の入力装置および出力装置(例えば、キーボード、マウス、ディスプレイ、プリンタ、スピーカ等)をコンピュータＣＬ、ＳＶに接続するＩ／Ｏ装置インターフェースＤＩがある。ネットワークインターフェースＮＩにより、コンピュータはネットワーク（例えば、図３１のネットワークＣＮＥＴ）に付随する種々の他の装置に接続することができる。
【０１０６】
メモリＭＥＭは、本発明の実施形態を実装するために使用されるコンピュータソフトウェア命令ＳＩおよびデータＣＰＰのための、揮発性記憶装置を提供する（例えば、第１のパスビルダＰＢ、第２のパスを計算するための手段ＣＭ、図１から３０において検討された方法を実装するアップデーターＵＤ、および、上記で詳述したサポーティングコード）。
【０１０７】
ディスク記憶装置ＤＳは、本発明の実施形態を実装するために使用されるコンピュータソフトウェア命令ＳＩおよびデータＤＡＴのための、不揮発性記憶装置を提供する。中央処理装置（ＣＰＵ）もまた、システムバスＳＢに付随し、コンピュータ命令の実行を提供する。
【０１０８】
一実施形態において、プロセッサルーチンＳＩおよびデータＤＡＴは、コンピュータプログラム製品（一般的には、ＣＰＰと呼ばれる）であり、これにはコンピュータ可読媒体（例えば、１つまたは複数のＤＶＤ−ＲＯＭ、ＣＤ−ＲＯＭ、ディスク、テープなどの着脱可能記憶媒体）が含まれ、本発明のシステムのソフトウェア命令の少なくとも一部を提供する。コンピュータプログラム製品ＣＰＰは、従来技術において周知であるように、任意の適切なソフトウェアインストールプロシージャによりインストールされる。
【０１０９】
別の実施形態において、ソフトウェア命令の少なくとも一部は、ケーブル、通信、および／または無線接続を介してダウンロードすることもできる。他の実施形態において、本発明のプログラムは、伝播媒体上の伝播信号上で具現化されるコンピュータプログラム伝播信号製品ＳＰである（例えば、無線波、赤外線波、レーザ波、音波、または、インターネットもしくは他のネットワークなどのグローバルネットワーク上を伝播される電波）。そのような搬送媒体または信号は、本発明のルーチン／プログラムＣＰＰのためのソフトウェア命令の少なくとも一部を提供する。
【０１１０】
代替実施形態において、伝播信号は、伝播媒体上で搬送されるアナログ搬送波またはデジタル信号である。例えば、伝播信号は、グローバルネットワーク（例えば、インターネット）、電気通信網、または他のネットワーク上を伝播される、デジタル化信号であってよい。
【０１１１】
一実施形態において、伝播信号は、ある時間をかけて伝播媒体上を送信される信号であり、例えば、ミリ秒、秒、またはもっと長い時間をかけてネットワーク上を送信されるソフトウェアアプリケーションのための命令などである。
【０１１２】
別の実施形態において、コンピュータプログラム製品ＣＰＰのコンピュータ可読媒体は、コンピュータシステムＣＬが、伝播媒体を受信すること、および、上述したように、コンピュータプログラム伝播信号製品のための伝播媒体において具現化される伝播信号を識別すること、により、受けとりかつ読むことができる伝播媒体である。
【０１１３】
一般的に言えば、用語「搬送媒体」すなわち一時的な搬送、には、前述の一時的な信号、伝播信号、伝播媒体、記憶媒体などが包含される。
【０１１４】
本発明を、その例示の実施形態を参照することで特に示して説明したが、当業者においては、添付の請求項により包含される本発明の範囲を逸脱することなく、形式および詳細の種々の変更がその中においてなされ得ることを理解するであろう。
【図１】
2015064876.tif 000005
【図２】
2015064876.tif 000006
【図３】
2015064876.tif 000007
【図４】
2015064876.tif 000008
【図５】
2015064876.tif 000009
【図６】
2015064876.tif 000010
【図７】
2015064876.tif 000011
【図８】
2015064876.tif 000012
【図９】
2015064876.tif 000013
【図１０】
2015064876.tif 000014
【図１１】
2015064876.tif 000015
【図１２】
2015064876.tif 000016
【図１３】
2015064876.tif 000017
【図１４】
2015064876.tif 000018
【図１５】
2015064876.tif 000019
【図１６】
2015064876.tif 000020
【図１７】
2015064876.tif 000021
【図１８】
2015064876.tif 000022
【図１９】
2015064876.tif 000023
【図２０】
2015064876.tif 000024
【図２１】
2015064876.tif 000025
【図２２】
2015064876.tif 000026
【図２３】
2015064876.tif 000027
【図２４】
2015064876.tif 000028
【図２５】
2015064876.tif 000029
【図２６】
2015064876.tif 000030
【図２７】
2015064876.tif 000031
【図２８】
2015064876.tif 000032
【図２９】
2015064876.tif 000033
【図３０】
2015064876.tif 000034
【図３１】
2015064876.tif 000035
【図３２】
2015064876.tif 000036
【外国語明細書】
2015064876000001.pdf