\documentclass[twoside,twocolumn,10pt]{jsarticle}
\usepackage{float}  %図を配置するためのパッケージ
\usepackage{latexsym}        % 数学記号を増やすためのパッケージ
\usepackage{amssymb,amsmath} % 複雑な数式を書くためのパッケージ
\usepackage[dvipdfmx]{graphicx} % グラフィクスを使うためのパッケージ
\usepackage{enumerate}       % enumerate環境を高機能にするためのパッケージ
\usepackage{stabst}         % 理工学部の予稿用スタイル
%\english %英語で論文を書く場合に宣言する. jasrticle の代わりに article を使用すること.
\usepackage{comment} %複数行をコメントアウトするためのパッケージ
%以下ソースコードを表示するためのパッケージ
\usepackage{listings}
\lstset{
  basicstyle={\ttfamily},
  identifierstyle={\small},
  commentstyle={\smallitshape},
  keywordstyle={\small\bfseries},
  ndkeywordstyle={\small},
  stringstyle={\small\ttfamily},
  frame={tb},
  breaklines=true,
  columns=[l]{fullflexible},
  numbers=left,
  xrightmargin=0zw,
  xleftmargin=3zw,
  numberstyle={\scriptsize},
  stepnumber=1,
  numbersep=1zw,
  lineskip=-0.5ex
}
\renewcommand{\lstlistingname}{プログラム}

\title{二次元多重連結領域内における構造安定な非圧縮流れの木表現の可視化手法}
%\subtitle{—要旨の場合—} % 副題がない場合はこの行をコメントアウトする．
                        % 副題を囲む横棒は全角ダッシュ文字を使う．
\author{2016SE024 亀谷拓磨\ \ \
        2016SE076 田島嘉人\ \ \
        2016SE090 渡辺康平}
\professor{指導教員：横山哲郎}

\begin{document}
\maketitle

\section{はじめに}
\label{sec:はじめに}
流体力学は，気体や液体の運動について取り扱う力学の主要な研究分野である．流体力学の歴史は古く，この学問が確立される以前から人々の生活に即したものとして発展してきた．流体解析の手法の1つに離散解析がある．離散解析は流れをトポロジカルな観点から解析する．トポロジカルな観点に着目することは大域的な構造に着目するということを意味し，これにより流れの本質的な構造を抜き出すことが可能となる．つまり流れの大枠に着目した解析を行いたい場合，離散解析を用いることで効率的に流れの解析を進められるということである．この解析法の代表的なアプローチとして，流体をその構造安定性に着目して解析する方法がある．構造安定性は，力学系に小さな乱れが加わっても流れのトポロジーが変化しない性質のことである．トポロジーは位相幾何学の用語であり，この立場に立てば，連続的に変形できる図形は同じ形である．例えば，四角形と三角形は同じ形である．構造安定性は一般の流体にはあり得ないが，文献\cite{トポロジカルな流れ構造の理解へ向けて}によれば，有限の制度や有限の時間における挙動に着目したり，本質的な構造に着目するなどの現実的な目的の範囲内であれば，現実の流体にもこの考え方が適応できる．構造安定性に着目すれば，構造安定性から流れの変化を考察することができるようになる．例えば，語表現の研究では流れのトポロジーに対して対応した文字列を定義することで，2つの流体構造の中間構造を文字列の変化として考察することが可能となった\cite{WOTFV}．

本研究は，離散解析手法の表現の1つである木表現に対して，図上への可視化手法を与える．ここで，本研究で扱う木表現は\cite{円盤上の非圧縮流の反転の解析}によって与えられた表現方法である．また，以下で木表現とはこの表現方法を指す．木表現は流線構造を代数的に扱い流れの解析を行うことができるが，その表現から直観的に2次元上の流れの形状を把握することは困難である．そのため，2次元の形状を得たい場合は解析者がその都度木表現を組み合わせて図示することになるが，木表現が複雑になればなるほどその変換も煩雑になり，ともすれば途中で間違った変換を行ってしまうこともあり得る．本研究は木表現を図に自動的に変換する方法を与えることで，解析者の効率的で確実な木文法による流れの解析に寄与するものである．

\section{関連研究}
\label{sec:construction}
本研究で扱う木表現は，語表現の研究を発展させたものである．語表現の研究では，流線のトポロジカルな構造を分類し，それぞれの流線構造を系統的に文字列で表現するアルゴリズムを与えた\cite{WOTFV}．語表現を用いた例として，翼の揚抗比の時間変化を語表現によって表した研究がある\cite{二次元多重連結領域内における構造安定な非圧縮流れの文字列表現アルゴリズム}．語表現は，有界な多重連結領域上で非圧縮かつ非粘性で構造安定な流れを代数的に表すことができる．多重連結領域とは複数の障害物が含まれている領域のことである．ここでは非圧縮・非粘性という理想流体を仮定しているが，この仮定は現実の流体に対しての直接の適用に制限を与える．しかし，現実への応用に関しては文献\cite{二次元多重連結領域内における構造安定な非圧縮流れの文字列表現アルゴリズム}でその適用方法が考えられている．語表現の利点として，流線構造を数学的に厳密に分類できるようになるため，流れの変動を特徴付けて捉えることができるようになる点が挙げられる．また，流れを代数的に扱うことができるため，流線の構造の特徴を説明するための共通言語として用いることができる．文献\cite{WOTFV}によって与えられた語表現には同じ流線に複数の語表現を与えることができるという問題があった．そのため，文献\cite{ハミルトン曲面流に対応する語の列挙アルゴリズム}によって自然な語表現を与えるアルゴリズムが与えられた．また，文献\cite{ハミルトン曲面流に対応する流れの向きを考慮した極大語の列挙アルゴリズム}によって流れの向きを考慮した場合の語表現を与えるアルゴリズムが与えられた．

木表現もその前提条件は語表現と共通であり，有界な多重連結領域上で非圧縮性かつ非粘性で構造安定である．木表現はその特性から，語表現より細かい流れの分類を可能とする．そのため流れの特徴を語表現より，多く捉えることを期待されている．実際，円盤状の非圧縮流の反転の解析を木表現によって行った研究では，語表現と比べた木表現の表現力の高さが確かめられた\cite{多重連結領域上の安定非圧縮流の解析}．

語表現および木表現と関連のある離散解析手法として，コンレイ・モース分解，グラフクラスタリングがある\cite{トポロジカルな流れ構造の理解へ向けて}．これらの手法は，流体に対してそれぞれ異なるアプローチを持つが，流体をその構造安定性に着目して解析するという点では一致している．

\section{自動可視化への準備}
\subsection{可読性の定義}
\label{sec:可読性の定義}
作成するプログラムには，木表現で作成されたトポロジーを確実に図に再現することが求められるが，さらに，再現されたトポロジーは可読性が高いものである必要もある．本研究では，可読性の高さを定義する上でグラフ描画アルゴリズムにおける可視性の高さの基準\cite{力学モデルを用いた階層型グラフデータ画面配置手法の改良手法とウェブサイト視覚化への応用}を参考にプログラムに求められる可読性を定義した．
\begin{itemize}
\item 線が重ならない
\item 線の間が適切な距離を保つ
\item 線が滑らかである
\end{itemize}

\subsection{文法の定義}
\label{sec:文法の定義}
木文法{G=(S，N，F，R)}は以下のように定められる．Sは開始記号，Vは非終端記号の集合，Fは終端記号の集合，Rを生成規則とする．このとき，N= \{ S，A，$B_{+}$，$B_{-}$，$C_{+}$，$C_{-}$，${}C_{+}^{*}$，${}C_{-}^{*}$，\} ，F＝ \{ $a_{\phi}$()，$b_{\phi}(，\{\})$，$b_{\phi-}(，\{\})$，$a_{+}()$，$a_{-}()$，$a_{2}()$，$b_{++}\{，\}$，$b_{+-}\{，\}$，$b_{--}\{，\}$，$b_{-+}\{，\}$，$\beta_{+}\{\}$，$\beta_{-}\{\}$，$c_{+}(，)$，$c_{-}(，)$，l，$\lambda$，cons(，)\}　とする．
\\ 
\\ 流れの生成規則\quad R
\\{\footnotesize
S\quad →\quad $a_{\phi}$($A^{*}$) ｜$b_{\phi+}$($B_{+}$，\{${}C_{-}^{*}$\})｜$b_{\phi-}$($B_{-}$，\{${}C_{+}^{*}$\})
\\A\quad →\quad$a_{+}$($B_{+}$) ｜$a_{-}$($B_{-}$)｜$a_{2}$(${}C_{+}^{*}$，${}C_{-}^{*}$)
\\$A^{*}$\quad  →\quad $\lambda$｜ cons(A，$A^{*}$)
\\$B_{+}$\quad  →\quad l ｜$b_{++}$\{$B_{+}$，$B_{+}$\}｜$b_{+-}$\{$B_{+}$，$B_{-}$\}｜$\beta_{+}$\{${}C_{+}^{*}$\}
\\$B_{-}$\quad  →\quad l ｜$b_{--}$\{$B_{-}$，$B_{-}$\}｜$b_{-+}$\{$B_{-}$，$B_{+}$\}｜$\beta_{-}$\{${}C_{-}^{*}$\}
\\$C_{+}$\quad →\quad $c_{+}$($B_{+}$，${}C_{-}^{*}$)
\\$C_{-}$\quad →\quad $c_{-}$($B_{-}$，${}C_{+}^{*}$)
\\${}C_{+}^{*}$\quad →\quad $\lambda$｜cons($C_{+}$，${}C_{+}^{*}$)
\\${}C_{-}^{*}$\quad →\quad $\lambda$｜cons($C_{-}$，${}C_{-}^{*}$)
\\}

\begin{figure}[H]
\centering
\includegraphics[width=8cm]{akei.png}
\caption{$a$系の流れ　左から$a_{+}$，$a_{-}$，$a_{2}$}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[width=8cm]{bkei.png}
\caption{$b$系の流れ　左から$b_{++}$，$b_{--}$，$b_{+-}$，$b_{-+}$，$b_{+}$，$b_{-}$}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[width=4cm]{ckei.png}
\caption{$c$系の流れ　左から$c_{+}$，$c_{-}$}
\end{figure}



\subsection{アプローチ}
\label{sec:アプローチ}
本研究の目的の達成には，\ref{sec:可読性の定義}の定義を満たすトポロジーな流れの図を二次元上の画面に表示することを必須としている．アプローチとしては，コンピュータのディスプレイ上に作成した図を可視化し，画像ファイルとして保存することを可能にするプログラミング言語を本研究で使用した．私達は様々な分野での実績があり多様な環境での信頼性が高い Python とベクタ形式での描画を支援するAsyptoteの２つプログラミング言語をアプローチ方法とした．

\subsection{構文解析}
\label{sec:構文解析}
本研究ではPythonでの実装を行うため，Python専用の構文解析ライブラリPLYを利用し構文解析を行った．PLYとは，Python Lex-Yaccの略であり，Python専用の構文解析ライブラリである．lex.pyとyacc.pyからなる．lex.pyでは，入力されたテキストを正規表現により定義されたデータ構造に分解し，字句解析を行う．その後，yacc.pyにより，自由文法によって定義された構文を評価して抽象構文木を作成し構文解析を行う．

\section{実装}
\label{sec:実装}
\subsection{Pythonによる実装}
\label{sec:pythonによる実装}
\subsubsection{実装するクラス図}
\label{sec:実装するクラス図}
本研究では，デザインパターンの１つであるインタプリタパターンを利用してクラス図を作成した．インタプリタパターンについては，\cite{Java言語で学ぶデザインパターン入門}を参考にした．インタプリタパターンは，解析された結果に則り，処理を実行したい場合に利用される．本研究では，与えられた文字列をPLYを利用し字句解析・構文解析を行う．そのため，木文法を扱うのに適しているインタプリタパターンを利用し，クラス図を作成した．メリットとして，プログラムの修正を容易にし，見た目をシンプルにすることができる．今回作成したクラスが多くなったため，例として一部分のみを図示する．
\begin{figure}[H]
\centering
\includegraphics[width=85mm]{class_diagram1.png}
\caption{作成したクラス図}
\end{figure}


\subsubsection{描画機能の実装：大きさの決定}
\label{sec:描画機能の実装：大きさの決定}
Pythonで流線図を描画するにあたり，Python用のライブラリであるmatplotlibを使用する．matplotlibはグラフ描画のためのライブラリであり，棒グラフや折れ線グラフなどの一般的なグラフを作図することができる．また，それ以外にも平面上への関数・図形の描画や波のシミュレーションなど様々な描画にも利用できる．

自動描画を実現するプログラムは木表現を与えるのみで動作することが求められ，私達が引数を与えて円を描くことはできない．また，子を持つ親を描画する際，子は親の描く流線の内部に描画される必要があるため，必然的に親の大きさは子の大きさよりも大きくなる．そのため，プログラムには描画した際の大きさを柔軟に変更できる仕組みを組み込む必要がある．本研究では，この課題を解決するため木表現の葉から大きさを決定することにした．例として，$a_{+}$($b_{++}$($b_{++}$($l$, $l$), $l$))という木表現を挙げる．この木表現では，$a_{+}$が$b_{++}$という子を持ち，その子である$b_{++}$は($b_{++}$($l$, $l$), $l$))という2つの子を持っている親である．この場合，プログラムは$b_{++}$($l$, $l$)からその大きさを決める．続いて，$b_{++}$($l$, $l$)の親である$b_{++}$($b_{++}$($l$, $l$), $l$)の大きさを決定する．ここで，親の$b_{++}$の大きさは，子の$b_{++}$($l$, $l$), $l$)を踏まえた大きさとなる．そして最後に，その大きさをもとに，$a_{+}$の大きさが決定される．この流れを図\ref{fig:draw_flow}に示した．ここで，それぞれについて「大きさを決定する」としているのは，大きさを決定した時点ではmatplotlibのグラフ上に描画しないからである．これは，子から描画しようとしても，その時点ではグラフ中の位置を決定できないことによる．この例では，$b_{++}$($l$, $l$)の位置を先に決定してしまうと，その親である$b_{++}$の位置もそれに依存して決まってしまう．しかし，もし親の$b_{++}$がもう一つの子を持っていた場合，葉から描画していく仕様上もう一つの子も既に決められた位置を持つことになる．ここで，子の位置を決定する時点で他の流線との位置関係を決定できる仕組みがあり，２つの子の位置の整合性が取れているのであれば子から順に描画することもできるが，子の情報だけでは親との位置関係は分からないためこの仕組みは作成できない．そのため，実際にグラフ上に描画する前に根までのすべての大きさを決定する処理を行い，次に根の位置を決定し順に子を描画していく方法を取った．

\begin{figure}[H]
\centering
\includegraphics[width=7cm]{draw_flow.png}
\caption{$a_{+}$($b_{++}$($b_{++}$($l$, $l$), $l$))大きさ決定のイメージ}
\label{fig:draw_flow}
\end{figure}

\subsubsection{描画機能の実装：流線の描画}
\label{sec:描画機能の実装：流線の描画}
matplotlibでは，円や長方形などの図形をもともと用意されている関数で呼び出したりできるが，これらは決められた形にしかならない．流線を描画するにあたり，一部のトポロジーは円などの固定された図形でも表現可能だが，$b$系を含む流線はそれらで表すことができず，時々に合わせて形を変えることが求められる．そこで，本研究ではこれらの$b$系を含む図形を点でモデル化することにした．例として，$a_{+}$が子に$b$系を持っていると想定した場合の流線を図\ref{fig:a+-have-beta}に示す．ただ，これは製作途中の仮のものであるため，その子の大きさの円を仮に与え描画している．この図形は，点5つから構成されている．子の専有領域の接合部である2点と最右点・最左点・最下点の3点である．この5点を、スプライン補間で補間することにより流線を表現した．

\begin{figure}[H]
\centering
\includegraphics[width=2cm]{a+-have-beta.png}
\caption{$b$系を持つ図形の作図}
\label{fig:a+-have-beta}
\end{figure}

\subsection{Asymptoteによる実装}
\label{sec:Asymptoteによる実装}
Asymptoteでは，木表現に対しての\ref{sec:可読性の定義}の定義を満たす図を作成するためのライブラリを提供し，実際に存在する流体をトポロジー的に再現することができれば本研究の目的を満たすことを示す．

\subsubsection{提供するライブラリ内の関数}
\label{sec:提供するライブラリ内の関数}
void ap(real d,pair s)

void am(real d,pair s)

void a2(real d, pair s)

void bpp(real d, pair s)

void bmm(real d, pair s)

void bp(real d, pair s)

void bm(real d, pair s)

void bpm(real d, pair s)

void bmp(real d, pair s)

void cp(real d, pair s)

void cm(real d, pair s)

以上が木文法の生成規則に準じた主な流れの関数である．だが，描画する際に描画対象の図によって流れの向きを調節する必要があるため，図が右向き(Right)か左向き(Left)，上向き(Up)か下向き(Down)の頭文字を関数の後ろにつける．例えば，右向きかつ上向きの$a_{+}$の流れを描画するにはvoid apRU(real d，pair s)となる．real型dは流線図の大きさを表し，pair型sは複素数(x，y)であり流線図を場所を表す．これらの関数を組み合わせ，パラメータを調節することにより目的の流れを描画できる．


\subsubsection{Asymptoteによる実行方法}
\label{sec:Asymptoteによる実行方法}
Asymptoteではプログラムを実行する方法として，Ubuntuの端末やWindowsのコマンドプロンプト上に直接コードを記述するinteractive mode(対話モード)という方法
が存在する．そこでライブラリを読み込み，画面上に表示させたい流線図に対応する関数を記述することで，画面上にトポロジー化された流線図を表示させる．



\subsubsection{実行例}
\label{sec:実行例}
本研究では非圧縮流体を題材としている．しかし，トポロジー的な流れの図を描画できるかは，非圧縮流体でなくても実証は可能である．さらに，非圧縮流体以外の実際に存在する流れを例題に示すことで本研究の多様性が高まるなどが期待できる．本研究では，カルマン渦を実例として挙げた\footnote{livedoor NEWS（2015年01月9日），＜http://news.livedoor.com/article/datail/9657771/＞（参照 2019-09-17）}．

\begin{figure}[H]
\centering
\includegraphics[width=4cm]{karman_vortex_street.png}
\caption{カルマン渦}
\end{figure}

ある範囲の速度の流れの中に円筒状の障害物が存在すると，その後流側に規則正しく左右交互に並んだ2列の渦が発生する．この渦をカルマン渦と呼ぶ．本研究では，一部のカルマン渦をトポロジー的に表した図をAsymptoteで再現する．トポロジー化してあるカルマン渦については，文献\cite{brons2007streamline}を参照した．

\begin{figure}[htbp]
  \begin{center}
  \begin{tabular}{c}    
  \begin{minipage}{0.5\hsize}
    \begin{center}
      \includegraphics[width=30mm]{karman_vortex_street_topology.png}
    \end{center}
    \caption{トポロジー化したカルマン渦}
    \label{fig:one}
  \end{minipage}
  \begin{minipage}{0.5\hsize}
    \begin{center}
      \includegraphics[width=30mm]{karman_vortex_street_reproduction.pdf}
    \end{center}
    \caption{作成したカルマン渦}
    \label{fig:two}
  \end{minipage}
  \end{tabular}
  \end{center}
\end{figure}

図\ref{fig:one}は$a$系と$c$系で構成されてる．本研究の現状では$c$系を組み合わせての描画は実現できていないため，関数amRU，amRD，a2Rにパラメータを与えてカルマン渦を作図した．

\section{おわりに}
\label{sec:おわりに}
\subsection{Python}
\label{sec:python}
作成中のプログラムは，現在再現できる$a$系と$b$系の組み合わせの範囲内では\ref{sec:可読性の定義}により定められた条件を満たす図を製図できる．また，まだ再現できない系の流線に対しても葉から大きさを決定し根から描画する考え方は適用可能であると考える．しかし，一部の流れにはループが存在し，その部分の要素は無限に増やすことが可能である．そのため，要素数が無限に増えても柔軟に生成される図を変更できることが求められる．現在，これを解決するためグラフ描画アルゴリズムを利用を検討している.グラフ描画アルゴリズムを用いることで，文献\cite{力学モデルを用いた階層型グラフデータ画面配置手法の改良手法とウェブサイト視覚化への応用}，\cite{デフォルメマップ生成のための道路変形モデルとそのシステム評価}にあるように柔軟に図の変更を行うことができるのではないかと考えている．具体的には$C$系の中ので発生する流れ同士の距離感を一定に保つことなどを考えているが，まだ実装には至っていない．今後は，これらの描画手法を実装し，また，作成したプログラムの有用性に関しての検証を行っていきたい．

\subsection{Asymptote}
\label{sec:Asymptote2}
Asymptoteで作成したプログラムもPythonと同等な理由で，$c$系を組み合わせ可能の段階には至っていない．また，本研究の目的である入力を完全な木文法での描画は現状実装できなかった．今後は，本研究の目的達成のために改良を施していきたい．
\bibliography{abst}
\bibliographystyle{junsrt}
\end{document}
