レイアウト #

概要 #

タカラトミーのプラレールという鉄道玩具が広く知られています [1]．前ページでは，プラレールのレールに関する形式的定義を与えました．本ページではレイアウト（線路配線）の数学的表現を考えます．

レイアウトの数学的表現 #

一般に，プラレールの配線結果を レイアウト と呼びますので，本ページでもそれにならいます．

レイアウトを考えるとき，レール同士は斜めに接続できず，接続部が凹凸の組み合わせである必要があります．ここでは，特に配線結果が環状であることを要求しません．

レールを頂点としたグラフを考えることで，レールごとの接続の仕方が表現できます．接続の仕方が決まると形状が決まりますが，これは各レールの端点や分岐点を頂点とする単純グラフで表現できます．以下，接続を表すグラフを 接続グラフ，形状を表すグラフを 形状グラフ とよぶことにします．これらをふまえて，レイアウトの形式的定義を考えます．

まず，そのレイアウトが実現できるかを確認する前段階である 擬レイアウト を定義します．

Definition 1.
\(\Gamma_m=(\mathbb{Z}^2\times(\mathbb{Z}^2)^*)^m \) とし，\(\Gamma^*\) の元を 接続情報 と呼ぶ．ただし，集合 \(A\) に対して \(A^*=\bigcup_mA^m\) とする．
\(\tilde{\mathcal{A}}\) を，以下を満たす \(R\) 全体の集合とし，\(\tilde{\mathcal{A}}\) の元 \(R\) を 擬レイアウト という．
\(R=(r,c)\in\bigcup_{n,m}(\mathcal{R}^n\times\Gamma_m)\) である．
\(r=(r_i)_{1\le i\le n},c=(c_k)_{1\le k\le m}\) が， \[ \begin{aligned} &r_i=(\phi_1^i,\dots,\phi_{n_i}^i,t_1^i,\dots,t_{m_i}^i,\psi^i,u_1^i,\dots,u_{n_i-1}^i)\quad(1\le i\le n),\\ &c_k=((i_1^k,i_2^k),((j_{11}^k,j_{12}^k),\dots,(j_{l_k1}^k,j_{l_k2}^k)))\quad(1\le k\le m) \end{aligned} \] と表せるとき，
任意の \(k=1,2,\dots,m\) について \(1\le i_1^k\le n\), \(1\le i_2^k\le n\) である．
任意の \(k=1,2,\dots,m\) と \(l=1,2,\dots,l_k\) について，\(1\le j_{l1}^k\le m_{i_1^k}\), \(1\le j_{l2}^k\le m_{i_2^k}\) である．
任意の \(k=1,2,\dots,m\) と \(l=1,2,\dots,l_k\) について，
\(t_{j_{l1}^k}^{i_1^k}\not=t_{j_{l2}^k}^{i_2^k},\quad t_{j_{l1}^k}^{i_1^k}\not=\bot,\quad t_{j_{l2}^k}^{i_2^k}\not=\bot\) である．
\(\psi^{i_1^k}(k_1,l_1)=j_{l1}^k\), \(\psi^{i_2^k}(k_2,l_2)=j_{l1}^k\) となる \(k_1,k_2,l_1,l_2\) について， \[ \lim_{x\to l_1}\frac{{\phi'}_{k_1}^{i_1^k}}{\|{\phi'}_{k_1}^{i_1^k}\|_2}=\lim_{x\to l_2}\frac{{\phi'}_{k_2}^{i_2^k}}{\|{\phi'}_{k_2}^{i_2^k}\|_2} \] が成り立つ．
擬レイアウト \(R\in\tilde{\mathcal{A}}\) の 接続グラフ \(C(R)\) とは，\(R=(r,c)\), \(r=(r_1,\dots,r_n)\), \(c=(c_1,\dots,c_m)\), \(c_k=((i_1^k,i_2^k),((j_{11}^k,j_{12}^k),\dots,(j_{l_k1}^k,j_{l_k2}^k)))\ (1\le k\le m)\) のとき，\(V=\{v_1,v_2,\dots,v_n\}\), \(E=\{e_{11},\dots,e_{1l_1},e_{21},\dots,e_{2l_2},\dots,e_{m1},\dots,e_{ml_m}\}\) であり，\(g(e_{kl})=(v_{i_1^k},v_{i_2^k})\) による（一般に多重辺をもつ）有向グラフ \(C(R)=(V,E,g)\) のことである．
\(\)

接続情報 \(c\in\Gamma_m\) はどのレール同士をどの端点で接続するかの情報を表します． \(c=(c_1,\dots,c_m)\) , \(c_1=((i_1,i_2),((j_{11},j_{12}),\dots,(j_{l1},j_{l2})))\) なら， \(c_1\) は，

インデックス \(i_1,i_2\) のレール同士を，
- \(i_1\) 側のインデックス \(j_{11}\) の端点と \(i_2\) 側のインデックス \(j_{12}\) の端点を接続する．
- \(i_1\) 側のインデックス \(j_{21}\) の端点と \(i_2\) 側のインデックス \(j_{22}\) の端点を接続する．
- ……

といった要領で接続することを表します．そして， \(c_i\,(i=2,\dots,m)\) についても，同様となります．

接続グラフは，レールを頂点とし，レール同士が接続されるときに有向辺をもつ有向グラフです．複数の端点どうしで，1組のレール同士を接続する場合は，多重辺となります．これは文字通り，レールの接続の仕方を表すグラフです．

ところで，2.3.1 は接続する点が内部点でなく，かつ凹凸の組み合わせとなっていることを要求しています．また，2.3.2 は接続部が同じ角度で接続されていることを要求しています．

したがって，擬レイアウトは，レール同士の接続のみに着目して，そのときに問題がない線路配線を表しているといえます．しかし，レールは一定の大きさをもつため，その接続が実際にできるかを確認しなければなりません．ここで，そのレイアウトが実現可能かを検証するために，形状グラフ を定義します．

Definition 2.
レール \(r=(\phi_1,\dots,\phi_n,t_1,\dots,t_m,\psi,u_1,\dots,u_{n-1})\in\mathcal{R}\) の 形状グラフ \(G(r)\) とは，\(V=\{v_1,v_2,\dots,v_m\}\), \(E=\{e_1,e_2,\dots,e_n\}\), \(\psi(i,0)=j_1,\psi(i,1)=j_2\) ならば \(g(e_i)=\{v_{j_1},v_{j_2}\}\) によって定まる無向グラフ \(G(r)=(V,E,g)\) である．
レール \(r=(\phi_1,\dots,\phi_n,t_1,\dots,t_m,\psi,u_1,\dots,u_{n-1})\in\mathcal{R}\) の形状グラフ \(G(r)=(V,E,g)\) について，\(e\in E\) が \(e=\{v_{j_1},v_{j_2}\}\) であるとする．\(\psi(i,0)=j_1,\psi(i,1)=j_2\) であるとき，\(v_{j_1}\) を \(e_i\) の 始点側ノード, \(v_{j_2}\) を \(e_i\) の 終点側ノード という．
擬レイアウト \(R=(r,c)\in\tilde{\mathcal{A}}\) に対する 形状グラフ \(G(R)\) とは，\(G(r_i)=(g_i,V_i,E_i)\quad(1\le i\le n)\) \(V_i=\{v^i_1,\dots,v^i_{m_i}\}\) とすると，\(\tilde{V}=\bigcup_iV_i\), \(\tilde{E}=\bigcup_iE_i\), \[ \tilde{g}(e)=\begin{cases} g_1(e),\quad e\in E_1,\\ g_2(e),\quad e\in E_2,\\ \cdots\cdots\\ g_n(e),\quad e\in E_n \end{cases} \] によって得られるグラフ \(\tilde{G}=(\tilde{V},\tilde{E},\tilde{g})\) に対して，任意の \(k=1,2,\dots,m\) と \(l=1,2,\dots,l_k\) について，\(v^{i^k_1}_{j_{l1}^k}\) と \(v^{i^k_2}_{j_{l2}^k}\) を1点に縮約して得られる無向グラフのこととする．
レール \(r\in\mathcal{R}\) の形状グラフ \(G(r)=(V,E,g)\) における 辺・曲線対応関数 \(f\) を，\(r=(\phi_1,\dots,\phi_n,t_1,\dots,t_m,\psi,u_1,\dots,u_{n-1})\), \(E=\{e_1,\dots,e_n\}\) において \(f(e_i)=\phi_i\) とする．
擬レイアウト \(R\in\tilde{\mathcal{A}}\) の形状グラフ \(G(R)=(V,E,g)\) における 辺・曲線対応関数 \(f\) を，\(R=(r,c)\), \(r=(r_1,\dots,r_n)\) とし，\(r_i\) の辺・曲線対応関数を \(f_i\) とするとき， \[ f(e)=\begin{cases} f_1(e),\quad e\in E_1,\\ f_2(e),\quad e\in E_2,\\ \cdots\cdots\\ f_n(e),\quad e\in E_n \end{cases} \] で定める．

もともとレールは単純な曲線の集まりでした．よって，擬レイアウトも単純な曲線の集まりとなります．形状グラフは，単純曲線を辺として，曲線同士の接続点を頂点とする無向グラフです．レールや儀レイアウトの辺・曲線対応関数は，この辺と曲線の対応を表す関数です．

形状グラフの頂点を，レールごとにグループ化して，1点に縮約すると，接続グラフが得られます．

さて，これまでの準備のもと，実際にレイアウトが組めるかどうかを判断する基準を設けます．

Definition 3. 擬レイアウト \(R\) の形状グラフを \(G(R)=(V,E,g)\) とし，\(R\) の辺・曲線対応関数を \(f\) とする．\(s,t\in V\) とする．\(s\) と \(t\) を結ぶ道 \(p\) について，\(p\) に沿った \(s\) に対する \(t\) の変位 \(u_{s,t,p}\) を以下のように定める．まず，\(p=v_0e_1v_1\cdots v_{n-1}e_{n-1}v_n\), \(v_0,v_1,\dots,v_n\in V\), \(e_1,\dots,e_{n-1}\in E\), \(v_0=s\), \(v_n=t\) とする．\(\phi_i=f(e_i)\quad(1\le i\le n-1)\) とする．ここで，\(i=1,2,\dots,n\) について \(v_{i-1}\) が \(e_i\) の始点側の点であれば \(s_i=1\), そうでなければ \(s_i=-1\) としたとき， \[ u_{s,t,p}=\sum_{i=1}^{n-1}s_i\left(\lim_{\theta\to1}\phi_i(\theta)\right) \] と定める．

\(u_{s,t,p}\) は形状グラフ上の2点間の距離ですが，その計算方法を経路に依存させています．しかし，距離なので，経路によらず同じ値をとるはずです．そうでない場合，レールを変形させない限り実現できない接続になっていると考えられます．そこで，レイアウトにおける各レールが 接続可能 であることを以下のように定義します．

Definition 4.
擬レイアウト \(R\) の形状グラフを \(G(R)=(V,E,g)\) とする．任意の \(s,t\in V\) について，\(s\) から \(t\) への任意の道 \(p\) に沿った \(s\) に対する \(t\) の変位が一致するとき，擬レイアウト \(R\) は 接続可能 であるという．
擬レイアウト \(R\) の形状グラフを \(G(R)=(V,E,g)\) とする．擬レイアウト \(R\) が接続可能であるとき，任意の \(s,t\in V\) について，\(s\) に対する \(t\) の変位 を，\(s\) から \(t\) へのある道 \(p\) によって，\(u_{s,t}=u_{s,t,p}\) で定める．

次に，レール同士が重ならないことを確認します．

Definition 5. 擬レイアウト \(R\) の形状グラフを \(G(R)=(V,E,g)\) とし，\(R\) の辺・曲線対応関数を \(f\) とする．擬レイアウト \(R\) が接続可能とする．\(s\in V\) をとる．\(\phi_e=f(e),(e\in E)\) とする．\(e\) の始点側ノードを \(v\) としたとき， \(\tilde{\phi}_e(\theta)=u_{s,v}+\phi_e(\theta),\ (0<\theta<1)\) とする．ここで， \[ \bigcap_{e\in E}\mathrm{Im}\,\tilde{\phi}_e=\emptyset \] のとき，\(R\) は 重なりがない という．

各単純関数 \(\phi_e\) は始点が原点に固定されているため，擬レイアウトのある点を基準として，実際の位置にシフトした曲線を \(\tilde{\phi}_e\) とします．このとき，各 \(\tilde{\phi}_e\) の像が重ならなければ，レール同士は重ならないとみなします．実際は，レールは幅をもち，情景や，レールに付随する構造物と干渉しないようにする必要がありますが，ここではそのような干渉判定は省略し，レールを幅のない曲線のあつまりとみなしています．

さて，接続ができて，重ならなければそのレイアウトは実現可能と考えられます．そこで，レイアウトを以下のように定義します．

Definition 6. \(R\) を擬レイアウトとする．\(R\) が接続可能かつ重なりがないとき，\(R\) を レイアウト と呼ぶ．レイアウト全体の集合を \(\mathcal{A}\) で表す．

レイアウトは，その上で走らせる列車が連続稼働できるよう，環状であることが多いと思います．そこで，それをふまえた用語を用意します．

Definition 7. \(R\) をレイアウトとし，\(G(R)=(V,E,g)\) とする．
\(G(R)\) の任意の頂点の次数が2以上のとき，\(R\) は 完全レイアウト という．
\(G(R)\) の頂点のうち，次数1の頂点が \(2k\) 個あり，それを \(v'_1,v'_2,\dots,v'_{2k}\) とする．\(s\in V\) とし，\(u'_i=u_{s,v'_i},(1\le i\le 2k)\) とする．一般性を失わず，\(\min_j\|u'_{2i-1}-u'_j\|_2=\|u'_{2i-1}-u'_{2i}\|_2\) とする．\(1\le i\le 2k\) について，\(v'_i\) に接続する辺を \(e'_i\) とし，\(\phi_i=f(e'_i)\) とする．\(v'_i\) が \(e'_i\) の始点側ノードなら \(a_i=0\), そうでなければ \(a_i=1\) として，\(p_i=\lim_{\theta\to a_i}\phi'_i(\theta)/\|\phi'_i(\theta)\|_2\) とする．\(1\le i\le 2k\) について，\(\delta_i=\|u'_{2i-1}-u'_{2i}\|_2\), \(\delta'_i=\sqrt{(p_{2i-1},p_{2i})^{-2}-1}\) とし，\(\delta=(\delta_i),\delta'=(\delta'_i)\) とする．ただし，\((\cdot,\cdot)\) は内積を表す．このとき，レイアウト \(R\) は \((\delta,\delta')\)-レイアウト であるという．
レイアウト \(R\) が \((\delta,0)\)-レイアウトであるとき，\(\delta\)-レイアウト であるという．

完全レイアウトとは，配線結果が環状になっていて，無理なく接続されている状況を表します．一方で， \((\delta,\delta')\) -レイアウトは，多少離れている端点を強引につなぐことで環状にできるもので，いわゆる なじませつなぎ によるレイアウトを表現しています． \(\delta\) は端点間の距離， \(\delta'\) は端点における向きのずれ（向きのなす角の正接 (tan) の絶対値）を表します． \(\delta\approx0\) とは端点の距離が小さく，比較的無理なくつなげていることをあらわし， \(\delta'\approx0\) とは端点における向きのずれも小さいことを表します．逆に端点どうしの距離が小さくても，直交する場合は接続できませんが，この場合は \(\delta'=\infty\) になります．

まとめ #

本ページでは，プラレールのレイアウトに関する形式的定義についてまとめました．

参考文献 #

[1] タカラトミー，“トップページ｜プラレール｜タカラトミー”, https://www.takaratomy.co.jp/products/plarail/ , 2023/5/14 最終アクセス．