真度円問

題

一一計算幾何学的アプローチ一一

榎原博之
111
川11111川川
11111川11111川111川川
11川
11川
11川
11川
11川
11111川川
111111川'"川川"川"川"川11 111川"川"川"川"川"川""'"川111川"川"川"川"川"川"川"川"川'"川"附"""川I川"川l川111川'"川"川"''''川"川"川"川"川'"川"川"川111川111川"川"附""川川"川"川"川"川"川"川"川川"川"川11 川"川11 川'"川'"川
11 川
11川"川"川"川"川
11 川
11川
11川
11川
11川
11川"川
11 川
11111附"'"川川
11川
11川
11川
11川
11川
11川"川"川11 川
11川"川"""川"川"川
11川
11川
11川
11川
11川"川"川11 川"川"川'"川'"川"川'"川"川
11
川
11川
11川
11川
11川"川"川"川"川""川"川"川"川"川"川"川"川"川""""川"川"川"川"川"川
11川
111"'''''11川"1川"川川
11川
11111'"l1.

はじめに機械部品の精度として重要な幾何公差(形状公差)の1 つに真円度 [15J と呼ばれるものがある.これは， r 円筒断面の輪郭を 2 つの同心円で挟んだとき，両円の間隔が最小となる両円の半径差J と定義されている [8J. 真円度
は，円形状の機械部品ーたとえば，ポールベアリング，エンジンのシリンダ，ピデオテープレコーダのロータリーヘッドなどーの精度を測定するためにはなくてはならないものであり，真円度測定機と呼ばれる装置によって測られる.

真円度測定機では，一般に輪郭形状を有限個の点集合

図 1

真円度問題に置き換えて計算機で処理するため，筆者らはこの真円度を求める問題を輿円度問題として次のように定式化し本稿では，筆者らが提案した真円度問題に対する多項式時間のアルゴリズムを述べ，それを実用的に効率の良Tこ [2J.

実円度問題:平面上に n 個の点、が与えられたとき，同心いものにするために，前処理として解の厳密性を保証しの 2 つの円を考え，その 2 つの円の間にすべての点がたまま不要点を削除するアルゴリズムを提案し，その実含まれると L 、う条件のもとで，その 2 つの円の半径差用性を計算機実験を通して示す.

を最小にする問題(図1)
この問題はある種の設備配置問題と考えることができ応用の多い問題であると考えられる.

2.

真円度アルゴリズム

2.
1 ポロノイ図(勢力阻図)

この問題に対する古くから使われている解法は，最小ボロノイ図とは，計算幾何学において非常に有名な概2 乗法による解法， Min.Max 法を適用した解法，シン念で，近さを効率良く表わす一種のデータ構造と考えるプレックス法を用いた解法等があるが，近似解法に過ぎことができる.真円度問題だけでなく，各種の施設配置ないとか，厳密解法であっても時間計算量に難点がある問題に利用することが可能であり，現にいくつかの間題ものばかりであった [10J[14J[15J.に利用されている [12J.

そこで，筆者らは最近アルゴリズム理論の分野で非常われわれの扱うボロノイ図は，ユークリッド距離 (L 2に注目されている計算幾何学 [IJ[7J[11J( 特に，ボロノイ距離)における最近点のボロノイ図(一般のポロノイ図)
k 番目までに近い点の図 [7J[11J[12J) をこの問題に適用することを考えた [3J.と最違点のポロノイ図であるが計算織何学とは，幾何学に計算の複雑さの理論を導入し，ポロノイ図や，マンハッタン距離(ム距離)や L∞距離

幾何学的な問題を計算機で効率よく処理するアルゴリズなどに対するものもある.また，点ばかりでなく直線やムを開発するとともに，その限界を究明する研究分野で多角形などに対するものもある.

2.
1.
1 最近点のボロノイ図ある.

動丘点のポロノイ図(勢力圃図)は，次のように定義
えばらひろゆき大阪大学工学部通信工学科
干 565 吹田市山田丘 2-1

82(28)

されるものである [12J.
「平面上の n 個の点 Pt=(Xi ， Yd (i=I ， 2 ， … ， n) に対© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーショ γ ズ・リサーチ

••••
図 2

最近点のポロノイ図

図 3

して，点仇の‘勢力圏 . V( 九)をい点( 1 点とは限らな L 、)の距離の差が最小になる点であnV( ム )=piρ =(x.y)ld(Pi. ρ) 孟 d( ρj. ρ))と定め ， V( ム) (i= 1, 2, •••. n)による平面分割j を最近点のボロノイ図と呼ぶ(図 2 ).J ここで ， d (Pi> P) は 2点九 ρ のユーグリッド距離，最遠点のボロノイ図

すなわち .

V(X-X;)2平る.

ところで，与えられた点についてのボロノイ図を考えると，最近点のボロノイ領域内の任意の点はその領域に対応する点が最近点であり，最速点のボロノイ領域内の任意の点、はその領域に対応する点が最遠点、になっている.ここで，最近点のボロノイ図と最遠点のポロノイ図

市=五)2である.
ボロノイ図において，勢力圏 V( ρ;) を点、あのボロノイ領域と呼び，これは凸多角形である.また，ボロノイ領域の頂点をボロノイ点，辺をボロノイ辺と呼ぶ.

2.
1.
2 最速点のボロノイ図
最速点のボロノイ図(非努力圃図)は，次のように定義の結び(Ui non) をとると(図 4 )，各結びの領域内の任意の点は最近点と最遠点が唯一に決められていることになる.

このことから，真円度を決める同心円の中心は与えられた n 個の点に対する 2つのボロノイ図の結びの領域(凸されるものである [12J.

,,,,,,fJ「平函上の n 個の点、 ρi=(Xi> Y;) (i =1.2 ， … .n) に対,,,,“rして，点九の‘非勢力圏 . U( ん)をU( ん )=Jcy=(z，制 Id( 九州以 (Pj> ρ))‑‑‑‑‑-~と定め ，U( 九) (i=I.2, …. n) による平面分割を最遠点のボロノイ図と呼ぶ(図 3 ).J 最遠点のボロノイ図の場
合はすべての点が領域を持つわけではなく，与えられた点集合の凸包上の点についてのみ領域を持つ.
これら 2 つのボロノイ図を構成するアルゴリズムは，
文献 [12J で提案されている.その時間計算量は，分割統治法を使うことにより O(n logn) である.ただし，われわれの計算機実験の際には，平均的には計算時聞が短い文献 [6J の逐次添加法を用いた.この時間計算量は O(n 2 )である.

thenearest~point Voronoidiagram2.
2 真向度アルゴリズム

thefarthest‑pointVoronoidiagram

真円度問題において，真円度を決める同心円の中心はその中心から最も近い点、( 1 点とは限らな L 、)と最も遠1992 年 2 月号

図 4

最近点のボロノイ図と最遠点のボロノイ図の結び© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(29)83

unionpolygon

u:theneU l' e~t pllt

図 6u:Lhefarthc凶t pOlllL

図 5

真円度問題における不要点距離の差の関数と凸領域ボロノイ辺の交点を求めている.ボロノイ辺の数はおの領域となる)について，その各領域内の点の中で対応する最近点と最遠点の距離の差を最小とする領域内の点を見つければよいこととなる.

ここで，距離の差の関数は双曲線となるので，結びの領域側(最近点側)からみると凹関数であり，結びの領域は凸であるので厳密解は必ず結びの領域の頂点に存在する(図 5 ).すなわち，真円度を決める同心円の中心は，最近点のボロノイ点，最遠点、のボロノイ点，あるいは，最近点のボロノイ辺と最遠点のボロノイ辺の交点に存在する.しかし，実際には最近点のボロノイ点と最速点のボロノイ点には厳密解が存在しないことが証明できるので，ボロノイ辺の交点のみを調べればよいことになる[4J.
以上の論拠にもとづいた真円度を求めるアルゴリズム

を[アルゴリズム 1 J として次に述べる.

C アルゴリズム1]

おの O(n) であり，その交点の数はたかだか O(n 2 ) である.したがって，全体の時間計算量は O(n 2 ) となる.ここで，ボロノイ辺の交点の数が O(n 2 ) となる例がすでに知られている[ 4].

3. 改訂真円度アルゴリズム
3.
1 不要点の削除
実際の真円度調u 定においては実時間性も要求され，真円度の計算は 30秒以内(遅くても 1 分以内)が望まれる.
しかし，データ点の数は 1000点以上であり，いくら多項式時間でも O(n 2 ) では十分な速度が得られず，高速化が必要である.
ここで，もう一度真円度問題を考えてみる.与えられた n 個の点、の中には明らかに不要であると考えられる点(外接円あるいは内接円に関与しない点)がたくさん存在する(図 6 ).これらの点(不要点)を厳密性を保証したままあらかじめ削除することができれば，高速化が図

step1 最近点のボロノイ図を構成する.
step2 最遠点のボロノイ図を構成する.
step3 step1 ， 2 で求めた 2つのボロノイ図の結び(Ui n­on) をとる.

れると考える.

具体的には，まず，与えられた点に対して内接円に関与しない点の削除を行ない，これらの点に対して最近点のボロノイ図を構成する.次に，もとの与えられた点に

step4 2 つのボロノイ図の結びの図の中で，最近点のボ対して外接円に関与しない点の削除を行な L 、，これらのロノイ辺と最遠点のボロノイ辺との交点に対し点に対して最遠点のボロノイ図を構成する.そして，最て，その点からの最近点と最遠点の距離の差を求後にこれら 2 つのポロノイ図の結びをとり，その交点かめる.

ら真円度を求める.

step5 最近点、と最遠点の距離の差が最小となる点とその値を求める.最小となる距離の差が真円度あでり，最小となる点が真円度を決める同心円の中心である.

[アルゴリズム1]

述べる.

3.1
.1 内接円に関する不要点削除
最遠点対を用いた内接円の半径の下界に関する定理をの時間計算量を考える. s
tep 1, 2は O(nlogll) あるいは O(n 2 ) である.

84 (30)次に，厳密性を保証するための定理とアルゴリズムを

step 3， 4， 5 て1 土，以下に示す.

[定理 1 ] データ点集合の最遠点対の中点を OF ，最遠© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

ているものとする. [アルゴリズム 2J では. 11原方向のポインタを L[ 'O J. 逆方向のポインタを R[ 'O] で表わす.
[アルゴリズム 2 ]step1 データ点集合の最遠点、対をキャリパ一法により求める [13J.

step2 最遠点対の中点を OF とする.また，最遠点対の距離を D とする.

step3 点 OF に最も近い点までの距離を Rin ， 点。 F に最も遠い点までの距離を Rout とする.

向 4 RL=Rinー(んut-3) とする
pointα ， b: thefarthestpairhecenterofthefarthestpair
pointOF:tMr2
図 7

step ラ最遠点対のどちらか一方を start とする.

step6 '0:=start;[定理 1 J の説明図

点、対の距離を D とする.点、 OF から最も近いデータ点までの距離を Rin ，最も速いデータ点までの距離を Rout と0]=t‑start)
WHILE(L['IF('0, L[ 'O], L[L[ 'O JJ が左折れ )THEN1':=('0, L[ 'O], L[L[ 'O]] の 3 点でできる円の半径);IF(r<RL)THEN
L[ 'O] を削除;すると， Rin ー (Rout-g) は真向度の厳密解を与える
内接円の半径の下界となる(図 7 ).

'O:=R['O];
ELSE[証明]

r=~ ， d=R叫 -r とするここで ， Rout -R川真円度の上界を示すことに注意しておく.

このとき ， R'in<

Rin-d なる内接円の半径を持ち，かっ Rout -Rin 未満の真円度を与えるような真円度の中心は存在しないことを以下に示す.

'O :=L[ 叶;

END;
ELSE

'0:=L['O];
END;
END;

Rout‑Rin=(Rout-d) ー (Rin-d)=r ー (Rin- d )また特にR[start]=start とする.

Rin- d より半径の小さい半径 R'in を持つ内接円の中心 S が存在するとする.そして，点 S を中心とする外接円の半径を R'out とする.
2r=D は最遠点対聞の距離を示しているので，.2 外接円に関する不要点削除
3.1
最大内接円を用いた外接円の半径の上界に関する定理を以下に示す.

[定理 2 ] データ点集合の最大内銭円の中心を OL とし，点。 L から最も遠いデータ点までの距離を Rout とする

r 三王(最小外接円の半径)と ， Rout は真円度の厳密解を与える外接円の半径の上界

よって，となる(図 8 ).

R'out>r[証明]である.また，仮定により，最大内接円の半径を Rin とすると ， R
out-Rin は真円

R'in<Rin ー d度の上界となることは明らかである.このとき ， R'out>であるので，

Rout‑Rin=r‑(Rin‑d)<R'out‑R'in

Rout なる外接円の半径を持ち，かっ Rout -Rin未満の真円度を与えるような真円度の中心は存在しないことを以である. [証明終り〕[定理1]から厳密性を保証した次のような内接円に関下に示す.

する不要点削除アルゴリズムを導くことができる([アルRout より大き L 、 R'out の半径の外接円を持つ中心 S がゴリズム 2 J)
. このアノレコリズムは R. L
.Graham の凸存在し，点、 S を中心とする内接円の半径を R'in とする.

法アルゴリズム [5J と類似の形で形成されている.
ここで，データ点は半時間回りにポインタでつながれ1992 年 2 月号

Rin' 土最大内接円の半径であるから，R'in<Rin© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(31)85

step1 [内接円に関する不要点削除]を行なう.
step2 step1 で残った点集合で最近点のボロノイ図を機成する.

step3 最近点、のボロノイ図を利用して， [外接円に関する不要点削除]を行なう.

step4 step3 で残った点集合で最遠点のポロノイ図を構成する.

step5 step2 で構成した最近点、のボロノイ図と step 4で構成した最違点のポロノイ図の結びをとる.

step62 つのポロノイ図の結びの図の中で最近点のボロノイ辺と最速点のボロノイ辺との交点に対して，そpointOL:thecellterofthclar昌;e8t emptycircle
図 8[定理 2J の説明図の点からの最近点と最速点の距離の差を求める.

step7 最近点、と最遠点、の距離の差が最小となる点とその{直を求める.最小となる距離の差が真門度でありである.また，仮定により，最小となる点が真円度を決める同心円の中心である>

R'out Rout4. 計算機実験であるので，R'out‑R'in>Rout‑Rinである.

実際の真向度測定に対して，[証明終り][定理2]から厳密性を保証した次のような外接円に関する不要点削除アルゴリズムを導くことができる( [アルゴリズム 3 J).

ここで，データ点のつながりは[アルゴ[改訂真円度アルゴリズム]を適用した場合の効果を検証するために計算機上で実験を行なう.
本実験で用いたデータは，実際の真円度調g定機から得られたもので，約 3cm の円筒状断面より原点を中心としズリム 2 J と同様である.

反時計回りに 0.2 度ごとに 1800点サンプリングしたもの[アルゴリズム 3 J

step1 データ点集合の最大内接円の中心 OL を求める.
step2 点。 L から最も遠いデータ点までの距離を Ruである.また，データの半径方向の偏移は数 μm 程度で、ある.実際に用いた計算機は， CPU として MC68020をもったソニー製の UNIX ワークステーションであり，使とする.

step3 点。L から最も遠いデータ点を start とする.特用言語は C 言語である.

表 1 に，凸包上のデータ点数とそれぞれの不要点削除に， R[startJ=start とする.

によって残ったデータ点数を示す.

step4 v:=start;

表 2 には， [アルゴリズム1]と〔アルゴリズム 4J の計WHILE(L[vJ*start)
r:=(v , L[vJ , L[L[vJJ の 3 点でできる円の半径);算時間の比較を示す.
実験結果から，不要点削除を行なえばそれぞれのボロIF(r>Ru)THEN
L[vJ を削除 L

ノイ図を構成するのに必要なデータ点の数は，最近点のv:=R[vJ;

ボロノイ図の構成で約 20 分の 1 ，最遠点のボロノイ図の構成で約 200分の l で済むことがわかる.また，計算時間でELSEは 20倍以上高速になっている.ここて、， [内接円に関するv:=L[vJ;不要点削除]で削除されるデータ点の数が少ないのは，内END;END;

接円の半径の下界が最遠点女すから求められており， [外接3.
2 改訂真円度アルゴリズム

円に関する不要点削除]での外接円の半径の上界に比べ以上の考察からて良くないためであると考えられる.

2 つの不要点削除アルゴリズムを組み込んだ改訂真円度アルゴリズムを〔アルゴリズム 4 J として述べる.

[アルゴリズム 4 J

86 (32)

5.

むすび

本稿では，著者らのアルゴリズムを中心に真円度問題© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

表 1

各不要点削除後に残るデータ点の数

データ 11

凸包上のN'0.

データ点数|

表 2[アルゴリズム 1 J と[アルゴリズム 4J の計算時間の比較|不要点削除後に残ったデータ数￨

内接円

外接円107~I̲ 5￨1273

デ~タ 121297

11431273

10241125411113ー-5~-11-1233
三寸120122L__~~一一311兄54--11 一つ五 411275 5 9 . 1

4.86

69.39

78

1
11170

12

計算時間(秒)[アルゴリズム 1 J 1 [アルゴリズム 2J

下i ?‑

し一三三

11ω9;千五「IiF下1
16.
2
11211142.3

776.3

16.26
7.00

下一九94

子

6.9

86.
4
16.
7

r--1 ~-I一一一正面一一仏 57.89

平均6.95149.7

について計算幾何学と関連づけながら概説した.少し理論的になってしまったのではな L 、かと危倶している
本稿では述べなかったが，真円度問題に関して別の定式化が提案されており，理論的に面白い結果が出ている[9J. また，詳しいことはまだ良く知らないが，この真円

Computer Journal , vo l. 21 , no.2 , pp.168~173 ，1978.

[7] 伊理正夫監修/腰塚武志編集:“計算幾何学と情報処理'\bit 別冊，共立出版， 1986年.

度問題に対する O(J) アルゴリズムが提案されたという[8J 1SO R1101/1 , 1
969.

噌である・まだただ興味深い問題のようである・[9J V.B. LeandD.T. Lee: “ Out-Of・Roundness

最後に，本稿の解法に関してご指導いただ L 、た大阪大

Problem Revisitedヘ 1EEE Trans. on Pattern

学名営教授(現在，国立奈良工業高等専門学校校長)中西

Analysisand Machine 1ntelligence , vo 1.1 3 , no.

義郎先生と，大阪大学工学部助教授中野秀男先生に感謝の意を表す.また，本稿の解法に関して共同研究者であった現在富士通株式会社の福山訓行氏に感謝する.

3, pp.217~223 ， 1
991.
[10J T.S.R. Murshyand S.
Z. Abdin: “ Minimum
Zone Evaluation of Surfaces" , 1nternational
Journal ofMachine ToolDesign & Research ,参芳文献

vo 1. 20 , pp.123-137 , 1
980.

[1J 浅野哲夫:“計算幾何学ヘ朝倉書店， 1990年.
[2J H. Ebara , N. Fukuyama , H. Nakano , andY. Nakanishi

“APr
act
ical Algorithm for

Computing the Roundness" , Trans. IEICE ,toappear.

F.P. Preparataand M. 1. Shamos: “ Com-putational Geometry ‑An Introduction 一"Springer‑Verlag , 1
985.
[12J M. 1. Shamos ond D. Hoey: “ Closest-PointProblems" , Proceedings of16th AnnualIEEE[3J 擾原博之，中野秀男，中西義良11 ，真凶友宏:“ボロノイ図を応用した真円度を求める解法'二信学論， Vol.

]70-A , No.4 , pp.620-624 , 1987年[4J 福山訓行:“ボロノイ図を用いた真円度計算に関する研究大阪大学工学部通信工学科，修土論文， 1988
年

Symposium on Foundations of Computer
Science , pp.15 ト 162 ， 1
975.
[13JforDetermining the Convex Hull ofa FinitePlanar Set" , Information Processing Letters ,vo l. 1, pp.132-133 , 1972.

G. T. Toussaint“ Solving

Geometric

Problemswith the Rotating Calipers" , Proce‑edingsof IEEE MELECON '83 , 1983.
[14J[5J R. L. Graham: “ An Efficient Algorithm

T. Tsukadaand T. Kanada: “ Measurementof Cylindrical Form Errors Using a Non‑
Contact Detector'¥Precision Engineering ,vo l. 4, pp.153-158 , 1
982.
[15J 塚田忠夫，金田徹，奥田謙造:“最適化技法を用い[6J P.J. Green and R. Sibson: “ Computing
Dirichlet Tessellations in the Plane'¥The1992 年 2 月号

日 1J

た辰小領域法真円度の評価法"，精密機械，

No.10 , pp.1351-1357 ,© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

Vo l. 49 ,1983年.

(33)87