(57)【特許請求の範囲】
【請求項１】
コンピュータを用いて、複数の線材を互いに重ならないようにできるだけ小さい円形状に束ねてパッキングしてその外径を取得するための算出方法であって、
前記複数の線材の断面形状をそれぞれの外形に対応した直径を有する複数の円とみなして、平面上に互いに重ならないように配置される前記複数の円を包含する包含円を想定する包含円想定工程と、
前記包含円と同じ中心を有し、かつこの包含円より少し小さく、少なくとも、前記複数の円のうちのひとつがはみ出す目標円を定める目標円定義工程と、
前記目標円からはみ出している円を挿込試行円とし、前記挿込試行円以外の前記複数の円が、互いに重なることなく前記目標円内でできるだけ遠くに移動可能な位置を探索する探索工程と、
前記探索工程による探索結果に基づいて前記複数の円を配置変更することによりできる前記目標円内のスペースに前記挿込試行円を挿し込む挿込工程と、
前記挿込試行円のすべてが前記目標円内に挿し込まれた場合には、現在よりも少し小さく、かつ前記挿込試行円を有する新たな前記目標円を定めたうえで、前記探索工程に戻る第１探索制御工程、を含み、
前記目標円定義工程、前記探索工程、前記挿込工程及び前記第１探索制御工程を繰り返し実行することにより、前記包含円を徐々に小さくしていく、
ことを特徴とする線材パッキング算出方法。
【請求項２】
請求項１記載の線材パッキング算出方法において、
前記探索工程では、
前記挿込試行円及び前記複数の円のうちのひとつを除いた円群と、前記目標円と、で円ボロノイ図を作成し、前記円ボロノイ図における各境界辺を形成する両側円に接する前記ひとつの円の中心が、前記境界辺上にあるか否かを前記挿込試行円以外の前記複数の円に対して調べていくことにより、これらの円が前記目標円内で移動可能である位置を探索する、
ことを特徴とする線材パッキング算出方法。
【請求項３】
請求項１又は請求項２記載の線材パッキング算出方法において、
前記目標円定義工程、前記探索工程、前記挿込工程及び前記第１探索制御工程と共に繰り返し実行され、
前記挿込試行円の挿し込みが不可能である場合には、前記包含円と現在の前記目標円との中間的な大きさであって、かつ前記挿込試行円を有する他の新たな前記目標円を定めたうえで、前記探索工程に戻る第２探索制御工程、
を更に含むことを特徴とする線材パッキング算出方法。
【請求項４】
複数の線材を互いに重ならないようにできるだけ小さい円形状に束ねてパッキングしてその外径を算出するための装置であって、
前記複数の線材の断面形状をそれぞれの外形に対応した直径を有する複数の円とみなして、平面上に互いに重ならないように配置される前記複数の円を包含する包含円を想定する包含円想定手段と、
前記包含円と同じ中心を有し、かつこの包含円より少し小さく、少なくとも、前記複数の円のうちのひとつがはみ出す目標円を定める目標円定義手段と、
前記目標円からはみ出している円を挿込試行円とし、前記挿込試行円以外の前記複数の円が、互いに重なることなく前記目標円内でできるだけ遠くに移動可能な位置を探索する探索手段と、
前記探索手段による探索結果に基づいて前記複数の円を配置変更することによりできる前記目標円内のスペースに前記挿込試行円を挿し込む挿込手段と、
前記挿込試行円のすべてが前記目標円内に挿し込まれた場合には、現在よりも少し小さく、かつ前記挿込試行円を有する新たな前記目標円を定めたうえで、前記探索手段による探索を行わせる第１探索制御手段と、
前記複数の線材に関する初期情報を入力する入力手段と、
少なくとも、前記包含円の外径を出力する出力手段と、
を含むことを特徴とする線材パッキング算出装置。
【請求項５】
請求項４記載の線材パッキング算出装置において、
前記出力手段は、
前記包含円及び前記複数の円のそれぞれの位置情報も出力する、
ことを特徴とする線材パッキング算出装置。
【請求項６】
請求項４又は請求項５記載の線材パッキング算出装置において、
前記探索手段は、
前記挿込試行円及び前記複数の円のうちのひとつを除いた円群と、前記目標円と、で円ボロノイ図を作成し、前記円ボロノイ図における各境界辺を形成する両側円に接する前記ひとつの円の中心が、前記境界辺上にあるか否かを前記挿込試行円以外の前記複数の円に対して調べていくことにより、これらの円が前記目標円内で移動可能である位置を探索する第２探索手段、
を含むことを特徴とするパッキング算出装置。
【請求項７】
請求項４、請求項５、又は請求項６記載の線材パッキング算出装置において、
前記挿込試行円の挿し込みが不可能である場合には、前記包含円と現在の前記目標円との中間的な大きさであって、かつ前記挿込試行円を有する他の新たな前記目標円を定めたうえで、前記探索手段による探索を行わせる第２探索制御手段、
を更に含むことを特徴とする線材パッキング算出装置。
【請求項８】
複数の線材を互いに重ならないようにできるだけ小さい円形状に束ねてパッキングしてその外径を算出するために、コンピュータを、
前記複数の線材の断面形状をそれぞれの外形に対応した直径を有する複数の円とみなして、平面上に互いに重ならないように配置される前記複数の円を包含する包含円を想定する包含円想定手段、
前記包含円と同じ中心を有し、かつこの包含円より少し小さく、少なくとも、前記複数の円のうちのひとつがはみ出す目標円を定める目標円定義手段、
前記目標円からはみ出している円を挿込試行円とし、前記挿込試行円以外の前記複数の円が、互いに重なることなく前記目標円内でできるだけ遠くに移動可能な位置を探索する探索手段、
前記探索手段による探索結果に基づいて前記複数の円を配置変更することによりできる前記目標円内のスペースに前記挿込試行円を挿し込む挿込手段、
前記挿込試行円のすべてが前記目標円内に挿し込まれた場合には、現在よりも少し小さく、かつ前記挿込試行円を有する新たな前記目標円を定めたうえで、前記探索手段による探索を行わせる第１探索制御手段、
前記複数の線材に関する初期情報を入力する入力手段、
少なくとも、前記包含円の外径を出力する出力手段、として機能させる、
ことを特徴とする線材パッキング算出プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の線材をできるだけ小さい円形状に束ねてパッキングしてその外径を取得するための算出方法、その装置及びそのプログラムに関する。
【０００２】
【従来の技術】
車両や屋内には、複数の電線等の線材が束ねられて構成され、電子機器、電子部品等を電気的に接続するワイヤーハーネスとよばれるワイヤー様構造物が配策されている。このようなワイヤーハーネスは、近年、スペース効率向上等の観点から、電気的特性を低下させず、かつできるだけコンパクトなものが求められている。これにともない、設計段階において、より正確にワイヤーハーネスの外径を計算する必要がでてくるが、従来、その計算は、経験や以下に示す算出方法により行われていたのみであり、特に、有効な算出方法は提案されていなかった。
【０００３】
以下に、図８を用いて、従来のワイヤーハーネスの外径の算出方法による問題点を示す。図８（ａ）は比較的少ない線材で構成されるワイヤーハーネスを示し、図８（ｂ）は比較的多い線材で構成されるワイヤーハーネスを示す図である。
【０００４】
従来の算出方法においては、図８（ａ）に示すように、ｎ本の線材ａiが与えられた時、これら線材ａi及びこれら線材ａiで構成されるワイヤーハーネス１０の断面を円形とみなし、これら線材ａiで構成されるワイヤーハーネス１０の直径Ｌを、
πＬ2／４＝ＫΣ（πｌi2／４）という式に基づき求める。
ここで、ｌiは線材ａiの直径を示し、Ｋはすきま係数を示す。上記すきま係数Ｋは、様々な線材の数や配置にそれぞれ適合するようにそれぞれ求めるのは困難であるため、ワイヤーハーネス１０を構成する線材の数や配置によらず、すべての場合に対して常に一定の値が用いられる。
【０００５】
ところが、図８（ａ）及び図８（ｂ）に示すように、同等の直径Ｌをもつワイヤーハーネスでも、構成される線材ａi、ａ′iの数や配置によって、それらのすきま１１、１１′の面積は異なることは明らかである。それにも拘わらず、上記のように常に一定の値のすきま係数Ｋを用いてその直径Ｌを求めると、その値は不正確なものになってしまい、実用的ではなかった。
【０００６】
【非特許文献１】
Ａ．オカベ，Ｂ．ブーツ，Ｋ．スギハラ  アンド  Ｓ．Ｎ．チョイ（Ａ．Ｏｋａｂｅ，  Ｂ．Ｂｏｏｔｓ，  Ｋ．Ｓｕｇｉｈａｒａａｎｄ  Ｓ．Ｎ．Ｃｈｏｉ）著，「スペーシアル  テセレーションズ−コンセプツ  アンド  アプリケーションズ  オブ  ボロノイ  ダイアグラムズ（Ｓｐａｔｉａｌ  Ｔｅｓｓｅｌｌａｔｉｏｎｓ  −Ｃｏｎｃｅｐｔｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆＶｏｒｏｎｏｉ  Ｄｉａｇｒａｍｓ）」，第２版，ジョン  ワイリーアンド  サンズ，チチェスター（Ｊｏｈｎ  Ｗｉｌｅｙ  ａｎｄＳｏｎｓ，Ｃｈｉｃｈｅｓｔｅｒ），２０００年
【非特許文献２】
Ｄ．Ｓ．キム  アンド  Ｋ．スギハラ（Ｄ．Ｓ．Ｋｉｍ  ａｎｄＫ．Ｓｕｇｉｈａｒａ）著，「ボロノイ  ダイアグラム  オブ  アサークル  セット  フロム  ボロノイ  ダイアグラム  オブ  ア  ポイント  セット，Ｉ（Ｖｏｒｏｎｏｉ  ｄｉａｇｒａｍ  ｏｆ  ａｃｉｒｃｌｅ  ｓｅｔ  ｆｒｏｍ  Ｖｏｒｏｎｏｉ  ｄｉａｇｒａｍｏｆ  ａ  ｐｏｉｎｔ  ｓｅｔ，Ｉ）」，第１８巻，トポロジー  コンピュータ  エイディッド  ジオメトリック  デザイン（Ｔｏｐｏｌｏｇｙ  Ｃｏｍｐｕｔｅｒ  ＡｉｄｅｄＧｅｏｍｅｔｒｉｃ  Ｄｅｓｉｇｎ），２００１年，ｐｐ．５４１−５６２
【非特許文献３】
Ｄ．Ｓ．キム  アンド  Ｋ．スギハラ（Ｄ．Ｓ．Ｋｉｍ  ａｎｄＫ．Ｓｕｇｉｈａｒａ）著，「ボロノイ  ダイアグラム  オブ  アサークル  セット  フロム  ボロノイ  ダイアグラム  オブ  アポイント  セット，II（Ｖｏｒｏｎｏｉ  ｄｉａｇｒａｍ  ｏｆ  ａｃｉｒｃｌｅ  ｓｅｔ  ｆｒｏｍ  Ｖｏｒｏｎｏｉ  ｄｉａｇｒａｍｏｆ  ａ  ｐｏｉｎｔ  ｓｅｔ，II）」，第１８巻，ジオメトリ．コンピュータ  エイディッド  ジオメトリック  デザイン（Ｇｅｏｍｅｔｒｙ．Ｃｏｍｐｕｔｅｒ  ＡｉｄｅｄＧｅｏｍｅｔｒｉｃ  Ｄｅｓｉｇｎ），２００１年，ｐｐ．５６３−５８５
【０００７】
【発明が解決しようとする課題】
このように、従来、任意の数の線材で構成されるワイヤーハーネスの外径を求めるための実用的な方法はなく、いうまでもなく、それらをできるだけ小さい円形状に束ねてパッキングした際のワイヤーハーネスの外径を取得するための有効な算出方法もなかった。
【０００８】
よって本発明は、上述した現状に鑑み、任意の数の複数の線材をできるだけ小さい円形状に束ねてパッキングしてその外径を取得するために有効な算出方法、その装置及びそのプログラムを提供することを課題としている。
【０００９】
【課題を解決するための手段】
上記課題を解決するためになされた請求項１記載の線材パッキング算出方法は、コンピュータを用いて、複数の線材を互いに重ならないようにできるだけ小さい円形状に束ねてパッキングしてその外径を取得するための算出方法であって、前記複数の線材の断面形状をそれぞれの外形に対応した直径を有する複数の円とみなして、平面上に互いに重ならないように配置される前記複数の円を包含する包含円を想定する包含円想定工程と、前記包含円と同じ中心を有し、かつこの包含円より少し小さく、少なくとも、前記複数の円のうちのひとつがはみ出す目標円を定める目標円定義工程と、前記目標円からはみ出している円を挿込試行円とし、前記挿込試行円以外の前記複数の円が、互いに重なることなく前記目標円内でできるだけ遠くに移動可能な位置を探索する探索工程と、前記探索工程による探索結果に基づいて前記複数の円を配置変更することによりできる前記目標円内のスペースに前記挿込試行円を挿し込む挿込工程と、前記挿込試行円のすべてが前記目標円内に挿し込まれた場合には、現在よりも少し小さく、かつ前記挿込試行円を有する新たな前記目標円を定めたうえで、前記探索工程に戻る第１探索制御工程、を含み、前記目標円定義工程、前記探索工程、前記挿込工程及び前記第１探索制御工程を繰り返し実行することにより、前記包含円を徐々に小さくしていく、ことを特徴とする。
【００１０】
請求項１記載の発明によれば、コンピュータを用いて、上記目標円定義工程、探索工程、挿込工程及び第１探索制御工程を繰り返し実行することにより、複数の線材の包含円を徐々に小さくしていく。これにより、複数の線材を囲む円の外径が効率的に取得される。
【００１１】
上記課題を解決するためになされた請求項２記載の線材パッキング算出方法は、請求項１記載の線材パッキング算出方法において、前記探索工程では、前記挿込試行円及び前記複数の円のうちのひとつを除いた円群と、前記目標円と、で円ボロノイ図を作成し、前記円ボロノイ図における各境界辺を形成する両側円に接する前記ひとつの円の中心が、前記境界辺上にあるか否かを前記挿込試行円以外の前記複数の円に対して調べていくことにより、これらの円が前記目標円内で移動可能である位置を探索する、ことを特徴とする。
【００１２】
請求項２記載の発明によれば、円ボロノイ図を利用することにより、挿込試行円の移動候補位置探索が非常に簡便化される。
【００１３】
上記課題を解決するためになされた請求項３記載の線材パッキング算出方法は、請求項１又は請求項２記載の線材パッキング算出方法において、前記目標円定義工程、前記探索工程、前記挿込工程及び前記第１探索制御工程と共に繰り返し実行され、前記挿込試行円の挿し込みが不可能である場合には、前記包含円と現在の前記目標円との中間的な大きさであって、かつ前記挿込試行円を有する他の新たな前記目標円を定めたうえで、前記探索工程に戻る第２探索制御工程、を更に含むことを特徴とする。
【００１４】
請求項３記載の発明によれば、挿込試行円の挿し込みが不可能である場合には、包含円と現在の目標円との中間的な大きさの目標円を定めたうえで、探索工程に戻す第２探索制御工程を更に含むことにより、複数の線材を囲む円の外径がより効率的に取得される。
【００１５】
上記課題を解決するためになされた請求項４記載の線材パッキング算出装置は、複数の線材を互いに重ならないようにできるだけ小さい円形状に束ねてパッキングしてその外径を算出するための装置であって、前記複数の線材の断面形状をそれぞれの外形に対応した直径を有する複数の円とみなして、平面上に互いに重ならないように配置される前記複数の円を包含する包含円を想定する包含円想定手段と、前記包含円と同じ中心を有し、かつこの包含円より少し小さく、少なくとも、前記複数の円のうちのひとつがはみ出す目標円を定める目標円定義手段と、前記目標円からはみ出している円を挿込試行円とし、前記挿込試行円以外の前記複数の円が、互いに重なることなく前記目標円内でできるだけ遠くに移動可能な位置を探索する探索手段と、前記探索手段による探索結果に基づいて前記複数の円を配置変更することによりできる前記目標円内のスペースに前記挿込試行円を挿し込む挿込手段と、前記挿込試行円のすべてが前記目標円内に挿し込まれた場合には、現在よりも少し小さく、かつ前記挿込試行円を有する新たな前記目標円を定めたうえで、前記探索手段による探索を行わせる第１探索制御手段と、前記複数の線材に関する初期情報を入力する入力手段と、少なくとも、前記包含円の外径を出力する出力手段と、を含むことを特徴とする。
【００１６】
請求項４記載の発明によれば、入力手段にて複数の線材に関する初期情報を入力し、目標円定義手段、探索手段、挿込手段及び第１探索制御手段にて、徐々に複数の線材の包含円を小さくしていき、出力手段にてその包含円の外径を出力する。これにより、複数の線材を囲む円の外径が効率的に取得される。
【００１７】
上記課題を解決するためになされた請求項５記載の線材パッキング算出装置は、請求項４記載の線材パッキング算出装置において、前記出力手段５が、前記包含円及び前記複数の円のそれぞれの位置情報も出力する、ことを特徴とする。
【００１８】
請求項５記載の発明によれば、包含円及び複数の円のそれぞれの位置情報も出力されるので、複数の線材の配置も含めて、それらを囲む円の外径が効率的に取得される。
【００１９】
上記課題を解決するためになされた請求項６記載の線材パッキング算出装置は、請求項４又は請求項５記載の線材パッキング算出装置において、前記探索手段が、前記挿込試行円及び前記複数の円のうちのひとつを除いた円群と、前記目標円と、で円ボロノイ図を作成し、前記円ボロノイ図における各境界辺を形成する両側円に接する前記ひとつの円の中心が、前記境界辺上にあるか否かを前記挿込試行円以外の前記複数の円に対して調べていくことにより、これらの円が前記目標円内で移動可能である位置を探索する第２探索手段、を含むことを特徴とする。
【００２０】
請求項６記載の発明によれば、第２探索手段にて円ボロノイ図を利用することにより、挿込試行円の移動候補位置探索が非常に簡便化される。
【００２１】
上記課題を解決するためになされた請求項７記載の線材パッキング算出装置は、請求項４、請求項５、又は請求項６記載の線材パッキング算出装置において、前記挿込試行円の挿し込みが不可能である場合には、前記包含円と現在の前記目標円との中間的な大きさであって、かつ前記挿込試行円を有する他の新たな前記目標円を定めたうえで、前記探索手段による探索を行わせる第２探索制御手段、を更に含むことを特徴とする。
【００２２】
請求項７記載の発明によれば、第２探索制御手段にて挿込試行円の挿し込みが不可能である場合には、包含円と現在の目標円との中間的な大きさの目標円を定めたうえで、探索手段による探索を再度行わせることにより、複数の線材を囲む円の外径がより効率的に取得される。
【００２３】
上記課題を解決するためになされた請求項８記載の線材パッキング算出プログラムは、複数の線材を互いに重ならないようにできるだけ小さい円形状に束ねてパッキングしてその外径を算出するために、コンピュータを、前記複数の線材の断面形状をそれぞれの外形に対応した直径を有する複数の円とみなして、平面上に互いに重ならないように配置される前記複数の円を包含する包含円を想定する包含円想定手段、前記包含円と同じ中心を有し、かつこの包含円より少し小さく、少なくとも、前記複数の円のうちのひとつがはみ出す目標円を定める目標円定義手段、前記目標円からはみ出している円を挿込試行円とし、前記挿込試行円以外の前記複数の円が、互いに重なることなく前記目標円内でできるだけ遠くに移動可能な位置を探索する探索手段、前記探索手段による探索結果に基づいて前記複数の円を配置変更することによりできる前記目標円内のスペースに前記挿込試行円を挿し込む挿込手段、前記挿込試行円のすべてが前記目標円内に挿し込まれた場合には、現在よりも少し小さく、かつ前記挿込試行円を有する新たな前記目標円を定めたうえで、前記探索手段による探索を行わせる第１探索制御手段、前記複数の線材に関する初期情報を入力する入力手段、少なくとも、前記包含円の外径を出力する出力手段、として機能させる、ことを特徴とする。なお、この請求項８の発明にも、同様に、上記請求項５〜請求項７の発明の主旨を付加することが可能である。
【００２４】
請求項８記載の発明によれば、コンピュータを、目標円定義手段、探索手段、挿込手段、第１探索制御手段、入力手段及び出力手段として機能させることにより、徐々に複数の線材の包含円を小さくしていき、その包含円の外径を出力させる。
【００２５】
【発明の実施の形態】
以下、本発明の実施の形態を図面に基づいて説明する。
まず、図１を用いて、本線材パッキング算出方法を実現するためのハードウエア構成を説明する。図１は、本発明の算出方法及びその装置を実現するためのハードウエア構成の一例を示すブロック図である。
【００２６】
図１に示すように、そのハードウエア構成は、公知のパーソナルコンピュータや汎用コンピュータ等で実現される。このコンピュータは、入力装置１、Ｉ／Ｏ（入出力インターフェース回路）２、ＣＰＵ（Central Processing Unit）３、メモリ４、出力装置５及びリードライト装置６を含んで構成される。入力装置１、メモリ４、出力装置５及びリードライト装置６は、Ｉ／Ｏ２等を介して、ＣＰＵ３に電気的に接続されている。
【００２７】
入力装置１は、後述の処理においてその入力データを投入するのに用いられる、例えば、キーボードやマウスデバイスである。ＣＰＵ３は、入力装置１や出力装置５等を制御するための制御部３１及び後述の本算出方法に係る処理をメモリ４に格納されるプログラムにしたがって行う演算部３２を含んでいる。
【００２８】
メモリ４は、後述の後述の本算出方法に係る各処理に対応するプログラム等を格納するプログラムメモリ４１及びＣＰＵ３が行う各種処理のための作業領域が割り当てられた演算用メモリ４２を含んでいる。そして、出力装置５は、ＣＰＵ３が行った処理結果を出力する、例えば、モニタディスプレイや印字装置である。
【００２９】
リードライト装置６は、ＣＤＲＯＭ等の記録媒体７に格納される本発明に係る線材パッキング算出プログラム７ａ（例えば、後述する図２、図４、図５、図６に示すような処理手順のプログラム）を読み込み、これを上記プログラムメモリ４１に転送するための装置である。また、リードライト装置６は、算出結果を記録媒体７に書き込む機能も有する。なお、このコンピュータには、図示しないモデムボードやＬＡＮカード等の通信インターフェースが含まれていてもよい。
【００３０】
ＣＰＵ３は、リードライト装置６にて読み込まれた線材パッキング算出プログラム７ａをメモリ４のプログラムメモリ４１にインストールする。そして、電源投入後には、このプログラム７ａが立ちあがり、このコンピュータは線材パッキング算出装置として機能する。線材パッキング算出プログラム７ａは、上記構成を有する他のパーソナルコンピュータや汎用コンピュータ等にもインストール可能であり、インストール後は、そのコンピュータが線材パッキング算出装置として機能する。
【００３１】
なお、記録媒体７に格納される線材パッキング算出プログラム７ａは、請求項８に対応する。線材パッキング算出プログラム７ａは、ＣＤＲＯＭ等の記録媒体７のみならず、インターネットや専用回線、ＬＡＮ等の通信回線を経由して、このコンピュータに提供されたものであってもよい。
【００３２】
次に、図２〜図７を用いて、本発明の算出方法の一実施形態に係る処理手順について説明する。そこで、まず、図２を用いて、本算出方法の基本処理手順について説明する。図２は、本発明の算出方法の一実施形態に係る基本処理手順を示すフローチャートである。
【００３３】
本算出方法では、ワイヤーハーネスを構成する複数の線材の断面形状をそれぞれの外形に対応した直径を有する複数の円とみなし、これら円を断面にもつｎ本の円柱を束ねた時、その全体を囲む円の大きさを調べるという問題に帰着させる。実際的には、上記コンピュータを用いて、複数の線材をできるだけ小さい円形状に束ねてパッキングしてその外径を取得するための有効な算出方法を考える。
【００３４】
図２に示す基本処理においては、入力情報としては、ワイヤーハーネスを構成する電線等の複数の線材の断面形状をそれぞれの外形に対応したｎ個の円ｃ1、ｃ2、…、ｃnの半径ｒ1、ｒ2、…、ｒn、１より小さくて十分１に近い数ｐ、例えば、ｐ＝０．９５、及び十分小さい正数である終了基準値ε、例えば、終了基準値ε＝ｍｉｎ（（ｒ1、ｒ2、…、ｒn）／１００）が与えられる。
【００３５】
また、出力情報としては、ｎ個の円ｃ1、ｃ2、…、ｃnを互いに重ならないように詰め込める、なるべく小さい円の半径Ｒ、及びこのときの円Ｃ、円ｃ1、ｃ2、…、ｃnの位置情報が出力される。
【００３６】
このため、図２に示すステップＳ１においては、まず、円ｃ1、ｃ2、…、ｃnを互いに重ならないように平面上に配置し、それらを囲む大円、すなわち包含円Ｃを見つける。
【００３７】
次に、ステップＳ２、ステップＳ３及びステップＳ４においては、上記包含円Ｃと同じ中心を持ち、半径が包含円Ｃの上記ｐ倍である円、すなわち、目標円Ｄを定める。すなわち、ステップＳ２、ステップＳ３のＮ及びステップＳ４からなるループでは、包含円Ｃと同じ中心を有し、かつこの包含円Ｃより少し小さく、少なくとも、複数の円ｃ1、ｃ2、…、ｃnのうちのひとつが包含円Ｄからはみ出すような目標円Ｄを定める。なお、以下の処理過程では、円ｃ1、ｃ2、…、ｃnが目標円Ｄの中に入るように配置を変更していく。
【００３８】
次に、ステップＳ５においては、探索挿込処理を行う。すなわち、ここでは、目標円Ｄからはみ出している任意のひとつの円ｃiから、距離の大きい順に円ｃi以外の円を取り出し、より遠くへ置けるものはできるだけ遠くへ移動させ、そのような移動ができない場合は現位置に残す。そして、このような移動によりできたスペースにひとつのこの円ｃiを移動する、すなわち、挿し込むことを試みる。なお、このステップＳ３の処理については、図４〜図７を用いて後で説明を加える。
【００３９】
次に、ステップＳ６においては、上記ステップＳ５における円ｃiの挿し込みが成功したか否かを判定し、成功の場合はステップＳ３に戻り（ステップＳ６のＹ）、さもなければステップＳ７に進む（ステップＳ６のＮ）。ステップＳ３に戻ると、他にはみ出している円があるか否を判定し、これがあればこのはみ出している円に対して再度ステップＳ５の探索挿込処理を行い、なければステップＳ４に進んで上記と同様の処理を行うことになる。
【００４０】
一方、ステップＳ７においては、上記包含円Ｃと挿込みが成功しなかった上記目標円Ｄとの中間の大きさの円を、新たに目標円Ｄに定める。次に、ステップＳ８において、上記ステップＳ７の処理に用いられた包含円及び目標円Ｄのそれぞれの半径の差が上記終了基準値ε以下か否かを判定し、この差が終了基準値εより大きければ上記ステップＳ３に戻り上記と同様の処理を繰り返し（ステップＳ８のＮ）、この差が終了基準値ε以下であればステップＳ９に進む（ステップＳ８のＹ）。
【００４１】
ステップＳ９においては、この包含円Ｃの半径を最終的な、ワイヤーハーネスの半径Ｒとしてこれを出力装置５に出力する。また、このときの包含円Ｃ及び各円ｃ1、ｃ2、…、ｃnの位置情報も出力装置５に出力する。これら出力は、モニタディスプレイ上であってもよいし、紙上への印字であってもよい。なお、上記ｐ及び終了基準値εを適宜、若干変更してもよい。
【００４２】
上記処理手順による各円のふるまいを図３を用いて示す。図３は、図２の処理手順によるふるまいを示す図であり、特に、図３（ａ）は初期状態を示し、図３（ｂ）は目標円からはみ出した挿込試行円を示し、図３（ｃ）は図３（ｂ）の挿込試行円を目標円の内部に挿し込んだ様子を示し、そして、図３（ｄ）は最終結果を示す図である。
【００４３】
図３（ａ）においては、与えられたｎ個の円ｃiの初期配置と、それらを囲む包含円Ｃが示されている。図３（ｂ）においては、処理の途中の状態が示され、現在得られている包含円Ｃより少し小さい目標円Ｄ、及びこの目標円Ｄからはみ出す円のひとつであり、挿し込みが試行される挿込試行円ｃnが示されている。
【００４４】
また、図３（ｃ）においては、図３（ｂ）で示した挿込試行円ｃnに対して、図２に示したステップＳ５の探索挿込処理が施されたあとの状態が示されている。なお、図３（ｃ）中、円ｍi（粗斜線を囲む円群）は、上記探索挿込処理において挿込試行円ｃnを挿し込むために移動した移動円群を示している。なお、この図からわかるように、他のはみ出している円も、挿込試行円ｃnの挿込処理の過程で、目標円Ｄに入ることもある。そして、図３（ｄ）においては、すべてのはみだしている円に対して、挿込処理が行われた結果が示されている。
【００４５】
このように、ワイヤーハーネスを構成する複数の線材を、包含円からはみ出している線材からできるだけ遠くに配置変更し、これによりできたスペースにはみ出している線材を挿し込むという操作を繰り返し計算することにより、複数の線材を囲むワイヤーハーネスの外径が効率的に取得される。
【００４６】
次に、上記図２のステップＳ５の探索挿込処理について、図４を用いて説明を加える。図４は、図２における探索挿込処理を示すフローチャートである。
【００４７】
図４に示す探索挿込処理においては、入力情報として、ｎ個の円ｃiの半径ｒiと、それらの中心（ｘi、ｙi）、ｉ＝１、２、…、ｎ、及び目標円Ｄが与えられる。但し、ｎ個の円ｃiは互いに重なることはなく、また最後の円ｃnは目標円Ｄからはみ出しているとする。なお、この他にもはみ出している円があってもよい。
【００４８】
また、出力情報としては、既に目標円Ｄ内に入っている円をこの目標円Ｄからはみ出させることなく、最後の円ｃnを目標円Ｄ内へ挿し込むことができるなら成功結果としてそれを実現するｎ個の円の中心位置が出力され、できないなら失敗結果としてその旨示すメッセージが出力される。
【００４９】
まず、探索挿込処理のステップＳ５１においては、ｎ個の円ｃiを、上記最後の円ｃnから遠い順に並べ替える。この順は、詳しくは、ｎ個の円ｃiのそれぞれの中心と、最後の円ｃnの中心と、の距離に基づく。そして、ここで、並び替えた結果の円番号を、簡単のために、新ためてｃ1、ｃ2、…、ｃnとする。なお、以下、この最後の円を挿込試行円とよぶ。
【００５０】
次に、ｉ＝１、２、…、ｎ−１に対して、ステップＳ５２〜ステップＳ５４ａ（又はステップＳ５４ｂ）に示す処理を行う。ステップＳ５２においては、探索処理を行う。すなわち、円ｃiが、目標円Ｄ内で他の円と重ならずに移動可能な移動候補位置を探索する。詳しくは、この探索処理では、図５に示す第１探索処理、又は図６に示す第２探索処理が行われる。第１探索処理では、円ｃiが目標円Ｄ内で他の円と重ならずに、現在の円ｃiの位置より、挿込試行円ｃnから遠くなるような移動候補位置を探索する。また、図６に示す第２探索処理では、円ボロノイ図の概念を用いて、円ｃiが目標円Ｄ内で他の円と重ならずに移動可能な移動候補位置を探索する。これらについては後述する。
【００５１】
そして、ステップＳ５３及びステップＳ５４ａ、ステップＳ５４ｂにおいては、上記探索処理にて移動候補位置があればその中で挿込試行円ｃnから最も遠い位置へ円ｃiを移動し（ステップＳ５３のＹ、ステップＳ５４ａ）、移動候補位置がなければ円ｃiを現在位置に残す（ステップＳ５３のＮ、ステップＳ５４ｂ）。このような処理が、ｉ＝１、２、…、ｎ−１に対して行われた後、ステップＳ５５に進む。なお、上記ステップＳ５２〜ステップＳ５４が請求項の探索工程に対応している。
【００５２】
次に、ステップＳ５５においては、上記ステップＳ５２〜ステップＳ５４ａ（又はステップＳ５４ｂ）からなるループ処理にてできた目標円Ｄ内のスペースに対しての、挿込試行円ｃnの挿し込みを試行する。
【００５３】
そして、ステップＳ５６及びステップＳ５７ａ、ステップＳ５７ｂにおいては、上記挿し込みの試行により挿し込みが成功すれば、挿込試行円ｃnをそこへ移動し（ステップＳ５６のＹ、ステップＳ５７ａ）、挿し込みができなければ、その旨示すメッセージを出力する（ステップＳ５６のＮ、ステップＳ５７ｂ）。なお、上記成功時には、それを実現するｎ個の円の中心位置が出力される。そして、これらステップＳ５１〜ステップＳ５７ａ（又はステップＳ５７ｂ）からなる一連の処理が終了すれば、図２に示すこれに続く処理に戻る。
【００５４】
更に、図５及び図６を用いて、上記探索処理の２例について説明を加える。まず、第１探索処理を図５を用いて説明する。図５は、第１探索処理を示すフローチャートである。
【００５５】
図５の第１探索処理においては、ｎ個の円ｃiを移動するスペースがあった時、上記挿込試行円ｃnから最も遠くへ移動した状態では、円ｃiは２つの円に接しているはずであるということに着目している。但し、この接する２つの円のうちのひとつは、上記目標円Ｄの場合もある。そこで、ここでは、与えられたｎ個の円ｃiと目標円Ｄの全体がなす集合をＳ＝｛ｃ1、ｃ2、…、ｃn、Ｄ｝とおく。そして、円ｃi以外の全ての２つの円ｃj、ｃk∈Ｓに対して、以下のステップＳ５２１〜ステップＳ５２９に示す処理を行う。
【００５６】
まず、ステップＳ５２１においては、半径ｒiの円ｃiが、円ｃjと円ｃkの両方に接する位置を探す。但し、円ｃj又は円ｃkが目標円Ｄ以外の円なら外側から接し、目標円Ｄなら内側から接するものとする。そのような位置は、高々、２個しかなく、その場合の中心をそれぞれ（ｘ′i、ｙ′i）、（ｘ″i、ｙ″i）とする。
【００５７】
次に、ステップＳ５２２においては、上記２個のうちの一方の位置に移動させると、円ｃiは現在位置よりも挿込試行円Ｃnから遠くなるか否かを判定する。すなわち、一方の中心（ｘ′i、ｙ′i）から挿込試行円Ｃnの中心までの距離Ｘ′と、現在位置の円ｃiの中心から挿込試行円Ｃnの中心までの距離Ｘと、を比較し、距離Ｘ′が距離Ｘより大きければステップＳ５２３に進み（ステップＳ５２２のＹ）、さもなければ後述するステップＳ５２６に進む（ステップＳ５２２のＮ）。
【００５８】
ステップＳ５２３においては、円ｃi、円ｃj、円ｃk及び目標円Ｄ以外の全ての円に対して、半径ｒiの円ｃiを上記中心（ｘ′i、ｙ′i）に置いた時、重なるか否かを調べ、その重なりをステップＳ５２４において判定する。ここで、どの円とも重ならないと判定されればステップＳ５２５に進み（ステップＳ５２４のＮ）、ステップＳ５２５において上記中心（ｘ′i、ｙ′i）を円ｃiの移動候補位置のひとつに加え、さもなければステップＳ５２６に進む（ステップＳ５２４のＹ）。
【００５９】
更に、上記一方の中心（ｘ′i、ｙ′i）を他方の中心（ｘ″i、ｙ″i）に置き換えて、上記ステップＳ５２２〜ステップＳ５２５と同様、以下のステップＳ５２６〜ステップＳ５２９の処理を行う。ステップＳ５２６においては、上記２個のうちの他方の位置に移動させると、円ｃiは現在位置よりも挿込試行円Ｃnから遠くなるか否かを判定する。すなわち、他方の中心（ｘ″i、ｙ″i）から挿込試行円Ｃnの中心までの距離Ｘ″と、現在位置の円ｃiの中心から挿込試行円Ｃnの中心までの距離Ｘと、を比較し、距離Ｘ″が距離Ｘより大きければステップＳ５２７に進み（ステップＳ５２６のＹ）、さもなければ直接次に進む（ステップＳ５２６のＮ）。
【００６０】
ステップＳ５２８においては、円ｃi、円ｃj、円ｃk及び目標円Ｄ以外の全ての円に対して、半径ｒiの円ｃiを上記中心（ｘ″i、ｙ″i）に置いた時、重なるか否かを調べ、その重なりをステップＳ５２８において判定する。ここで、どの円とも重ならないと判定されればステップＳ５２９に進み（ステップＳ５２８のＮ）、ステップＳ５２９において上記中心（ｘ″i、ｙ″i）を円ｃiの移動候補位置のひとつに加え、さもなければ直接次に進む（ステップＳ５２８のＹ）。このような処理が、円ｃi以外の全ての２つの円ｃj、ｃkに対して行われると、図４に示すこれに続く処理に戻る。
【００６１】
このような、第１探索処理を用いることにより、従来、図８で示した方法や経験によりで行っていたワイヤーハーネスの外径の計算が改善されて、より正確に行えるようになる。したがって、ワイヤーハーネスの設計の一助となる。その一方で、第１探索処理を用いると、計算量が膨大になるという問題も生じる。すなわち、上記図５に示した第１探索処理では、円ｃi、円ｃj、円ｃkの組に対して、上記のような操作を行うので、その計算時間はＯ（ｎ3）となる。上記図４の探索挿入処理では、これをすべてのｉ＝１、２、…、ｎに対して行うので、その計算時間はＯ（ｎ4）となる。更に、図２の処理では、これを組み込んで繰り返し処理が行われるので、全体の計算量は、膨大なものになってしまう。これを以下の図６に示す第２探索処理では改善する。
【００６２】
図６は、第２探索処理を示すフローチャートである。図７（ａ）は円の集合の一例を示す図であり、図７（ｂ）及び図７（ｃ）はそれぞれ、図７（ａ）の円の集合に対する円ボロノイ図及びラゲール円ボロノイ図である。
【００６３】
まず、この第２探索処理の基本的な考え方を示す。この第２探索処理においては、公知のボロノイ図の概念を利用して、挿込試行円ｃiの移動候補位置の探索を効率化する。すなわち、上記第１探索処理においては、この円ｃiの移動候補位置を求めるために、すべての円の組ｃj、ｃkと接する位置を求めたが、ボロノイ図の概念を利用すると、その候補を限定することができる。
【００６４】
平面上に互いに重ならない有限個の円が与えられた時、どの円に最も近いかによって平面を分割することができる。この分割図形は円ボロノイ図とよばれ、これは、上記非特許文献１にも示されている。
【００６５】
例えば、図７（ａ）に示される円群に対する円ボロノイ図は、図７（ｂ）に示す通りである。図７（ｂ）におけるボロノイ辺とよばれる境界辺ｅj上の点は、２つの円ｃk、ｃlから等しい距離にあって、他の円はもっと遠くにあるという性質を持っている。したがって、２つ円ｃk、ｃlに接し、他の円と重ならない円は、円ボロノイ図の境界辺ｅj上に中心をもつことになる。よって、円ｃiの移動候補位置は、円ボロノイ図の境界辺ｅjを挟む２つの円ｃk、ｃlの組だけに対して探せばよい。ｎ個の円の円ボロノイ図の境界辺ｅjの数はｎに比例する本だから、検索すべき円ｃk、ｃlの組は、上記図５の第１探索処理がＯ（ｎ2）であるのに対し、ここでは、Ｏ（ｎ）になる。
【００６６】
更に、２つの円ｃk、ｃlと接する円ｃiの移動位置候補に対して、上記図５の第１探索処理では、円ｃi以外のすべての円ｃj、ｃkとの重なりの検査を行ったが、ここでは、その必要もなくなる。すなわち、円ｃiの移動候補位置が、境界辺ｅj上にあるか否かを調べれば十分である。なぜなら、境界辺ｅj上にあれば、他の円と重なることはなく、境界辺ｅj上になければ他の円と重なることが、円ボロノイ図の性質から導かれるからである。したがって、Ｏ（ｎ）の検査時間をＯ（１）にすることができる。
【００６７】
このような考え方に基づく、第２探索処理の処理手順は以下の図６に示すようになる。図６のステップＳ５２１′においては、まず、上記円集合Ｓ−｛ｃi｝、すなわち、円ｃi以外の全円に対する円ボロノイ図を作る。ここで、この円集合Ｓ−｛ｃi｝はｎ個の円で構成されるので、境界辺の数もｎに比例する。
【００６８】
そして、各境界辺ｅj、（ｊ＝１、２、…、ｎ）に対して、以下のステップＳ５２２′〜ステップＳ５２５′の処理を行う。
【００６９】
ステップＳ５２２′においては、境界辺ｅjの両側の円ｃk、ｃlに接する半径ｒiの円ｃ′iを作る。但し、ここでも、円ｃk又は円ｃlが目標円Ｄ以外の円なら外側から接し、目標円Ｄなら内側から接するものとする。なお、そのような円は、高々、２個、存在する。
【００７０】
そして、ステップＳ５２３′において上記のように接する半径ｒiの円ｃ′iが有りと判定され（ステップＳ５２３′のＹ）、更にステップＳ５２４′においてその中心が境界辺ｅj上に有ると判定されれば（ステップＳ５２４′のＹ）、ステップＳ５２５′に進んでこの円ｃ′iを円ｃiの移動候補位置に加える。さもなければ、直接次に進む（ステップＳ５２３′のＮ、ステップＳ５２４′のＮ）。このような処理が、すべての境界辺ｅjに対して行われると、図４に示すこれに続く処理に戻る。
【００７１】
上記説明から明らかなように、ボロノイ図の概念を利用することにより、円ｃiの移動候補位置の探索が非常に簡略化されることがわかる。ｎ個の円の円ボロノイ図は、Ｏ（ｎlogｎ）の計算時間で作ることができることが、上記非特許文献１に示されている。したがって、上記ステップＳ５２１′の処理は、Ｏ（ｎlogｎ）時間で実行できる。一方、ｎ個の円の円ボロノイ図の境界辺はｎに比例する本数しかないので、上記ステップＳ５２２′〜ステップＳ５２４′の処理は、Ｏ（ｎ）時間で実行できる。以上より、図６で示した第２探索処理の計算時間は、Ｏ（ｎlogｎ）となる。参考までに、上記図５で示した第１探索処理では、Ｏ（ｎ3）の計算時間を要したので、大きく効率向上していることがわかる。ちなみに、この図６の第２探索処理を、上記図４の探索挿込処理に組み込むと、上記図４の探索挿込処理では、この図６の処理をＯ（ｎ）回実行するので、図４の探索挿込処理の計算時間はＯ（ｎ2logｎ）となる。
【００７２】
なお、上記円ボロノイ図の簡便な計算法は、上記非特許文献１記載のラゲールボロノイ図を作り、次に、上記非特許文献２及び上記非特許文献３記載の辺のフリップ操作によって、これを円ボロノイ図に変更する方法である（図７（ｃ）参照）。
【００７３】
このように、本実施形態によると、コンピュータを用いて、ワイヤーハーネスを構成する複数の線材を、包含円からはみ出している線材からできるだけ遠くに配置変更し、これによりできたスペースにはみ出している線材を挿し込むという操作を繰り返し計算することにより、複数の線材を囲むワイヤーハーネスの外径が効率的に取得できる。特に、円ボロノイ図の概念を採用することにより、非常に簡便、かつ短時間で、ワイヤーハーネスの外径を取得することができるようになる。
【００７４】
なお、上記実施形態では、ワイヤーハーネスの外径を求めるために、半径を出力しているが、これは直径であってもよいことはいうまでもない。また、上記のようにワイヤーハーネスの半径を出力するだけでなく、各線材の配置を示す情報を出力するようにしてもよい。また、ｐ及びεの値は、上記実施形態で示した値に限定されず、本発明の主旨の範囲で適宜変更可能である。
【００７５】
【発明の効果】
以上説明したように、請求項１記載の発明によれば、コンピュータを用いて、上記目標円定義工程、探索工程、挿込工程及び第１探索制御工程を繰り返し実行することにより、複数の線材の包含円を徐々に小さくしていく。したがって、複数の線材を囲む円の外径を効率的に取得できる。
【００７６】
請求項２記載の発明によれば、円ボロノイ図を利用することにより、挿込試行円の移動候補位置探索が非常に簡便化される。したがって、複数の線材を囲む円の外径を短時間に取得できる。
【００７７】
請求項３記載の発明によれば、挿込試行円の挿し込みが不可能である場合には、包含円と現在の目標円との中間的な大きさの目標円を定めたうえで、探索工程に戻す第２探索制御工程を更に含んでいるので、複数の線材を囲む円の外径をより効率的に取得できる。
【００７８】
請求項４記載の発明によれば、入力手段にて複数の線材に関する初期情報を入力し、目標円定義手段、探索手段、挿込手段及び第１探索制御手段にて、徐々に複数の線材の包含円を小さくしていき、出力手段にてその包含円の外径を出力する。したがって、複数の線材を囲む円の外径を効率的に取得できる。
【００７９】
請求項５記載の発明によれば、包含円及び複数の円のそれぞれの位置情報も出力されるので、複数の線材の配置も含めて、それらを囲む円の外径が効率的に取得できる。
【００８０】
請求項６記載の発明によれば、第２探索手段にて円ボロノイ図を利用することにより、挿込試行円の移動候補位置探索が非常に簡便化される。したがって、複数の線材を囲む円の外径を短時間に取得できる。
【００８１】
請求項７記載の発明によれば、第２探索制御手段にて挿込試行円の挿し込みが不可能である場合には、包含円と現在の目標円との中間的な大きさの目標円を定めたうえで、探索手段による探索を再度行わせるようにしているので、複数の線材を囲む円の外径をより効率的に取得できる。
【００８２】
請求項８記載の発明によれば、コンピュータを、目標円定義手段、探索手段、挿込手段、第１探索制御手段、入力手段及び出力手段として機能させることにより、徐々に複数の線材の包含円を小さくしていき、その包含円の外径を出力させる。したがって、複数の線材を囲む円の外径を効率的に取得できる。
【図面の簡単な説明】
【図１】本発明の算出方法及びその装置を実現するためのハードウエア構成の一例を示すブロック図である。
【図２】本発明の算出方法の一実施形態に係る基本処理手順を示すフローチャートである。
【図３】図３（ａ）は初期状態を示し、図３（ｂ）は目標円からはみ出した挿込試行円を示し、図３（ｃ）は図３（ｂ）の挿込試行円を目標円の内部に挿し込んだ様子を示し、そして、図３（ｄ）は最終結果を示す図である。
【図４】図２における探索挿込処理を示すフローチャートである。
【図５】第１探索処理を示すフローチャートである。
【図６】第２探索処理を示すフローチャートである。
【図７】図７（ａ）は円の集合の一例を示す図であり、図７（ｂ）及び図７（ｃ）はそれぞれ、図７（ａ）の円の集合に対する円ボロノイ図及びラゲール円ボロノイ図である。
【図８】図８（ａ）は比較的少ない線材で構成されるワイヤーハーネスを示し、図８（ｂ）は比較的多い線材で構成されるワイヤーハーネスを示す図である。
【符号の説明】
１  入力装置
２  入出力インターフェース回路
３  ＣＰＵ
４  メモリ
５  出力装置
Ｃ  包含円
Ｄ  目標円
ｃn  挿込試行円
ｍn  移動円
ｅj  境界辺
【図１】
0004146296.tif 000002
【図２】
0004146296.tif 000003
【図３】
0004146296.tif 000004
【図４】
0004146296.tif 000005
【図５】
0004146296.tif 000006
【図６】
0004146296.tif 000007
【図７】
0004146296.tif 000008
【図８】
0004146296.tif 000009