すべての点を囲む最小の円の中心と半径を計算
平面上の点の座標(x, y)から、すべての点を囲むいちばん小さい円(最小包含円)の中心と半径を計算します。中心は「いちばん遠い点までの距離が最も短くなる場所」なので、1か所からいくつもの地点へ行くときの、最遠距離を最小にする位置の目安になります。図をクリックして点を足したり、点を動かしたりもできます。
- 最小の円は、いちばん外側にある2点か3点で決まります。円はいつも1つに決まります。
- 2点で決まるとき:中心は2点の中点、半径は2点の距離の半分です。
- 3点で決まるとき:3点を通る円(外接円)です。3点の三角形は鋭角三角形で、中心はその内側にあります。鈍角三角形の外接円は、最小の円ではありません。
計算結果
点の一覧(中心から遠い順)
ほかの中心の決め方と比べる
計算の方法と検算
すべての点を囲む最小の円とは
平面上にいくつかの点があるとき、全部の点を内側(円周の上を含む)に入れる円のうち、半径がいちばん小さいものを最小包含円(最小包囲円とも呼ばれます)といいます。このような円は、点の並び方にかかわらずいつもただ1つに決まります(Welzl, 1991)。
円の中心は、「そこからいちばん遠い点までの距離」が最も短くなる場所で、半径はそのいちばん遠い点までの距離です。たとえば、1か所の拠点からいくつかの配達先へ向かうとき、いちばん遠い配達先までの直線距離をできるだけ短くしたい、という問題と同じ形をしています。平面上のいくつかの点からの最大の距離を最小にする位置を求める問題は、施設の配置の問題(ミニマックス型の配置)としても研究されてきました(Elzinga と Hearn, 1972)。
ほかにも、1か所から全部の地点を覆うのに必要な範囲(半径)を見積もる、穴やピンの位置を全部囲む円形の部品の大きさを決める、といった場面で使えます。
円は2点か3点で決まる
最小の円は、円周の上にある2点か3点だけで決まります(Welzl, 1991)。ほかの点は、円の内側にある限り、動かしても消しても円は変わりません。
- 2点で決まるとき……2点が円の直径の両端にあります。中心は2点の中点、半径は2点の距離の半分です。
- 3点で決まるとき……3点を通る円(外接円)です。このとき3点がつくる三角形は鋭角三角形で、中心は三角形の内側にあります。
よくある間違いは「3点を囲む最小の円=外接円」と考えることです。(0, 0)・(10, 0)・(5, 1) の3点は、(5, 1) の角が鈍角の三角形をつくります。この3点の外接円は中心 (5, −12)、半径13ですが、最小の円は (0, 0) と (10, 0) を直径の両端とする中心 (5, 0)・半径5の円で、(5, 1) はその内側に入ります。三角形に直角か鈍角があるときは、いちばん長い辺を直径とする円が最小です。
正三角形 (0, 0)・(2, 0)・(1, √3) では3点を通る円が最小で、中心は (1, 0.57735)、半径は 1.1547(2/√3)です。「例を入れる」の「正三角形」で確かめられます。
計算例:6つの地点を1つの円で囲む
6つの地点 (0, 0)・(8, 0)・(4, 8)・(2, 3)・(6, 5)・(7, 2)(単位はkm)を考えます。ページを開いたときの入力がこの例です。最小の円は (0, 0)・(8, 0)・(4, 8) の3点を通り、中心 (4, 3)、半径 5 kmです。残りの3点は、中心から 2〜3.16 km のところにあります。
中心をほかの決め方で置くと、全部を囲むのに必要な半径は大きくなります。
| 中心の決め方 | 中心 | 全部を囲むのに必要な半径 |
|---|---|---|
| 最小の円の中心 | (4, 3) | 5 km |
| 6点の平均の位置(重心) | (4.5, 3) | 5.41 km |
| 外枠の長方形の中央 | (4, 4) | 5.66 km |
| いちばん離れた2点の中点 | (2, 4) | 7.21 km |
いちばん離れた2点は (0, 0) と (4, 8) で、距離は 8.94 km です((8, 0) と (4, 8) も同じ距離)。この2点の中点 (2, 4) を中心に、距離の半分の 4.47 km の円をかくと、(8, 0) と (7, 2) がはみ出します。「いちばん離れた2点を直径とする円」で足りるのは、円が2点で決まるときだけです。
一般に、最小の円の半径は、いちばん離れた2点の距離 D の半分以上で、D を √3 で割った値以下です(平面の場合。Jung, 1901)。この例では 4.47 ≤ 5 ≤ 5.16 です。上限になるのは、3点が正三角形に並ぶときです。
結果の読み方
- 半径……中心から、いちばん遠い点までの直線距離です。どこに中心を置いても、全部を囲むにはこれ以上の半径が必要です。
- 中心……入力と同じ単位・同じ向きの座標で表示します。
- 円を決める点……円周の上にあって円を決めている2点か3点です。円周の上にほかの点がないときは、この点のどれかを円の内側へ動かすと、円は小さくなります。正方形の4つの角のように円周の上にほかの点もあるときは、1点を動かしても円が変わらないことがあります。
- 円周上……正方形の4つの角のように、円を決める点のほかにも円周の上にちょうど乗る点があれば、一覧に「円周上」と表示します。
- 半径 R で確かめる……半径を入れると、その半径の円で全部を囲めるかがわかります。中心も入れると、その場所を中心にした円からはみ出す点を一覧にします。今ある拠点から全部の地点が R 以内にあるか、を確かめるときに使います。
- 点の一覧……中心から遠い順に、中心からの距離と、円周までの残りの距離を表示します。
計算の方法と正確さ
このページは、Welzl(1991)のランダム化した逐次法で計算します。点を1つずつ加えていき、今の円の外にある点が来たら、その点は新しい最小の円の円周の上にある、という性質を使って円を作り直します。点を加える順番をランダムにすると、計算の手間は平均して点の数に比例します(期待線形時間)。最小の円を点の数に比例する時間で求める方法は、Megiddo(1983)が先に示しています。
原著の手順は自分自身を呼び出す(再帰の)形で書かれていますが、このページでは点が多くても止まらないように、同じ手順を3重のくり返しで書いています。並べ替えに使った乱数の種は結果の「計算の方法と検算」に表示し、入力の「計算の設定」で変えられます。種を変えても答えは変わりません。
計算の前に、点の範囲の中央を原点に移して大きさをそろえ、計算してから元に戻します。とても大きい座標や小さい座標でも、2乗の計算で数があふれたり消えたりしないようにするためです。3点がほぼ一直線に並ぶときは、外接円を作らずに、いちばん離れた2点の円を使います。
最後に2つの検算をします。1つ目に、中心からいちばん遠い点までの距離を半径にするので、全部の点が円に入ります。2つ目に、円周の上の点が中心のまわりを取り囲んでいる(どの半円にも収まらない)ことを確かめます。こうなっていれば、中心をどの向きに動かしても円周の上のどれかの点から遠ざかるので、これより小さい円はありません。座標はコンピューターのふつうの数(倍精度、約15〜17桁)で計算し、表示は円の大きさに合わせて有効数字6桁ほどにしています。
地図の上の地点で使うときの注意
- 緯度・経度は平面の座標ではありません……経度1度ぶんの東西の長さは、赤道から離れるほど短くなります。緯度・経度のまま入れると、東西と南北で縮尺の違う図で円をかくことになります。日本国内なら、国土地理院が示す平面直角座標系(全国を19の座標系に分けたもの。平成14年国土交通省告示第9号で定義)に直すと、メートル単位の平面の座標になります。国土地理院の測量計算サイトに平面直角座標への換算があります。
- 道のりや移動時間ではありません……計算するのは直線距離です。川・線路・山があると、実際の道のりはずっと長くなることがあります。
- 中心がよい場所とは限りません……中心は計算で決まる位置なので、川や海の上、建物を建てられない土地になることもあります。候補の場所を決めたら、「半径 R で確かめる」に中心の座標を入れて、いちばん遠い地点までの距離を比べてください。
- 「合計の距離」が最も小さい場所とは違います……最小の円の中心は、いちばん遠い点だけを見て決まります。全員の移動距離の合計を小さくしたいときは、別の考え方(距離の合計を最小にする点)になり、答えの場所も変わります。
この計算が扱わないこと
- 地球の表面の距離・道路の距離……平面上の直線距離だけです。
- 点ごとの重み……大事な地点を優先する、件数の多い地点に近づける、といった重みは付けられません。
- 2つ以上の円……拠点を2か所以上置いて、それぞれの円で分けて囲む計算はしません。
- 外れた点の扱い……ほかから遠く離れた点が1つでもあると、その点に合わせて円が大きくなります。その点を入れるかどうかは、目的に合わせて決めてください。
- 立体(球)……3次元の点を囲む最小の球は計算しません。
実際に拠点の場所を決めるときは、道のり、土地の条件、費用なども合わせて確かめてください。
よくある質問
最小包含円とは何ですか?
3点を囲む最小の円は、外接円と同じですか?
最小の円の中心は、点の平均(重心)とは違うのですか?
いちばん離れた2点の中点を中心にすれば、最小の円になりますか?
緯度・経度のまま入力してもいいですか?
拠点を置くのにいちばんよい場所がわかりますか?
点が一直線に並んでいるときや、同じ点が重なっているときは?
何点まで計算できますか?計算は正確ですか?
関連するツール
計算式と出典
- Welzl E. Smallest enclosing disks (balls and ellipsoids). In: Maurer H, ed. New Results and New Trends in Computer Science. Lecture Notes in Computer Science 555. Springer; 1991:359-370. doi:10.1007/BFb0038202(ランダム化した逐次法、最小の円がただ1つに決まること、円周上の3点以内で決まること、期待線形時間)
- Megiddo N. Linear-Time Algorithms for Linear Programming in R3 and Related Problems. SIAM Journal on Computing 1983;12(4):759-776. doi:10.1137/0212052(点を囲む最小の円を点の数に比例する時間で求める方法)
- Elzinga J, Hearn DW. Geometrical Solutions for Some Minimax Location Problems. Transportation Science 1972;6(4):379-394. doi:10.1287/trsc.6.4.379(いくつかの点からの最大の距離を最小にする位置の問題)
- Jung H. Ueber die kleinste Kugel, die eine räumliche Figur einschliesst. Journal für die reine und angewandte Mathematik 1901;123:241-257. doi:10.1515/crll.1901.123.241(直径1の点の集まりを囲む最小の球の半径は √(n/(2(n+1))) 以下。平面(n=2)では 1/√3)
- 岡本吉央「離散最適化基礎論 第2回 最小包囲円問題(1):基本的な性質」電気通信大学 講義資料, 2017年10月20日(「最小包囲円」という呼び方。2026年10月6日確認)
- 国土地理院「わかりやすい平面直角座標系」「平面直角座標への換算」(2026年10月6日確認)
計算は、Welzl の方法を再帰を使わないくり返しで書いたものです(入力の順番を種つきの乱数で並べ替え)。計算の前に点の範囲の中央を原点に移して大きさをそろえ、3点がほぼ一直線のときは、いちばん離れた2点の円を使います。半径は中心から全点までの距離の最大で、円周上の点がどの半円にも収まらないことを確かめて、これより小さい円がないことを検算しています。いちばん離れた2点は、外周の点(凸包)どうしを比べて求めています。結果は入力した座標にもとづく平面上の数学の値で、実際の道のりや場所の良し悪しを示すものではありません。