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