(57)【特許請求の範囲】
【請求項１】
矩形の部品配置領域に、矩形の複数の部品を互いに重ならないように配置する部品配置装置であって、
前記部品配置領域の縦および横サイズを定めた配置領域サイズ情報と、
各前記部品の縦および横サイズを定めた部品サイズ情報と、
前記各部品の配置可能範囲を定めた配置可能範囲情報と、
前記各部品の配置戦略を定めた戦略情報と、
前記各部品の配置順序を定めた順序情報と、
の入力を受け付ける入力受付手段と、
前記順序情報に応じて前記部品を選択する部品選択手段と、
前記部品選択手段により選択された選択部品の前記配置戦略に応じて前記選択部品の左上、左下、右上、右下の角の４つの基準点のうちの１つを利用基準点として決定し、前記選択部品の前記配置可能範囲において前記利用基準点を位置づけ可能な領域を特定し、特定した領域の範囲端をなす複数の第１線分を取得する線分取得手段と、
前記複数の第１線分に基づいて前記選択部品の前記利用基準点を位置づける候補点を算出する候補点算出手段と、
前記利用基準点を前記候補点に位置づけるように前記選択部品を配置したときに前記選択部品が配置済みの部品と重ならずかつ前記配置可能範囲に含まれることとなる前記候補点を検出し、検出した候補点に前記利用基準点を位置づけるように前記選択部品を配置する部品配置手段と、
前記選択部品の配置位置に基づき、前記選択部品の前記４つの基準点の各々について前記基準点から前記選択部品の存在する方向に前記部品配置領域の縦の辺及び横の辺まで引かれた複数の線分である複数の第２線分を設定する線分設定手段と、
前記４つの基準点の各々について設定された前記複数の第２線分の情報を記憶する線分情報記憶手段と、を備え、
前記候補点算出手段は、
前記部品選択手段により１番目に選択された前記選択部品については、前記１番目に選択された前記選択部品の前記複数の第１線分上の１つ以上の位置を前記候補点として算出し、
前記部品選択手段によりｉ（ｉは２以上の整数）番目に選択された前記選択部品については、前記ｉ番目に選択された前記選択部品の前記複数の第１線分と、前記ｉ番目に選択された前記選択部品の前記利用基準点と同一の基準点に対して設定された、前記１〜ｉ−１番目の各前記選択部品の前記複数の第２線分と、を含む線分集合を用いて線分の交点を計算することにより前記ｉ番目の選択部品に対する前記候補点を算出する、
ことを特徴とする部品配置装置。
【請求項２】
前記配置戦略は、
前記配置可能範囲において部品をできるだけ下側に詰め、次いでできるだけ左側に詰める「下から左詰め」
前記配置可能範囲において部品をできるだけ下側に詰め、次いでできるだけ右側に詰める「下から右詰め」
前記配置可能範囲において部品をできるだけ上側に詰め、次いでできるだけ左側に詰める「上から左詰め」
前記配置可能範囲において部品をできるだけ上側に詰め、次いでできるだけ右側に詰める「上から右詰め」
前記配置可能範囲において部品をできるだけ左側に詰め、次いでできるだけ下側に詰める「左から下詰め」
前記配置可能範囲において部品をできるだけ左側に詰め、次いでできるだけ上側に詰める「左から上詰め」
前記配置可能範囲において部品をできるだけ右側に詰め、次いでできるだけ下側に詰める「右から下詰め」
前記配置可能範囲において部品をできるだけ右側に詰め、次いでできるだけ上側に詰める「右から上詰め」
のうちのいずれかであることを特徴とする請求項１に記載の部品配置装置。
【請求項３】
前記候補点算出手段により算出された前記候補点を前記選択部品の前記配置戦略に応じてソートするソート手段をさらに備え、
前記ソート手段は、
前記選択部品の配置戦略が
前記「下から左詰め」であるときは、縦座標、横座標の優先順位で、縦座標が昇順、横座標が昇順、
前記「下から右詰め」であるときは、縦座標、横座標の優先順位で、縦座標が昇順、横座標が降順、
前記「上から左詰め」であるときは、縦座標、横座標の優先順位で、縦座標が降順、横座標が昇順、
前記「上から右詰め」であるときは、縦座標、横座標の優先順位で、縦座標が降順、横座標が降順、
前記「左から下詰め」であるときは、横座標、縦座標の優先順位で、横座標が昇順、縦座標が昇順、
前記「左から上詰め」であるときは、横座標、縦座標の優先順位で、横座標が昇順、縦座標が降順、
前記「右から下詰め」であるときは、横座標、縦座標の優先順位で、横座標が降順、縦座標が昇順、
前記「右から上詰め」であるときは、横座標、縦座標の優先順位で、横座標が降順、縦座標が降順、
により前記候補点をソートし、
前記部品配置領域の左下角から右へ行くほど横座標が大きく、上へ行くほど縦座標が大きくなり、
前記部品配置手段は、前記選択部品の前記利用基準点を前記候補点に位置づけるように前記選択部品を配置したとき前記選択部品が他の部品と重ならずかつ前記配置可能範囲に含まれるかどうかを前記候補点のソート順に検査し、最初に検出された候補点に前記利用基準点を位置づけるように前記選択部品を配置する、
ことを特徴とする請求項２に記載の部品配置装置。
【請求項４】
前記各部品の配置戦略は、
指定座標に対し前記利用基準点ができるだけ近くに位置するように部品を配置する「指定座標から近接詰め」
指定座標に対し前記利用基準点ができるだけ遠くに位置するように部品を配置する「指定座標から遠方詰め」
のうちのいずれかであり、
前記入力受付手段は、前記指定座標の入力を受け付けることを特徴とする請求項１に記載の部品配置装置。
【請求項５】
前記候補点算出手段により算出された前記候補点を前記選択部品の前記配置戦略に応じてソートするソート手段をさらに備え、
前記ソート手段は、
前記選択部品の配置戦略が
前記「指定座標から近接詰め」であるときは、前記指定座標との距離が近い順に前記候補点をソートし、
前記「指定座標から遠方詰め」であるときは、前記指定座標との距離が遠い順に前記候補点をソートし、
前記部品配置手段は、前記選択部品の前記利用基準点を前記候補点に位置づけるように前記選択部品を配置したとき前記選択部品が他の部品と重ならずかつ前記配置可能範囲に含まれるかどうかを前記候補点のソート順に検査し、最初に検出された候補点に前記利用基準点を位置づけるように前記選択部品を配置する、
ことを特徴とする請求項４に記載の部品配置装置。
【請求項６】
前記配置戦略は、
前記配置可能範囲において部品をできるだけ下側に詰め、次いでできるだけ左側に詰める「下から左詰め」
前記配置可能範囲において部品をできるだけ下側に詰め、次いでできるだけ右側に詰める「下から右詰め」
前記配置可能範囲において部品をできるだけ上側に詰め、次いでできるだけ左側に詰める「上から左詰め」
前記配置可能範囲において部品をできるだけ上側に詰め、次いでできるだけ右側に詰める「上から右詰め」
前記配置可能範囲において部品をできるだけ左側に詰め、次いでできるだけ下側に詰める「左から下詰め」
前記配置可能範囲において部品をできるだけ左側に詰め、次いでできるだけ上側に詰める「左から上詰め」
前記配置可能範囲において部品をできるだけ右側に詰め、次いでできるだけ下側に詰める「右から下詰め」
前記配置可能範囲において部品をできるだけ右側に詰め、次いでできるだけ上側に詰める「右から上詰め」
指定座標に対し前記利用基準点ができるだけ近くに位置するように部品を配置する「指定座標から近接詰め」
指定座標に対し前記利用基準点ができるだけ遠くに位置するように部品を配置する「指定座標から遠方詰め」
のうちのいずれかであり、
前記入力受付手段は、前記指定座標の入力を受け付けることを特徴とする請求項１に記載の部品配置装置。
【請求項７】
前記候補点算出手段により算出された前記候補点を前記選択部品の前記配置戦略に応じてソートするソート手段をさらに備え、
前記ソート手段は、
前記選択部品の配置戦略が
前記「下から左詰め」であるときは、縦座標、横座標の優先順位で、縦座標が昇順、横座標が昇順、
前記「下から右詰め」であるときは、縦座標、横座標の優先順位で、縦座標が昇順、横座標が降順、
前記「上から左詰め」であるときは、縦座標、横座標の優先順位で、縦座標が降順、横座標が昇順、
前記「上から右詰め」であるときは、縦座標、横座標の優先順位で、縦座標が降順、横座標が降順、
前記「左から下詰め」であるときは、横座標、縦座標の優先順位で、横座標が昇順、縦座標が昇順、
前記「左から上詰め」であるときは、横座標、縦座標の優先順位で、横座標が昇順、縦座標が降順、
前記「右から下詰め」であるときは、横座標、縦座標の優先順位で、横座標が降順、縦座標が昇順、
前記「右から上詰め」であるときは、横座標、縦座標の優先順位で、横座標が降順、縦座標が降順、
により前記候補点をソートし、
前記「指定座標から近接詰め」であるときは、前記指定座標との距離が近い順に前記候補点をソートし、
前記「指定座標から遠方詰め」であるときは、前記指定座標との距離が遠い順に前記候補点をソートし、
前記部品配置領域の左下角から右へ行くほど横座標が大きく、上へ行くほど縦座標が大きくなり、
前記部品配置手段は、前記選択部品の前記利用基準点を前記候補点に位置づけるように前記選択部品を配置したとき前記選択部品が他の部品と重ならずかつ前記配置可能範囲に含まれるかどうかを前記候補点のソート順に検査し、最初に検出された候補点に前記利用基準点を位置づけるように前記選択部品を配置する、
ことを特徴とする請求項６に記載の部品配置装置。
【請求項８】
前記配置戦略と前記利用基準点とを対応づけた対応情報を記憶した対応情報記憶手段をさらに備え、
前記線分取得手段は、前記選択部品の前記利用基準点を、前記選択部品の前記配置戦略と、前記対応情報とに基づいて決定することを特徴とする請求項１ないし７のいずれか一項に記載の部品配置装置。
【請求項９】
前記線分取得手段は、前記特定した領域の前記範囲端において、前記選択部品の前記配置可能範囲の範囲端に一致する部分を前記複数の第１線分として取得することを特徴とする請求項１ないし８のいずれか一項に記載の部品配置装置。
【請求項１０】
前記候補点算出手段は、前記１番目に選択された前記選択部品について、前記複数の第１線分の交点を前記候補点として算出することを特徴とする請求項１ないし９のいずれか一項に記載の部品配置装置。
【請求項１１】
前記線分設定手段は、前記各部品の前記利用基準点のどれにも合致しない基準点については、前記複数の第２線分の設定を省略することを特徴とする請求項８に記載の部品配置装置。
【請求項１２】
前記線分設定手段は、
前記選択部品の左下の前記基準点に対しては、右上の前記基準点から前記部品配置領域の下辺および左辺へ向けて引いた線分を前記複数の第２線分として設定し、
前記選択部品の左上の前記基準点に対しては、右下の前記基準点から前記部品配置領域の上辺および左辺へ向けて引いた線分を前記複数の第２線分として設定し、
前記選択部品の右下の前記基準点に対しては、左上の前記基準点から前記部品配置領域の下辺および右辺へ引いた線分を前記複数の第２線分として設定し、
前記選択部品の右上の前記基準点に対しては、左下の前記基準点から前記部品配置領域の上辺および右辺へ引いた線分を前記複数の第２線分として設定する、
ことを特徴とする請求項１ないし１１のいずれか一項に記載の部品配置装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、矩形の部品配置領域に、矩形の複数の部品を、互いに重ならないように配置する部品配置装置および部品配置方法に関する。
【背景技術】
【０００２】
電子機器筐体内に配置する部品には、配置する場所や他の部品との位置関係等様々な配置制約が存在する。それらの配置制約を満たすように部品を筐体内に配置するには時間的コストがかかる。したがって、出来るだけ高速に部品を筐体内に配置する方法が望まれる。
【０００３】
なお、非特許文献１では、部品ごとに、x軸方向の配置位置に関するコスト関数およびy軸方向の配置位置に関するコスト関数を定義し、総コストが低くなるように部品配置を行っている。
【非特許文献１】S. Imahori, M. Yagiura, T. Ibaraki, “Local Search Algorithms for the Rectangle Packing Problem with General Spatial Costs”, 2002
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、矩形の部品配置領域内に、矩形の部品を、部品同士の重なりがないようにかつ各部品の制約を満たすように、高速に配置する部品配置装置および部品配置方法を提供する。
【課題を解決するための手段】
【０００５】
本発明の一態様としての部品配置装置は、
矩形の部品配置領域に、矩形の複数の部品を互いに重ならないように配置する部品配置装置であって、
前記部品配置領域の縦および横サイズを定めた配置領域サイズ情報と、
各前記部品の縦および横サイズを定めた部品サイズ情報と、
前記各部品の配置可能範囲を定めた配置可能範囲情報と、
前記各部品の配置戦略を定めた戦略情報と、
前記各部品の配置順序を定めた順序情報と、
の入力を受け付ける入力受付手段と、
前記順序情報に応じて前記部品を選択する部品選択手段と、
前記部品選択手段により選択された選択部品の前記配置戦略に応じて前記選択部品の左上、左下、右上、右下の角の４つの基準点のうちの１つを利用基準点として決定し、前記選択部品の前記配置可能範囲において前記利用基準点を位置づけ可能な領域を特定し、特定した領域の範囲端をなす複数の第１線分を取得する線分取得手段と、
前記複数の第１線分に基づいて前記選択部品の前記利用基準点を位置づける候補点を算出する候補点算出手段と、
前記利用基準点を前記候補点に位置づけるように前記選択部品を配置したときに前記選択部品が配置済みの部品と重ならずかつ前記配置可能範囲に含まれることとなる前記候補点を検出し、検出した候補点に前記利用基準点を位置づけるように前記選択部品を配置する部品配置手段と、
前記選択部品の配置位置に基づき、前記選択部品の前記４つの基準点の各々について前記部品配置領域内に複数の第２線分を設定する線分設定手段と、
前記４つの基準点の各々について設定された前記複数の第２線分の情報を記憶する線分情報記憶手段と、を備え、
前記候補点算出手段は、
前記部品選択手段により１番目に選択された前記選択部品については、前記１番目に選択された前記選択部品の前記複数の第１線分上の１つ以上の位置を前記候補点として算出し、
前記部品選択手段によりｉ（ｉは２以上の整数）番目に選択された前記選択部品については、前記ｉ番目に選択された前記選択部品の前記複数の第１線分と、前記ｉ番目に選択された前記選択部品の前記利用基準点と同一の基準点に対して設定された、前記１〜ｉ−１番目の各前記選択部品の前記複数の第２線分と、を含む線分集合を用いて線分の交点を計算することにより前記ｉ番目の選択部品に対する前記候補点を算出する、
ことを特徴とする。
【０００６】
本発明の一態様としての部品配置方法は、
矩形の部品配置領域に、矩形の複数の部品を互いに重ならないように配置する部品配置方法であって、
前記部品配置領域の縦および横サイズを定めた配置領域サイズ情報と、
各前記部品の縦および横サイズを定めた部品サイズ情報と、
前記各部品の配置可能範囲を定めた配置可能範囲情報と、
前記各部品の配置戦略を定めた戦略情報と、
前記各部品の配置順序を定めた順序情報と、
の入力を受け付ける入力受付ステップと、
前記順序情報に応じて前記部品を選択する部品選択ステップと、
前記部品選択ステップによりにより選択された選択部品の前記配置戦略に応じて前記選択部品の左上、左下、右上、右下の角の４つの基準点のうちの１つを利用基準点として決定し、前記選択部品の前記配置可能範囲において前記利用基準点を位置づけ可能な領域を特定し、特定した領域の範囲端をなす複数の第１線分を取得する線分取得ステップと、
前記複数の第１線分に基づいて前記選択部品の前記利用基準点を位置づける候補点を算出する候補点算出ステップと、
前記利用基準点を前記候補点に位置づけるように前記選択部品を配置したときに前記選択部品が配置済みの部品と重ならずかつ前記配置可能範囲に含まれることとなる前記候補点を検出し、検出した候補点に前記利用基準点を位置づけるように前記選択部品を配置する部品配置ステップと、
前記選択部品の配置位置に基づき、前記選択部品の前記４つの基準点の各々について前記部品配置領域内に複数の第２線分を設定する線分設定ステップと、
前記４つの基準点の各々について設定された前記複数の第２線分の情報を記憶する線分情報記憶ステップと、を備え、
前記候補点算出ステップは、
前記部品選択ステップにより１番目に選択された前記選択部品については、前記１番目に選択された前記選択部品の前記複数の第１線分上の１つ以上の位置を前記候補点として算出し、
前記部品選択ステップによりｉ（ｉは２以上の整数）番目に選択された前記選択部品については、前記ｉ番目に選択された前記選択部品の前記複数の第１線分と、前記ｉ番目に選択された前記選択部品の前記利用基準点と同一の基準点に対して設定された、前記１〜ｉ−１番目の各前記選択部品の前記複数の第２線分と、を含む線分集合を用いて線分の交点を計算することにより前記ｉ番目の選択部品に対する前記候補点を算出する、
ことを特徴とする。
【発明の効果】
【０００７】
本発明により、矩形の部品配置領域内に、矩形の部品を、部品同士の重なりがないようにかつ各部品の制約を満たすように高速に配置することが可能になる。
【発明を実施するための最良の形態】
【０００８】
図１は、本発明の一実施の形態にしたがった部品配置装置の構成を示すブロック図である。図２は、図１の部品配置装置の動作を説明するフローチャートである。この部品配置装置は、縦サイズおよび横サイズが定められた矩形領域（部品配置領域）内に、矩形の複数の部品を、部品ごとに予め与えられた制約（たとえば配置戦略および配置可能範囲）を満たすように、かつ互いに重ならないように高速に配置しようとするものである。
【０００９】
図１の部品配置装置は、配置部品情報記憶部１１および配置領域情報記憶部１２を有する入力情報記憶部２０と、線分情報記憶部１３と、配置結果記憶部１４と、配置可能範囲線分算出部１５と、配置候補点算出部１６と、配置候補点ソート部１７と、配置点決定部１８と、配置結果線分算出部１９とを備える。
【００１０】
以下では、まず、入力情報記憶部２０に記憶された情報について説明し、その後、図１の他のブロックについて、図１の部品配置装置の動作とともに、説明する。
【００１１】
入力情報記憶部２０における配置領域情報記憶部１２は、部品を配置しようとする部品配置領域のサイズ情報（配置領域サイズ情報）を記憶している。当該サイズ情報は、部品配置領域の縦サイズおよび横サイズを規定している。部品配置領域は、たとえば矩形領域である。本実施形態では矩形の部品配置領域に、矩形の複数の部品を２次元的に高速に配置しようとするものであり、部品の高さについては考慮しない。
【００１２】
入力情報記憶部２０における配置部品情報記憶部１１は、配置する部品の配置順序を定めた配置順序情報、配置する部品の詳細を定めた配置部品情報、その他の情報（たとえば後述する図５および図１１の表）を記憶している。入力情報記憶部２０は、配置順序情報および配置部品情報等の入力、ならびに上述の配置領域サイズ情報の入力をユーザから受け付け、前者を配置部品情報記憶部１１に、後者を配置領域情報記憶部１２に格納する入力受付手段を有していても良い。
【００１３】
上記配置順序情報は、部品を配置する順序を表す情報である。部品の配置順序は配置結果（最終的に部品が配置される位置）に影響を与えるが、本発明の本質には無関係なので配置順に関する詳細は省略する。
【００１４】
上記配置部品情報は、
（i）配置する部品の縦および横サイズを表すサイズ情報（部品サイズ情報）と、
（ii）配置する部品の配置可能範囲（配置領域内の一部領域であり、本実施形態では矩形を有する）を示す配置可能範囲情報と、
（iii）配置する部品が利用する配置戦略（後述する図３、図５、図６、図１１参照）を表す戦略情報と、を含む。
【００１５】
（iii）の配置戦略について説明する。配置戦略は全１６通り存在し、大きく配置戦略群１（８個の配置戦略を含む）と、配置戦略群２（残りの８個の配置戦略を含む）とに分かれる。
【００１６】
図３は、配置戦略群１に含まれる８個の配置戦略を説明する図である。○の中の数字は部品を配置した順序（配置順位）を表している。これら８個の配置戦略は、図３（Ａ）の「左から下詰め」、図３（Ｂ）の「左から上詰め」、図３（Ｃ）の「右から下詰め」、図３（Ｄ）の「下から左詰め」、図３（Ｅ）の「下から右詰め」、図３（Ｆ）の「右から上詰め」、図３（Ｇ）の「上から左詰め」、図３（Ｈ）の「上から右詰め」を含む。
【００１７】
図３（Ａ）の「左から下詰め」は、配置可能範囲内で部品をできるだけ左側に詰め、次いでできるだけ下側に詰める戦略である。
【００１８】
図３（Ｂ）の「左から上詰め」は、配置可能範囲内で部品をできるだけ左側に詰め、次いでできるだけ上側に詰める戦略である。
【００１９】
図３（Ｃ）の「右から下詰め」は、配置可能範囲内で部品をできるだけ右側に詰め、次いでできるだけ下側に詰める戦略である。
【００２０】
図３（Ｄ）の「下から左詰め」は、配置可能範囲内で部品をできるだけ下側に詰め、次いでできるだけ左側に詰める戦略である。
【００２１】
図３（Ｅ）の「下から右詰め」は、配置可能範囲内で部品をできるだけ下側に詰め、次いでできるだけ右側に詰める戦略である。
【００２２】
図３（Ｆ）の「右から上詰め」は、配置可能範囲内で部品をできるだけ右側に詰め、次いでできるだけ上側に詰める戦略である。
【００２３】
図３（Ｇ）の「上から左詰め」は、配置可能範囲内で部品をできるだけ上側に詰め、次いでできるだけ左側に詰める戦略である。
【００２４】
図３（Ｈ）の「上から右詰め」は、配置可能範囲内で部品をできるだけ上側に詰め、次いでできるだけ右側に詰める戦略である。
【００２５】
図３（Ａ）〜図３（Ｇ）の各配置戦略は、特定方向に部品を詰めたい場合に利用できる。例えば、ある部品をできるだけ手前から詰めたい場合には、ある部品の配置戦略として、「下から左詰め」または「下から右詰め」を指定すればよい。
【００２６】
一方、もう一つの配置戦略群２は、たとえばユーザにより指定される指定座標から、部品の利用部品基準点（あるいは単に利用基準点と称される）までの距離が最小または最大になるように部品を配置していく戦略群である。指定座標はたとえば入力受付手段から指定可能であるとする。部品には、４つの部品基準点（あるいは単に基準点と称される）があり、これら４つの部品基準点のうち、当該部品が利用する部品基準点が、利用部品基準点（利用基準点）と称される。部品基準点の例を図４に示す。矩形の部品には、左上、右上、左下、右下の４つの角があり、これら４つの角が部品基準点に相当する。配置戦略２は、指定座標から、利用部品基準点までの距離が最小または最大になるように部品を配置する戦略を集めたものである。
【００２７】
具体的に、配置戦略群２は、
「指定座標から近接詰め（利用部品基準点：左下）」
「指定座標から近接詰め（利用部品基準点：左上）」
「指定座標から近接詰め（利用部品基準点：右下）」
「指定座標から近接詰め（利用部品基準点：右上）」
「指定座標から遠方詰め（利用部品基準点：左下）」
「指定座標から遠方詰め（利用部品基準点：左上）」
「指定座標から遠方詰め（利用部品基準点：右下）」
「指定座標から遠方詰め（利用部品基準点：右上）」を含む。
【００２８】
配置する部品の利用部品基準点は、図５の表に示すように、配置戦略に応じてあらかじめ一意に決められている。図５の表は配置部品情報記憶部１１に記憶されている。
【００２９】
図６は、配置戦略群２に含まれる８個の配置戦略のうち４つの「指定座標からの近接詰め」を説明する図である。○の中の数字は部品を配置した順序（配置順位）を表している。
【００３０】
図６（Ａ）は、「指定座標から近接詰め（利用部品基準点：左下）」を表し、この戦略では、指定座標と、部品の左下の基準点との距離が最小になるように部品を配置する。
【００３１】
図６（Ｂ）は、「指定座標から近接詰め（利用部品基準点：左上）」を表し、この戦略では、指定座標と、部品の左上の基準点との距離が最小になるように部品を配置する。
【００３２】
図６（Ｃ）は、「指定座標から近接詰め（利用部品基準点：右下）」を表し、この戦略では、指定座標と、部品の右下の基準点との距離が最小になるように部品を配置する。
【００３３】
図６（Ｄ）は、「指定座標から近接詰め（利用部品基準点：右上）」を表し、この戦略では、指定座標と、部品の右上の基準点との距離が最小になるように部品を配置する。
【００３４】
図示は省略するが、４つの「指定座標からの遠方詰め」についても、上記と同様の考えで配置する。
【００３５】
すなわち、「指定座標から遠方詰め（利用部品基準点：左下）」では、指定座標と、部品の左下の基準点との距離が最大になるように部品を配置する。
【００３６】
「指定座標から遠方詰め（利用部品基準点：左上）」では、指定座標と、部品の左上の基準点との距離が最大になるように部品を配置する。
【００３７】
「指定座標から遠方詰め（利用部品基準点：右下）で」は、指定座標と、部品の右下の基準点との距離が最大になるように部品を配置する。
【００３８】
「指定座標から遠方詰め（利用部品基準点：右上）」では、指定座標と、部品の右上の基準点との距離が最大になるように部品を配置する。
【００３９】
これらの配置戦略群２に含まれる各配置戦略は、例えばある部品と別の部品とをなるべく近く（または遠く）に配置したい場合等に利用できる。仮にある部品の配置後に別の部品を配置する場合、別の部品の配置戦略として、配置済みの上記ある部品の点（重心位置または部品基準点等）を指定座標として「指定座標からの近接（または遠方）詰め」を用いればよい。
【００４０】
以下、図１および図２を用いて、２つの矩形の部品（部品Aおよび部品B）を配置する例をもとに、図１の部品配置装置について詳細に説明する。
【００４１】
前提として、部品Aの配置戦略は「右から上詰め」、部品Bの配置戦略は「上から左詰め」であるとする。したがって、図５の表から、部品Ａの利用部品基準点は右上、部品Ｂの利用部品基準点は左上に決まる。また、部品の配置順序は、部品Ａ、部品Ｂの順であるとする。すなわち部品Ａの順序は１番、部品Ｂの順序は２番である。
【００４２】
まず、ステップＳ１０１において、図１の部品配置装置が、全部品の配置が完了したかどうかを判定する。ここではまだ全部品の配置が完了していないため（ＮＯ）、ステップＳ１０２に進む。
【００４３】
ステップＳ１０２では、配置可能範囲線分算出部１５が、配置部品情報記憶部１１から、部品の配置順序情報を読み出して配置すべき部品を選択し、選択した部品の配置部品情報を配置部品情報記憶部１１から読み出す。ここでは部品Ａが選択され、部品Ａの部品配置情報が読み出される。配置可能範囲線分算出部１５はたとえば部品選択手段を有する。
【００４４】
ステップＳ１０３では、配置可能範囲線分算出部１５が、配置する部品の配置可能範囲に基づき、当該部品の利用部品基準点に対応する配置可能範囲線分を計算し、計算した配置可能範囲線分を線分情報記憶部１３に登録する。配置可能範囲線分は、たとえば利用基準点を位置づけ可能な領域の範囲端をなす第１線分に対応し、配置可能範囲線分算出部１５は当該範囲端をなす複数の第１線分を取得する線分取得手段を含む。ここでは部品Ａの利用部品基準点「右上」に対応する配置可能範囲線分を計算し、計算した配置可能範囲線分を線分情報記憶部１３に登録する。以下、配置可能範囲線分およびその計算方法について詳しく説明する。
【００４５】
図８は、利用部品基準点が左下、左上、右下、右上の各場合について配置可能範囲線分を計算する例を示す。
【００４６】
配置可能範囲線分は、配置可能範囲において当該部品の利用部品基準点の可動領域の辺（位置づけ可能な領域の範囲端）において、配置可能範囲の範囲端（配置可能範囲の辺）に一致する辺を選択することにより求める。したがって、配置可能範囲線分は、１本の垂直線分と１本の水平線分との２本の線分からなる。配置可能範囲の範囲端に一致しない方の線分でなく、一致する方の線分を採用する理由については後述する。
【００４７】
配置可能範囲線分の具体的な求め方としては、たとえば利用部品基準点が配置可能範囲の頂点に一致するように部品を置いた状態（開始状態）から配置可能範囲の辺に沿って大きく一周させ、そのとき利用部品基準点がたどって得られる矩形枠（可動領域）の辺において、配置可能範囲の辺に一致する辺を、配置可能範囲線分（第１線分）として取得する。
【００４８】
図において、点線矩形が利用部品基準点の可動領域を規定し、点線矩形の辺に沿って描かれた太線で示される線分Ｖ１、Ｈ１が配置可能範囲線分（第１線分）である。線Ｖ１が垂直線分、線Ｈ１が水平線分である。
【００４９】
図中、参照符号Ｘおよび参照符号Ｘ’が示されるが、参照符号Ｘは部品を一周させる前の部品位置を示し、参照符号Ｘ’は、参照符号Ｘの位置から最も遠い位置まで部品が移動したときの部品位置を示す。
【００５０】
なお、以上に示した配置可能範囲線分はあくまで一例であり、利用部品基準点の可動領域の辺（位置づけ可能な領域の範囲端）の一部または全部であればよく、本発明は上記の例に限定されない。たとえば、利用部品基準点の可動領域の辺全体、すなわち２本の水平線分と、２本の垂直線分とを、配置可能範囲線分として採用してもかまわない。
【００５１】
ここでは、上述のように部品Ａ（利用部品基準点は右上）について配置可能範囲線分を計算する。部品Ａについて計算された配置可能範囲線分の例を図７（Ａ）に示す。
【００５２】
ステップＳ１０４では、配置候補点算出部１６が、配置する部品の配置候補点を計算する。具体的に、まず配置部品情報記憶部１１から、配置する部品の利用部品基準点を読み出し、読み出した利用部品基準点に対応する線分（ステップＳ１０３で計算された配置可能範囲線分と、後述する配置結果線分（２番目以降に選択された部品の場合のみ））を線分情報記憶部１３から取得する。そして、配置候補点算出部１６は、取得した線分（全線分）の交点を、平面走査法を利用して算出し、算出した交点を配置候補点として得る。
【００５３】
ここでは、取得した線分は、ステップＳ１０３で計算した部品Ａの配置可能範囲線分（１本の垂直線分と１本の水平線分）のみであるため、図７（Ｂ）に示すように、これら垂直線分と水平線分との交点を配置候補点として取得する。あるいは１番目に選択された部品については、配置可能範囲線分（第１線分）上の１つ以上の点を配置候補点として得る。
【００５４】
ステップＳ１０５では、配置候補点ソート部（ソート手段）１７が、ステップＳ１０４で得られた配置候補点を、配置する部品の配置戦略に基づいてソートする。ただし、部品Ａについて取得された配置候補点は１つであるため、ここではソートは不要である。
【００５５】
ステップＳ１０６では、配置点決定部（部品配置手段）１８が、配置部品情報記憶部１１から、配置する部品の利用部品基準点を読み出し、また、配置領域情報記憶部１２から矩形領域（部品配置領域）のサイズ情報を読み出し、ステップＳ１０５でソートされた配置候補点に利用部品基準点が一致するように、部品を配置可能かどうか順番に調べる。具体的には、他の部品と重ならないように、配置可能範囲内に配置可能かどうかを調べる。配置可能な配置候補点が見つからなかったら、配置不可能な部品が存在することを示すエラーメッセージを返して、処理を終了する。ここでは部品Ａを唯一の配置候補点に配置可能であることを決定したとする。
【００５６】
ステップＳ１０７では、配置点決定部１８が、ステップＳ１０６で最初に見つかった配置候補点に利用基準点が一致するように部品を配置する。そして、部品を配置した箇所（配置結果）を配置結果記憶部１４に記録する。ここでは部品Ａを、図７（Ｃ）に示すように、その唯一の配置候補点に配置し、部品Ａを配置した箇所を配置結果記憶部１４に記録する。
【００５７】
ステップＳ１０８では、配置点決定部１８が、ステップＳ１０７で配置された部品の配置可能範囲線分を線分情報記憶部１３から削除する。ここでは部品Ａの配置可能範囲線分を、図７（Ｃ）に示すように、線分情報記憶部１３から削除する。
【００５８】
ステップＳ１０９では、配置結果線分算出部１９が配置点決定部１８から、配置した部品の配置箇所の通知を受け、当該部品の部品基準点ごとに、配置結果線分（第２線分）を算出する。そして、配置結果線分算出部１９は、部品基準点ごとに計算した配置結果線分を線分情報記憶部１３に記録する。配置結果線分算出部１９は、たとえば部品の部品基準点ごとに第２線分を設定する線分設定手段を含む。
【００５９】
図９は、配置結果線分の計算例を説明する図である。ここでは、ある位置に配置された部品Ｇについて配置結果線分を計算する例が示される。
【００６０】
配置結果線分（第２線分）は、部品Ｇが利用する利用部品基準点によらず、４つ（全て）の部品基準点の各々に対して計算される。たとえばある部品基準点（Ｒ１とする）に対する配置結果線分は、部品基準点Ｒ１の対角に位置する部品基準点（Ｒ２とする）から、配置領域の辺との間で部品基準点Ｒ１を囲む矩形を形成するように、配置領域の端（辺）まで引いた２本の線分（水平線分と垂直線分）である。図中、Ｖ２が水平線分を示し、Ｈ２は水平線分を示す。配置結果線分は、配置された部品毎に、部品基準点数×(垂直線分＋水平線分)＝８本が作成される。
【００６１】
ここでは、部品Ａの配置結果線分が計算され、計算された配置結果線分は図７（Ｄ）に示す通りである。これらの配置結果線分（８本）が、線分情報記憶部１３に記録される。
【００６２】
ステップＳ１０１に戻り、部品配置装置は、全部品の配置が完了したかどうかを判定し、まだ部品Ｂの配置が完了していないため、ステップＳ１０２に進む。
【００６３】
ステップＳ１０２では、配置可能範囲線分算出部１５が、次に配置すべき部品Ｂの配置部品情報を配置部品情報記憶部１１から読み出す。
【００６４】
ステップＳ１０３では、配置可能範囲線分算出部１５が、部品Ｂの利用部品基準点（左上）および配置可能範囲に基づき、部品Ｂの利用部品基準点に対応する配置可能範囲線分を、図１０（Ａ）に示すように、計算する。そして、配置可能範囲線分算出部１５は、計算した配置可能範囲線分を、部品Ｂの利用部品基準点と対応づけて、線分情報記憶部１３に登録する。
【００６５】
ステップＳ１０４では、配置候補点算出部１６が、部品Ｂの配置候補点を計算する。具体的に、まず、配置候補点算出部１６が、配置部品情報記憶部１１から、部品Ｂの利用部品基準点を読み出し、読み出した利用部品基準点に一致する部品基準点に対応する配置結果線分（部品Ｂの前に配置された全ての部品の配置結果線分）と、部品Ｂの配置可能範囲線分（部品Ｂの利用基準点を位置づけ可能な領域の範囲端をなす複数の第１の線分）とを線分情報記憶部１３から取得する。次いで、配置候補点算出部１６は、取得した線分の交点を、平面走査法を利用して算出し、算出した交点を配置候補点として取得する。ただし、同一の部品から得られた配置結果線分（１本の水平線分と１本の垂直線分）の交点は、計算量を少なく抑えつつなるべく配置戦略に従う形で部品を配置するという観点から、配置候補点から除去してもよい。
【００６６】
ここでは、取得した線分は、部品Ｂの配置可能範囲線分（１本の垂直線分と１本の水平線分）と、部品Ａの配置結果線分「部品基準点：右上用」（１本の垂直線分、１本の水平線分）である。これらの線分の交点を求めると、図１０（Ｂ）に示すように、２つの配置候補点１、２が取得される。ただし、部品Ａの配置結果線分の交点Ｉは、上述の理由により、配置候補点から除いている。
【００６７】
ステップＳ１０５では、配置候補点ソート部１７が、ステップＳ１０４で取得された配置候補点を、部品Ｂの配置戦略に基づいてソートする。配置戦略と、ソート方法との対応表を図１１に示す。図１１の表は配置部品情報記憶部１１に記憶されている。
【００６８】
部品Ｂの配置戦略は、上述したように、「上から左詰め」である。「上から左詰め」に対応するソート方法は、「ｙ座標を降順にソート→ｘ座標を昇順にソート」である。これは、ｙ座標、ｘ座標の優先順位で、ｙ座標が降順、ｘ座標が昇順になるようにソートすることを意味する。x軸は紙面に沿って左から右向きの軸、y軸は紙面に沿って下から上向きの軸である。
【００６９】
したがって、ここでは、部品Ｂの配置候補点１、２をまずｙ座標で降順にソートすると、それぞれ同じｙ座標であるため優劣はない。そこで、次に、ｘ座標で昇順にソートすると、配置候補点１の方が配置候補点２よりもｘ座標が小さいため、配置候補点１、配置候補点２の順にソートされる。ｘ座標はたとえば横座標に対応し、ｙ座標はたとえば縦座標に相当する。
【００７０】
ステップＳ１０６では、配置点決定部１８が、配置部品情報記憶部１１から、部品Ｂの利用部品基準点を読み出し、また配置領域情報記憶部１２から矩形領域（部品配置領域）のサイズ情報を読み出し、各配置候補点１、２に利用部品基準点が合致するように部品Ｂを配置可能かどうか、配置結果記憶部１４を参照しつつ、ソートされた順番に調べる。具体的には、他の部品と重ならないように、配置可能範囲に配置可能かどうかを調べる。
【００７１】
ここではまず、配置候補点１と利用部品基準点とが一致するように部品Bを配置することを試みるが、部品Aと重なるので配置不可であると判断する。次に配置候補点２と利用部品基準点とが一致するように部品Bを配置することを試みると配置可能であることが分かるため、部品Bを配置候補点２に配置することを決定する。
【００７２】
ステップＳ１０７では、配置点決定部１８が、最初に見つかった配置候補点２に部品Ｂを配置する。すなわち、図１０（Ｃ）に示すように、利用部品基準点を配置候補点２に一致させるように部品Ｂを配置する。そして、部品Ｂを配置した箇所（配置結果）を配置結果記憶部１４に記録する。
【００７３】
ステップＳ１０８では、配置点決定部１８が、ステップＳ１０７で配置された部品Ｂの配置可能範囲線分を線分情報記憶部１３から削除する。
【００７４】
ステップＳ１０９では、配置結果線分算出部１９が配置点決定部１８から、部品Ｂの配置箇所の通知を受け、部品Ｂの部品基準点ごとに、配置結果線分（第２線分）を計算する。そして、配置結果線分算出部１９は、部品Ｂの部品基準点ごとに計算した配置結果線分を線分情報記憶部１３に記録する。
【００７５】
線分情報記憶部１３には、先に配置された部品Ａの配置結果線分も記憶されており、したがって、線分情報記憶部１３には、配置済みの全ての部品の配置結果線分が、部品基準点ごとに記録されている。現時点では、図１０（Ｄ）に示すように、部品基準点ごとに、部品Ａおよび部品Ｂの配置結果線分がそれぞれ記録されている。
【００７６】
次にステップＳ１０１に戻り、部品配置装置は、全ての部品の配置が完了したかどうかを判定する。配置する部品は部品Ａおよび部品Ｂのみであり、部品Ａおよび部品Ｂの配置は完了したため（ＹＥＳ）、処理を終了する。
【００７７】
上述の例では、部品Ａの利用部品基準点が右上、部品Ｂの利用部品基準点が左上であったため、配置結果線分は、右上および左上の部品基準点に対応するものだけを登録するようにしてもよい。つまり、配置するすべての部品のいずれの利用部品基準点にも合致しない部品基準点については、配置結果線分の計算を省略してもよい。
【００７８】
また上述の例では、部品の利用部品基準点の可動領域の辺（２本の垂直線分と、２本の水平線分）のうち、配置可能範囲の範囲端に一致する辺（１本の垂直線分と１本の水平線分）を、配置可能範囲線分（第１線分）として採用した。このように配置可能範囲の範囲端に一致する辺を採用したのは、できるだけ配置戦略に従う形で、部品を配置可能範囲に配置したいからである。たとえば、「左から下詰め」では、利用部品基準点が左下であり、また配置可能範囲内でできるだけ左下に部品を詰めたいため、可動領域の左辺と下辺（配置可能範囲の範囲端に一致する辺）上に配置候補点がある方が有利になる。ただし、「指定座標からの近接詰め」「指定座標からの遠方詰め」では、利用部品基準点の可動領域の辺の全て（２本の水平線分と、２本の垂直線分）を採用した方が、より好ましい配置案が得られる可能性が高くなる。したがって「指定座標からの近接詰め」「指定座標からの遠方詰め」の少なくともいずれかの配置戦略が適用される部品が存在するときは、可動領域の全ての辺（２本の水平成分と、２本の垂直線分）を配置可能範囲線分として採用することが好ましい。ただし辺の数が増えるとそれだけ計算量が増加するため、配置結果が得られるまでに要する時間が長くなる。
【００７９】
これまで説明してきた例と異なる例を用いて、配置候補点の計算と、配置候補点のソートについてさらに説明する。
【００８０】
図１２は、部品Ｐ１、Ｐ２、Ｐ３、Ｐ４を配置する例を示す。部品Ｐ１〜Ｐ３が配置済みで、いま、部品Ｐ４を配置しようとしているとする。
【００８１】
図中の配置候補点は、これから配置しようとする部品Ｐ４について計算された配置候補点である。部品Ｐ４の配置戦略は、「指定座標から近接詰め（利用部品基準点：左下）」であるとする。同じ部品から得られた配置結果線分（水平線分、垂直線分）の交点は、ここでは計算量低減の観点から、配置候補点から除かれている。
【００８２】
部品Ｐ４の配置候補点をソートする際、部品Ｐ４の配置戦略が「指定座標から近接詰め（利用部品基準点：左下）」であるため、これらの配置候補点を、指定座標との距離が短い順にソートする。仮に指定座標を部品Ｐ３の部品基準点（右上）とすると、配置候補点は、Ｓ１、Ｓ５、Ｓ４、Ｓ２、Ｓ３、Ｓ８、Ｓ９、Ｓ７、Ｓ６の順にソートされる。
【００８３】
以下、本発明の具体的な実施例として、電子機器としてのノート型PC(Personal Computer)の筐体内に
１．バッテリ
２．外部コネクタ1
３．外部コネクタ2
４．CPU(中央処理装置)
５．画像処理チップ（ＶＧＡ）
を配置する例を示す。
【００８４】
まず、各部品についてあらかじめ与えられた制約に基づいて、ノート型ＰＣの設計者が、各部品の配置可能範囲および配置戦略を決定する。各部品の配置順序は、上記に記載された順、すなわち、バッテリ→外部コネクタ1→外部コネクタ2→CPU(中央処理装置)→画像処理チップの順であるとする。
【００８５】
各部品についてあらかじめ与えられた制約は以下の通りであるとする。
（１）バッテリは筐体の奥側に接するように配置しなければならない
（２）外部コネクタ1は筐体の奥側に接するように配置しなければならない。また、できるだけバッテリから離して配置したい
（３）外部コネクタ2は右側面に接するように配置しなければならない。また、できるだけ手前側に配置したい
（４）CPUは筐体内のどこにでも配置可能だが、なるべく奥側に配置したい
（５）画像処理チップは筐体内のどこにでも配置可能だが、CPUと近接して配置しなければならない。
【００８６】
これらの制約を満たすように、ノート型ＰＣの設計者が、各部品の配置可能範囲を、たとえば図１３（Ａ）〜図１３（Ｅ）のように設定する。図１３（Ａ）がバッテリの配置可能範囲（およびバッテリ形状）、図１３（Ｂ）がコネクタ１の配置可能範囲（およびコネクタ１形状）、図１３（Ｃ）がコネクタ２の配置可能範囲（およびコネクタ２形状）、図１３（Ｄ）がＣＰＵの配置可能範囲（およびＣＰＵ形状）、図１３（Ｅ）が画像処理チップの配置可能範囲（および画像処理チップ形状）を示す。なお、図１３（Ａ）においてバッテリのｙ軸方向の幅と、バッテリの配置可能範囲のｙ軸方向の幅とは等しい。また図１３（Ｂ）においてコネクタ１のｙ軸方向の幅と、コネクタ１の配置可能範囲のｙ軸方向の幅とは等しい。また図１３（Ｃ）においてコネクタ２のｘ軸方向の幅と、コネクタ２の配置可能範囲のｘ軸方向の幅とは等しい。
【００８７】
また、ノート型ＰＣの設計者が、各部品の配置戦略を、たとえば次の表のように決める。
【表１】
0005075576.tif 000002
【００８８】
以上のように、配置可能範囲および配置戦略を決定することにより、各部品についてあらかじめ与えられたすべての制約が満たされる。この後、本実施形態で示した方法を用いて各部品を配置すると、図１４のような配置結果が高速に得られる。筐体枠（配置領域）内に、各部品が各々の配置可能範囲内で、かつ重なりなく配置されていることが理解される。
【図面の簡単な説明】
【００８９】
【図１】本発明の一実施の形態にしたがった部品配置装置の構成を示すブロック図。
【図２】図１の部品配置装置の動作の流れを示すフローチャート。
【図３】配置戦略群１を説明する図。
【図４】部品基準点の例を示す図。
【図５】配置戦略と利用部品基準点との対応表を示す図。
【図６】配置戦略群２を説明する図。
【図７】部品Ａの配置位置を決定する過程を示す図。
【図８】配置可能範囲線分の計算例を示す図。
【図９】配置結果線分の計算例を示す図。
【図１０】部品Ｂの配置位置を決定する過程を示す図。
【図１１】配置戦略と、ソート方法との対応表を示す図。
【図１２】配置候補点の算出例および配置候補点のソート例を示す図。
【図１３】本発明の具体的な実施例において各部品の配置可能範囲を示す図。
【図１４】本発明の具体的な実施例により部品を配置した結果を示す図。
【符号の説明】
【００９０】
１１：配置部品情報記憶部
１２：配置領域情報記憶部
１３：線分情報記憶部
１４：配置結果記憶部
１５：配置可能範囲線分算出部（部品選択手段、線分取得手段）
１６：配置候補点算出部（候補点算出手段）
１７：配置候補点ソート部（ソート手段）
１８：配置点決定部（部品配置手段）
１９：配置結果線分算出部（線分設定手段）
２０：入力情報記憶部（入力受付手段）
Ｖ１、Ｈ１：配置可能範囲線分（第１線分）
Ｖ２、Ｈ２：配置結果線分（第２線分）
【図１】
0005075576.tif 000003
【図２】
0005075576.tif 000004
【図３】
0005075576.tif 000005
【図４】
0005075576.tif 000006
【図５】
0005075576.tif 000007
【図６】
0005075576.tif 000008
【図７】
0005075576.tif 000009
【図８】
0005075576.tif 000010
【図９】
0005075576.tif 000011
【図１０】
0005075576.tif 000012
【図１１】
0005075576.tif 000013
【図１２】
0005075576.tif 000014
【図１３】
0005075576.tif 000015
【図１４】
0005075576.tif 000016