(57)【要約】【課題】任意の次元に存在する点集合における最遠点対を容易に算出することができるようにする。【解決手段】第１の計算部は、ステップＳ５１において、セルを作成して点を登録し、第２の計算部は、ステップＳ５２において、そのセルを用いて探索エリア対を生成する。第３の計算部は、ステップＳ５３において、全ての探索エリア対を処理したか否かを判定する。未処理の探索エリア対が存在する場合、第４の計算部は、ステップＳ５４において、探索エリア対内で最遠点対を求め、第５の計算部は、ステップＳ５５において、保持している値と、その最遠点対の距離を比較し、値が大きい方を最遠点対候補とし、ステップＳ５３に処理を戻し、全ての探索エリア対を処理するまで、それ以降の処理を繰り返す。本発明は、コンピュータグラフィックスに適用できる。【選択図】      図１０
2004348188.tif 000002
【特許請求の範囲】
【請求項１】
包含空間の対象とされる複数の点が存在する領域を分割して複数のセルを生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する点登録ステップと、
前記点登録ステップの処理により前記点が登録された前記複数のセルの中から２つの前記セルを抽出し、その抽出された２つの前記セルを用いて、前記複数の点の内、互いの距離が最も離れた２点からなる最遠点対が探索される探索エリアの対である探索エリア対を生成する探索エリア対生成ステップと、
前記探索エリア対生成ステップの処理により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対を決定する探索エリア対内最遠点対決定ステップと、
前記探索エリア対内最遠点対決定ステップの処理により決定された前記探索エリア対内最遠点対の距離と、保持されている前記最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御ステップと、
前記探索エリア対生成ステップの処理により生成された全ての前記探索エリア対を処理したか否かを判定し、その判定結果に基づいて、前記最遠点対候補保持制御ステップの処理により制御されて保持されている前記最遠点対の候補を前記最遠点対として決定する最遠点対決定ステップと
をコンピュータに実行させることを特徴とするプログラム。
【請求項２】
前記点登録ステップは、
前記複数の点が存在する空間の座標系の各座標について、値が最大の点、および値が最小の点を抽出する抽出ステップを含み、
前記複数の点を全て包含し、前記抽出ステップの処理により抽出された前記点を境界点とする領域を等分して前記セルを生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する
ことを特徴とする請求項１に記載のプログラム。
【請求項３】
前記点登録ステップは、
前記領域の前記境界点からなる境界点対の内、距離が最大となる前記境界点対の距離を算出する距離算出ステップと、
前記距離算出ステップの処理により算出された前記境界点対の距離に関する情報を、前記最遠点対の候補として保持する保持ステップと
をさらに含むことを特徴とする請求項２に記載のプログラム。
【請求項４】
前記探索エリア対生成ステップは、
前記セルの配置パターンによりクラスとして前記探索エリア対を分類し、各クラスに属する探索エリア対を作成する作成ステップと、
前記作成ステップの処理により作成された前記探索エリア対毎に、前記探索エリアにおいて点対が取り得る最大長を算出する算出ステップと、
前記作成ステップの処理により作成された前記探索エリア対に関する情報を生成し、前記探索エリア対に関する情報を、前記算出ステップの処理により算出された前記最大長に基づいてソートし、所定のスタックに保存させる保存制御ステップと
を含むことを特徴とする請求項１に記載のプログラム。
【請求項５】
前記最遠点対決定ステップは、
前記探索エリア対生成ステップの処理により生成された前記探索エリア対の中から、前記最遠点対を検索する処理を行う前記探索エリア対を選択し、取得する探索エリア対取得ステップと、
前記探索エリア対取得ステップの処理により取得された前記探索エリア対の中に、未処理の探索エリア対が存在するか否かを判定する存在判定ステップと、
前記存在判定ステップの処理による判定の結果、未処理の探索エリア対が存在しない場合、保持している前記最遠点対の候補を前記最遠点対として決定して出力する出力ステップと
を含むことを特徴とする請求項１に記載のプログラム。
【請求項６】
前記探索エリア対取得ステップは、
前記探索エリア対生成ステップの処理により生成された前記探索エリア対の最大長が、前記領域の前記境界点からなる境界点対の距離の最大値より大きいか否かを判定する距離判定ステップを含み、
前記距離判定ステップの処理による判定の結果、前記最大長が前記境界点対の距離より大きいと判定された前記探索エリア対を選択し、取得する
ことを特徴とする請求項５に記載のプログラム。
【請求項７】
前記最遠点対決定ステップの処理により、未処理の探索エリア対が存在しないと判定されるまで、前記探索エリア対内最遠点対決定ステップおよび前記最遠点対候補保持ステップを繰り返し実行する
ことを特徴とする請求項１に記載のプログラム。
【請求項８】
包含空間の対象とされる複数の点が存在する領域を分割して複数のセルを生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する点登録ステップと、
前記点登録ステップの処理により前記点が登録された前記複数のセルの中から２つの前記セルを抽出し、その抽出された２つの前記セルを用いて、前記複数の点の内、互いの距離が最も離れた２点からなる最遠点対が探索される探索エリアの対である探索エリア対を生成する探索エリア対生成ステップと、
前記探索エリア対生成ステップの処理により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対を決定する探索エリア対内最遠点対決定ステップと、
前記探索エリア対内最遠点対決定ステップの処理により決定された前記探索エリア対内最遠点対の距離と、保持されている前記最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御ステップと、
前記探索エリア対生成ステップの処理により生成された全ての前記探索エリア対を処理したか否かを判定し、その判定結果に基づいて、前記最遠点対候補保持制御ステップの処理により制御されて保持されている前記最遠点対の候補を前記最遠点対として決定する最遠点対決定ステップと
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
【請求項９】
情報処理装置の情報処理方法であって、
包含空間の対象とされる複数の点が存在する領域を分割して複数のセルを生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する点登録ステップと、
前記点登録ステップの処理により前記点が登録された前記複数のセルの中から２つの前記セルを抽出し、その抽出された２つの前記セルを用いて、前記複数の点の内、互いの距離が最も離れた２点からなる最遠点対が探索される探索エリアの対である探索エリア対を生成する探索エリア対生成ステップと、
前記探索エリア対生成ステップの処理により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対を決定する探索エリア対内最遠点対決定ステップと、
前記探索エリア対内最遠点対決定ステップの処理により決定された前記探索エリア対内最遠点対の距離と、保持されている前記最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御ステップと、
前記探索エリア対生成ステップの処理により生成された全ての前記探索エリア対を処理したか否かを判定し、その判定結果に基づいて、前記最遠点対候補保持制御ステップの処理により制御されて保持されている前記最遠点対の候補を前記最遠点対として決定する最遠点対決定ステップと
を含むことを特徴とする情報処理方法。
【請求項１０】
包含空間の対象とされる複数の点が存在する領域を分割して複数のセルを生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する点登録手段と、
前記点登録手段により前記点が登録された前記複数のセルの中から２つの前記セルを抽出し、その抽出された２つの前記セルを用いて、前記複数の点の内、互いの距離が最も離れた２点からなる最遠点対が探索される探索エリアの対である探索エリア対を生成する探索エリア対生成手段と、
前記探索エリア対生成手段により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対を決定する探索エリア対内最遠点対決定手段と、
前記探索エリア対内最遠点対決定手段により決定された前記探索エリア対内最遠点対の距離と、保持されている前記最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御手段と、
前記探索エリア対生成手段により生成された全ての前記探索エリア対を処理したか否かを判定し、その判定結果に基づいて、前記最遠点対候補保持制御手段により制御されて保持されている前記最遠点対の候補を前記最遠点対として決定する最遠点対決定手段と
を備えることを特徴とする情報処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はプログラム、記録媒体、並びに情報処理方法および装置に関し、特に、任意の次元に存在する点集合における最遠点対を容易に算出することができるようにしたプログラム、記録媒体、並びに情報処理方法および装置に関する。
【０００２】
【従来の技術】
コンピュータグラフィックスにおいて、物体と物体が衝突する画像を表現することがある。このような場合、それぞれの物体の形状を正確に表現し、その正確に表現された物体どうしが衝突するかどうかを判定することが基本となる。
【０００３】
しかしながら、正確に表現した物体どうしが衝突するかどうかを判定するようにすると、その演算に時間がかかることになる。そこで、２次元空間において物体の衝突を判定する場合、物体を、その物体を包含する長方形で表現し、その方形が衝突するか否かを判定することが行われる。なお、３次元空間において物体の衝突を判定する場合、物体は、その物体を包含する直方体で表現され、その長方体が衝突するか否かを判定することが行われる。
【０００４】
このとき、２次元空間において、物体を表現した長方形（３次元の場合、直方体）が必要以上に大きいと、物体が他の物体と衝突する正確なタイミングを判定することが困難になるので、任意の形状の物体を内包する最小の長方形（３次元の場合、直方体）を求めることが必要となる。
【０００５】
このように、物体を包含する最小の長方形（直方体）を算出する場合、物体の形状において最も距離が離れた２点を算出することが必要になる。すなわち、物体を点集合の集まりと考えると、任意に配置された点集合の内、互いの距離が最も離れた２点の対（以下、最遠点対と称する）を算出することにより、点集合（物体）を包含する最小の長方形（直方体）を算出することが可能になる。
【０００６】
従来、このような任意に配置された点集合の最遠点対を算出する方法として、例えば２次元空間の場合、点集合を包含する凸多角形を算出し、その凸多角形を用いて最遠点対を求めるキャリパー法がある。
【０００７】
また、２次元以上の空間においては、最も単純な方法として、点集合より全ての組み合わせの２点（点対）について総当りで距離を算出し、距離が最大の点対を決定する方法がある。さらに、ランダム追加法による線形計画法の解法に似たＬＰ型解法、多次元パラメトリック探索法、並びに、これらを組み合わせた方法等がある（例えば、非特許文献１参照）。
【０００８】
【非特許文献１】
徳山  豪（東北大学  大学院  情報科学研究科）「パラメトリック最適化と計算幾何学」情報処理学会研究報告、Ｖｏｌ．２０００，ＮＯ．１０３（ＡＬ−７５）；ＰＡＧＥ．２５−２８；２０００年；ＪＡ
【０００９】
【発明が解決しようとする課題】
しかしながら、例えば、キャリパー法の場合、その計算量はＯ（ｎ×ｌｏｇ（ｎ））となり、総当りで行う場合、その計算量はＯ（ｎ＾２）となるなど、上述したような方法の場合、その計算量が多く、点の数が増えると計算が非効率にり、処理の負荷が増大してしまうという課題があった。
【００１０】
本発明はこのような状況に鑑みてなされたものであり、任意の次元に存在する点集合における最遠点対を容易に算出することができるようにするものである。
【００１１】
【課題を解決するための手段】
本発明のプログラムは、包含空間の対象とされる複数の点が存在する領域を分割して複数のセルを生成し、複数の点を、各点が対応するセルにそれぞれ登録する点登録ステップと、点登録ステップの処理により点が登録された複数のセルの中から２つのセルを抽出し、その抽出された２つのセルを用いて、複数の点の内、互いの距離が最も離れた２点からなる最遠点対が探索される探索エリアの対である探索エリア対を生成する探索エリア対生成ステップと、探索エリア対生成ステップの処理により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対を決定する探索エリア対内最遠点対決定ステップと、探索エリア対内最遠点対決定ステップの処理により決定された探索エリア対内最遠点対の距離と、保持されている最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御ステップと、探索エリア対生成ステップの処理により生成された全ての探索エリア対を処理したか否かを判定し、その判定結果に基づいて、最遠点対候補保持制御ステップの処理により制御されて保持されている最遠点対の候補を最遠点対として決定する最遠点対決定ステップとをコンピュータに実行させることを特徴とする。
【００１２】
前記点登録ステップは、複数の点が存在する空間の座標系の各座標について、値が最大の点、および値が最小の点を抽出する抽出ステップを含み、複数の点を全て包含し、抽出ステップの処理により抽出された点を境界点とする領域を等分してセルを生成し、複数の点を、各点が対応する前記セルにそれぞれ登録することができる。
【００１３】
前記点登録ステップは、領域の境界点からなる境界点対の内、距離が最大となる境界点対の距離を算出する距離算出ステップと、距離算出ステップの処理により算出された境界点対の距離に関する情報を、最遠点対の候補として保持する保持ステップとをさらに含むことができる。
【００１４】
前記探索エリア対生成ステップは、セルの配置パターンによりクラスとして探索エリア対を分類し、各クラスに属する探索エリア対を作成する作成ステップと、作成ステップの処理により作成された探索エリア対毎に、探索エリアにおいて点対が取り得る最大長を算出する算出ステップと、作成ステップの処理により作成された探索エリア対に関する情報を生成し、探索エリア対に関する情報を、算出ステップの処理により算出された最大長に基づいてソートし、所定のスタックに保存させる保存制御ステップとことができる。
【００１５】
前記最遠点対決定ステップは、探索エリア対生成ステップの処理により生成された探索エリア対の中から、最遠点対を検索する処理を行う探索エリア対を選択し、取得する探索エリア対取得ステップと、探索エリア対取得ステップの処理により取得された探索エリア対の中に、未処理の探索エリア対が存在するか否かを判定する存在判定ステップと、存在判定ステップの処理による判定の結果、未処理の探索エリア対が存在しない場合、保持している最遠点対の候補を最遠点対として決定して出力する出力ステップとを含むことができる。
【００１６】
前記探索エリア対取得ステップは、探索エリア対生成ステップの処理により生成された探索エリア対の最大長が、領域の境界点からなる境界点対の距離の最大値より大きいか否かを判定する距離判定ステップを含み、距離判定ステップの処理による判定の結果、最大長が境界点対の距離より大きいと判定された探索エリア対を選択し、取得することができる。
【００１７】
前記最遠点対決定ステップの処理により、未処理の探索エリア対が存在しないと判定されるまで、探索エリア対内最遠点対決定ステップおよび最遠点対候補保持ステップを繰り返し実行することができる。
【００１８】
本発明の記録媒体のプログラムは、包含空間の対象とされる複数の点が存在する領域を分割して複数のセルを生成し、複数の点を、各点が対応するセルにそれぞれ登録する点登録ステップと、点登録ステップの処理により点が登録された複数のセルの中から２つのセルを抽出し、その抽出された２つのセルを用いて、複数の点の内、互いの距離が最も離れた２点からなる最遠点対が探索される探索エリアの対である探索エリア対を生成する探索エリア対生成ステップと、探索エリア対生成ステップの処理により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対を決定する探索エリア対内最遠点対決定ステップと、探索エリア対内最遠点対決定ステップの処理により決定された探索エリア対内最遠点対の距離と、保持されている最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御ステップと、探索エリア対生成ステップの処理により生成された全ての探索エリア対を処理したか否かを判定し、その判定結果に基づいて、最遠点対候補保持制御ステップの処理により制御されて保持されている最遠点対の候補を最遠点対として決定する最遠点対決定ステップとを含むことを特徴とする。
【００１９】
本発明の情報処理方法は、包含空間の対象とされる複数の点が存在する領域を分割して複数のセルを生成し、複数の点を、各点が対応するセルにそれぞれ登録する点登録ステップと、点登録ステップの処理により点が登録された複数のセルの中から２つのセルを抽出し、その抽出された２つのセルを用いて、複数の点の内、互いの距離が最も離れた２点からなる最遠点対が探索される探索エリアの対である探索エリア対を生成する探索エリア対生成ステップと、探索エリア対生成ステップの処理により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対を決定する探索エリア対内最遠点対決定ステップと、探索エリア対内最遠点対決定ステップの処理により決定された探索エリア対内最遠点対の距離と、保持されている最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御ステップと、探索エリア対生成ステップの処理により生成された全ての探索エリア対を処理したか否かを判定し、その判定結果に基づいて、最遠点対候補保持制御ステップの処理により制御されて保持されている最遠点対の候補を最遠点対として決定する最遠点対決定ステップとを含むことを特徴とする。
【００２０】
本発明の情報処理装置は、包含空間の対象とされる複数の点が存在する領域を分割して複数のセルを生成し、複数の点を、各点が対応するセルにそれぞれ登録する点登録手段と、点登録手段により点が登録された複数のセルの中から２つのセルを抽出し、その抽出された２つのセルを用いて、複数の点の内、互いの距離が最も離れた２点からなる最遠点対が探索される探索エリアの対である探索エリア対を生成する探索エリア対生成手段と、探索エリア対生成手段により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対を決定する探索エリア対内最遠点対決定手段と、探索エリア対内最遠点対決定手段により決定された探索エリア対内最遠点対の距離と、保持されている最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御手段と、探索エリア対生成手段により生成された全ての探索エリア対を処理したか否かを判定し、その判定結果に基づいて、最遠点対候補保持制御手段により制御されて保持されている最遠点対の候補を最遠点対として決定する最遠点対決定手段とを備えることを特徴とする。
【００２１】
本発明においては、包含空間の対象とされる複数の点が存在する領域が分割されて複数のセルが生成され、その複数の点が、各点が対応するセルにそれぞれ登録され、点が登録された複数のセルの中から２つのセルが抽出され、その抽出された２つのセルが用いられて、複数の点の内、互いの距離が最も離れた２点からなる最遠点対が探索される探索エリアの対である探索エリア対が生成され、そのように生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対が決定され、その決定された探索エリア対内最遠点対の距離と、保持されている最遠点対の候補の距離とが比較され、値が大きい方が最遠点対の候補として保持されるように制御され、生成された全ての探索エリア対を処理したか否かを判定し、その判定結果に基づいて、保持されている最遠点対の候補が最遠点対として決定される。
【００２２】
【発明の実施の形態】
以下に本発明の実施の形態を説明するが、請求項に記載の構成要件と、発明の実施の形態における具体例との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする具体例が、発明の実施の形態に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、構成要件に対応するものとして、ここには記載されていない具体例があったとしても、そのことは、その具体例が、その構成要件に対応するものではないことを意味するものではない。逆に、具体例が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その具体例が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００２３】
さらに、この記載は、発明の実施の形態に記載されている具体例に対応する発明が、請求項に全て記載されていることを意味するものではない。換言すれば、この記載は、発明の実施の形態に記載されている具体例に対応する発明であって、この出願の請求項には記載されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加される発明の存在を否定したりするものではない。
【００２４】
［請求項１］  包含空間（例えば、図１２の領域１４０）の対象とされる複数の点（例えば、図９の点１１１ｉ）が存在する領域を分割して複数のセル（例えば、図１２のセル１４１乃至セル１４４）を生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する点登録ステップ（例えば、図１１のステップＳ５１）と、
前記点登録ステップの処理により前記点が登録された前記複数のセルの中から２つの前記セルを抽出し、その抽出された２つの前記セルを用いて、前記複数の点の内、互いの距離が最も離れた２点からなる最遠点対（例えば、図９の最遠点対１０１）が探索される探索エリア（セル１４２またはセル１４４）の対である探索エリア対（セル１４２およびセル１４４）を生成する探索エリア対生成ステップ（例えば、図１２のステップＳ５２）と、
前記探索エリア対生成ステップの処理により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対（例えば、図２５の軸２８２）を決定する探索エリア対内最遠点対決定ステップ（例えば、図１２のステップＳ５４）と、
前記探索エリア対内最遠点対決定ステップの処理により決定された前記探索エリア対内最遠点対の距離と、保持されている前記最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御ステップ（例えば、図１２のステップＳ５５）と、
前記探索エリア対生成ステップの処理により生成された全ての前記探索エリア対を処理したか否かを判定し、その判定結果に基づいて、前記最遠点対候補保持制御ステップの処理により制御されて保持されている前記最遠点対の候補を前記最遠点対として決定する最遠点対決定ステップ（例えば、図１２のステップＳ５３）と
をコンピュータに実行させることを特徴とするプログラム。
［請求項２］  前記点登録ステップは、
前記複数の点が存在する空間の座標系の各座標について、値が最大の点（例えば、図１２の点１３２および点１３３）、および値が最小の点（例えば、図１２の点１３１および点１３４）を抽出する抽出ステップ（例えば、図１１のステップＳ７３）を含み、
前記複数の点を全て包含し、前記抽出ステップの処理により抽出された前記点を境界点とする領域を等分して前記セルを生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する
ことを特徴とする請求項１に記載のプログラム。
［請求項３］  前記点登録ステップは、
前記領域の前記境界点からなる境界点対の内、距離が最大となる前記境界点対の距離を算出する距離算出ステップ（例えば，図１１のステップＳ７５）と、
前記距離算出ステップの処理により算出された前記境界点対の距離に関する情報を、前記最遠点対の候補として保持する保持ステップと（例えば、図１１のステップＳ７６）
をさらに含むことを特徴とする請求項２に記載のプログラム。
［請求項４］  前記探索エリア対生成ステップは、
前記セルの配置パターンによりクラスとして前記探索エリア対を分類し、各クラスに属する探索エリア対を作成する作成ステップ（例えば、図１３のステップＳ１３１）と、
前記作成ステップの処理により作成された前記探索エリア対毎に、前記探索エリアにおいて点対が取り得る最大長を算出する算出ステップ（例えば、図１３のステップＳ１３２）と、
前記作成ステップの処理により作成された前記探索エリア対に関する情報を生成し、前記探索エリア対に関する情報を、前記算出ステップの処理により算出された前記最大長に基づいてソートし、所定のスタックに保存させる保存制御ステップ（例えば、図１３のステップＳ１３３）と
を含むことを特徴とする請求項１に記載のプログラム。
［請求項５］  前記最遠点対決定ステップは、
前記探索エリア対生成ステップの処理により生成された前記探索エリア対の中から、前記最遠点対を検索する処理を行う前記探索エリア対を選択し、取得する探索エリア対取得ステップ（例えば、図１１のステップＳ９１）と、
前記探索エリア対取得ステップの処理により取得された前記探索エリア対の中に、未処理の探索エリア対が存在するか否かを判定する存在判定ステップ（例えば、図１１のステップＳ９２）と、
前記存在判定ステップの処理による判定の結果、未処理の探索エリア対が存在しない場合、保持している前記最遠点対の候補を前記最遠点対として決定して出力する出力ステップ（例えば、図１１のステップＳ９３）と
を含むことを特徴とする請求項１に記載のプログラム。
［請求項６］  前記探索エリア対取得ステップは、
前記探索エリア対生成ステップの処理により生成された前記探索エリア対の最大長が、前記領域の前記境界点からなる境界点対の距離の最大値より大きいか否かを判定する距離判定ステップ（例えば、図２１のステップＳ１５９）を含み、
前記距離判定ステップの処理による判定の結果、前記最大長が前記境界点対の距離より大きいと判定された前記探索エリア対を選択し、取得する
ことを特徴とする請求項５に記載のプログラム。
［請求項７］  前記最遠点対決定ステップの処理により、未処理の探索エリア対が存在しないと判定されるまで、前記探索エリア対内最遠点対決定ステップおよび前記最遠点対候補保持ステップを繰り返し実行する
ことを特徴とする請求項１に記載のプログラム。
［請求項８］  包含空間（例えば、図１２の領域１４０）の対象とされる複数の点（例えば、図９の点１１１ｉ）が存在する領域を分割して複数のセル（例えば、図１２のセル１４１乃至セル１４４）を生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する点登録ステップ（例えば、図１１のステップＳ５１）と、
前記点登録ステップの処理により前記点が登録された前記複数のセルの中から２つの前記セルを抽出し、その抽出された２つの前記セルを用いて、前記複数の点の内、互いの距離が最も離れた２点からなる最遠点対（例えば、図９の最遠点対１０１）が探索される探索エリア（セル１４２またはセル１４４）の対である探索エリア対（セル１４２およびセル１４４）を生成する探索エリア対生成ステップ（例えば、図１２のステップＳ５２）と、
前記探索エリア対生成ステップの処理により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対（例えば、図２５の軸２８２）を決定する探索エリア対内最遠点対決定ステップ（例えば、図１２のステップＳ５４）と、
前記探索エリア対内最遠点対決定ステップの処理により決定された前記探索エリア対内最遠点対の距離と、保持されている前記最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御ステップ（例えば、図１２のステップＳ５５）と、
前記探索エリア対生成ステップの処理により生成された全ての前記探索エリア対を処理したか否かを判定し、その判定結果に基づいて、前記最遠点対候補保持制御ステップの処理により制御されて保持されている前記最遠点対の候補を前記最遠点対として決定する最遠点対決定ステップ（例えば、図１２のステップＳ５３）と
を含むことを特徴とするコンピュータが読み取り可能なプログラムが記録されている記録媒体。
［請求項９］  情報処理装置の情報処理方法であって、
包含空間（例えば、図１２の領域１４０）の対象とされる複数の点（例えば、図９の点１１１ｉ）が存在する領域を分割して複数のセル（例えば、図１２のセル１４１乃至セル１４４）を生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する点登録ステップ（例えば、図１１のステップＳ５１）と、
前記点登録ステップの処理により前記点が登録された前記複数のセルの中から２つの前記セルを抽出し、その抽出された２つの前記セルを用いて、前記複数の点の内、互いの距離が最も離れた２点からなる最遠点対（例えば、図９の最遠点対１０１）が探索される探索エリア（セル１４２またはセル１４４）の対である探索エリア対（セル１４２およびセル１４４）を生成する探索エリア対生成ステップ（例えば、図１２のステップＳ５２）と、
前記探索エリア対生成ステップの処理により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対（例えば、図２５の軸２８２）を決定する探索エリア対内最遠点対決定ステップ（例えば、図１２のステップＳ５４）と、
前記探索エリア対内最遠点対決定ステップの処理により決定された前記探索エリア対内最遠点対の距離と、保持されている前記最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御ステップ（例えば、図１２のステップＳ５５）と、
前記探索エリア対生成ステップの処理により生成された全ての前記探索エリア対を処理したか否かを判定し、その判定結果に基づいて、前記最遠点対候補保持制御ステップの処理により制御されて保持されている前記最遠点対の候補を前記最遠点対として決定する最遠点対決定ステップ（例えば、図１２のステップＳ５３）と
を含むことを特徴とする情報処理方法。
［請求項１０］  包含空間（例えば、図１２の領域１４０）の対象とされる複数の点（例えば、図９の点１１１ｉ）が存在する領域を分割して複数のセル（例えば、図１２のセル１４１乃至セル１４４）を生成し、前記複数の点を、各点が対応する前記セルにそれぞれ登録する点登録手段（例えば、図１１のステップＳ５１の処理を実行する図８の第１の計算部８１）と、
前記点登録手段により前記点が登録された前記複数のセルの中から２つの前記セルを抽出し、その抽出された２つの前記セルを用いて、前記複数の点の内、互いの距離が最も離れた２点からなる最遠点対（例えば、図９の最遠点対１０１）が探索される探索エリア（セル１４２またはセル１４４）の対である探索エリア対（セル１４２およびセル１４４）を生成する探索エリア対生成手段（例えば、図１１のステップＳ５２の処理を実行する図８の第２の計算部８２）と、
前記探索エリア対生成手段により生成された探索エリア対内において、探索エリア対内における最遠点対である探索エリア対内最遠点対（例えば、図２５の軸２８２）を決定する探索エリア対内最遠点対決定手段（例えば、図１１のステップＳ５４の処理を実行する図８の第４の計算部８４）と、
前記探索エリア対内最遠点対決定手段により決定された前記探索エリア対内最遠点対の距離と、保持されている前記最遠点対の候補の距離とを比較し、値が大きい方を最遠点対の候補として保持するように制御する最遠点対候補保持制御手段（例えば、図１１のステップＳ５５の処理を実行する図８の第５の計算部８５）と、
前記探索エリア対生成手段により生成された全ての前記探索エリア対を処理したか否かを判定し、その判定結果に基づいて、前記最遠点対候補保持制御手段により制御されて保持されている前記最遠点対の候補を前記最遠点対として決定する最遠点対決定手段（例えば、図１１のステップＳ５３の処理を実行する図８の第３の計算部８３）と
を備えることを特徴とする情報処理装置。
【００２５】
以下、本発明の実施の形態について説明するが、最初に本発明が適用される技術の例について説明する。
【００２６】
図１は、物体監視システムの例を表している。この例においては、ベルトコンベア３により、任意の形状の物体２が搬送されている。ただし、図１においては、便宜上、物体２は四角形で示されている。ビデオカメラ１は、搬送される物体２をベルトコンベア３の進行方向と垂直な方向から撮影する。ビデオカメラ１の撮影可能範囲は撮影領域１１とされる。
【００２７】
ベルトコンベア３上の所定の位置に一定の間隔で物体２が順次配置され、搬送される場合において、ビデオカメラ１により物体２が撮影されているか否かを判定し、撮影されているとき、ビデオカメラ１の画像データを処理し、物体２の映像を分析するような場合、物体２がビデオカメラ１の撮影領域１１内に入ったか否かを判定する必要がある。図２は、このための処理の例を表している。
【００２８】
ステップＳ１において、ユーザは、ビデオカメラ１の撮影領域１１のデータを入力する。
【００２９】
ステップＳ２において、図示せぬ判定処理装置において、物体を包含する最小の長方形である境界矩形が撮影領域１１にかかっているか否かを判定する。
【００３０】
図３は、ビデオカメラ１から見た物体２の、平面上における、より詳細な形状の例を表している。この物体２は、不特定の形状（数学的な表現が複雑となる形状）をしているため、この物体２を包含する長方形２１により物体２が近似的に表現される。この長方形２１の大きさを物体２と比較してあまり大きくすると、物体２（長方形２１）が撮影領域１１内にかかったか否かのタイミングを正確に判定することが困難になる。そこで、この長方形２１は、図３に示されるように、物体２を包含する最小の長方形（境界矩形）であることが望ましい。すなわち、物体２は、物体２において最も距離が遠い２点である最遠点対を両端とする線分２２と平行な２辺と、線分２２と直交する２辺により構成され、物体２を包含し、さらに、全ての辺が物体２に接する長方形により近似的に表現される。
【００３１】
なお、本明細書において、長方形は、四つの内角がすべて直角である四辺形であり、その長方形には、四つの辺および四つの内角がそれぞれ等しい四辺形である正方形も含まれる。同様に、本明細書において、直方体は、すべての面が長方形で、相対する面が平行な六面体であり、その直方体には、六つの合同な正方形で囲まれた立体である立方体（正六面体）も含まれる。
【００３２】
図２に戻り、ステップＳ２において、物体２の長方形２１が撮影領域１１にかかっていると判定された場合、ステップＳ３に進み、物体２の実際の形状が撮影領域１１にかかっているか否かが判定される。この判定処理は、物体２の実際の形状に基づいて行われる。物体２の形状は、複雑な形状となっているため、その形状の少なくとも一部が撮影領域１１にかかっているか否かの判定処理には、演算が多く、比較的長い時間が必要となる。
【００３３】
ステップＳ３において、物体２が撮影領域１１にかかっていると判定された場合、ステップＳ４に進み、物体２がビデオカメラ１により撮影されていると判断される。
【００３４】
これに対して、ステップＳ２において、物体２の境界矩形である長方形２１が撮影領域１１にかかっていないと判定された場合、ステップＳ５に進み、物体２は、ビデオカメラ１により撮影されてないと判断される。
【００３５】
ステップＳ３において、物体２が撮影領域１１にかかっていないと判定された場合にも、ステップＳ５に進み、物体２が撮影されていないと判断される。
【００３６】
このように、演算量が多く、処理に時間を必要とするステップＳ３の処理は、ステップＳ２において、境界矩形（長方形２１）が撮影領域１１にかかっていると判定された場合においてのみ実行される。換言すれば、ステップＳ２において、物体２の境界矩形（長方形２１）が撮影領域１１にかかっていないと判定された場合には、ステップＳ３の処理は実行されないため、迅速な判定処理が可能となる。
【００３７】
図２のフローチャートに示される処理は、コンピュータグラフィックスの分野においても行われる。例えば、図４に示されるように、コンピュータグラフィックスシステムが描画する仮想的な３次元空間内に、視点としてのビデオカメラ３１−１とビデオカメラ３１−２が、それぞれ撮影領域３２−１と撮影領域３２−２を撮影しているものと仮定し、その撮像画像を表示するものとする。物体３３が移動しているとすると、仮想的なビデオカメラ３１−１が撮影する撮影領域３２−１内を物体３３が通過するタイミングの時、仮想的なビデオカメラ３１−１で撮影された画像の中に物体３３の画像を描画する必要がある。同様に、仮想的なビデオカメラ３１−２の撮影領域３２−２を、物体３３が通過するタイミングにおける仮想的ビデオカメラ３１−２の画像には、物体３３の画像を含める必要がある。
【００３８】
このような場合においても、物体３３が撮影領域３２−１，３２−２にかかったか否かが、物体３３を包含する境界矩形３４に基づいて、図２のステップＳ２において判定され、撮影領域３２−１，３２−２にかかっていると判定された場合においてのみ、ステップＳ３の判定処理が行われる。ステップＳ２において、境界矩形３４が撮影領域３２−１，３２−２にかかっていないと判定された場合には、直ちにステップＳ５において、物体３３が撮影されていないと判断されるので、迅速な判定処理が可能となる。
【００３９】
図５は、コンピュータグラフィックスシステムにおいて行われる運動シミュレーションの例を表している。この例においては、図６に示されるように、運動するボール４１（４１Ａ，４１Ｂ，４１Ｃ）が物体４３に衝突し、跳ね返る画像を描画するものとする。
【００４０】
ステップＳ２１において、矢印４２に沿って運動するボール４１の位置と速度が入力される。ステップＳ２２において、ボール４１が物体４３の境界矩形４４にかかっているか否かが判定される。この物体４３もまた不特定の任意の形状であり、それを包含する最小の長方形である境界矩形４４によって、このステップＳ２２の判定処理が行われる。
【００４１】
ステップＳ２２において、ボール４１が物体４３の境界矩形４４にかかっていると判定された場合（ボール４１が、ボール４１Ｂまたは４１Ｃとして示されている位置にある場合）、ステップＳ２３に進み、ボール４１が物体４３の具体的な形状に基づく領域にかかっているか否かが判定される。ステップＳ２２の判定処理は、物体４３の形状が境界矩形４４で近似的に表現されているため、迅速に行うことができるが、ステップＳ２３の判定処理は、物体４３の実際の形状に基づいて判定処理が行われるため、時間がかかることになる。
【００４２】
ステップＳ２３において、ボール４１が物体４３の領域にかかっていると判定された場合（ボール４１が、ボール４１Ｃとして示される位置にある場合）には、ボール４１が物体４３に衝突し反射するので、ステップＳ２４に進み、そのボール４３が反射した位置と速度を設定する処理が行われる。その後、処理はステップＳ２２に戻り、それ以降の処理が繰り返し実行される。
【００４３】
ステップＳ２２において、ボール４１が物体４３の境界矩形４４にかかっていないと判定された場合（ボール４１が、ボール４１Ａとして示される位置にある場合）、並びにステップＳ２３において、ボールが物体の領域にかかっていないと判定された場合（ボール４１が、ボール４１Ｂとして示される位置にある場合）、ステップＳ２５に進み、次の時間におけるボール４１の位置を設定する処理が行われる。その後、処理はステップＳ２２に戻り、それ以降の処理が繰り返し実行される。
【００４４】
このように、この場合においても、ステップＳ２２において、ボール４１が物体４３の境界矩形４４にかかっていないと判定された場合には、比較的複雑な演算が必要となるステップＳ２３の処理は実行されないので、迅速な描画処理を行うことが可能である。
【００４５】
図７は、本発明を適用したコンピュータグラフィックス機能を有する画像処理装置６１の構成例を表している。入力部７１は、マウス、キーボードなどにより構成され、ユーザにより、必要に応じ操作され、操作に対応する信号を出力する。出力部７２は、ディスプレイ、スピーカなどにより構成され、画像または音声を出力する。最遠点対計算部７３は、物体を包含する最小の長方形（境界矩形）を求めるために、物体における最も距離が遠い２点の点対である最遠点対を算出する計算に関する処理を行う。また、凸図形計算部７４は、最遠点対計算を行う前処理として凸図形を算出する処理を行う。
【００４６】
なお、凸図形計算部７４による凸図形の算出処理は、後述するように省略することも可能であり、その場合、凸図形計算部７４を省略することもできる。
【００４７】
ＣＰＵ７５は、ＲＯＭ７７から読み出され、ＲＡＭ７６に展開されたプログラムに従って、各種の処理を実行する。ＲＡＭ７６には、コンピュータプログラムの他、ＣＰＵ７５が各種の処理を実行する上において必要なデータやパラメータなどが適宜記憶される。ＲＯＭ７７には、コンピュータプログラム、その他、各種の処理に必要なパラメータやデータが記憶されている。
【００４８】
入力部７１乃至ＲＯＭ７７は、バス７０を介して相互に接続されている。
【００４９】
図８は、最遠点対計算部７３の機能的構成例を表している。同図に示されるように、最遠点対計算部７３は、第１の計算部８１，第２の計算部８２，第３の計算部８３、第４の計算部８４、および第５の計算部８５により構成される。第１の計算部８１は、後述するセルを作成し、登録する登録処理（図１０のステップＳ５１の処理）を行う。第２の計算部８２は、第１の計算部８１で求められたセル毎に、後述する探索エリア対を生成する生成処理を行う（図１０のステップＳ５２の処理）。第３の計算部８３は、第２の計算部８２の生成処理により生成された全ての探索エリアについて、後述するステップＳ５４およびＳ５５の処理を行ったか否かを判定する判定処理（図１０のステップＳ５３の処理）を実行する。第４の計算部８４は、第３の計算部８３の判定処理により未処理の探索エリア対が存在すると判定された探索エリアにおいて、探索エリア対内における最遠点対を求める処理（図１０のステップＳ５４の処理）を実行する。第５の計算部８５は、第４の計算部８４による処理により求められた探索エリア対内における最遠点対と、保持している最遠点対との距離を比較し、大きい方を新たな最遠点対とする決定処理（図１０のステップＳ５５の処理）を実行する。
【００５０】
この画像処理装置６１においては、物体を包含する境界矩形を求める処理を行うのであるが、以下においては、物体の代わりに任意に配置された複数の点からなる点列より、最遠点対を求めるものとする。なお、最遠点対が求まれば、物体を包含する最小の長方形である境界矩形は容易に算出することができるので、その処理の説明は省略する。
【００５１】
図９に、２次元に配置された点列における最遠点対の例を示す。
【００５２】
図９に示されるように、最遠点対１０１は、２次元空間に任意に配置された複数の点１１１ｉ（ｉ＝１，２，３，・・・）において距離が最も遠い２点の組み合わせ（点対）である。図９の場合、点１２１および点１２２間の距離が最も遠く、この２点（点１２１および点１２２）からなる点対が最遠点対１０１となる。
【００５３】
このような最遠点対を求める最遠点対決定処理について、図１０のフローチャートを参照して説明する。
【００５４】
ステップＳ５１において、最遠点対計算部７３の第１の計算部８１は、後述するセルを作成し、各セルに点を登録する処理を行う。次に、ステップＳ５２において、第２の計算部８２は、ステップＳ５１の処理により作成されたセルを組み合わせて最遠点対を探索する探索エリア対を生成する。探索エリア対の詳細については後述する。ステップ５２の処理が終了した後、ステップＳ５３において、第３の計算部８３は、ステップＳ５２において生成された全ての探索エリア対について、後述するステップＳ５４およびステップＳ５５の処理を行ったか否かを判定する。ステップＳ５４およびステップＳ５５の処理により、処理済の探索エリア対の中で最も距離が遠い点対を求めることができるので、全ての探索エリア対が処理された場合、図９に示されるように、点列の中で最も距離が遠い点対である最遠点対１０１が求められたことになる。
【００５５】
これに対して、未だ未処理の探索エリア対が存在する場合には、距離を比較していない点対が存在することを示しており、まだ最遠点対は求められていないことになる。そこで、ステップＳ５４に進み、第４の計算部８４は、未処理の探索エリア対の１つに注目し、その探索エリア対内における最遠点対を求める処理を行う。そして、ステップＳ５５において、第５の計算部８５は、今回のステップＳ５４の処理により求められた探索エリア対内の最遠点対と、前回までに処理された探索エリア対の中で最も距離が遠い点対である最遠点対の候補とを比較し、距離が大きい方を最新の最遠点対候補として保持する。そして、最遠点対計算部７３は、ステップＳ５３に処理を戻し、それ以降の処理を繰り返す。
【００５６】
以上の図１０の処理の詳細が、図１１に示されている。図１０のステップＳ５１の処理の詳細は、図１１にステップＳ７１乃至ステップＳ７６の処理として表されており、図１０のステップＳ５２の処理の詳細は、図１１にステップＳ８１の処理として表されており、図１０のステップＳ５３の処理の詳細は、図１１においてステップＳ９１乃至ステップＳ９３の処理として表されており、図１０のステップＳ５４の処理の詳細は、図１１においてステップＳ１０１の処理として表されており、図１０のステップＳ５５の処理の詳細は、図１１においてステップＳ１１１乃至ステップＳ１１３の処理として表されている。
【００５７】
ステップＳ７１において、第１の計算部８１は、入力部７１より入力された点列を読み込む。即ち、図９に示されるような、任意に配置された複数の点１１１ｉの座標データが読み込まれる。
【００５８】
ステップＳ７２において、第１の計算部８１は、凸図形計算部７４を制御し、ステップＳ７１において読み込んだ複数の点１１１ｉからなる点列が２次元空間に配置された場合、その点列の各点の座標データに基づいて、点列の一部の点を頂点とし、点列の全ての点を包含する最小の凸多角形を算出する。ステップＳ７１において読み込んだ複数の点１１１ｉからなる点列が３次元空間に配置された場合、第１の計算部８１は、凸図形計算部７４を制御し、点列の一部の点を頂点とし、点列の全ての点を包含する最小の凸多面体を算出する。すなわち、凸図形計算部７４は、最遠点対計算部７３の第１の計算部８１の制御に基づいて、ｎ次元の空間に任意に配置された複数の点１１１ｉの一部の点を頂点とし、複数の点１１１ｉを全て包含するｎ次元の最小の凸図形を算出する。
【００５９】
最遠点対計算部７３の第２の計算部８２乃至第５の計算部８５は、このように算出された凸多角形（凸図形）の頂点を処理の対象とし、この頂点により構成される点対の中から最遠点対を求める。上述したように、最遠点対は、点列の中で距離が最も離れた２点により構成される。すなわち、この点列を包含する最小の凸多角形において、この最遠点対間の距離より大きな距離を有する点対は存在しない。従って、最遠点対は必ず凸多角形の頂点の２点により構成されることになるので、ステップＳ７２の処理を行うことにより、第２の計算部８２乃至第５の計算部８５は、処理の対象とする点を限定することができるので、最遠点対を求める処理による負荷を軽減させることができる。
【００６０】
なお、このステップＳ７２の処理は、以下の処理において計算量をさらに軽減させるものであり必須ではないので、省略されるようにしてもよい。その場合、第２の計算部８２乃至第５の計算部８５は、複数の点１１１ｉによる全ての点対を対象として以下の処理を行う。
【００６１】
ステップＳ７２の処理を終了した第１の計算部８１は、ステップＳ７３において、各軸に沿って、点列より最大または最小となる点を選択し、それらの点に基づいて、セルを生成する。
【００６２】
図１２は、２次元空間に配置された点列に対して、セルを生成する様子の例を示す図である。
【００６３】
図１２において、点１３１乃至点１３４は、ｘ−ｙ平面に配置された複数の点から、ステップＳ７３の処理により抽出されたｘ座標またはｙ座標が最大または最小の点である。すなわち、点１３１は、処理の対象となる複数の点の内、ｙ座標が最小の点であり、点１３２は、処理の対象となる複数の点の内、ｘ座標が最大の点であり、点１３３は、処理の対象となる複数の点の内、ｙ座標が最大の点であり、点１３４は、処理の対象となる複数の点の内、ｘ座標が最小の点である。
【００６４】
ステップＳ７３の処理において、さらに、ｘ軸に平行な２辺、およびｙ軸に平行な２辺からなる４辺形であり、抽出された４点を包含する最小の４辺形で囲まれた領域１４０において、各辺を２等分することによって領域１４０を４分割した４つの領域であるセル１４１乃至セル１４４が生成される。図１２に示されるように、領域１４０は、点１３１および点１３３のｙ座標、並びに、点１３２および点１３４のｘ座標を境界とする領域であり、各辺がｘ軸またはｙ軸に平行な４角形に囲まれた領域である。また、セル１４１は、領域１４０の各境界線を２等分することにより、領域１４０を４等分した４つの領域の内、図中、右上の領域（ｘ座標およびｙ座標がともに大きい領域）であり、セル１４２は、図中、左上の領域（ｘ座標が小さく、ｙ座標が大きい領域）であり、セル１４３は、図中、左下の領域（ｘ座標およびｙ座標がともに小さい領域）であり、セル１４４は、図中、右下の領域（ｘ座標が大きく、ｙ座標が小さい領域）である。
【００６５】
図１１に戻り、図１２に示されるようにセルを生成した第１の計算部８１は、ステップＳ７４において、処理の対象となる複数の点を、その点の存在位置に基づいて、各セルに登録する。すなわち、第１の計算部８１は、図１２において、セル１４１に存在する点はセル１４１に関連付けて登録し、セル１４２に存在する点はセル１４２に関連付けて登録し、セル１４３に存在する点はセル１４３に関連付けて登録し、セル１４４に存在する点はセル１４４に関連付けて登録する。
【００６６】
点を各セルに登録した第１の計算部８１は、ステップＳ７５において、セルを生成した領域の境界点となる２つの点からなる境界点対の内、距離が最大となる境界点対を最遠点対（Ｂ１，Ｂ２）の初期値に設定し、ステップＳ７６において、最遠点対に設定された点Ｂ１と点Ｂ２との距離を変数Ｄに代入する。図１２の場合、点１３１乃至点１３４は、処理の対象となる複数の点を包含する領域１４０の境界点となる。従って、第１の計算部８１は、この場合、点１３１乃至点１３４を用いて６個の点対を設定し、これらの点対の２点間の距離を算出し、それらの点対の中で距離が最大となる点対を最遠点対（Ｂ１，Ｂ２）の初期値に設定し、その値を変数Ｄに代入する。
【００６７】
処理の対象となる複数の点において、ｘ座標が最大の点と最小の点からなる点対は、少なくともｘ座標に関して最も離れた点対であり、同様に、ｙ座標が最大の点と最小の点は、少なくともｙ座標に関して最も離れた点対である。従って、これらの点からなる点対は、目的とする最遠点対の有力な候補となる。そこで、第１の計算部８１は、ステップＳ７５およびＳ７６の処理によって、これらの点対の内、距離が最大となる点対を最遠点対の初期値とし、後述する処理に用いられる変数Ｄにその値を代入することにより、後段の処理を効率よく実行できるようにしている。
【００６８】
次に、ステップＳ８１において、第２の計算部８２は、探索エリア対生成処理を実行し、最遠点対を効率よく探索するために、探索処理の対象とされる点対を構成する点が存在するエリアである探索エリアの対を生成する。探索エリア対生成処理の詳細については、図１３のフローチャートを参照して後述する。
【００６９】
次に、ステップＳ９１において、第３の計算部８３は、探索エリア対取得処理を実行し、ステップＳ８１の処理により生成された探索エリア対の中から、最遠点対が存在しうる探索エリア対を選択し取得する。探索エリア対取得処理の詳細については、図２１のフローチャートを参照して後述する。この処理を行うことにより、最遠点対計算部７３は、最遠点対が明らかに存在しない探索エリア対を処理の対象から外すことができ、後段における最遠点対を探索する処理を効率よく実行することができる。ステップＳ９１の処理を終了した第３の計算部８３は、ステップＳ９２において、未処理の探索エリア対が存在するか否かを判定する。後段の最遠点対を探索する処理を実行していない探索エリア対が存在しないと判定した場合、第３の計算部８３は、ステップＳ９３に処理を進め、現在変数Ｄの値に対応する点対を最遠点対と決定し、その点対を構成する点Ｂ１および点Ｂ２に関する情報を出力して他の処理で使用できるような状態にし、最遠点対決定処理を終了する。
【００７０】
また、ステップＳ９２において、未処理の探索エリア対が存在すると判定した場合、第３の計算部８３は、処理をステップＳ１０１に進め、その未処理の探索エリア対に対する処理を行うように、最遠点対決定処理を続ける。
【００７１】
次に、第４の計算部８４は、ステップＳ１０１において、探索エリア対内最遠点対取得処理を実行し、未処理の探索エリア対の中の１つの探索エリア対に注目し、その探索エリア対に含まれる点対についてそれぞれ距離を算出し、それらの距離を比較して、最も距離が大きい点対、すなわち、その探索エリア対内における最遠点対を探索エリア対内最遠点対（ｂ１，ｂ２）として決定し取得する。
【００７２】
次に、第５の計算部８５は、ステップＳ１１１において、その取得した点対を構成する点ｂ１および点ｂ２の距離を変数ｄに代入し、ステップＳ１１２において、変数ｄの値が変数Ｄの値より大きいか否かを判定し、変数ｄの値の方が大きいと判定した場合、ステップＳ１１３において、変数ｄの値を変数Ｄに代入した後、ステップＳ９２に処理を戻し、それ以降の処理を繰り返す。また、ステップＳ１１２において、変数Ｄの値の方が大きいと判定した場合、第５の計算部８５は、ステップＳ１１３の処理を省略し、変数Ｄの値を変更せずに、ステップＳ９２に処理を戻し、それ以降の処理を繰り返す。
【００７３】
以上のようにして最遠点対を決定することにより、画像処理装置６１は、最遠点対となり得ないと判断できる不要な点に関する処理を省略し、効率よく最遠点対を決定することができ、任意の点列における最遠点対を容易に求めることができる。
【００７４】
次に、図１１のステップＳ８１において実行される探索エリア対生成処理について、図１３のフローチャートを参照して説明する。
【００７５】
最初に、ステップＳ１３１において、最遠点対計算部７３の第２の計算部８２は、図１１のステップＳ７３の処理において第１の計算部８１が生成したセルより２つのセルを探索エリアとして抽出し、その抽出された２つのセルを用いて、探索エリアの対である探索エリア対を作成する。第２の計算部８２は、この処理を繰り返し、生成されたセルを用いて全ての探索エリア対を作成する。すなわち、第２の計算部８２は、生成された複数のセルの中から、全ての組み合わせで２つのセルを抽出し、探索エリア対を生成する。その際、第２の計算部８２は、セルの配置パターンによりクラスとして探索エリア対を分類し、各クラスに属する探索エリア対を作成する。探索エリアは、後段の処理において最遠点対計算部７３が最遠点対（最遠点対を構成する点）を探索する領域である。最遠点対計算部７３は、この探索エリア内に存在する点により構成される点対の距離を算出し、最遠点対を求める。その際、最遠点対計算部７３は、２つの探索エリア内にそれぞれ存在する２点により構成される点対の距離を算出する。すなわち、最遠点対計算部７３は、２つの探索エリアに跨る点対を処理の対象とする。従って、第２の計算部８２は、ステップＳ７３の処理において生成されたセルより２つのセルを探索エリアとして任意に抽出し、探索エリア対を生成する。
【００７６】
図１２の場合、４つのセルが生成されており、２つのセルの組み合わせは６通り存在する。従って、第２の計算部８２は、６つの探索エリア対を生成する。後述するように、探索エリア対は、その探索エリア対を構成するセルの配置パターンによって最遠点対の探索方法が異なる。従って、第２の計算部８２は、探索エリア対をそのセルの配置パターンによってクラスとして分類し、各クラスに属する探索エリア対を作成する。なお、探索エリア対は、ｎ次元に配置された複数の点に対してｎ個のクラスに分類することができる。図１２の場合、探索エリア対は、後述するように、２つのクラスに分類することができる。
【００７７】
探索エリア対を生成した第２の計算部８２は、ステップＳ１３２に処理を進め、探索エリア対毎に最大長を算出する。探索エリア対の最大長とは、探索エリア対において、点対が取り得る最も遠い距離のことである。この最大長は、後段の処理においてその探索エリア対を処理の対象とするか否かを判断するのに用いられる。
【００７８】
探索エリア対の最大長を算出した第２の計算部８２は、ステップＳ１３３に処理を進め、作成した探索エリア対を最大長によってソートし、その順番でスタックに保存する。探索エリア対をスタックに保存した第２の計算部８２は、探索エリア対生成処理を終了する。
【００７９】
以上の探索エリア対生成処理の具体的な例を、図１４乃至図２０を参照して説明する。なお、ここでは、図１２に示されるように、２次元空間に配置された複数の点に対する処理について説明する。
【００８０】
まず、図１４乃至図１６を参照して、クラス１に属する探索エリア対について説明する。
【００８１】
クラス１に属する探索エリア対は、図１４に示されるように、図１２の４つのセルの内、領域１４０の対角の位置に存在するセル（例えば、図中斜線で示されるセル１４２およびセル１４４）により構成される。図１４の場合、最遠点対の探索順序は、２つのセル間で互いに逆向きとなるように、図中上の探索エリアにおいては、点１６１から点１６２に向かって行われ、図中下の探索エリアにおいては、点１６３から点１６４に向かって行われる。また、この探索エリア対において、領域１４０の対角線となる線分の距離（点１６２と点１６４からなる点対の距離）が、この探索エリア対の最大長となる。
【００８２】
図１２のように作成されたセルにおいて、このようなクラス１に属する探索エリア対のパターンは、図１５の領域１４０−１に示されるように、セル１４２とセル１４４からなる場合と、領域１４０−２のようにセル１４１とセル１４３からなる場合の２通りある。
【００８３】
上述したように、最遠点対の探索は、距離が近いと想定される点対より開始され、距離が遠いと想定される点対の方向に進められる。すなわち、セル１４２とセル１４４からなるクラス１に属する探索エリア対の場合、図１６に示されるように、点対１８１から距離の算出が開始され、その次に点対１８２、その次に点対１８３のように、点対の距離の算出が行われ、探索エリア対内最遠点対の探索が、斜め方向に進められる。
【００８４】
次に、図１７乃至図１９を参照して、クラス２に属する探索エリア対について説明する。
【００８５】
クラス２に属する探索エリア対は、図１７に示されるように、図１２の４つのセル（領域２００を４等分したセル２０１乃至２０４）の内、隣り合う位置に存在するセル（例えば、図中斜線で示されるセル２０２および２０３）により構成される。図１７の場合、最遠点対の探索順序は、２つのセル間において互いに同じ向きとなるように、図中上の探索エリアにおいては、点２１１から点２１２に向かって行われ、図中下の探索エリアにおいても、同様に点２１３から点２１４に向かって行われる。また、この探索エリア対の対角線となる線分の距離（点２１２と点２１３からなる点対の距離、または点２１１と点２１４からなる点対の距離）の遠い方が、この探索エリア対の最大長となる。
【００８６】
図１２のように作成されたセルにおいて、このようなクラス２に属する探索エリア対は、図１８の領域２００−１に示されるように、セル２０２とセル２０３からなる場合と、領域２００−２のようにセル２０１とセル２０２からなる場合と、領域２００−３のようにセル２０１とセル２０４からなる場合と、領域２００−４のようにセル２０３とセル２０４からなる場合の４通りある。
【００８７】
上述したように、最遠点対の探索は、距離が近いと想定される点対より開始され、距離が遠いと想定される点対の方向に進められる。すなわち、図１９において示されるような、セル２０２とセル２０３からなるクラス２に属する探索エリア対の場合、図１９に示されるように、点対２３１から距離の算出が開始され、その次に点対２３２、その次に点対２３３のように、点対の距離の算出が行われ、探索エリア対内最遠点対の探索が、這うように進められる。
【００８８】
このような探索エリア対に関する情報は、図２０に示されるような構造体のデータとして生成される。図２０に示されるように、この構造体２４０は、探索エリア対を構成する２つのセルのエリア番号（領域内におけるセルの位置を示す番号）を登録するエリア番号２４１およびエリア番号２４２、その探索エリア対の最大長を登録する最大長２４３、並びに、探索パターンのタイプを登録するパターンタイプ２４４により構成される。なお、探索パターンは、図１６および図１９を参照して説明したように、探索エリア対が属するクラスによって決定される。
【００８９】
このような構造体２４０は、図１３のステップＳ１３３の処理により、最大長でソートされ、クラス毎にスタックに保存される。
【００９０】
クラスは、探索エリア対を構成するセルの配置パターンによる分類であるが、換言すると、探索エリア対の最大長による分類である。例えば、図１４に示されるクラス１に属する探索エリア対の最大長は、図１７に示されるクラス２に属する探索エリア対の最大長より大きい。従って、構造体２４０は、探索エリア対の最大長によって分類されたクラスにおいて、さらに、その最大長に基づいてソートされて、スタックに保存される。
【００９１】
このように生成されスタックに保存された探索エリア対に関する情報は、図１１のステップＳ９１の処理により、最遠点対が存在しうる探索エリア対が選択されて読み出される。
【００９２】
次に、図１１のステップＳ９１において実行される探索エリア対取得処理の詳細について、図２１のフローチャートを参照して説明する。
【００９３】
最初に、第３の計算部８３は、ステップＳ１５１において、クラス毎に取得処理を行うために、まず、クラス１の探索エリア対のスタックを取得し、ステップＳ１５２において、初期設定として、処理の対象となるクラス番号を示す変数ｃの値を「１」に設定する。
【００９４】
次に、ステップＳ１５３において、第３の計算部８３は、図１１のステップＳ７６において、第１の計算部８１により設定された点対の距離である変数Ｄの初期値を取得する。変数Ｄは、その時点で最も２点間の距離が遠い点対、すなわち、最遠点対の候補（最有力候補）となる点対の距離の値を保持する変数である。第３の計算部８３は、最遠点対の最有力候補の距離の値を取得するとステップＳ１５４に処理を進める。
【００９５】
ステップＳ１５４において、第３の計算部８３は、取得したクラスｃのスタックが空であるか否かを判定する。すなわち、第３の計算部８３は、処理の対象として注目されるクラスのスタックに、未処理の探索エリア対（探索エリア対を示す構造体）が存在するか否かを判定する。
【００９６】
スタックが空であると判定した場合、第３の計算部８３は、処理をステップＳ１５５に進め、変数ｃの値が、処理の対象としている複数の点が配置された空間の次元数より小さいか否かを判定する。変数ｃの値が次元数より小さいと判定した場合、第３の計算部８３は、未処理のクラスが存在すると判定し、処理をステップＳ１５６に進め、変数ｃの値に「１」を加算する。そして、ステップＳ１５７において、第３の計算部８３は、クラスｃの探索エリア対のスタックを新たに取得し、処理をステップＳ１５８に進める。
【００９７】
なお、ステップＳ１５４において、スタックが空ではないと判定した場合、第３の計算部８３は、ステップＳ１５５乃至ステップＳ１５７の処理を省略し、ステップＳ１５８に処理を進める。
【００９８】
ステップＳ１５８において、第３の計算部８３は、スタックより１つの探索エリア対Ａ保存時にソートされた順番、すなわち、最大長が大きい順で取り出す。
【００９９】
探索エリア対Ａを取り出した第３の計算部８３は、ステップＳ１５９に処理を進め、探索エリア対Ａの最大長が変数Ｄの値より大きいか否かを判定し、大きいと判定した場合、ステップＳ１６０に処理を進め、その探索エリア対を他の処理により使用できるような状態に出力する。
【０１００】
すなわち、第３の計算部８３は、生成された探索エリア対の内、最大長が変数Ｄの値より大きい探索エリア対、すなわち、変数Ｄの値より大きな距離の点対が存在する可能性のある探索エリア対のみを最遠点対決定処理の後段の処理において使用できるよう出力する。
【０１０１】
ステップＳ１６０の処理を終了した第３の計算部８３は、ステップＳ１５３に処理を戻し、それ以降の処理を繰り返す。
【０１０２】
また、ステップＳ１５５において、変数ｃの値が次元数より小さくないと判定した場合、第３の計算部８３は、全てのクラスについて、処理を行ったと判定し、探索エリア対取得処理を終了する。
【０１０３】
さらに、ステップＳ１５９において、探索エリア対Ａの最大長が変数Ｄの値より大きくないと判定した場合、第３の計算部８３は、それ以降の探索エリア対に最遠点対が存在しないと判定し、探索エリア対取得処理を終了する。
【０１０４】
すなわち、第３の計算部８３は、ステップＳ１５３乃至ステップＳ１６０の処理を繰り返し、第２の計算部８２により作成された全ての探索エリア対に対して、その最大長が変数Ｄの値より大きいか否かを判定する。その際、第３の計算部８３は、探索エリア対のクラス毎に処理を行い、各クラスの全ての探索エリア対の最大長を変数Ｄと比較すると、ステップＳ１５５乃至１５７の処理を行い、処理の対象を次のクラスに変更する。
【０１０５】
そして、ステップＳ１５５において、全てのクラスについて、処理したと判定した場合、または、ステップＳ１５９において、最大長の大きい方から変数Ｄと比較していった結果、処理対象の探索エリア対の最大長が変数Ｄより小さくなって、それ以降の探索エリア対に変数Ｄより大きい距離の点対が存在しないと判定した場合、第３の計算部８３は、探索エリア対取得処理を終了する。
【０１０６】
以上のようにすることにより、画像処理装置６１は、最遠点対決定処理の対象となる探索エリア対を効率よく削減することができ、処理の負荷を軽減させることができる。
【０１０７】
次に、図１１のステップＳ１０１において、実行される探索エリア対内最遠点対取得処理における、探索エリア対内最遠点対の具体的な探索手順の例について、図２２乃至図２７を参照して説明する。なお、ここでは、図１２に示されるように、２次元空間に配置された複数の点に対する処理について説明する。
【０１０８】
図１２のセル１４１およびセル１４３を探索エリア対とし、セル１４１から探索を開始する場合（クラス１に属する探索エリア対において探索エリア対内最遠点対の探索を行う場合）、図２２に示されるように、探索を開始する点対である開始軸が設定される。
【０１０９】
セル１４１において、最遠点対を構成する点の探索は、図２２に示される点２５１から開始される。図２２において、点２５１は、領域１４０の境界線上の、セル１４１とセル１４２が接する点に位置する点であり、点２５２は、領域１４０の境界線上の、セル１４３とセル１４４が接する点に位置する点であり、点２５３は、領域１４０の境界線上の、セル１４１とセル１４４が接する点に位置する点であり、点２５４は、領域１４０の境界線上の、セル１４２とセル１４３が接する点に位置する点である。
【０１１０】
すなわち、図２２に示される探索エリア対の上側のセルであるセル１４１において、最遠点対を構成する点の探索は、点２５１のように、セル１４１に存在する点の内、図中最も左上に位置する点から開始され、ｘ座標の小さい点から大きい点に向かって順に進められる。逆に、図２２に示される探索エリア対の下側のセルであるセル１４３において、最遠点対を構成する点の探索は、点２５２のように、セル１４３に存在する点の内、図中最も右下に位置する点から開始され、ｘ座標の大きい点から小さい点に向かって順に進められる。このとき、セル１４１から探索を開始するために、点２５２が初期固定点とされ、点２５１が初期可動点とされ、点２５１および点２５２を両端とする線分が、探索処理の開始軸２５０とされる。
【０１１１】
開始軸２５０が設定されると、可動点側であるセル１４１において、点２５２との距離が点２５１より大きい点が、ｘ座標の小さい点から大きい点に向かって検索される。なお、図２２の場合、セル１４１の点２５１よりｘ座標が大きい領域において、点２５１と点２５３を両端とする線分より下側の部分（ｙ座標が小さい領域）に存在する点は、明らかに、点２５１より点２５２に近いので、第４の計算部８４は、その線分の上側（点２５１よりｘ座標が大きく、かつ、その線分よりｙ座標が大きい領域）に位置する部分に存在する点のみを検索の対象とすればよい。
【０１１２】
さらに検索する領域を絞り込む場合、図２２に示されるように、点２５２との距離が点２５１より大きい点は、点２５２を中心とし、開始軸２５０を半径とする円の外側の領域２６０に位置する。従って、第４の計算部８４は、この領域２６０において、検索を行えばよい。このようにして、領域２６０に存在する点２６１が最初に検索され、新たな軸２６２が得られる。
【０１１３】
次に、第４の計算部８４は、図２３に示されるように、セル１４３において点２６１との距離が点２５２より大きい点を検索する。すなわち、今度は、点２６１が固定点とされ、点２５２が可動点とされ、可動点側であるセル１４３において、点２６１との距離が点２５２より大きい点が、ｘ座標の大きい点から小さい点に向かって検索される。なお、図２３の場合、セル１４３の点２５２よりｘ座標が小さい領域において、点２５２と点２５４を両端とする線分より上側の部分（ｙ座標が大きい領域）に存在する点は、明らかに、点２５２より点２６１に近いので、第４の計算部８４は、その線分下側（点２５２よりｘ座標が小さく、かつ、その線分よりｙ座標が小さい領域）に位置する部分に存在する点のみを検索の対象とすればよい。
【０１１４】
さらに検索する領域を絞り込む場合、図２３に示されるように、点２６１との距離が点２５２より大きい点は、点２６１を中心とし、軸２６２を半径とする円の外側の領域２７０に位置する。従って、第４の計算部８４は、この領域２７０において、検索を行えばよい。このようにして、領域２７０に存在する点２７１が最初に検索され、新たな軸２７２が得られる。
【０１１５】
次に、第４の計算部８４は、図２４に示されるように、セル１４１において点２７１との距離が点２６１より大きい点を検索する。すなわち、今度は、点２７１が固定点とされ、点２６１が可動点とされ、可動点側であるセル１４１において、点２７１との距離が点２６１より大きい点が、ｘ座標の小さい点から大きい点に向かって検索される。なお、図２４の場合、セル１４１の点２６１よりｘ座標が大きい領域において、点２６１と点２５３を両端とする線分より下側の部分（ｙ座標が小さい領域）に存在する点は、明らかに、点２６１より点２７１に近いので、第４の計算部８４は、その線分の上側（点２６１よりｘ座標が大きく、かつ、その線分よりｙ座標が大きい領域）に位置する部分に存在する点のみを検索の対象とすればよい。
【０１１６】
さらに検索する領域を絞り込む場合、図２４に示されるように、点２７１との距離が点２６１より大きい点は、点２７１を中心とし、軸２７２を半径とする円の外側の領域２８０に位置する。従って、第４の計算部８４は、この領域２８０において、検索を行えばよい。このようにして、領域２８０に存在する点２８１が最初に検索され、新たな軸２８２が得られる。
【０１１７】
次に、第４の計算部８４は、図２５に示されるように、セル１４３において点２８１との距離が点２７１より大きい点を検索する。すなわち、今度は、点２８１が固定点とされ、点２７１が可動点とされ、可動点側であるセル１４３において、点２８１との距離が点２７１より大きい点が、ｘ座標の大きい点から小さい点に向かって検索される。なお、図２５の場合、セル１４３の点２７１よりｘ座標が小さい領域において、点２７１と点２５４を両端とする線分２９１より上側の部分（ｙ座標が大きい領域）に存在する点は、明らかに、点２７１より点２８１に近いので、第４の計算部８４は、その線分２９１の下側（点２７１よりｘ座標が小さく、かつ、その線分２９１よりｙ座標が小さい領域）に位置する部分に存在する点のみを検索の対象とすればよい。
【０１１８】
さらに検索する領域を絞り込む場合、図２５に示されるように、点２８１との距離が点２７１より大きい点は、点２８１を中心とし、軸２８２を半径とする円の外側の領域に位置する。従って、第４の計算部８４は、上述したように、点２７１よりｘ座標が小さく、かつ、その線分２９１よりｙ座標が小さい領域と、この領域が重なる領域２９２において、検索を行えばよい。なお、このように検索を行い、例えば、領域２９２において、新たな点が検索されなかった場合、第４の計算部８４は、軸２８２を探索エリア対内最遠点対とし、この探索エリア対に対する探索エリア対内最遠点対の探索処理を終了し、次のクラス１に属する探索エリア対に対する処理を開始する。
【０１１９】
そして、クラス１に属する探索エリア対における探索エリア対内最遠点対の探索が終了すると、第４の計算部８４は、上述したように、次にクラス２に属する探索エリア対における探索エリア対内最遠点対の探索を開始する。
【０１２０】
図１２のセル１４１およびセル１４４を探索エリア対とし、セル１４１から探索を開始する場合（クラス２に属する探索エリア対において探索エリア対内最遠点対の探索を行う場合）、最初の処理は、図２２に説明した場合と同様であるので、その説明は省略する。すなわち、セル１４１において、点２６１が検索され、軸２６２が得られる。
【０１２１】
この状態（図２２の状態）から、第４の計算部８４は、次に、図２６に示されるように、セル１４４において点２６１との距離が点２５２より大きい点を検索する。すなわち、今度は、点２６１が固定点とされ、点２５２が可動点とされ、可動点側であるセル１４４において、点２６１との距離が点２５２より大きい点が、セル１４１の場合と同様に、ｘ座標の小さい点から大きい点に向かって検索される。なお、図２６の場合、セル１４４の点２５２よりｘ座標が大きい領域において、点２５２と点２５３を両端とする線分より上側の部分（ｙ座標が大きい領域）に存在する点は、明らかに、点２５２より点２６１に近いので、第４の計算部８４は、その線分下側（点２５２よりｘ座標が大きく、かつ、その線分よりｙ座標が小さい領域）に位置する部分に存在する点のみを検索の対象とすればよい。
【０１２２】
さらに検索する領域を絞り込む場合、図２６に示されるように、点２６１との距離が点２５２より大きい点は、点２６１を中心とし、軸２６２を半径とする円の外側の領域３１０に位置する。従って、第４の計算部８４は、この領域３１０において、検索を行えばよい。このようにして、領域３１０に存在する点３１１が最初に検索され、新たな軸３１２が得られる。
【０１２３】
次に、第４の計算部８４は、図２７に示されるように、セル１４１において点３１１との距離が点２６１より大きい点を検索する。すなわち、今度は、点３１１が固定点とされ、点２６１が可動点とされ、可動点側であるセル１４１において、点３１１との距離が点２６１より大きい点が、ｘ座標の小さい点から大きい点に向かって検索される。
【０１２４】
このとき、第４の計算部８４は、まず、点２６１と点３１１とのｘ座標の値の差３２１を算出し、点２６１と同じｙ座標上の、ｘ軸方向において点３１１から見て点２６１と反対側の位置に存在し、点３１１とのｘ座標の値の差３２２が差３２１と同じ大きさとなる点を求める。そしてこの点が領域１４０の外側に存在する場合、この探索エリア対において点２６１と点３１１からなる点対より距離が大きい点対が存在しないので、第４の計算部８４は、この探索エリア対に対する探索エリア対内最遠点対取得処理を終了し、次のクラス２に属する探索エリア対に対する処理を開始する。
【０１２５】
なお、上述した点が、領域１４０内に存在する場合、第４の計算部８４は、この探索エリア対に対する処理を続ける。
【０１２６】
以上のようにして、クラス２に属する探索エリア対における探索エリア対内最遠点対の探索が繰り返され、全ての探索エリア対に対する処理が終了すると、第４の計算部８４は、探索エリア対内最遠点対取得処理を終了する。
【０１２７】
以上のように、探索エリア対の２つのセルにおいて交互に点が検索され、探索エリア対内最遠点対が求められる。このようにして求められた探索エリア対内最遠点対は、第５の計算部８５により、図１１のステップＳ１１１乃至ステップＳ１１３の処理に利用される。すなわち、以上のようにして求められた探索エリア対内最遠点対は、その距離を変数Ｄの値と比較され、今回求められた探索エリア対内最遠点対の距離の方が大きい場合、その値が変数Ｄに新たに代入される。換言すると、その場合、今回求められた探索エリア対内最遠点対が、新たな最遠点対の候補とされる。そして、新たな値が代入された変数Ｄは、次に求められる他の探索エリア対内最遠点対の距離との比較に用いられる。すなわち、最遠点対計算部７３は、以上のように、全ての有効な（最遠点対が存在する可能性のある）探索エリア対に対して、探索エリア対内最遠点対を求めてその距離をその時点の最遠点対の候補の距離と比較する処理を繰り返すことにより、最遠点対を算出する。
【０１２８】
以上のように処理を行うことにより、画像処理装置６１は、２次元に存在する点集合における最遠点対を容易に算出することができる。
【０１２９】
次に、３次元に配置された点集合における最遠点対の決定方法について説明する。２次元の場合と同様に、最遠点対計算部７３は、図１１の最遠点対決定処理を実行し、最遠点対を決定する。すなわち、最遠点対計算部７３の第１の計算部８１は、図１１のステップＳ７１の処理において、入力部７１より入力された点列を読み込み、ステップＳ７２において、凸図形計算部７４を制御し、点列の各点の座標データに基づいて、点列の一部の点を頂点とし、点列の全ての点を包含する最小の凸多面体を算出する。
【０１３０】
図２８は、３次元空間に配置された点列に対して、セルを生成する様子の例を示す図であり、２次元空間の場合の図１２に対応する図である。第１の計算部８１は、図１１のステップＳ７３の処理において、ステップＳ７１において読み込んだ複数の点の中から、３次元空間（ｘ−ｙ−ｚ空間）の各軸に沿って、座標が最大または最小となる点を選択し、それらの点に基づいて、図２８に示されるようなセルを生成する。図２８において、点４０１乃至点４０６は、ｘ−ｙーｚ空間に配置された複数の点から、ステップＳ７３の処理により抽出されたｘ座標、ｙ座標、またはｚ座標が最大または最小の点である。すなわち、処理の対象となる複数の点の内、点４０１はｚ座標が最小の点であり、点４０２はｘ座標が最大の点であり、点４０３はｚ座標が最大の点であり、点４０４はｘ座標が最小の点であり、点４０５はｙ座標が最小の点であり、点４０６はｙ座標が最大の点である。
【０１３１】
このとき、図２８に示されるように、ステップＳ７３の処理において、さらに、ｘ軸に平行な２平面、ｙ軸に平行な２平面、およびｚ軸に平行な２平面からなる直方体であり、抽出された６点を包含する最小の直方体で囲まれた領域４００において、領域４００の直方体の各辺を２等分する点を結び、直方体の各面を縦横に４等分するように領域４００を８等分した８つの直方体の領域であるセル４１１乃至セル４１８が生成される。図２８に示されるように、領域４００は、点４０１および点４０３のｚ座標、点４０２および点４０４のｘ座標、並びに点４０５および点４０６のｙ座標を境界とする領域であり、各辺がｘ軸またはｙ軸に平行な４角形（境界面）に囲まれた領域である。また、セル４１１は、領域４００の各境界面を縦横に４等分するように領域４００を８等分した８つの領域の内、図中、左上手前の領域（ｘ座標およびｙ座標がともに小さく、ｚ座標が大きい領域）であり、セル４１２は、図中、右上手前の領域（ｙ座標が小さく、ｚ座標およびｘ座標がともに大きい領域）であり、セル４１３は、図中、右上奥の領域（ｘ座標、ｙ座標、およびｚ座標が全て大きい領域）であり、セル４１４は、図中、左上奥の領域（ｘ座標が小さく、ｙ座標およびｚ座標がともに大きい領域）であり、セル４１５は、図中、左下手前の領域（ｘ座標、ｙ座標、およびｚ座標が全て小さい領域）であり、セル４１６は、図中、右下手前の領域（ｘ座標が大きく、ｙ座標およびｚ座標がともに小さい領域）であり、セル４１７は、図中、右下奥の領域（ｘ座標およびｙ座標がともに大きく、ｚ座標が小さい領域）であり、セル４１８は、図中、左下奥の領域（ｙ座標が大きく、ｚ座標およびｘ座標がともに小さい領域）である。
【０１３２】
なお、境界点４０１乃至４０６のいずれかが重合を起こす場合、該当する探索エリアが体積を持たなくなり、これを用いた探索エリア対は生成されなくなる。
【０１３３】
以上のようにして生成されたセル４１１乃至セル４１８に、第１の計算部８１は、図１１のステップＳ７４の処理において、処理の対象となる複数の点を、その点の存在位置に基づいて登録する。
【０１３４】
３次元に配置された複数の点を登録する場合、登録される点は、図２９に示されるように、ベクトルの内積を用いてその存在位置を判定され、その位置に対応するセルに登録される。
【０１３５】
図２９に示されるように、セル４１１乃至セル４１８は、ｘ軸、ｙ軸、またはｚ軸に垂直な平面であり、それぞれが領域４００を２等分する平面である平面４２１乃至平面４２３により領域４００を分割した領域であるので、例えば、ある点Ｐをセル４１１に登録するか否かは、平面４２１乃至平面４２３の各平面について、それぞれ、平面上の点から点Ｐに向かうベクトルと、その平面の法線ベクトルの内積の符号に基づいて、判断することができる。
【０１３６】
例えば、点Ｐがセル４１１内に存在する場合、平面４２１上の点から点Ｐに向かうベクトルと、ｘ軸と垂直な平面４２１の、ｘ軸と逆向きに向かう法線ベクトルとの内積の符号は正となる。また、平面４２２上の点から点Ｐに向かうベクトルと、ｙ軸と垂直な平面４２１の、ｙ軸と逆向きに向かう法線ベクトルとの内積の符号も正となる。さらに、平面４２１上の点から点Ｐに向かうベクトルと、ｚ軸と垂直な平面４２３の、ｚ軸と同じ向きに向かう法線ベクトルとの内積の符号も正となる。このように、平面４２１乃至平面４２３の法線ベクトルを利用して、点Ｐがどの領域に存在するかを識別することができる。
【０１３７】
各点が各セルに登録されると、第１の計算部８１は、図１１のステップＳ７５において、領域４００の境界点となる点４０１乃至点４０６を用いて点対を生成し、その点対の内、距離が最大となる点対（Ｂ１，Ｂ２）を最遠点対の初期値に設定し、ステップＳ７６において、最遠点対に設定された点Ｂ１と点Ｂ２との距離を変数Ｄに代入する。
【０１３８】
次に、ステップＳ８１において、第２の計算部８２は、図１３のフローチャートのように探索エリア対生成処理を実行し、最遠点対を効率よく探索するために、探索処理の対象とされる点対を構成する点が存在するエリアである探索エリアの対を生成する。
【０１３９】
すなわち、第２の計算部８２は、２次元の場合と同様に、ステップＳ１３１において、セルの配置パターンによりクラスとして探索エリア対を分類し、各クラスに属する探索エリア対を作成し、ステップＳ１３２において、探索エリア対毎に最大長を算出し、ステップＳ１３３において、作成した探索エリア対を最大長によってソートし、その順番でスタックに保存する。３次元の場合、第２の計算部８２は、探索エリア対を以下の３つのクラスに分類して作成する。
【０１４０】
まず、図３０乃至図３２を参照して、クラス１に属する探索エリア対について説明する。
【０１４１】
クラス１に属する探索エリア対は、図３０Ａに示されるように、図２８の４つのセルの内、領域４００の対角の位置に存在するセル（例えば、図中斜線で示されるセル４１１および４１７）により構成される。このようなクラス１に属する探索エリア対のパターンは、図３０Ｂに示される領域４００−１乃至領域４００−４のように、各セルの位置関係により４通りある。
【０１４２】
このクラス１に属する探索エリア対の最大長は、図３１に示されるように、領域４００の対角線となる線分の距離となる。すなわち、例えば、図３０Ａに示されるセル４１１およびセル４１４により構成される探索エリア対において、図３１の点Ｂ１と点Ｈ２を端点とする線分４３１が、この探索エリア対の最大長となる。
【０１４３】
最遠点対の探索は、距離が近いと想定される点対より開始され、距離が遠いと想定される点対の方向に進められる。すなわち、図３０Ａの探索エリア対の場合、図３２に示されるように、点対４４１から距離の算出が開始され、その次に点対４４２、その次に点対４４３のように、点対の距離が長くなるように、各セルにおいて点が選択され、その点対の距離の算出が行われ、探索エリア対内最遠点対の探索が、対角線方向に進められる。
【０１４４】
次に、図３３乃至図３５を参照して、クラス２に属する探索エリア対について説明する。
【０１４５】
クラス２に属する探索エリア対は、図３３Ａに示されるように、図２９の４つのセルの内、領域４００の同一の境界面に接し、その境界面の対角の位置に存在するセル（例えば、図中斜線で示されるセル４１１および４１６）により構成される。すなわち、これらのセルは、１方向については対角線の位置にあり、もう１方向については、同じ側にあるという関係になっている。このようなクラス２に属する探索エリア対のパターンは、図３３Ｂに示される領域４００−１１乃至領域４００−２２のように、各セルの位置関係により１２通りある。
【０１４６】
このクラス２に属する探索エリア対の最大長は、図３４に示されるように、領域４００を２分割する図２９の平面４２１乃至平面４２３の内、探索エリア対の両方のセルに接する平面によって領域４００が２分割され、その２つの領域の内の探索エリア対を含む方の直方体の対角線となる線分の距離となる。すなわち、例えば、図３３Ａに示されるセル４１１およびセル４１６からなる探索エリア対の場合、図３４の点Ａ１と点Ｇ２を端点とする線分４５１、および点Ｂ１と点Ｈ２を端点とする線分４５２の内、値が大きい方がこの探索エリア対の最大長となる。
【０１４７】
最遠点対の探索は、距離が近いと想定される点対より開始され、距離が遠いと想定される点対の方向に進められる。すなわち、図３３Ａの探索エリア対の場合、図３５に示されるように、点対４６１から距離の算出が開始され、その次に点対４６２、その次に点対４６３と、点対の距離が長くなるようにセルにおいて点が選択され、その点対の距離の算出が行われ、探索エリア対内最遠点対の探索が、ｘ軸方向には対角線方向に進められ、ｙ軸方向には、同じ向きに這うように探索が進む。
【０１４８】
次に、図３６乃至図３８を参照して、クラス３に属する探索エリア対について説明する。
【０１４９】
クラス３に属する探索エリア対は、図３６Ａに示されるように、図２９の４つのセルの内、領域４００の同一の境界線に接するセル（例えば、図中斜線で示されるセル４１１および４１５）により構成される。すなわち、これらのセルは、互いに隣接する関係になっている。このようなクラス３に属する探索エリア対のパターンは、図３６Ｂに示される領域４００−３１乃至領域４００−４２のように、各セルの位置関係により１２通りある。
【０１５０】
このクラス３に属する探索エリア対の最大長は、図３７に示されるように、領域４００の内、探索エリア対により構成される直方体の対角線となる線分の距離となる。すなわち、例えば、図３６Ａに示されるセル４１１およびセル４１５からなる探索エリア対の場合、図３７の点Ａ１と点Ｇ２を端点とする線分４７１、点Ｂ１と点Ｈ２を端点とする線分４７２、点Ｃ１と点Ｅ２を端点とする線分４７３、点Ｄ１と点Ｆ２を端点とする線分４７４の内、距離が最も大きい線分がこの探索エリア対の最大長となる。
【０１５１】
最遠点対の探索は、距離が近いと想定される点対より開始され、距離が遠いと想定される点対の方向に進められる。すなわち、図３６Ａの探索エリア対の場合、図３８に示されるように、点対４８１から距離の算出が開始され、その次に点対４８２、その次に点対４８３と、点対の距離が長くなるように点が選択され、その点対の距離の算出が行われる。具体的には、図３８に示されるように、探索エリア対内最遠点対の探索が、ｘ軸方向およびｙ軸方向において、互いのセルで同じ向きに這うように探索が進められる。
【０１５２】
このような探索エリア対に関する情報は、２次元の場合と同様に、図２０に示されるような構造体のデータとして生成される。そして、図２０に示される構造体２４０は、２次元の場合と同様に、図１３のステップＳ１３３の処理により、最大長でソートされ、クラス毎にスタックに保存される。このように生成されスタックに保存された探索エリア対に関する情報は、２次元の場合と同様に、図１１のステップＳ９１の処理により、最遠点対が存在しうる探索エリア対が選択されて読み出される。図１１のステップＳ９１において実行される探索エリア対取得処理は、２次元の場合と同様に、図２１のフローチャートのように実行される。
【０１５３】
この処理を行うことにより、最遠点対計算部７３は、最遠点対が明らかに存在しない探索エリア対を処理の対象から外すことができ、後段における最遠点対を探索する処理を効率よく実行することができる。ステップＳ９１の処理を終了した第３の計算部８３は、ステップＳ９２において、未処理の探索エリア対が存在するか否かを判定する。後段の最遠点対を探索する処理を実行していない探索エリア対が存在しないと判定した場合、第３の計算部８３は、ステップＳ９３に処理を進め、現在変数Ｄの値に対応する点対を最遠点対と決定し、その点対を構成する点Ｂ１および点Ｂ２に関する情報を出力して他の処理で使用できるような状態にし、最遠点対決定処理を終了する。
【０１５４】
また、ステップＳ９２において、未処理の探索エリア対が存在すると判定した場合、第３の計算部８３は、処理をステップＳ１０１に進め、その未処理の探索エリア対に対する処理を行うように、最遠点対決定処理を続ける。
【０１５５】
次に、第４の計算部８４は、ステップＳ１０１において、探索エリア対内最遠点対取得処理を実行し、未処理の探索エリア対の中の１つの探索エリア対に注目し、その探索エリア対に含まれる点対についてそれぞれ距離を算出し、それらの距離を比較して、最も距離が大きい点対を探索エリア対内最遠点対（ｂ１，ｂ２）として決定し取得する。
【０１５６】
この処理は、図２２乃至図２７を参照して説明した２次元空間における場合と同様の手順で実行される。すなわち、第４の計算部８４は、点対を固定点と可動点にわけ、可動点側のセルにおいて、固定点との距離が遠くなる点を検索し、その点と固定点により新たな探索エリア対内最遠点対を生成する。そして、第４の計算部８４は、次に、固定点と可動点を逆に割り当て、新たな可動点側のセルにおいて、上述したように、固定点との距離が遠くなる点を検索し、その点と固定点により新たな探索エリア対内最遠点対を生成する。このような処理を繰り返して、第４の計算部８４は、探索エリア対内最遠点対を求める。
【０１５７】
なお、このとき、図２２乃至図２７において説明したように、新たな点を検索するセルにおいて、線分や円を用いてその検索範囲をある程度限定させることができるが、３次元の場合も同様に、点の検索範囲を限定させることができる。その場合、第４の計算部８４は、２次元の場合における線に対応する面を用いたり、２次元のばあいにおける円に対応する球を用いたりして、その検索範囲を限定させる。
【０１５８】
次に、第５の計算部８５は、ステップＳ１１１において、その取得した点対を構成する点ｂ１および点ｂ２の距離を変数ｄに代入し、ステップＳ１１２において、変数ｄの値が変数Ｄの値より大きいか否かを判定し、変数ｄの値の方が大きいと判定した場合、ステップＳ１１３において、変数ｄの値を変数Ｄに代入した後、ステップＳ９２に処理を戻し、それ以降の処理を繰り返す。また、ステップＳ１１２において、変数Ｄの値の方が大きいと判定した場合、第５の計算部８５は、ステップＳ１１３の処理を省略し、変数Ｄの値を変更せずに、ステップＳ９２に処理を戻し、それ以降の処理を繰り返す。
【０１５９】
以上のようにして最遠点対を決定することにより、画像処理装置６１は、３次元に存在する点集合における最遠点対も容易に算出することができる。
【０１６０】
以上に説明した２次元の場合と３次元の場合と同様に、上述した処理を行うことにより、画像処理装置６１は、任意の次元に存在する点集合における最遠点対を容易に算出することができる。また、以上のように最遠点対を求めることにより、物体を包含する境界矩形を容易に算出することもできる。
【０１６１】
以上においては、本発明をコンピュータグラフィックスの画像処理装置に適用した場合を例としたが、本発明は、画像データ、その他のデータを処理する情報処理装置に適用することが可能である。
【０１６２】
上述した一連の処理は、ハードウエアにより実行させることもできるし、ソフトウエアにより実行させることもできる。ソフトウエアにより実行される場合、上述した画像処理装置は、図３９に示されるようなパーソナルコンピュータにより構成される。
【０１６３】
図３９において、パーソナルコンピュータ５００のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）５０１は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）５０２に記憶されているプログラム、または記憶部５１３からＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５０３にロードされたプログラムに従って各種の処理を実行する。ＲＡＭ５０３にはまた、ＣＰＵ５０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１６４】
ＣＰＵ５０１、ＲＯＭ５０２、およびＲＡＭ５０３は、バス５０４を介して相互に接続されている。このバス５０４にはまた、入出力インタフェース５１０も接続されている。
【０１６５】
入出力インタフェース５１０には、キーボード、マウスなどよりなる入力部５１１、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  ｄｉｓｐｌａｙ）などよりなるディスプレイ、並びにスピーカなどよりなる出力部５１２、ハードディスクなどより構成される記憶部５１３、モデムなどより構成される通信部５１４が接続されている。通信部５１４は、インターネットを含むネットワークを介しての通信処理を行う。
【０１６６】
入出力インタフェース５１０にはまた、必要に応じてドライブ５１５が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア９２１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部５１３にインストールされる。
【０１６７】
一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、ネットワークや記録媒体からインストールされる。
【０１６８】
この記録媒体は、図３９に示されるように、装置本体とは別に、ユーザにプログラムを提供するために配布される、プログラムが記録されている磁気ディスク（フロッピディスクを含む）、光ディスク（ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ），ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）を含む）、光磁気ディスク（ＭＤ（Ｍｉｎｉ−Ｄｉｓｋ）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア５２１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに提供される、プログラムが記録されているＲＯＭ５０２や、記憶部５１３に含まれるハードディスクなどで構成される。
【０１６９】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１７０】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０１７１】
【発明の効果】
以上のごとく本発明によれば、複数の点における最遠点対を求めることができる。特に、任意の次元に存在する点集合における最遠点対を容易に算出することができる。また、物体を包含する境界矩形を容易に算出することもできる。さらに、点集合のグルーピング、幾何学的な交差、包含を少ない計算回数で求めることができる。
【図面の簡単な説明】
【図１】本発明を適用した物体監視システムの構成例を示す図である。
【図２】図１の物体監視システムの動作を説明するフローチャートである。
【図３】図１の物体のより詳細な形状を示す図である。
【図４】コンピュータグラフィックスにおける視点の原理を説明する図である。
【図５】コンピュータグラフィックスにおける運動シミュレーションの処理を説明するフローチャートである。
【図６】ボールが物体と衝突する状態を説明する図である。
【図７】本発明を適用した画像処理装置の構成例を示すブロック図である。
【図８】図８の凸包計算部の機能的構成を示すブロック図である。
【図９】点集合における最遠点対の例を示す図である。
【図１０】最遠点対決定処理を説明するフローチャートである。
【図１１】最遠点対決定処理を説明するフローチャートである。
【図１２】２次元においてセルを作成する様子の例を説明する図である。
【図１３】探索エリア対生成処理の詳細を説明するフローチャートである。
【図１４】２次元におけるクラス１に属する探索エリア対を説明する図である。
【図１５】２次元におけるクラス１に属する探索エリア対のパターン例を示す図である。
【図１６】２次元におけるクラス１に属する探索エリア対において、探索エリア対内最遠点対を求める様子の例を説明する図である。
【図１７】２次元におけるクラス２に属する探索エリア対を説明する図である。
【図１８】２次元におけるクラス２に属する探索エリア対のパターン例を示す図である。
【図１９】２次元におけるクラス２に属する探索エリア対において、探索エリア対内最遠点対を求める様子の例を説明する図である。
【図２０】スタックに登録される構造体の構成例を説明する図である。
【図２１】探索エリア対取得処理について説明する図である。
【図２２】２次元におけるクラス１に属する探索エリア対において、探索エリア対内最遠点対を求める様子の具体的な例を示す図である。
【図２３】２次元におけるクラス１に属する探索エリア対において、探索エリア対内最遠点対を求める様子の具体的な例を示す、図２２に続く図である。
【図２４】２次元におけるクラス１に属する探索エリア対において、探索エリア対内最遠点対を求める様子の具体的な例を示す、図２３に続く図である。
【図２５】２次元におけるクラス１に属する探索エリア対において、探索エリア対内最遠点対を求める様子の具体的な例を示す、図２４に続く図である。
【図２６】２次元におけるクラス２に属する探索エリア対において、探索エリア対内最遠点対を求める様子の具体的な例を示す図である。
【図２７】２次元におけるクラス２に属する探索エリア対において、探索エリア対内最遠点対を求める様子の具体的な例を示す、図２６に続く図である。
【図２８】３次元においてセルを作成する様子の例を説明する図である。
【図２９】３次元において点をセルに登録する様子の例を説明する図である。
【図３０】３次元におけるクラス１に属する探索エリア対を説明する図である。
【図３１】３次元におけるクラス１に属する探索エリア対の最大長を説明する図である。
【図３２】３次元におけるクラス１に属する探索エリア対において、探索エリア対内最遠点対を求める様子の例を説明する図である。
【図３３】３次元におけるクラス２に属する探索エリア対を説明する図である。
【図３４】３次元におけるクラス２に属する探索エリア対の最大長を説明する図である。
【図３５】３次元におけるクラス２に属する探索エリア対において、探索エリア対内最遠点対を求める様子の例を説明する図である。
【図３６】３次元におけるクラス３に属する探索エリア対を説明する図である。
【図３７】３次元におけるクラス３に属する探索エリア対の最大長を説明する図である。
【図３８】３次元におけるクラス３に属する探索エリア対において、探索エリア対内最遠点対を求める様子の例を説明する図である。
【図３９】パーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
６１  画像処理装置，７１  入力部，  ７２  出力部，  ７３  最遠点対計算部，  ７５  ＣＰＵ，  ７６ＲＡＭ，  ７７  ＲＯＭ，  ８１  第１の計算部，  ８２  第２の計算部，  ８３  第３の計算部，  ８４  第４の計算部，  ８５  第５の計算部
【図１】
2004348188.tif 000003
【図２】
2004348188.tif 000004
【図３】
2004348188.tif 000005
【図４】
2004348188.tif 000006
【図５】
2004348188.tif 000007
【図６】
2004348188.tif 000008
【図７】
2004348188.tif 000009
【図８】
2004348188.tif 000010
【図９】
2004348188.tif 000011
【図１０】
2004348188.tif 000012
【図１１】
2004348188.tif 000013
【図１２】
2004348188.tif 000014
【図１３】
2004348188.tif 000015
【図１４】
2004348188.tif 000016
【図１５】
2004348188.tif 000017
【図１６】
2004348188.tif 000018
【図１７】
2004348188.tif 000019
【図１８】
2004348188.tif 000020
【図１９】
2004348188.tif 000021
【図２０】
2004348188.tif 000022
【図２１】
2004348188.tif 000023
【図２２】
2004348188.tif 000024
【図２３】
2004348188.tif 000025
【図２４】
2004348188.tif 000026
【図２５】
2004348188.tif 000027
【図２６】
2004348188.tif 000028
【図２７】
2004348188.tif 000029
【図２８】
2004348188.tif 000030
【図２９】
2004348188.tif 000031
【図３０】
2004348188.tif 000032
【図３１】
2004348188.tif 000033
【図３２】
2004348188.tif 000034
【図３３】
2004348188.tif 000035
【図３４】
2004348188.tif 000036
【図３５】
2004348188.tif 000037
【図３６】
2004348188.tif 000038
【図３７】
2004348188.tif 000039
【図３８】
2004348188.tif 000040
【図３９】
2004348188.tif 000041