１２．５．１Ｃ．１　点列からなる閉曲線の共通接線を求める計算法　　　 ２００８−１１−１４

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　２００９−６−２６追加

・経路生成には，人間がAGVの始点終点の位置と向き，室内の障害物の配置の全体を見渡し，始点から順に，「障害物を選定」・「その障害物（限界等高線）間の複数共通接線から適当と思われる接線選択」を繰り返して終点に到る経路を対話形式で生成する．

・選定された２等高線間の共通接線はコンピュータが計算する．

・このシミュレータで実行している共通接線の計算手順を以下に示す．

・基本的には曲線の接線の勾配と共通接線の勾配が一致する点を接点とすればよい．

・障害物を横切る共通接線は経路にはならないので除外する．

・特別な場合として，近くに２つの異なる共通接線がある場合，一方の曲線上に２つの共通接線の接点が重なっている場合などがあり得る．

・曲線が点列で与えられている場合，完全に正しい接点を得ることができず，その近傍の誤差極小の点を接点とすることになる．その極小値判定に際し，近傍の２点を接点とする誤り，近傍にある筈の２接点を見落とす誤りなどがあり得る．

・これらを考慮して，点列で与えられる２閉曲線間の共通接線を求める手順を説明する．

Ｃ１．１．２つの曲線について直線lが共通接線となる点

・点の数だけ接線として誤差が極小になるかどうかを虱潰しに探索する．

・障害物の限界等高線は閉曲線とし，，は点列

，，　，；　　(C1-1)

　で与えられているとする．なお最終点B1f，B2fは始点B10，B20と同じものとする．

・点の接線の勾配は両隣の点(k=1,2)を使って

　　　，　j1=0,1,2,….,n1f　　　　　　　　　　　(C1-2)

,　j2=0,1,2,….,n2f　　　　　　　　　　　(C1-3)

　で近似する．あるいはその逆数を利用する．

・D1とD2を結ぶ直線lの勾配は

　　　，　　　　　　　　　　　　　　　　　　　(C1-4)

　　　　　　　　　　　　　　　　　　　　　　　　　　(C1-5)

・直線lの勾配が等高線の接線の勾配と一致する条件を

，，　　　　　　　　　　　　　(C1-6)

　かつ　　　　　　　　　　　　　　　　　　　　　　　(C1-7)

　とする．

・すなわち，B1上で点列Dj1（j1=0,1,2,…），B2上で点列Dj2（j1=0,1,2,…）とすると，e3が小さくなる限りは,j1，,j2を変える．

・e3が増加に向かったとき，その前が極小値である．その極小値がε以下であれば共通接線であるとする．

Ｃ１．２．B1上で近傍に２接点がありB2上で近傍でない２接点がある場合に，接点を選別する誤差極小となる接点の探索

・図12.5.5の接線（C13,C23）と（C13,C23）を選別するために，B1曲線上の点D1を固定し，B2上の点D2を１周し，D1を変えてまたD2が１周するという手順を踏む．

・Dj1（）に対し，それぞれDj2（）と進め，誤差がある程度小さくなったらその近傍でj1,j2を変えて極小値を探索する．

Ｃ１．３．B1,B2上で近傍の異なる２接点を選別する手順

・図12.5.5の接線（C11,C21）と（C12,C22）が異なるものであるかどうかは，前述の勾配誤差e3が極小値から一旦は増加してまた減少に転ずるかどうかで判断できる．

・実際には点列の数個以内には２接線は存在しないと仮定して，計算を簡略化している．

Ｃ１．４．障害物を横切る接線の除外

・図12.5.5の接線（C15,C25）は障害物（限界等高線）を横切っている．これは経路として不適当であり除外する．

・図12.5.6に見るように，接点C2の近傍に点D2sをとり，C1から引いた直線をl2sとする．

・B2曲線上に，共通接線lを挟んでD2sと反対側にあり，長さがlより小さいこと

，　　　　　　　　　　　　　　(C1-9)

　となる点D2jがあれば，この接線は曲線を横切る．

・B1曲線を横切るかどうかの判別も同様にする．

Ｃ１．５．AGVの始点・終点と限界等高線との共通接線

・始点P0・終点Pfからの自由空間経路は，２点間が遠ければ円弧から始まっている．

・障害物回避の経路も一定の半径raの円弧から始まるとする．（円弧でなくてもよいとすると，その場でAGVの向きを変えてから始まる経路が経路長を短くすることになり，現実的でない．）

・その円は左回りとなる反時計回り(CCW)の円と右回りとなる時計回り(CW)の円とがある．

・図12.5.7に見るようにAGVの向きを考えると，限界等高線がAGV左側にあればCCW円と限界等高線の共通接線，右側にあればCW円との共通接線が有効である．

・前述の共通接線探索の計算では，CCW円またはCW円との共通接線はAGVの走行と同じ向きと逆向きの接線が含まれている．

・この判定は簡単なのでコンピュータで処理する．すなわちCCW円，CW円のそれぞれの方向に接線の傾き角θ1を定義し，共通接線の傾き角と等しければ（離散化誤差を考慮して極めて近ければ）共通接線として（経路生成候補として）採用し，180°違っていれば除外する．

・以上は始点からの経路生成についてであるが，終点からの経路生成も手続きは同じである．

１２．５．１Ｃ．２　点列からなる非凸多角形のペイント　　　　　　　　　２００８−１１−２８

・経路生成に関係ない事項であるが，このシミュレータにおいて，障害物は形状内部を色で塗りつぶしているが，グラフィックスで塗りつぶす手続きの問題である．

・物体形状の内部を塗りつぶす描画は，基本的に三角形の内部塗りつぶしであり，最初の点を視点として全ての点が視点から見えなければならない．

　（glBegin(GL_TRIANGLES)，glBegin(GL_POLYGON) 等）

・すなわち多角形が非凸の場合の塗りつぶしは凹点を探し，視点から全ての点が見える凸多角形点列に分解してそれぞれを塗りつぶすという手法をとらねばならない．

・ここで障害物の描画塗りつぶしについて，以下の仮定を設ける．

（１）障害物の輪郭を多角形の点列で近似する．ただし，単純な形状は部分的に円弧でも表現する．

（２）点列を反時計回りに番号をつける．

・凹点の探索と塗りつぶしの視点の指定の手順は以下の通りに行う．

・元の多角形を第０層多角形とする．

（１）第０層多角形の点列について両隣りから見て凹である点を探す．（図12.5.12のP0，P3，P8，．．点）

（２）凹点Pc1から次の凹点Pc2までは凸点のみであり，この２つの凹点間で多角形を作る．

（３）この凸多角形には２通りある（凸多角形と非凸多角形，図12.5.13）．

（３−１）図(a)は凹点P3から全ての点が見えるので，P3を視点として塗りつぶすことができる．

（３−２）図(b)は凹点P15からP18が見えないので，２つの凸多角形に分割する．

P15から見える点ばの右側にある点であり，となる点Pk探し，によって２つの凸多角形に分ければよい．

（４）凹点間多角形の内部に別の凹点が突き出ている場合がある（図12.5.12の凹点P3−P8間にP12が突き出ている）．

（４−１）この場合は，直線の右にある点P6を新たな凹点と考え，P3P6間の多角形とP6P8間の多角形に分ける．

　　　突き出た凹点の存在はとなる点Pk（=P12）があるかどうかを調べればよい．また，となる点Pi（=P6)が新たな凹点である．

（４−２）２つに分けた各多角形が凸か非凸か判定し非凸なら(3)の手続きによって凸多角形のみとする．

［註1］突き出ている凹点が複数存在することがある．その場合は最も突き出た凹点を対象とする．

［註2］非凸多角形でも視点をこの図12.5.13(b)の例でP0かP16を視点とすれば全ての点が見えるから分割する必要がない．

　しかし全てが見える点があるかどうかを調べる新たな手続きを付け加えることが面倒なので，ここでは始めの凹点を視点とすることで統一する．

［註3］凹点が連続していて多角形をなさない場合もある．その場合の特別な手続きは必要ない．ただし，(5)以下の多角形層形成で凹点の数が１つ減るだけでそれだけ層が多重となり能率が悪い．

　以上で，凹点間の多角形を始めの凹点を視点として塗りつぶすことができる．

（５）第０層の凹点列の中は空白なので，次に凹点のみからなる第１層の多角形を作る（図12.5.14）．

（６）第１層多角形の凹点が４点以上あるときは(1),(2)の手続きによって新たな凹点間多角形と凹点のみからなる次の層の多角形を作ることを繰り返す．

（７）最終的には凹点が０−３点からなる４通りの多角形が得られる．

（７−０）凹点がなければ，どれを視点としても他の全ての点が見え，この多角形を塗りつぶすことができる．

（７−１）凹点が１つならば，その凹点を視点として全ての点が見え，この多角形を塗りつぶすことができる．（図12.5.15）．

（７−２）凹点が２つ（Pc1，Pc2）ならば，直線によって２分割する（図12.5.16）．２つの多角形を塗りつぶす操作

は図12.5.14に述べた通りである．

（７−３）凹点が３つならば，３凹点からなる三角形を塗りつぶすことができる．

［註］３凹点が図12.5.18のように残る場合はない．その前に(4-1)の手続きによって第４の凹点を作り４凹点多角形となるからである．

これで非凸多角形をいくつかの凸多角形に分解し，視点を適当に採れば，隙間なく塗りつぶすことができる．

１２．５．１Ｃ．３　楕円の周線分dsと円周角増分dθの関係

・楕円を極座標表示で

　　　，　　，　　　　　　　　(C3-1)

　　　　　　　　　　　　　　　　　　　　　(C3-2)

　とする．

　以下，，と置く．

・rの変化分は

　　　　　　　　　　　　　　　　　　　　　(C3-3)

・周線分dsは

　　　　　　　　　　　　　　　　　　　　　　　　(C3-4)

　　　

　　　

　　　

　　　　　　　　　　　　　　　　　　　　　(C3-5)

・dsを一定に周を回るとき回転角は

　　　　　　　　　　　　　　　　　　　(C3-6)

　とすればよい．

・楕円の周長Sは

　　　　　　　　　　　　　　(C3-7)

１２．５．Ｃ１．４　楕円からp離れた曲線とその線分増分一定となる点列の生成　２００９−６−２６

・楕円の限界等高線を線の増分＝一定となるような点列を作成する．

・楕円からp離れた点の座標は

　　　　　　　　　　　　　　　　　　　　　　　　　　(C4-1)

　　　　　　　　　　　　　　　　　　　　　　　　　　(C4-2)

　但し

　　　，　　　　　　　　　　　　　　　　　　　(C4-3)

　　　　　　　　　　　　　　　　　　　　　(C4-4)

　角φは

　，　　　　　　　　　　　　　　　　(C4-5)

・限界等高線の増分は

　　　　　(C4-6)

　と表現し，を求める．

・以下，θの微分を‘で表す．

・は

　　　　　　　　　　　　　　　　　　　　　　(C4-7)

　　　　　　　　　　　　　　　　　　　　　　(C4-8)

・は

　　　　　　　　　　　　　　　　　　　　　　　　(C4-9)

　　　　　　　　　　　　　　　　　　　　　　　　(C4-10)

　　　　　　(C4-11)

・r’, r’’は

　　　　　　　　　　　　　　　　　　　　(C4-12)

　　　　　(C4-13)

・(C4-7)〜(C4-13)式を(C4-6)に代入すればが分かる．

・包絡線（限界等高線）の全長Sは

　　　　　　　　　　　　　　　　　　　　　　　　　　　(C4-14)

・全長を等分にNf分割すると

　　　

・このときθの増分は

　　　

　である．すなわち回転角の増分を上記のように可変とすれば周の増分は一定となる．