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