流域抽出プログラムおよび流域抽出装置
【課題】あらかじめ流域を知らないユーザが使用しても正しい流域を抽出できるコンピュータプログラムを提供する。
【解決手段】コンピュータを制御する流域抽出プログラムであって、前記コンピュータは地図上の複数の領域の標高を示す標高データを保持し、前記複数の領域は、第１領域を含み、前記流域抽出プログラムは、前記第１領域に流れ込む水の流域を、前記標高データに基づいて上流方向に探索する第１手順と、前記第１手順によって特定された流域が正しいか否かを判定する第２手順と、を前記コンピュータのプロセッサに実行させ、前記第２手順において、前記特定された流域が正しくないと判定された場合、前記第１手順を再び前記プロセッサに実行させる。
【解決手段】コンピュータを制御する流域抽出プログラムであって、前記コンピュータは地図上の複数の領域の標高を示す標高データを保持し、前記複数の領域は、第１領域を含み、前記流域抽出プログラムは、前記第１領域に流れ込む水の流域を、前記標高データに基づいて上流方向に探索する第１手順と、前記第１手順によって特定された流域が正しいか否かを判定する第２手順と、を前記コンピュータのプロセッサに実行させ、前記第２手順において、前記特定された流域が正しくないと判定された場合、前記第１手順を再び前記プロセッサに実行させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータを使って流域を抽出する方法に関する。本発明は特に、１以上の地点の位置を入力データとし、それぞれの地点の流域を数値地形モデル（digital elevation mode, DEM）に基づいて抽出するコンピュータプログラム（流域抽出プログラム）に関する。
【背景技術】
【０００２】
流域は、河川またはダムなどの水を管理する土木構造物にとって重要な情報である。ある地点の流域とは、その地点に集まってくる水が流れてきた領域である。ダムの建設のためには、そのダムに平均的に入ってくると予想される水量、すなわちダムの流域の平均降雨量が不可欠である。また、ダムの管理のためには、そのダムの水源林、すなわち流域内の森林の状態管理が不可欠である。河川の水位予測のためには、その河川の流域の予想降雨量が不可欠である。都市機能を豪雨から守るための雨水排水設備（下水）の設計には、その設備が対応すべき最大の降雨強度と、流域面積とが不可欠である。
【０００３】
流域は、水が流れる方向を逆にたどることによって求めることができる。実際に、この流れの性質を利用して流域を抽出するコンピュータプログラム（流域抽出プログラム）が存在する。主要な流域抽出プログラムの処理手順は、非特許文献１に詳しい。
【０００４】
流域抽出プログラムで利用する電子データは、地表面の標高データである。この様な電子データはＤＥＭ（Digital Elevation Model）と呼ばれる。ＤＥＭでは、ある領域の地表面がセル（cell）と呼ばれる小領域に分割され、それぞれのセルに標高値が与えられる。
【０００５】
通常、水が流れる方向はその地点の最も急な下り勾配方向と一致する。この流れの性質を利用した流域抽出方法が、最急勾配法（steepest slope method）と呼ばれる方法である。この方法では、あるセルの流域が、そのセルから最も急な下り勾配の方向を逆にたどった時に通過したセルとなる。あるセルの勾配は、そのセルおよびそのセルの周囲の８セルの標高データから求めることができる。
【０００６】
最急勾配法では、周囲のセルの標高以下の標高を持つセルの取り扱いが問題となる。このようなセルは、流域抽出プログラムの研究分野で「平地（flat）」または「窪地（sink, depression）」と呼ばれている。平地は周囲の１以上のセルの標高と同じ標高を持つセルであり、窪地は周囲のすべてのセルの標高より小さい標高を持つセルである。このようなセルが存在する場合、最急勾配法を利用すると、正しい流域を抽出することができない。ところが、平地および窪地は通常のＤＥＭに多数存在する。したがって、最急勾配法のみでは、正しい流域が抽出できない。
【０００７】
図１８は、窪地を説明するための図である。グラフ１８００は、ＤＥＭの鉛直断面図に最急勾配法で決定した水が流れる方向を重ねた図である。セル１８０１は河口であり、最も標高が低い。セル１８０４は隣接するセル（１８０３および１８０５）よりわずかに標高が低い。最急勾配法で決定した水が流れる方向を矢印で示す。セル１８０１の流域セルはこの矢印をセル１８０１から逆にたどった範囲であり、セル１８０２〜１８０３となる。しかしこの結果は誤りである。専門家であれば、セル１８０１の流域セルをセル１８０２〜１８０９とするであろう。
【０００８】
この問題の最も一般的な解決方法は、勾配を無視し、標高の配置に基づいて水の流れる方向を決定する窪地埋め（sink filling）法である。窪地埋め法は、最急勾配法に比べ、より多くのセルの標高データを利用する。窪地埋め法を使う流域抽出プログラムは非特許文献２および非特許文献３に詳しく説明されている。
【０００９】
窪地埋め法では、まず窪地を平地に変える。つまり、窪地の標高を、周囲のセルのうち最小の標高にする。図１８では、窪地セル１８０４の標高をセル１８０５と同じ標高にする。次に、平地の流出口を決定する。具体的には、平地に隣接する平地よりも低い標高を持つセルを流出口として決定する。流出口が存在しない場合は、平地にするセルを広げる。
【００１０】
図１８では、セル１８０４および１８０５の流出口が存在しない。そこで、平地にするセルをセル１８０３から１８０５に広げる。広げた後の状態をグラフ１８２０に示す。
【００１１】
グラフ１８２０のセル１８２１〜１８２９は、それぞれ、グラフ１８００のセル１８０１〜１８０９に対応する。
【００１２】
グラフ１８２０を参照すると、セル１８２３から１８２５の標高が等しく、これらのセルが平地になっていることがわかる。この場合、流出口はセル１８２２となる。最後に、平地内の流れが流出口に向かうように平地内の水が流れる方向を決定する。平地セル１８２３から１８２５の水が流れる方向は、その流出口であるセル１８２２に向かうように決定される。セルごとの水が流れる方向を、グラフ１８２０に矢印で示す。この矢印をセル１８２１から逆にたどると、セル１８２９までたどれる。最急勾配法の結果を窪地埋め法により修正すると、セル１８２１の流域セルはセル１８２２〜１８２９である、という正しい結果が得られる。
【００１３】
窪地埋め法の処理効率を上げる実装方法として、特許文献１に開示された「Method for flow analysis utilizing cell elevation topography」が挙げられる。この方法では、あらかじめ領域の内部を複数のmajor cellに分割し、さらにmajor cellの内部を少なくとも横方向３縦方向３のminor cellに分割する。そして、あるminor cellにおける勾配を算出するときに、そのminor cellを含むmajor cellと、さらにそのmajor cellに隣接するmajor cellについて窪地埋め法を適用する。その後、これらのmajor cellに含まれるminor cellについて勾配を再度算出する。非特許文献１に開示された方法では、処理の対象とする領域全体に窪地埋め法を適用する必要があったが、特許文献１に開示された方法では、処理の対象とする領域を複数に分割し、それぞれ分割された領域ごとに窪地埋め法を適用することが可能になる。
【００１４】
いずれの方法であっても、次の手順で流域を抽出する。まず、水の流れる方向を勾配のみから決定する（最急勾配法）。次に、水が流れ出ない平地セルおよび窪地セルに対して、そのセルの水の流れる方向を標高の配置に基づいて決定する（窪地埋め法）。最後に、ユーザが指定したセルから水の流れる方向を逆にたどる。そのときに通ったセルが、流域セルである。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】米国特許出願公開第２００５／００４９８０２号明細書
【非特許文献】
【００１６】
【非特許文献１】Costa-Cabral, M. C., and S. J. Burges (1994), Digital elevation model networks (DEMON): A model of flow over hillslopes for computation of contributing and dispersal areas, Water Resource Research, 30(6), 1681−1692.
【非特許文献２】O'Callaghan, J. F., and D. M. Mark: The extraction of drainage networks from digital elevation data, Computer Vision, Graphics, and Image Processing, 28 (3), 323-344, 1984.
【非特許文献３】Jenson, S. K., and J. O. Domingue: Extracting topographic structure from digital elevation data for geographic information system analysis, Photogrammetric Engineering and Remote Sensing, 54 (11), 1593−1600, 1988.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
従来の流域抽出プログラムでは、水の流れる方向を決定した後に、流域を抽出する。したがって、流域を抽出する前に、水の流れる方向を決定する範囲をプログラムに与える必要がある。もし、水の流れる方向を決定する範囲が流域よりも小さい場合、正しい流域は抽出できない。したがって、正しい流域を抽出するためには、抽出される流域をプログラムのユーザがあらかじめ知っておく必要がある。しかし、流域を知っているユーザは、流域抽出プログラムを使う必要はない。このため、従来の流域抽出プログラムは、限られた用途にしか適用されてこなかった。
【００１８】
本発明はこの問題に鑑みてなされたものである。本発明の目的は、あらかじめ流域を知らないユーザであっても流域を抽出できるプログラムコンピュータプログラムを提供することである。
【課題を解決するための手段】
【００１９】
本願で開示する代表的な発明は、コンピュータを制御する流域抽出プログラムであって、前記コンピュータは、前記流域抽出プログラムが格納されるメモリと、前記メモリに格納された前記流域抽出プログラムを実行するプロセッサと、を備え、地図上の複数の領域の標高を示す標高データを保持し、前記複数の領域は、第１領域を含み、前記流域抽出プログラムは、前記第１領域に流れ込む水の流域を、前記標高データに基づいて上流方向に探索する第１手順と、前記第１手順によって特定された流域が正しいか否かを判定する第２手順と、を前記プロセッサに実行させ、前記第２手順において、前記特定された流域が正しくないと判定された場合、前記第１手順を再び前記プロセッサに実行させることを特徴とする。
【発明の効果】
【００２０】
本発明の一実施形態によれば、ＤＥＭから流域を抽出するコンピュータプログラムを提供できる。このプログラムによって、あらかじめ流域を知らないユーザであっても、流域を抽出することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施の形態におけるコンピュータシステムの構成を示す概略ブロック図である。
【図２】本発明の実施形態のＰＣによって実行される処理を示すシーケンス図である。
【図３】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの入力待ちの状態を示す説明図である。
【図４】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの解析終了の状態を示す説明図である。
【図５】本発明の実施形態の流域抽出処理の詳細を示すフローチャートである。
【図６】本発明の実施形態の上流探索処理の詳細を示すフローチャートである。
【図７】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの上流探索処理の進捗を示す説明図である。
【図８】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの流域外セル抽出処理の進捗を示す説明図である。
【図９】本発明の実施形態の下流探索処理の詳細を示すフローチャートである。
【図１０】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの下流探索処理の進捗を示す説明図である。
【図１１】本発明の実施形態のセルおよび部分領域を示す説明図である。
【図１２】本発明の実施形態の部分領域のデータ構造を示す説明図である。
【図１３】本発明の実施形態のセルのデータ構造を示す説明図である。
【図１４】本発明の実施形態のセル勾配についての説明図である。
【図１５】本発明の実施形態において水が流れる方向と、それに対応するフラグの値を説明するための図である。
【図１６】本発明の実施形態の窪地のデータ構造を示す説明図である。
【図１７】本発明の実施形態の窪地埋め処理の詳細を示すフローチャートである。
【図１８】窪地を説明するための図である。
【発明を実施するための形態】
【００２２】
最初に、本発明の概要を説明する。
【００２３】
本発明は、以下の３つの発見に基づいている。
【００２４】
１．窪地および平地の面積、体積、形状等はあらかじめわからない。
【００２５】
２．窪地および平地がプログラムで得られた流域に隣接している場合、プログラムで得られたその流域が誤っている可能性がある。
【００２６】
３．流域の最上流は自明ではない一方、流域の最下流は自明である。
【００２７】
発見１および２は、発明者らが先に出願した発明（特願２００８−００２２８４，流域推定プログラム）を様々な流域でＤＥＭデータやセルの大きさを様々に変化させて検証する過程で発見した。そこで、特願２００８−００２２８４に示した発明の概要を以下に説明する。
【００２８】
特願２００８−００２２８４に示した発明は、任意のセルがある面積以下の窪地でないことを証明できる、という発見に基づく。ある面積をもった（すなわちある数のセルからなる）窪地または平地が取り得る最大の長さは、それらのセルを１列に直線上に並べた場合の長さである。あるセルからこの長さよりも近いセルについて窪地埋め法を適用すれば、少なくとも中心にあるセルはある面積以下の窪地または平地ではなくなる。そこで、特願２００８−００２２８４に示した発明では「窪地の最大面積」というパラメタを導入し、これ以下の面積の窪地および平地を埋めることにした。この発明はさらに、先に出願した別の発明（特開２００７−０３４３７３，空間シミュレーションプログラムおよび装置）の「部分領域」という概念を利用する。
【００２９】
特願２００８−００２２８４に示した発明の実施例は以下の通りである。あらかじめ窪地の最大面積を定義しておく。さらに、あらかじめ隣接する複数のセルから構成される部分領域を定義し、全てのセルを部分領域に対応づけておく。開始セルをユーザが指定すると、プログラムは開始セルを対象セルとする（ステップ１）。つづいて、対象セルを含む部分領域を対象部分領域とする（ステップ２）。対象部分領域からの距離が、最大の窪地が取り得る最大の長さよりも近い部分領域について、窪地埋め処理を行う（ステップ３）。この処理によって、対象部分領域からあらかじめ決めた面積以下の窪地が取り除かれる。つづいて、対象セルに隣接する８セルについて下流方向（すなわち、各セルから流出する水の流向）を算出する（ステップ４）。下流方向は、最も急な下り勾配の方向である。下流方向に対象セルがあるセルを、次の対象セルとする（ステップ５）。次の対象セルが存在する場合、ステップ２に戻る（ステップ６）。
【００３０】
一方、本発明は先の発明とは異なる発見を利用する。すなわち、本発明は上述した発見１から３に基づいている。本発明は、先の発明では必要であった「窪地の最大面積」というパラメタを不要にする。発明者らが考案した、本発明の流域抽出プログラムは以下のステップ１およびステップ２からなる。
【００３１】
ステップ１：ユーザが指定したセルの上流セルを探索する。
【００３２】
水の流れる方向は、最急勾配法、特願２００８−００２２８４に示した方法などで決定すればよい。これによって、ユーザが指定したセルを下流端とする流域が抽出される。ところが、ステップ１によって得られた流域は誤っている可能性がある。なぜなら、得られた流域の外側にその流域に隣接する窪地がある場合、得られた流域は誤っている可能性があり（発見２）、そのような窪地が存在しないことを保証できないためである（発見１）。また、最上流は自明ではない（発見３）。つまり、たとえば地図や現場に、最上流を示す印があるわけではないため、ステップ１で得られる流域が正しいことを保証できない。
【００３３】
ステップ２：ステップ１で抽出された流域の真偽を判定する。
【００３４】
この判定には、流域の定義の対偶を利用する。すなわち、流域でないセルの下流に、流域でないセルしかなければその流域は正しい。発見３によれば、最下流は自明である。つまり、河川の最下流は海である（正確には、最下流は水の流出口がない領域であり、地域によっては、水の流出口がない湖、砂漠などが最下流となる場合もある。以下、水の流出口がない領域を「無効領域」、その領域に含まれるセルを「無効セル」と表記する）。ところが、プログラムでは最下流が無効領域とならない場合がありうる。つまり最下流が窪地となる場合である。そこで、このセル近傍の水の流れる方向を窪地埋め法により決定した後、下流探索をやり直す。こうして、ステップ１で抽出された流域以外のセルを開始セルとし、無効セルまで下流探索する。こうして得られた下流セルにユーザが指定したセルが含まれない場合、ステップ１で抽出された流域は真であると判定する。なお、プログラムの処理においては、標高値などの指標に基づいて下流探索を打ち切ってもよい。
【００３５】
ステップ２の判定の結果が偽であれば、ステップ１に戻る。その場合、ユーザが指定したセルの上流に、ステップ１で抽出された流域以外のセルが存在する。したがって、再び実行されたステップ１で得られる流域は、前回のステップ１で得られた流域とは異なる。
【００３６】
なお、ステップ２において下流探索の開始セルとするセルは、ステップ１で抽出された流域以外のセルであって、かつステップ１で抽出された流域セルに隣接するセルだけに限定してもよい。なぜならばこれらのセルは、流域が偽と判定される場合に必ず下流探索されるためである。
【００３７】
以下、本発明の実施形態を添付図面に基づいて説明する。
【００３８】
図１は、本発明の実施形態におけるコンピュータシステムの構成を示す概略ブロック図である。
【００３９】
本実施形態のコンピュータシステムは、ＰＣ（Personal Computer）１００によって構成される。ＰＣ１００は、入出力部１１０を備える。入出力部１１０は、キーボード１１１およびマウス１１２などからなる入力部と、ディスプレイ１１３などからなる出力部によって構成される。ユーザは、入力部から命令を入力し、出力部を用いて結果を確認することができる。
【００４０】
さらにＰＣ１００は、メモリ１２０及びＣＰＵ（Central Processing Unit）１３０を備える。メモリ１２０には流域抽出プログラム１４１が展開される。この流域抽出プログラム１４１はＣＰＵ１３０への命令によって構成される。ＣＰＵ１３０は、流域抽出プログラム１４１の命令に従い計算、ＨＤＤ（Hard Disk Drive）１９０へのアクセス、および入出力部１１０との情報の交換などを行う。以下の説明において流域抽出プログラム１４１が実行する処理は、実際には、流域抽出プログラム１４１に記述された命令に従うＣＰＵ１３０によって実行される。
【００４１】
ＨＤＤ１９０には地図データ１９１、標高データ１９２、海域データ１９３が格納されており、流域抽出プログラムはこれらのデータを読み込むことができる。なお、ＨＤＤ１９０は、ＰＣ１００に内蔵されてもよいし、ＰＣ１００の外部に接続されてもよいし、ＰＣ１００からネットワーク経由でアクセスできる別の装置に接続されてもよい。
【００４２】
地図データ１９１は、ユーザに場所を理解させる情報であればよい。地図データ１９１として適している情報として、地名、行政界、道路、鉄道、衛星画像、等高線、海岸線などが挙げられる。本実施形態では少なくとも等高線および海岸線が利用される。さらに、谷線、河道流路線、海岸線、湖沼面、海面等、水面の位置を示す情報、流域境界線など分水嶺の位置を示す情報が必要に応じて利用されてもよい。
【００４３】
標高データ１９２は、一般的にDigital elevation model（ＤＥＭ）と呼ばれるデータである。すなわち、セルの位置とそのセルにおける地表面の標高を記載した情報である。代表的なＤＥＭは、地表面に等間隔で並べた正方形のセル（square grid）における標高の値である。
【００４４】
海域データ１９３は、流出口がない水域を示すデータである。つまり、海域に加え、閉塞湖沼域（水の流出口がない湖）等が判別できるデータである。多くの場合、このデータは海域を示すデータと同じであり、海域は標高データ１９２に基づいて判別できる。すなわち、通常の標高データでは、陸域には標高値が、海域には海域を示す値が格納されている。その場合、この海域データ１９３は不要であり、標高データ１９２のみで十分である。
【００４５】
図２は、本発明の実施形態のＰＣ１００によって実行される処理を示すシーケンス図である。
【００４６】
以下、図２にしたがってシステムの処理シーケンスを説明する。
【００４７】
ＰＣ１００で流域抽出プログラム１４１が起動される。流域抽出プログラム１４１は、ＨＤＤ１９０から地図データ１９１を読み出す（ステップ２０１）。データを読み出した流域抽出プログラム１４１は、ウィンドウ３００からなるＧＵＩ（Graphical User Interface）をディスプレイ１１３に出力する（ステップ２０２）。
【００４８】
図３は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの入力待ちの状態を示す説明図である。
【００４９】
図３のＧＵＩは、ディスプレイ１１３の所定の領域に表示されるウィンドウ３００からなり、キーボード１１１及びマウス１１２による入力を受け付ける。ウィンドウ３００は、少なくとも地図３１０を表示する。ユーザは、所定の操作によって、ユーザが必要とする地域の地図３１０を表示させることができる。地図３１０の縮尺は、流出現象の空間スケールと同程度であることが望ましい。したがって典型的な流出現象であれば、1/25,000かそれより粗い縮尺が適当である。本実施例の地図３１０は等高線３１１および海岸線３１２の情報を含む。
【００５０】
さらにウィンドウ３００は少なくとも、ユーザが１以上の地点を指定するための機能、および、ユーザがその指定を確定するための機能を有する。後述するように、１以上の地点を指定するためにマウスポインタ３０１が使用され、その指定を確定するために解析ボタン３０３が使用される。
【００５１】
このＧＵＩを用いてユーザは解析対象を指定する（ステップ２０３）。本実施の形態では、ユーザがマウス１１２を動かすことによってマウスポインタ３０１を地図３１０上で動かし、マウス１１２をクリックすることによって、任意の地点を下流端として指定する。なお、ユーザの操作結果をユーザにわかりやすく伝えるために、指定した地点にアイコン３０２を表示することが望ましい。
【００５２】
図３は、ユーザが河口付近のごく近接した２地点を下流端として指定した状態を示している。この場合、流域抽出プログラム１４１は、これからこれらの２地点を下流端とし、それらの流域を解析することになる。ユーザは解析対象を入力した後、解析ボタン３０３をクリックする。解析ボタン３０３がクリックされると、流域抽出プログラム１４１は、入力された地点に対応するセルを「開始セル」として指定する。
【００５３】
なお、ステップ２０３で入力する解析対象を地点に限定する必要はない。セルに変換できる情報であるかぎり、どのような情報が入力されてもよい。地点以外の代表的な情報として、線又は面が挙げられる。入力された点、線又は面の情報は、地理情報システムの基本的な公知の技術を用いてセルに変換することができる。このような技術は、たとえば、伊里政夫 監修，腰塚武志 編集（１９９３），計算機科学と地理情報処理 第２版， 共立出版株式会社， ISBN 4320026365.に記載されている。
【００５４】
線として河道流路線（河心線）を入力した場合、ＤＥＭによる表現が難しい細かい水路を考慮した流域抽出が可能になる。線として海岸線を入力した場合、その海岸線の流域を抽出することが可能になるため、たとえば湾の流域を抽出する際に便利である。面として湖沼面を入力した場合、その湖に対する流域を抽出することが可能になる。
【００５５】
あるいは、これらの情報は、ユーザによって入力されるかわりに、地図データ１９１から取り込まれてもよい。たとえば、河道流路線、海岸線、湖沼面等は地理情報データとして一般に流通しているため、それらを利用することができる。
【００５６】
本実施形態では、サブウィンドウ３３０のラジオボタン３３２を操作することによって、ユーザが入力方法を選択できる。例えば、ユーザがラジオボタン３３２の「マウス指定」および「点」を指定した場合、ユーザは、マウス１１２を使用して下流端の地点を入力することができる。あるいは、ユーザがラジオボタン３３２の「開く」を指定した場合、ユーザは、地図データ１９１に含まれる情報（例えば河道流路線等）を入力することができる。
【００５７】
さらに、ステップ２０３で、ユーザは、流域外の点、線、面等を追加的に入力してもよい。その場合、ユーザは、流域内の点、線、面等に加え、流域外の地点、線、面等を入力した後、解析ボタン３０３をクリックする。解析ボタン３０３がクリックされると、流域抽出プログラム１４１は流域外として入力された点、線、面等に対応するセルを「無効セル」に指定する。したがって、１以上のセルが開始セルとして、それ以外の０以上のセルが無効セルとして指定されることになる。流域外の情報を入力すると、後に説明する下流探索処理（ステップ５０４）を大幅に短縮することが可能になる。本実施形態では、サブウィンドウ３３０のラジオボタン３３１を操作することによって、入力された地点等が流域内または流域外のどちらであるかを選択できる。
【００５８】
さらに、２０３で、ユーザは、標高データに基づく流域外セル（または無効セル）の判定方法を定義してもよい。一般に、ある地点の上流には、その地点よりも標高が高い地点のみが存在する。この知識を利用すれば、開始セルよりも標高の低いセルは流域外セル（または無効セル）と見なせる。したがって、流域抽出プログラム１４１は、開始セルよりも標高の低いセルを流域外セル（または無効セル）と見なしてもよい。あるいは、流域抽出プログラム１４１は、標高データに誤りがある場合を考慮し、ある値よりも小さい標高を持つセルを流域外セル（または無効セル）と見なしてもよい。
【００５９】
次に流域抽出プログラム１４１は、流域抽出処理（ステップ２０４）を繰り返し行う。このステップ２０４は、標高データおよび海域データ読み込み処理（ステップ２０５）、および、進捗表示処理（ステップ２０６）を含む。ステップ２０５では、流域抽出プログラム１４１がＨＤＤ１９０から標高データ１９２を読み込む。ステップ２０６では、流域抽出プログラム１４１が進捗を示す記号をウィンドウ３００に表示する。ステップ２０６は必須ではないため省いてもよい。ステップ２０４の詳細は図５から１０を用いて説明する。
【００６０】
最後に流域抽出プログラム１４１は処理結果である流域をウィンドウ３００に表示する（ステップ２０７）。
【００６１】
図４は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの解析終了の状態を示す説明図である。
【００６２】
この図４には、流域を示す２種類の記号が表示されている。第１の記号は、水が流れる方向を示す線分４０１である。水はこの線分に沿って流れ下る。第２の記号は、分水嶺を示す線分４０２である。この分水嶺の内側にある水は、図３で指定した二つの点３０２のいずれかに流れ下る。一方で、この分水嶺の外側にある水は、図３で指定した二つの点３０２のいずれにも流れ下らない。
【００６３】
次に、流域抽出処理（ステップ２０４）の詳細を説明する。
【００６４】
図５は、本発明の実施形態の流域抽出処理（ステップ２０４）の詳細を示すフローチャートである。
【００６５】
ステップ５０１において、流域抽出プログラム１４１は、開始セルを「流域セル」とする。具体的には、流域抽出プログラム１４１は、開始セルのデータに含まれる、セルの種類を示す変数を「流域」に変更する。セルのデータについては後述する（図１３参照）。開始セルは、ステップ２０３において解析対象として入力された点、線または面等に対応するセルである。前述の通り、点−セル、線−セル、または面−セルの変換には、地理情報システムの基本的な技術が用いられる。
【００６６】
ステップ５０２において、流域抽出プログラム１４１は、開始セルの上流を探索する。ここで、ステップ５０２で実行される上流探索処理について、図６および図７を参照して説明する。
【００６７】
図６は、本発明の実施形態の上流探索処理（ステップ５０２）の詳細を示すフローチャートである。図６の詳細な説明は後述する。
【００６８】
図７は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの上流探索処理（ステップ５０２）の進捗を示す説明図である。
【００６９】
図６のステップ６０２で対象セルとして指定されたセルが、図７に点７０１として示されている。上流探索処理の進捗に伴って、対象セルは開始セルから上流方向に向かって１セルずつ進んでいくため、点７０１は上流方向に向かって１セルずつ進んでいく。また、ステップ６０３で読み込んだ部分領域が、図７に矩形７０２として示されている。この矩形も、上流探索処理の進捗に伴って上流方向に追加されていく。図７には４つの矩形が描かれている。これは、すでに４つの部分領域が読み込まれていることを示す。これらの点および矩形の動きによって、ユーザは、現在上流探索処理が実行されていることを知ることができ、さらに、その処理の進捗を直感的に把握することができる。このステップ５０２の処理によって、開始セルの流域が「流域セル」として抽出される。
【００７０】
ステップ５０３において、流域抽出プログラム１４１は、流域外セルを抽出する。この処理によって、ステップ５０２で抽出された流域セルでなく、かつ流域セルに隣接するセルが抽出される。抽出されたセルを流域外セルと記載する。
【００７１】
図８は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの流域外セル抽出処理（ステップ５０３）の進捗を示す説明図である。
【００７２】
ステップ５０３で抽出された流域外セルが、図８に点８０１として示されている。ステップ５０４以降に行う流域の真偽判定によって、流域が正しいと判定された場合、これらの点８０１が分水嶺となる。あらかじめ分水嶺がどこにあるかがわかっているユーザは、これらの点からこれらからなされる真偽判定の結果を予想でき、さらに残りの処理にかかる時間をおおよそ予想することができる。
【００７３】
ステップ５０４において、流域抽出プログラム１４１は、ステップ５０３で抽出されたセルの下流を探索する。
【００７４】
図９は、本発明の実施形態の下流探索処理（ステップ５０４）の詳細を示すフローチャートである。図９の詳細な説明は後述する。
【００７５】
図１０は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの下流探索処理（ステップ５０４）の進捗を示す説明図である。
【００７６】
図９ステップ９０２で対象セルとして指定されたセルが、図１０に点１００１として示されている。下流探索処理の進捗に伴って、対象セルはステップ５０３で抽出した流域外セルから下流方向に向かって１セルずつ進んでいく。このため、点１００１の動きによって、ユーザは、現在下流探索処理が実行されていることを知ることができ、さらに、その処理の進捗を直感的に把握することができる。下流探索処理によって、ステップ５０３で抽出した流域外セルの下流のセルが「流域外セル」として抽出される。
【００７７】
ステップ５０５において、流域抽出プログラム１４１は、やり直しフラグ（図９を参照して後述）の値を判定する。やり直しフラグの値が真であると判定された場合、前回のステップ５０２の上流探索処理（現在までにステップ５０２から５０５のループが複数回実行された場合、最後に実行された上流探索処理）によって得られた流域が誤っている。言い換えると、真の流域は、前回の上流探索処理によって得られた流域のさらに外側まで広がっている。この場合、処理はステップ５０２に戻る。そして、流域抽出プログラム１４１は、再び開始セルの上流探索を実行する。前回の下流探索処理の際に窪地埋め処理が実行された場合、後述するように、窪地内のセルの下流方向が決定されている。この場合、今回の上流探索処理の結果は、前回の上流探索処理の結果と異なる。
【００７８】
ステップ５０５において、やり直しフラグの値が偽であると判定された場合、前回の上流探索処理によって得られた流域が正しい。このため、流域抽出プログラム１４１は、流域抽出処理を終了する。
【００７９】
以上、本実施例の全体的な処理の流れについて説明した。以下、個々の処理およびそれらの処理を実現するデータ構造について詳細に述べる。
【００８０】
図１１は、本発明の実施形態のセルおよび部分領域を示す説明図である。
【００８１】
本実施形態では、空間の東西方向をｘ軸（１１０１）、南北方向をｙ軸（１１０２）とする２次元直交座標系を利用する。さらにこの空間を、ｘ軸方向にｄｘ（１１０３）、ｙ軸方向にｄｙ（１１０４）の間隔で分割してセルを生成する。地点（ｘ，ｙ）にあるセル（ｉ，ｊ）は以下の式（１）で求められる。
【００８２】
i=floor(x/dx), j=floor(y/dy) ......... (1)
【００８３】
ただし、floor()は小数部分を切り捨てることによって整数にする関数である。
【００８４】
部分領域は、複数のセルからなる領域である。部分領域は、ｘ軸方向にsi（１１０５）、ｙ軸方向にsj（１１０６）のセルからなるとする。ただし、siおよびsjは２以上の整数である（この図１１にはsi＝１０，sj＝１０の例を示したが、図７、図８及び図１０にはsi＝２８，sj＝２８の例を示した）。したがって、１つのセルは１つの部分領域に含まれる。セル（ｉ，ｊ）が含まれる部分領域（bi，bj）は次の式（２）で求められる。
【００８５】
bi=floor(i/si), bj=floor(j/sj) ......... (2)
【００８６】
図１２は、本発明の実施形態の部分領域のデータ構造を示す説明図である。
【００８７】
以下のデータ構造に関する説明では、Ｃ＋＋などオブジェクト指向型言語に向いた実装方法を示す。表１２００に部分領域型のデータを示す。実装の際には、これらのデータをメンバ変数として持つ、クラス名CellUnitの型とすればよい。
【００８８】
CellUnitは、Id、Cells、Targetsの３つのメンバ変数を持つクラスである。
【００８９】
Idは整数型であり、上記式（２）に示したbi,bjから一意に生成した値を保持する（行１２０１）。Idは、たとえばbi,bjをそれぞれ３２ビット整数、Idを６４ビット整数とし、０から３１ビットまでにbiの値を、３２から６３ビットまでにbjの値を格納することによって作成されてもよい。
【００９０】
Cellsは図１３で説明するセル型を格納する固定長配列である（行１２０２）。配列の長さは、１つの部分領域に含まれるセルの数、すなわち、si*sjである。
【００９１】
Targetsは、セル型を格納する可変長配列である（行１２０３）。この変数の初期値はempty、すなわち格納された要素がない配列である。
【００９２】
図１３は、本発明の実施形態のセルのデータ構造を示す説明図である。
【００９３】
表１３００にセル型のデータを示す。セル型（クラス名Cell）は、Glev、Kind、DownDirの３つのメンバ変数を持つクラスである。
【００９４】
Glevは実数型であり、標高を保持する（行１３０１）。
【００９５】
Kindは列挙型であり、未定（０）、流域（１）、流域外（２）または無効（３）の別を示すフラグである（行１３０２）。未定（０）は、セルが有効セルであるが、流域セルまたは流域外セルのいずれであるかがまだ定まっていないことを示す。流域（１）は、セルが有効セルであり、かつ、流域セルであることを示す。流域外（２）は、セルが有効セルであり、かつ、流域外セルである（言い換えると他の流域に属する流域セルである）ことを示す。無効（３）は、セルが無効セルであることを示す。Kindの初期値は、未定（０）である。
【００９６】
DownDirは列挙型であり、水が流れる方向（すなわち隣接下流セルの方向）を示すフラグである（行１３０３）。DownDirの具体的な値については図１４及び図１５を参照して説明する。DownDirの初期値は、隣接下流セルが存在しないことを示す値０である。水が流れる方向を求めるためには、セル勾配を求める必要がある。
【００９７】
図１４は、本発明の実施形態のセル勾配についての説明図である。
【００９８】
図１４には、セル１４００を中心にｉ軸方向に３セル、ｊ軸方向に３セルを示した。セル（i,j）における勾配は、セル（i,j）の標高値と、その格子に隣接するセルにおける標高値との差をセル間の距離で割った値である。１セルには８セルが隣接する。したがって、セル（i,j）における８方向の勾配が算出される。勾配の方向をそれぞれ矢印１４０１から矢印１４０８で示す。矢印１４０１から矢印１４０８に対応する勾配をそれぞれGrad1からGrad8と命名する。変数Grad1からGrad8の値を求める式は以下の通りである。
【００９９】
Grad1=(Glev[i,j]-Glev[i-1,j+1])/hypot(dx,dy) ......... (3-1)
Grad2=(Glev[i,j]-Glev[i,j+1])/dy ......... (3-2)
Grad3=(Glev[i,j]-Glev[i+1,j+1])/hypot(dx,dy) ......... (3-3)
Grad4=(Glev[i,j]-Glev[i-1,j])/dx ......... (3-4)
Grad5=(Glev[i,j]-Glev[i+1,j])/dx ......... (3-5)
Grad6=(Glev[i,j]-Glev[i-1,j-1])/hypot(dx,dy) ......... (3-6)
Grad7=(Glev[i,j]-Glev[i,j-1])/dy ......... (3-7)
Grad8=(Glev[i,j]-Glev[i+1,j-1])/hypot(dx,dy) ......... (3-8)
【０１００】
ただし、Glev[i,j]はセル(i,j)における標高、hypot(x,y)は原点(0,0)と点(x,y)との距離を返す関数である。なお、本実施例では隣接するセルとして８近傍（すなわち隣接する８個のセル）を利用した。これは、隣接セルが増えるほど精度のよい結果が期待できるためである。ただし、隣接するセルとして８近傍ではなく４近傍（すなわち隣接する４個のセル）を使用してもよい。その場合は、上記８方向の勾配のうちGrad2、Grad4、Grad5、Grad7のみを利用すればよい。
【０１０１】
あるセル(i,j)の隣接下流セルは、そのセル(i,j)の勾配Grad1からGrad8から求められる。具体的には、あるセル(i,j)の隣接下流セルは、そのセルの最も急な下り勾配方向にある隣接セルである。最も急な下り勾配とは、勾配Grad1からGrad8の最大値であり、最も急な下り勾配方向とは、勾配Grad1からGrad8の最大値の方向である。この最も急な下り勾配方向は、以下（ａ）から（ｃ）の３ケースに分類できる。
【０１０２】
（ａ）最も急な下り勾配が０より大、かつ１方向の場合。この場合、最も急な下り勾配方向を水が流れる方向とする。
【０１０３】
（ｂ）最も急な下り勾配が０より大、かつ２方向以上の場合。この場合、最も急な下り勾配方向から、あらかじめ決めた方向優先度に従って１方向を選択する。本実施形態では、下記の式（４）の順に優先度の高さが設定される。
【０１０４】
Grad2 > Grad5 > Grad7 > Grad4 > Grad1 > Grad3 > Grad8 > Grad6......... (4)
【０１０５】
例えば、Grad2とGrad3の値が同じであり、かつ、これらが最も急な下り勾配方向である場合、Grad2の優先度がGrad3より高いため、Grad2に対応する方向１４０２のセル(i,j+1)が隣接下流セルである。
【０１０６】
（ｃ）最も急な下り勾配が０以下の場合。この場合、水が流れる方向は存在せず、隣接下流セルは存在しないと判定される。本実施形態では後に説明するように無効セルの標高を負の無限大として扱っているため、最も急な下り勾配方向が０以下であると判定されたセルは窪地または平地である。
【０１０７】
図１５は、本発明の実施形態において水が流れる方向と、それに対応するフラグの値を説明するための図である。
【０１０８】
実装では、セル型Cellのメンバ変数DownDirが、図１５に示す値を保持する。最も急な下り勾配方向が上記（ａ）または（ｂ）の場合、DownDirは１，２，４，８，１６，３２，６４，１２８のいずれかの値になる。たとえばセル(i,j)の水が流れる方向が図１４の方向１４０５である（すなわち、セル(i,j)の隣接下流セルがセル(i+1,j)である）場合、DownDirの値は１となる。最も急な下り勾配方向が上記（ｃ）の場合（すなわち隣接下流セルが存在しない場合）、DownDirは未定を表す値０になる。
【０１０９】
次に、図６を用いて上流探索処理（ステップ５０２）の詳細を説明する。
【０１１０】
流域抽出プログラム１４１は、それぞれの流域セルについてステップ６０１からステップ６１２までの処理を繰り返す。図６の説明において、このループの処理対象のセルをcell1と記載する。実装では、ステップ５０１で部分領域クラスCellUnitのメンバ変数Targetsに開始セルを格納し、Targetsのそれぞれの要素についてこのループを実行する。
【０１１１】
ステップ６０２において、流域抽出プログラム１４１は、cell1を「対象セル」として指定する。
【０１１２】
ステップ６０３において、流域抽出プログラム１４１は、対象セル（cell1）を含む部分領域を読み込む。これによって、標高データ１９２および海域データ１９３が読み込まれる。流域抽出プログラム１４１は、海域データ１９３に基づいて海域と判別されたセルを、無効セルに指定する。さらに、ステップ２０３で無効セルまたは流域外セルが指定されている場合、流域抽出プログラム１４１は、そのセルを無効セルまたは流域外セルに指定する。そして、流域抽出プログラム１４１は、無効セルの標高を負の無限大にする。
【０１１３】
実装では、例えば、下記の手順が実行される。まず、流域抽出プログラム１４１は、メモリ１２０に部分領域クラスCellUnitのインスタンスを生成する。部分領域クラスCellUnitのインスタンスは、変数Idにbi,bjから生成したＩＤを格納し、変数CellsにセルクラスCellのインスタンスをsi*sj個保持する。セルクラスCellのメンバ変数Kind及びDownDirは表１３００に示した初期値に初期化される。
【０１１４】
メンバ変数GlevおよびKindには、次のような値が格納される。海域データ１９３、または、ステップ２０３における指定に基づいて、セルが無効セルであると判定された場合、メンバ変数Glevには標高値として負の無限大が格納され、メンバ変数Kindには無効（３）が格納される。セルが有効セルであると判定された場合、メンバ変数Glevには標高値としてＨＤＤ１９１から読み込まれた標高データ１９２が格納され、メンバ変数Kindには未定（０）が格納される。ただし、セルが流域外セルであると判定された場合、メンバ変数Kindには流域外（２）が格納される。
【０１１５】
次に、流域抽出プログラム１４１は、対象セル（cell1）のそれぞれの隣接セルについてステップ６０４からステップ６１１までの処理を繰り返す。図６の説明において、このループの処理対象のセル（すなわち、cell1に隣接する複数のセルの各々）をcell2と記載する。
【０１１６】
ステップ６０５において、流域抽出プログラム１４１は、cell2の隣接下流セルが対象セル（cell1）であるか否かを判定する。この判定の結果が真である場合、処理はステップ６０６に、偽である場合、処理はステップ６１１に進む。
【０１１７】
cell2の隣接下流セルは、図１４を参照して説明したように、最急勾配法によって求められる。ただし、後述するように、窪地埋め処理によってcell2の下流方向が決定された場合、その下流方向に基づいてcell2の隣接下流セルが求められる。
【０１１８】
実装では、このステップによってcell2のメンバ変数DownDirに水が流れる方向を示す値が格納される。
【０１１９】
ステップ６０６において、流域抽出プログラム１４１は、cell2の種類を判定する。具体的には、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を参照して、cell2が流域セル、流域外セル、無効セルまたは未定セルのいずれであるかを判定する。
【０１２０】
流域の定義によれば、cell2が有効セルであり、cell2の隣接下流セルがcell1であり、かつ、cell1が流域セルである場合、cell2は必ず流域セルである。このことに合致するように、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を更新する（ステップ６０７〜ステップ６１０）。
【０１２１】
cell2に関するセルクラスCellのメンバ変数Kindの値が流域（１）である場合、cell2は既に流域セルとして扱われている。この場合、メンバ変数Kindの値を更新する必要がないため、流域抽出プログラム１４１は、メンバ変数Kindの値を更新せずに（ステップ６０７）、ステップ６１１に進む。
【０１２２】
メンバ変数Kindの値が流域外（２）である場合、cell2は流域外セルである。このことは、cell2が既に他の流域に属する流域セルであると判定されていることを意味する。この場合、流域抽出プログラム１４１は、メンバ変数Kindの値を更新せずに（ステップ６０８）、ステップ６１１に進む。ただし、流域の定義によれば、ステップ６０６においてcell2が有効セルであると判定された場合、cell2は必ず流域セルである。このため、上流探索が正常に実行されている限り、ステップ６０６においてcell2が流域外セルであると判定されることはあり得ない。
【０１２３】
メンバ変数Kindの値が無効（３）である場合、cell2は無効セルである。この場合、cell2は流域セルになり得ないため、流域抽出プログラム１４１は、メンバ変数Kindの値を更新せずに（ステップ６０９）、ステップ６１１に進む。
【０１２４】
メンバ変数Kindの値が未定（０）である場合、cell2は未定セルである。上記のように、流域の定義によれば、ステップ６０６においてcell2が有効セルであると判定された場合、cell2は必ず流域セルである。このため、流域抽出プログラム１４１は、cell2を流域セルに変更して（ステップ６１０）、ステップ６１１に進む。具体的には、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を流域（１）に更新する。さらに、流域抽出プログラム１４１は、部分領域クラスCellUnitのメンバ変数Targetsにcell2を追加する。これによって、cell2は新たな対象セルとなる。
【０１２５】
ステップ６１１では、ステップ６０４のループに戻る。cell1に隣接する全てのcell2についてステップ６０４〜６１１のループが終了するまで、このループが繰り返し実行される。
【０１２６】
ステップ６１２では、ステップ６０１のループに戻る。全ての対象セルについてステップ６０１〜６１２のループが終了するまで、このループが繰り返し実行される。
【０１２７】
次に、図９を用いて下流探索処理（ステップ５０４）の詳細を説明する。
【０１２８】
流域抽出プログラム１４１は、それぞれの流域外セルについて、ステップ９０１からステップ９１２までの処理を繰り返す。図９の説明において、このループの処理対象のセルをcell1と記載する。実装では、ステップ５０３で部分領域クラスCellUnitのメンバ変数Targetsに流域外セルを格納し、Targetsのそれぞれの要素についてこのループを実行する。
【０１２９】
例えば、ステップ５０２が終了した時点で図８に示す複数のセル８０１が流域外セルである場合、これらの全てのセル８０１がメンバ変数Targetsに格納される。そして、全ての流域外セルについて処理が終了するまで、各流域外セルを対象として図９のループが繰り返される。
【０１３０】
なお、図９の説明において、「流域セル」とは、開始セル（図３の例ではアイコン３０２に対応するセル）が属する流域に属するセルを、「他の流域」とは、開始セルが属する流域と異なる流域を、流域外セルとは、他の流域に属するセル（すなわち、開始セルの上流にないセル）を、それぞれ意味する。
【０１３１】
ステップ９０２において、流域抽出プログラム１４１は、cell1を「対象セル」として指定する。
【０１３２】
ステップ９０３において、流域抽出プログラム１４１は、対象セル（cell1）を含む部分領域を読み込む。この動作はステップ６０３と同じである。
【０１３３】
ステップ９０４において、流域抽出プログラム１４１は、cell1の隣接下流セル（図９の説明においてcell2と記載する）を特定し、その種類を判定する。具体的には、流域抽出プログラム１４１は、cell2が存在するか否か、及び、存在する場合、cell2に関するセルクラスCellのメンバ変数Kindの値を参照して、cell2が流域セル、流域外セル、無効セルまたは未定セルのいずれであるかを判定する。cell1の隣接下流セルは、最急勾配法（図１４参照）によって求められる。実装では、cell1のメンバ変数DownDirに、水が流れる方向を示す値が格納される。
【０１３４】
ここで、ステップ９０４の判定結果に基づく処理の概要を説明する。
【０１３５】
流域の定義によれば、ステップ５０３で抽出されたセルが流域外セルであれば、その下流の有効セルは、必ず流域外セルである。図９のcell1は、ステップ５０３で抽出されたセル自体またはその下流のセルであり、cell2はさらにその下流のセルである。したがって、cell1が流域外セルであり、cell１の隣接下流セルがcell２であり、かつ、cell2が有効セルである場合、cell2は必ず流域外セルである。このことに合致するように、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を更新する。
【０１３６】
このような処理において、cell１が流域外セルであるにもかかわらずcell2が流域セルであると判定されることは、ステップ５０３で抽出されたセルが実は流域セルであることを示す。これは、直前の上流探索処理によって取得された流域が誤っていたこと、すなわち、上流探索処理のやり直しが必要であることを意味する。この場合、流域抽出プログラム１４１は、やり直しフラグの値を更新する。
【０１３７】
やり直しフラグは、上流探索処理のやり直しが必要であるか否かを示す。具体的には、やり直しフラグの値がtrue（真）であることは、上流探索処理のやり直しが必要であることを示す。やり直しフラグは、例えば、初期値false（偽）のブール型のグローバル変数Failedである。
【０１３８】
次に、上記の処理の詳細を説明する。
【０１３９】
cell2に関するセルクラスCellのメンバ変数Kindの値が流域（１）である場合、cell2は流域セルである。このことは、cell1が流域外セルであることと矛盾する。すなわち、このことは、既に流域外セルであると判定されているcell1及びその上流の全てのセルが実は流域セルであること、さらに言い換えると、前回の上流探索処理（ステップ５０２）の結果が誤っていることを意味する。このため、流域抽出プログラム１４１は、やり直しフラグの値を真に更新し（ステップ９０５）、ステップ９１２に進む。
【０１４０】
メンバ変数Kindの値が流域外（２）である場合、cell2は流域外セルである。このことは、cell1が流域外セルであることと矛盾しない。言い換えると、これによって、cell2及びその上流の全てのセルが流域外セルであることが確認された。このため、流域抽出プログラム１４１は、やり直しフラグ及びメンバ変数Kindの値を更新せずに（ステップ９０６）、ステップ９１２に進む。この場合、cell2のさらに下流を探索する必要がないため、cell2は新たな対象セルとして選択されない。
【０１４１】
なお、cell2が流域外セルであるか否かは、どのような方法によって判定されてもよい。例えば、過去に実行された別の流域抽出処理によって、cell2が別の流域に属することが確定している場合、cell2に関するメンバ変数Kindの値が流域外（２）であるため、上記のようにcell2が流域外セルであると判定され、処理はステップ９０６に進む。ユーザがあらかじめ流域外の範囲を指定した場合も同様である。あるいは、メンバ変数Kindの値にかかわらず、cell2の標高が所定の標高（例えば、開始セルの標高）より低いと判定された場合に、cell2が流域外セルであると判定され、処理がステップ９０６に進んでもよい。あるいは、開始セルが河川上のセルである場合において、cell2が、開始セルが属するものと別の河川上のセルであると判定された場合、cell2が流域外セルであると判定され、処理がステップ９０６に進んでもよい。各セルがどの河川上にあるかは、地図データ１９１に基づいて判定することができる。
【０１４２】
メンバ変数Kindの値が無効（３）である場合、cell2は無効セルである。このことは、cell1が流域外セルであることと矛盾しない。言い換えると、これによって、cell1及びその上流の全てのセルが流域外セルであることが確認された。このため、流域抽出プログラム１４１は、やり直しフラグ及びメンバ変数Kindの値を更新せずに（ステップ９０７）、ステップ９１２に進む。この場合も、cell2のさらに下流を探索する必要がないため、cell2は新たな対象セルとして選択されない。
【０１４３】
メンバ変数Kindの値が未定（０）である場合、cell2は未定セルである。流域の定義によれば、ステップ９０４においてcell2が有効セルであると判定された場合、cell2は必ず流域外セルである。このため、流域抽出プログラム１４１は、cell2を流域外セルに変更して（ステップ９０８）、ステップ９１２に進む。具体的には、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を流域外（２）に更新する。さらに、流域抽出プログラム１４１は、部分領域クラスCellUnitのメンバ変数Targetsにcell2を追加する。これによって、cell2は新たな対象セルとなる。
【０１４４】
cell1に隣接する全てのセルの標高がcell1の標高以上である場合（すなわち、cell1が図１４において説明したケース（ｃ）に該当する場合）、最急勾配法によれば、cell1の下流方向は存在しない（言い換えるとcell1から水が流出しない）。このため、ステップ９０４において、cell2が存在しないと判定される。この場合、流域抽出プログラム１４１は、最急勾配法ではなく、cell1の周囲の複数のセルの標高の配置に基づいてcell1の下流方向を決定するための処理を実行する。
【０１４５】
具体的には、流域抽出プログラム１４１は、cell1を窪地セルに変更し（ステップ９０９）、窪地埋め処理を実行する（ステップ９１０）。ステップ９０９及びステップ９１０において実行される処理については後述する（図１６及び図１７参照）。窪地埋め処理が終了すると、流域抽出プログラム１４１は、窪地セルを流域外セルに変更して（ステップ９１１）、ステップ９１２に進む。
【０１４６】
全ての流域外セルについてステップ９０１からステップ９１２までのループが終了すると、流域抽出プログラム１４１は、下流探索処理を終了する。
【０１４７】
次に、図１６および図１７を用いて窪地埋め処理（ステップ９１０）の詳細を説明する。
【０１４８】
図１６は、本発明の実施形態の窪地のデータ構造を示す説明図である。
【０１４９】
表１６００に窪地型のデータを示す。実装の際には、これらのデータをメンバ変数として持つ、クラス名Sinkの型とすればよい。
【０１５０】
Sinkは、Cells、Outlets、WlevおよびFinishedの４つのメンバ変数を持つクラスである。CellsおよびOutletsはセル型を格納する可変長配列である（行１６０１および１６０２）。CellsおよびOutletsは、それぞれ、図１７で説明する窪地セルおよび流出口セルを格納する。CellsおよびOutletsの初期値はemptyである。図９のステップ９０９は、cell1をメンバ変数Cellsに追加することによって実行される。Wlevは実数型であり、図１７で説明する隣接最小標高を格納する（行１６０３）。Finishedはブール型であり、終了フラグを格納する（行１６０４）。Finishedの初期値はfalseである。
【０１５１】
図１７は、本発明の実施形態の窪地埋め処理（ステップ９１０）の詳細を示すフローチャートである。
【０１５２】
ステップ１７０１において、流域抽出プログラム１４１は、「隣接最小標高」を算出する。隣接最小標高とは、窪地セルに隣接するセルの標高のうち最小の標高である。この窪地埋め処理の開始時点において、窪地セルはステップ９０９で得られたものだけである。したがってその時点の隣接最小標高はステップ９０９で得られた各窪地セルに隣接する８セルの標高の最小値であり、その値はステップ９０９で得られた窪地セルの標高と同じか、またはそれよりも大きい。
【０１５３】
実装では、ステップ９０９の終了時点で、窪地型Sinkのメンバ変数Cellsには、ステップ９０９において取得された窪地セル１つのみが格納されている。さらに、このステップ１７０１では、メンバ変数Cellsに隣接するセルの標高の最小値がメンバ変数Wlevに格納される。
【０１５４】
流域抽出プログラム１４１は、それぞれの窪地セルについてステップ１７０２からステップ１７１０までの処理を繰り返す。図１７の説明において、このループの処理対象のセルをcell1と記載する。実装では、メンバ変数Cellsのそれぞれの要素についてこのループを実行する。
【０１５５】
流域抽出プログラム１４１は、cell1のそれぞれの隣接セルについてステップ１７０３からステップ１７０９までの処理を繰り返す。図１７の説明において、このループの処理対象のセルをcell2と記載する。
【０１５６】
ステップ１７０４において、流域抽出プログラム１４１は、cell2を含む部分領域を読み込む。この動作はステップ６０３と同じである。
【０１５７】
ステップ１７０５において、流域抽出プログラム１４１は、隣接最小標高Wlevとcell2の標高とを比較する。Wlevとcell2の標高とが等しい場合ステップ１７０６に進み、等しくない場合ステップ１７０７に進む。
【０１５８】
Wlevとcell2の標高とが等しい場合、cell2は窪地の一部である。このため、ステップ１７０６において、流域抽出プログラム１４１は、cell2を窪地セルに変更する。実装では、メンバ変数Cellsにcell2を追加する。ステップ１７０６が実行された場合、追加されたcell2を処理するためのステップ１７０２からステップ１７１０までの処理が後に実行されることになる。
【０１５９】
ステップ１７０６が実行された時点で、cell2の標高はメンバ変数Wlevの値に等しく、かつ、その標高の値が窪地セルの中で最も大きい。このため、図１７の説明において、メンバ変数Wlevを窪地最大標高とも記載する。
【０１６０】
ステップ１７０７において、流域抽出プログラム１４１は、窪地最大標高Wlevとcell2の標高とを比較する。Wlevがcell2の標高より大きい場合、cell2は窪地の一部ではない。さらにこの場合、cell2は、cell1を含む窪地に流入した水の流出口である。この場合、流域抽出プログラム１４１はステップ１７０８に進む。一方、Wlevがcell2の標高より小さい場合、cell2は窪地の一部である可能性があるが、そうでない可能性もある。この場合、流域抽出プログラム１４１は、ステップ１７０８を実行せずにステップ１７０９に進む。実装では、流域抽出プログラム１４１は、ステップ１７０８に進む前にcell2をメンバ変数Outletsに追加する。
【０１６１】
ステップ１７０８において、流域抽出プログラム１４１は、終了フラグFinishedを真（true）に更新する。なお、終了フラグの初期値は偽（false）である。つまり、ステップ１７０８が最初に実行されるまで、終了フラグFinishedは偽である。
【０１６２】
ステップ１７０９において、まだ処理されていない隣接セルがある場合、ステップ１７０３のループに戻る。
【０１６３】
ステップ１７１０において、まだ処理されていない窪地セルがある場合、ステップ１７０２のループに戻る。
【０１６４】
ステップ１７１１では、終了フラグFinishedの真偽判定をする。終了フラグが真の場合、窪地に流入した水の流出口が既に特定されている。このことは、窪地の範囲が特定されたことを意味する。すなわち、この時点における窪地セルの範囲が、特定された窪地の範囲である。この場合、処理はステップ１７１２に進む。一方、終了フラグが偽の場合、窪地に流入した水の流出口がまだ特定されていない。この場合、窪地の範囲がまだ特定されていないため、処理はステップ１７０１に戻る。
【０１６５】
ステップ１７１２において、流域抽出プログラム１４１は、すべての窪地セルの標高を隣接最小標高Wlevに変更する。なお、このステップで使用する隣接最小標高Wlevは、直前の回のステップ１７０１で求めた値であり、ステップ１７１２の時点の窪地セルに基づいて新たに隣接最小標高を算出するわけではない。この処理によって、すべての窪地セルの標高が等しくなる。以下の説明において、上記のように標高が変更された窪地セルを平地セルと言い換える。なお、実装ではメンバ変数Cellsに格納されたすべてのセルの標高をWlevに変更する。
【０１６６】
ステップ１７１３において、流域抽出プログラム１４１は、すべての平地セルの下流方向を決定する。具体的には、流域抽出プログラム１４１は、平地セルに隣接する、平地セルよりも低い標高を持つセル（図１７の例では、ステップ１７０７でＴｒｕｅと判定された場合のcell2）を、その平地の流出口セルとする。そして、平地内の流れが流出口セルに向かうように平地内の水が流れる方向（すなわち下流方向）を決定する。
【０１６７】
まず、流域抽出プログラム１４１は、平地セルのうち、流出口セルに隣接し、かつ、水が流れる方向が決定していないセルの下流方向を、流出口セルに向かう方向に決定する。１つの平地セルに複数の流出口セルが隣接している場合には、前述した方向優先度に従って下流方向が決定される。続いて、流域抽出プログラム１４１は、上記のように下流方向を決定したセルを流出口セルと見なし、その新たな流出口セルについて上記の処理を実行する。このように、すべての平地セルの水が流れる方向が決定するまで、同様の処理を繰り返す。実装では、メンバ変数Outletsに格納されたすべてのセルを流出口セルとする。
【０１６８】
なお、上記のような下流方向の決定方法は一例に過ぎない。窪地に流れ込んだ水が流出口セルから流出するように決定される限り、どのように下流方向が決定されてもよい。このように下流方向を特定することによって、全ての窪地セルがその窪地の流出口セルの上流であること、言い換えると、全ての窪地セルが、その窪地の流出口セルが属するものと同一の流域に属することが特定される。
【０１６９】
上記のように決定された下流方向は、その後に実行される上流探索処理（ステップ５０２）において使用される。具体的には、上記のように下流方向が決定されたセルが図６の処理のcell2として選択された場合、その決定された下流方向に基づいてステップ６０５の判定が実行される。
【０１７０】
このようにして、本実施形態ではユーザが図３に示した入力画面から情報を入力すると、プログラムが図７，８，１０に示した進捗画面を提示して、最終的に図４に示した結果表示画面を提示することができる。
【０１７１】
本実施形態では部分領域を使用した場合の実施方法について説明した。しかし、部分領域を使用せずに本発明を実施することもできる。この場合、対象部分領域の読み込み処理（ステップ６０３、ステップ９０３、ステップ１７０４）を削除する。そして、ステップ２０３の直後に、次の処理を追加する。流域抽出プログラム１４１は、最初に、ユーザに解析対象領域を指定させる。次に、指定された領域の標高データ１９２および海域データ１９３を読み込む。次に、海域データ１９３により海域と判別されたセルを、無効セルに指定する。さらに、ステップ２０３で無効セルが指定されている場合は、そのセルも無効セルとする。そして、無効セルの標高を負の無限大にする。
【産業上の利用可能性】
【０１７２】
以上述べたとおり、本発明によれば、流域に関する事前知識を要求しない流域抽出コンピュータプログラムが提供できる。このプログラムを用いることによって、コンピュータが使えるユーザであれば、専門家と同等の品質の流域抽出ができるようになる。
【符号の説明】
【０１７３】
１００ ＰＣ
３１０ 地図
３０２ 下流端
４０１ 水が流れる方向を示す線分
４０２ 分水嶺を示す線分
７０１ 上流探索処理における処理対象セルを示す点
７０２ 標高データ１９２等をメモリに読み込んだ部分領域を示す矩形
１００１ 下流探索処理における処理対象セルを示す点
【技術分野】
【０００１】
本発明は、コンピュータを使って流域を抽出する方法に関する。本発明は特に、１以上の地点の位置を入力データとし、それぞれの地点の流域を数値地形モデル（digital elevation mode, DEM）に基づいて抽出するコンピュータプログラム（流域抽出プログラム）に関する。
【背景技術】
【０００２】
流域は、河川またはダムなどの水を管理する土木構造物にとって重要な情報である。ある地点の流域とは、その地点に集まってくる水が流れてきた領域である。ダムの建設のためには、そのダムに平均的に入ってくると予想される水量、すなわちダムの流域の平均降雨量が不可欠である。また、ダムの管理のためには、そのダムの水源林、すなわち流域内の森林の状態管理が不可欠である。河川の水位予測のためには、その河川の流域の予想降雨量が不可欠である。都市機能を豪雨から守るための雨水排水設備（下水）の設計には、その設備が対応すべき最大の降雨強度と、流域面積とが不可欠である。
【０００３】
流域は、水が流れる方向を逆にたどることによって求めることができる。実際に、この流れの性質を利用して流域を抽出するコンピュータプログラム（流域抽出プログラム）が存在する。主要な流域抽出プログラムの処理手順は、非特許文献１に詳しい。
【０００４】
流域抽出プログラムで利用する電子データは、地表面の標高データである。この様な電子データはＤＥＭ（Digital Elevation Model）と呼ばれる。ＤＥＭでは、ある領域の地表面がセル（cell）と呼ばれる小領域に分割され、それぞれのセルに標高値が与えられる。
【０００５】
通常、水が流れる方向はその地点の最も急な下り勾配方向と一致する。この流れの性質を利用した流域抽出方法が、最急勾配法（steepest slope method）と呼ばれる方法である。この方法では、あるセルの流域が、そのセルから最も急な下り勾配の方向を逆にたどった時に通過したセルとなる。あるセルの勾配は、そのセルおよびそのセルの周囲の８セルの標高データから求めることができる。
【０００６】
最急勾配法では、周囲のセルの標高以下の標高を持つセルの取り扱いが問題となる。このようなセルは、流域抽出プログラムの研究分野で「平地（flat）」または「窪地（sink, depression）」と呼ばれている。平地は周囲の１以上のセルの標高と同じ標高を持つセルであり、窪地は周囲のすべてのセルの標高より小さい標高を持つセルである。このようなセルが存在する場合、最急勾配法を利用すると、正しい流域を抽出することができない。ところが、平地および窪地は通常のＤＥＭに多数存在する。したがって、最急勾配法のみでは、正しい流域が抽出できない。
【０００７】
図１８は、窪地を説明するための図である。グラフ１８００は、ＤＥＭの鉛直断面図に最急勾配法で決定した水が流れる方向を重ねた図である。セル１８０１は河口であり、最も標高が低い。セル１８０４は隣接するセル（１８０３および１８０５）よりわずかに標高が低い。最急勾配法で決定した水が流れる方向を矢印で示す。セル１８０１の流域セルはこの矢印をセル１８０１から逆にたどった範囲であり、セル１８０２〜１８０３となる。しかしこの結果は誤りである。専門家であれば、セル１８０１の流域セルをセル１８０２〜１８０９とするであろう。
【０００８】
この問題の最も一般的な解決方法は、勾配を無視し、標高の配置に基づいて水の流れる方向を決定する窪地埋め（sink filling）法である。窪地埋め法は、最急勾配法に比べ、より多くのセルの標高データを利用する。窪地埋め法を使う流域抽出プログラムは非特許文献２および非特許文献３に詳しく説明されている。
【０００９】
窪地埋め法では、まず窪地を平地に変える。つまり、窪地の標高を、周囲のセルのうち最小の標高にする。図１８では、窪地セル１８０４の標高をセル１８０５と同じ標高にする。次に、平地の流出口を決定する。具体的には、平地に隣接する平地よりも低い標高を持つセルを流出口として決定する。流出口が存在しない場合は、平地にするセルを広げる。
【００１０】
図１８では、セル１８０４および１８０５の流出口が存在しない。そこで、平地にするセルをセル１８０３から１８０５に広げる。広げた後の状態をグラフ１８２０に示す。
【００１１】
グラフ１８２０のセル１８２１〜１８２９は、それぞれ、グラフ１８００のセル１８０１〜１８０９に対応する。
【００１２】
グラフ１８２０を参照すると、セル１８２３から１８２５の標高が等しく、これらのセルが平地になっていることがわかる。この場合、流出口はセル１８２２となる。最後に、平地内の流れが流出口に向かうように平地内の水が流れる方向を決定する。平地セル１８２３から１８２５の水が流れる方向は、その流出口であるセル１８２２に向かうように決定される。セルごとの水が流れる方向を、グラフ１８２０に矢印で示す。この矢印をセル１８２１から逆にたどると、セル１８２９までたどれる。最急勾配法の結果を窪地埋め法により修正すると、セル１８２１の流域セルはセル１８２２〜１８２９である、という正しい結果が得られる。
【００１３】
窪地埋め法の処理効率を上げる実装方法として、特許文献１に開示された「Method for flow analysis utilizing cell elevation topography」が挙げられる。この方法では、あらかじめ領域の内部を複数のmajor cellに分割し、さらにmajor cellの内部を少なくとも横方向３縦方向３のminor cellに分割する。そして、あるminor cellにおける勾配を算出するときに、そのminor cellを含むmajor cellと、さらにそのmajor cellに隣接するmajor cellについて窪地埋め法を適用する。その後、これらのmajor cellに含まれるminor cellについて勾配を再度算出する。非特許文献１に開示された方法では、処理の対象とする領域全体に窪地埋め法を適用する必要があったが、特許文献１に開示された方法では、処理の対象とする領域を複数に分割し、それぞれ分割された領域ごとに窪地埋め法を適用することが可能になる。
【００１４】
いずれの方法であっても、次の手順で流域を抽出する。まず、水の流れる方向を勾配のみから決定する（最急勾配法）。次に、水が流れ出ない平地セルおよび窪地セルに対して、そのセルの水の流れる方向を標高の配置に基づいて決定する（窪地埋め法）。最後に、ユーザが指定したセルから水の流れる方向を逆にたどる。そのときに通ったセルが、流域セルである。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】米国特許出願公開第２００５／００４９８０２号明細書
【非特許文献】
【００１６】
【非特許文献１】Costa-Cabral, M. C., and S. J. Burges (1994), Digital elevation model networks (DEMON): A model of flow over hillslopes for computation of contributing and dispersal areas, Water Resource Research, 30(6), 1681−1692.
【非特許文献２】O'Callaghan, J. F., and D. M. Mark: The extraction of drainage networks from digital elevation data, Computer Vision, Graphics, and Image Processing, 28 (3), 323-344, 1984.
【非特許文献３】Jenson, S. K., and J. O. Domingue: Extracting topographic structure from digital elevation data for geographic information system analysis, Photogrammetric Engineering and Remote Sensing, 54 (11), 1593−1600, 1988.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
従来の流域抽出プログラムでは、水の流れる方向を決定した後に、流域を抽出する。したがって、流域を抽出する前に、水の流れる方向を決定する範囲をプログラムに与える必要がある。もし、水の流れる方向を決定する範囲が流域よりも小さい場合、正しい流域は抽出できない。したがって、正しい流域を抽出するためには、抽出される流域をプログラムのユーザがあらかじめ知っておく必要がある。しかし、流域を知っているユーザは、流域抽出プログラムを使う必要はない。このため、従来の流域抽出プログラムは、限られた用途にしか適用されてこなかった。
【００１８】
本発明はこの問題に鑑みてなされたものである。本発明の目的は、あらかじめ流域を知らないユーザであっても流域を抽出できるプログラムコンピュータプログラムを提供することである。
【課題を解決するための手段】
【００１９】
本願で開示する代表的な発明は、コンピュータを制御する流域抽出プログラムであって、前記コンピュータは、前記流域抽出プログラムが格納されるメモリと、前記メモリに格納された前記流域抽出プログラムを実行するプロセッサと、を備え、地図上の複数の領域の標高を示す標高データを保持し、前記複数の領域は、第１領域を含み、前記流域抽出プログラムは、前記第１領域に流れ込む水の流域を、前記標高データに基づいて上流方向に探索する第１手順と、前記第１手順によって特定された流域が正しいか否かを判定する第２手順と、を前記プロセッサに実行させ、前記第２手順において、前記特定された流域が正しくないと判定された場合、前記第１手順を再び前記プロセッサに実行させることを特徴とする。
【発明の効果】
【００２０】
本発明の一実施形態によれば、ＤＥＭから流域を抽出するコンピュータプログラムを提供できる。このプログラムによって、あらかじめ流域を知らないユーザであっても、流域を抽出することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施の形態におけるコンピュータシステムの構成を示す概略ブロック図である。
【図２】本発明の実施形態のＰＣによって実行される処理を示すシーケンス図である。
【図３】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの入力待ちの状態を示す説明図である。
【図４】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの解析終了の状態を示す説明図である。
【図５】本発明の実施形態の流域抽出処理の詳細を示すフローチャートである。
【図６】本発明の実施形態の上流探索処理の詳細を示すフローチャートである。
【図７】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの上流探索処理の進捗を示す説明図である。
【図８】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの流域外セル抽出処理の進捗を示す説明図である。
【図９】本発明の実施形態の下流探索処理の詳細を示すフローチャートである。
【図１０】本発明の実施形態の流域抽出プログラムが提供するＧＵＩの下流探索処理の進捗を示す説明図である。
【図１１】本発明の実施形態のセルおよび部分領域を示す説明図である。
【図１２】本発明の実施形態の部分領域のデータ構造を示す説明図である。
【図１３】本発明の実施形態のセルのデータ構造を示す説明図である。
【図１４】本発明の実施形態のセル勾配についての説明図である。
【図１５】本発明の実施形態において水が流れる方向と、それに対応するフラグの値を説明するための図である。
【図１６】本発明の実施形態の窪地のデータ構造を示す説明図である。
【図１７】本発明の実施形態の窪地埋め処理の詳細を示すフローチャートである。
【図１８】窪地を説明するための図である。
【発明を実施するための形態】
【００２２】
最初に、本発明の概要を説明する。
【００２３】
本発明は、以下の３つの発見に基づいている。
【００２４】
１．窪地および平地の面積、体積、形状等はあらかじめわからない。
【００２５】
２．窪地および平地がプログラムで得られた流域に隣接している場合、プログラムで得られたその流域が誤っている可能性がある。
【００２６】
３．流域の最上流は自明ではない一方、流域の最下流は自明である。
【００２７】
発見１および２は、発明者らが先に出願した発明（特願２００８−００２２８４，流域推定プログラム）を様々な流域でＤＥＭデータやセルの大きさを様々に変化させて検証する過程で発見した。そこで、特願２００８−００２２８４に示した発明の概要を以下に説明する。
【００２８】
特願２００８−００２２８４に示した発明は、任意のセルがある面積以下の窪地でないことを証明できる、という発見に基づく。ある面積をもった（すなわちある数のセルからなる）窪地または平地が取り得る最大の長さは、それらのセルを１列に直線上に並べた場合の長さである。あるセルからこの長さよりも近いセルについて窪地埋め法を適用すれば、少なくとも中心にあるセルはある面積以下の窪地または平地ではなくなる。そこで、特願２００８−００２２８４に示した発明では「窪地の最大面積」というパラメタを導入し、これ以下の面積の窪地および平地を埋めることにした。この発明はさらに、先に出願した別の発明（特開２００７−０３４３７３，空間シミュレーションプログラムおよび装置）の「部分領域」という概念を利用する。
【００２９】
特願２００８−００２２８４に示した発明の実施例は以下の通りである。あらかじめ窪地の最大面積を定義しておく。さらに、あらかじめ隣接する複数のセルから構成される部分領域を定義し、全てのセルを部分領域に対応づけておく。開始セルをユーザが指定すると、プログラムは開始セルを対象セルとする（ステップ１）。つづいて、対象セルを含む部分領域を対象部分領域とする（ステップ２）。対象部分領域からの距離が、最大の窪地が取り得る最大の長さよりも近い部分領域について、窪地埋め処理を行う（ステップ３）。この処理によって、対象部分領域からあらかじめ決めた面積以下の窪地が取り除かれる。つづいて、対象セルに隣接する８セルについて下流方向（すなわち、各セルから流出する水の流向）を算出する（ステップ４）。下流方向は、最も急な下り勾配の方向である。下流方向に対象セルがあるセルを、次の対象セルとする（ステップ５）。次の対象セルが存在する場合、ステップ２に戻る（ステップ６）。
【００３０】
一方、本発明は先の発明とは異なる発見を利用する。すなわち、本発明は上述した発見１から３に基づいている。本発明は、先の発明では必要であった「窪地の最大面積」というパラメタを不要にする。発明者らが考案した、本発明の流域抽出プログラムは以下のステップ１およびステップ２からなる。
【００３１】
ステップ１：ユーザが指定したセルの上流セルを探索する。
【００３２】
水の流れる方向は、最急勾配法、特願２００８−００２２８４に示した方法などで決定すればよい。これによって、ユーザが指定したセルを下流端とする流域が抽出される。ところが、ステップ１によって得られた流域は誤っている可能性がある。なぜなら、得られた流域の外側にその流域に隣接する窪地がある場合、得られた流域は誤っている可能性があり（発見２）、そのような窪地が存在しないことを保証できないためである（発見１）。また、最上流は自明ではない（発見３）。つまり、たとえば地図や現場に、最上流を示す印があるわけではないため、ステップ１で得られる流域が正しいことを保証できない。
【００３３】
ステップ２：ステップ１で抽出された流域の真偽を判定する。
【００３４】
この判定には、流域の定義の対偶を利用する。すなわち、流域でないセルの下流に、流域でないセルしかなければその流域は正しい。発見３によれば、最下流は自明である。つまり、河川の最下流は海である（正確には、最下流は水の流出口がない領域であり、地域によっては、水の流出口がない湖、砂漠などが最下流となる場合もある。以下、水の流出口がない領域を「無効領域」、その領域に含まれるセルを「無効セル」と表記する）。ところが、プログラムでは最下流が無効領域とならない場合がありうる。つまり最下流が窪地となる場合である。そこで、このセル近傍の水の流れる方向を窪地埋め法により決定した後、下流探索をやり直す。こうして、ステップ１で抽出された流域以外のセルを開始セルとし、無効セルまで下流探索する。こうして得られた下流セルにユーザが指定したセルが含まれない場合、ステップ１で抽出された流域は真であると判定する。なお、プログラムの処理においては、標高値などの指標に基づいて下流探索を打ち切ってもよい。
【００３５】
ステップ２の判定の結果が偽であれば、ステップ１に戻る。その場合、ユーザが指定したセルの上流に、ステップ１で抽出された流域以外のセルが存在する。したがって、再び実行されたステップ１で得られる流域は、前回のステップ１で得られた流域とは異なる。
【００３６】
なお、ステップ２において下流探索の開始セルとするセルは、ステップ１で抽出された流域以外のセルであって、かつステップ１で抽出された流域セルに隣接するセルだけに限定してもよい。なぜならばこれらのセルは、流域が偽と判定される場合に必ず下流探索されるためである。
【００３７】
以下、本発明の実施形態を添付図面に基づいて説明する。
【００３８】
図１は、本発明の実施形態におけるコンピュータシステムの構成を示す概略ブロック図である。
【００３９】
本実施形態のコンピュータシステムは、ＰＣ（Personal Computer）１００によって構成される。ＰＣ１００は、入出力部１１０を備える。入出力部１１０は、キーボード１１１およびマウス１１２などからなる入力部と、ディスプレイ１１３などからなる出力部によって構成される。ユーザは、入力部から命令を入力し、出力部を用いて結果を確認することができる。
【００４０】
さらにＰＣ１００は、メモリ１２０及びＣＰＵ（Central Processing Unit）１３０を備える。メモリ１２０には流域抽出プログラム１４１が展開される。この流域抽出プログラム１４１はＣＰＵ１３０への命令によって構成される。ＣＰＵ１３０は、流域抽出プログラム１４１の命令に従い計算、ＨＤＤ（Hard Disk Drive）１９０へのアクセス、および入出力部１１０との情報の交換などを行う。以下の説明において流域抽出プログラム１４１が実行する処理は、実際には、流域抽出プログラム１４１に記述された命令に従うＣＰＵ１３０によって実行される。
【００４１】
ＨＤＤ１９０には地図データ１９１、標高データ１９２、海域データ１９３が格納されており、流域抽出プログラムはこれらのデータを読み込むことができる。なお、ＨＤＤ１９０は、ＰＣ１００に内蔵されてもよいし、ＰＣ１００の外部に接続されてもよいし、ＰＣ１００からネットワーク経由でアクセスできる別の装置に接続されてもよい。
【００４２】
地図データ１９１は、ユーザに場所を理解させる情報であればよい。地図データ１９１として適している情報として、地名、行政界、道路、鉄道、衛星画像、等高線、海岸線などが挙げられる。本実施形態では少なくとも等高線および海岸線が利用される。さらに、谷線、河道流路線、海岸線、湖沼面、海面等、水面の位置を示す情報、流域境界線など分水嶺の位置を示す情報が必要に応じて利用されてもよい。
【００４３】
標高データ１９２は、一般的にDigital elevation model（ＤＥＭ）と呼ばれるデータである。すなわち、セルの位置とそのセルにおける地表面の標高を記載した情報である。代表的なＤＥＭは、地表面に等間隔で並べた正方形のセル（square grid）における標高の値である。
【００４４】
海域データ１９３は、流出口がない水域を示すデータである。つまり、海域に加え、閉塞湖沼域（水の流出口がない湖）等が判別できるデータである。多くの場合、このデータは海域を示すデータと同じであり、海域は標高データ１９２に基づいて判別できる。すなわち、通常の標高データでは、陸域には標高値が、海域には海域を示す値が格納されている。その場合、この海域データ１９３は不要であり、標高データ１９２のみで十分である。
【００４５】
図２は、本発明の実施形態のＰＣ１００によって実行される処理を示すシーケンス図である。
【００４６】
以下、図２にしたがってシステムの処理シーケンスを説明する。
【００４７】
ＰＣ１００で流域抽出プログラム１４１が起動される。流域抽出プログラム１４１は、ＨＤＤ１９０から地図データ１９１を読み出す（ステップ２０１）。データを読み出した流域抽出プログラム１４１は、ウィンドウ３００からなるＧＵＩ（Graphical User Interface）をディスプレイ１１３に出力する（ステップ２０２）。
【００４８】
図３は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの入力待ちの状態を示す説明図である。
【００４９】
図３のＧＵＩは、ディスプレイ１１３の所定の領域に表示されるウィンドウ３００からなり、キーボード１１１及びマウス１１２による入力を受け付ける。ウィンドウ３００は、少なくとも地図３１０を表示する。ユーザは、所定の操作によって、ユーザが必要とする地域の地図３１０を表示させることができる。地図３１０の縮尺は、流出現象の空間スケールと同程度であることが望ましい。したがって典型的な流出現象であれば、1/25,000かそれより粗い縮尺が適当である。本実施例の地図３１０は等高線３１１および海岸線３１２の情報を含む。
【００５０】
さらにウィンドウ３００は少なくとも、ユーザが１以上の地点を指定するための機能、および、ユーザがその指定を確定するための機能を有する。後述するように、１以上の地点を指定するためにマウスポインタ３０１が使用され、その指定を確定するために解析ボタン３０３が使用される。
【００５１】
このＧＵＩを用いてユーザは解析対象を指定する（ステップ２０３）。本実施の形態では、ユーザがマウス１１２を動かすことによってマウスポインタ３０１を地図３１０上で動かし、マウス１１２をクリックすることによって、任意の地点を下流端として指定する。なお、ユーザの操作結果をユーザにわかりやすく伝えるために、指定した地点にアイコン３０２を表示することが望ましい。
【００５２】
図３は、ユーザが河口付近のごく近接した２地点を下流端として指定した状態を示している。この場合、流域抽出プログラム１４１は、これからこれらの２地点を下流端とし、それらの流域を解析することになる。ユーザは解析対象を入力した後、解析ボタン３０３をクリックする。解析ボタン３０３がクリックされると、流域抽出プログラム１４１は、入力された地点に対応するセルを「開始セル」として指定する。
【００５３】
なお、ステップ２０３で入力する解析対象を地点に限定する必要はない。セルに変換できる情報であるかぎり、どのような情報が入力されてもよい。地点以外の代表的な情報として、線又は面が挙げられる。入力された点、線又は面の情報は、地理情報システムの基本的な公知の技術を用いてセルに変換することができる。このような技術は、たとえば、伊里政夫 監修，腰塚武志 編集（１９９３），計算機科学と地理情報処理 第２版， 共立出版株式会社， ISBN 4320026365.に記載されている。
【００５４】
線として河道流路線（河心線）を入力した場合、ＤＥＭによる表現が難しい細かい水路を考慮した流域抽出が可能になる。線として海岸線を入力した場合、その海岸線の流域を抽出することが可能になるため、たとえば湾の流域を抽出する際に便利である。面として湖沼面を入力した場合、その湖に対する流域を抽出することが可能になる。
【００５５】
あるいは、これらの情報は、ユーザによって入力されるかわりに、地図データ１９１から取り込まれてもよい。たとえば、河道流路線、海岸線、湖沼面等は地理情報データとして一般に流通しているため、それらを利用することができる。
【００５６】
本実施形態では、サブウィンドウ３３０のラジオボタン３３２を操作することによって、ユーザが入力方法を選択できる。例えば、ユーザがラジオボタン３３２の「マウス指定」および「点」を指定した場合、ユーザは、マウス１１２を使用して下流端の地点を入力することができる。あるいは、ユーザがラジオボタン３３２の「開く」を指定した場合、ユーザは、地図データ１９１に含まれる情報（例えば河道流路線等）を入力することができる。
【００５７】
さらに、ステップ２０３で、ユーザは、流域外の点、線、面等を追加的に入力してもよい。その場合、ユーザは、流域内の点、線、面等に加え、流域外の地点、線、面等を入力した後、解析ボタン３０３をクリックする。解析ボタン３０３がクリックされると、流域抽出プログラム１４１は流域外として入力された点、線、面等に対応するセルを「無効セル」に指定する。したがって、１以上のセルが開始セルとして、それ以外の０以上のセルが無効セルとして指定されることになる。流域外の情報を入力すると、後に説明する下流探索処理（ステップ５０４）を大幅に短縮することが可能になる。本実施形態では、サブウィンドウ３３０のラジオボタン３３１を操作することによって、入力された地点等が流域内または流域外のどちらであるかを選択できる。
【００５８】
さらに、２０３で、ユーザは、標高データに基づく流域外セル（または無効セル）の判定方法を定義してもよい。一般に、ある地点の上流には、その地点よりも標高が高い地点のみが存在する。この知識を利用すれば、開始セルよりも標高の低いセルは流域外セル（または無効セル）と見なせる。したがって、流域抽出プログラム１４１は、開始セルよりも標高の低いセルを流域外セル（または無効セル）と見なしてもよい。あるいは、流域抽出プログラム１４１は、標高データに誤りがある場合を考慮し、ある値よりも小さい標高を持つセルを流域外セル（または無効セル）と見なしてもよい。
【００５９】
次に流域抽出プログラム１４１は、流域抽出処理（ステップ２０４）を繰り返し行う。このステップ２０４は、標高データおよび海域データ読み込み処理（ステップ２０５）、および、進捗表示処理（ステップ２０６）を含む。ステップ２０５では、流域抽出プログラム１４１がＨＤＤ１９０から標高データ１９２を読み込む。ステップ２０６では、流域抽出プログラム１４１が進捗を示す記号をウィンドウ３００に表示する。ステップ２０６は必須ではないため省いてもよい。ステップ２０４の詳細は図５から１０を用いて説明する。
【００６０】
最後に流域抽出プログラム１４１は処理結果である流域をウィンドウ３００に表示する（ステップ２０７）。
【００６１】
図４は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの解析終了の状態を示す説明図である。
【００６２】
この図４には、流域を示す２種類の記号が表示されている。第１の記号は、水が流れる方向を示す線分４０１である。水はこの線分に沿って流れ下る。第２の記号は、分水嶺を示す線分４０２である。この分水嶺の内側にある水は、図３で指定した二つの点３０２のいずれかに流れ下る。一方で、この分水嶺の外側にある水は、図３で指定した二つの点３０２のいずれにも流れ下らない。
【００６３】
次に、流域抽出処理（ステップ２０４）の詳細を説明する。
【００６４】
図５は、本発明の実施形態の流域抽出処理（ステップ２０４）の詳細を示すフローチャートである。
【００６５】
ステップ５０１において、流域抽出プログラム１４１は、開始セルを「流域セル」とする。具体的には、流域抽出プログラム１４１は、開始セルのデータに含まれる、セルの種類を示す変数を「流域」に変更する。セルのデータについては後述する（図１３参照）。開始セルは、ステップ２０３において解析対象として入力された点、線または面等に対応するセルである。前述の通り、点−セル、線−セル、または面−セルの変換には、地理情報システムの基本的な技術が用いられる。
【００６６】
ステップ５０２において、流域抽出プログラム１４１は、開始セルの上流を探索する。ここで、ステップ５０２で実行される上流探索処理について、図６および図７を参照して説明する。
【００６７】
図６は、本発明の実施形態の上流探索処理（ステップ５０２）の詳細を示すフローチャートである。図６の詳細な説明は後述する。
【００６８】
図７は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの上流探索処理（ステップ５０２）の進捗を示す説明図である。
【００６９】
図６のステップ６０２で対象セルとして指定されたセルが、図７に点７０１として示されている。上流探索処理の進捗に伴って、対象セルは開始セルから上流方向に向かって１セルずつ進んでいくため、点７０１は上流方向に向かって１セルずつ進んでいく。また、ステップ６０３で読み込んだ部分領域が、図７に矩形７０２として示されている。この矩形も、上流探索処理の進捗に伴って上流方向に追加されていく。図７には４つの矩形が描かれている。これは、すでに４つの部分領域が読み込まれていることを示す。これらの点および矩形の動きによって、ユーザは、現在上流探索処理が実行されていることを知ることができ、さらに、その処理の進捗を直感的に把握することができる。このステップ５０２の処理によって、開始セルの流域が「流域セル」として抽出される。
【００７０】
ステップ５０３において、流域抽出プログラム１４１は、流域外セルを抽出する。この処理によって、ステップ５０２で抽出された流域セルでなく、かつ流域セルに隣接するセルが抽出される。抽出されたセルを流域外セルと記載する。
【００７１】
図８は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの流域外セル抽出処理（ステップ５０３）の進捗を示す説明図である。
【００７２】
ステップ５０３で抽出された流域外セルが、図８に点８０１として示されている。ステップ５０４以降に行う流域の真偽判定によって、流域が正しいと判定された場合、これらの点８０１が分水嶺となる。あらかじめ分水嶺がどこにあるかがわかっているユーザは、これらの点からこれらからなされる真偽判定の結果を予想でき、さらに残りの処理にかかる時間をおおよそ予想することができる。
【００７３】
ステップ５０４において、流域抽出プログラム１４１は、ステップ５０３で抽出されたセルの下流を探索する。
【００７４】
図９は、本発明の実施形態の下流探索処理（ステップ５０４）の詳細を示すフローチャートである。図９の詳細な説明は後述する。
【００７５】
図１０は、本発明の実施形態の流域抽出プログラム１４１が提供するＧＵＩの下流探索処理（ステップ５０４）の進捗を示す説明図である。
【００７６】
図９ステップ９０２で対象セルとして指定されたセルが、図１０に点１００１として示されている。下流探索処理の進捗に伴って、対象セルはステップ５０３で抽出した流域外セルから下流方向に向かって１セルずつ進んでいく。このため、点１００１の動きによって、ユーザは、現在下流探索処理が実行されていることを知ることができ、さらに、その処理の進捗を直感的に把握することができる。下流探索処理によって、ステップ５０３で抽出した流域外セルの下流のセルが「流域外セル」として抽出される。
【００７７】
ステップ５０５において、流域抽出プログラム１４１は、やり直しフラグ（図９を参照して後述）の値を判定する。やり直しフラグの値が真であると判定された場合、前回のステップ５０２の上流探索処理（現在までにステップ５０２から５０５のループが複数回実行された場合、最後に実行された上流探索処理）によって得られた流域が誤っている。言い換えると、真の流域は、前回の上流探索処理によって得られた流域のさらに外側まで広がっている。この場合、処理はステップ５０２に戻る。そして、流域抽出プログラム１４１は、再び開始セルの上流探索を実行する。前回の下流探索処理の際に窪地埋め処理が実行された場合、後述するように、窪地内のセルの下流方向が決定されている。この場合、今回の上流探索処理の結果は、前回の上流探索処理の結果と異なる。
【００７８】
ステップ５０５において、やり直しフラグの値が偽であると判定された場合、前回の上流探索処理によって得られた流域が正しい。このため、流域抽出プログラム１４１は、流域抽出処理を終了する。
【００７９】
以上、本実施例の全体的な処理の流れについて説明した。以下、個々の処理およびそれらの処理を実現するデータ構造について詳細に述べる。
【００８０】
図１１は、本発明の実施形態のセルおよび部分領域を示す説明図である。
【００８１】
本実施形態では、空間の東西方向をｘ軸（１１０１）、南北方向をｙ軸（１１０２）とする２次元直交座標系を利用する。さらにこの空間を、ｘ軸方向にｄｘ（１１０３）、ｙ軸方向にｄｙ（１１０４）の間隔で分割してセルを生成する。地点（ｘ，ｙ）にあるセル（ｉ，ｊ）は以下の式（１）で求められる。
【００８２】
i=floor(x/dx), j=floor(y/dy) ......... (1)
【００８３】
ただし、floor()は小数部分を切り捨てることによって整数にする関数である。
【００８４】
部分領域は、複数のセルからなる領域である。部分領域は、ｘ軸方向にsi（１１０５）、ｙ軸方向にsj（１１０６）のセルからなるとする。ただし、siおよびsjは２以上の整数である（この図１１にはsi＝１０，sj＝１０の例を示したが、図７、図８及び図１０にはsi＝２８，sj＝２８の例を示した）。したがって、１つのセルは１つの部分領域に含まれる。セル（ｉ，ｊ）が含まれる部分領域（bi，bj）は次の式（２）で求められる。
【００８５】
bi=floor(i/si), bj=floor(j/sj) ......... (2)
【００８６】
図１２は、本発明の実施形態の部分領域のデータ構造を示す説明図である。
【００８７】
以下のデータ構造に関する説明では、Ｃ＋＋などオブジェクト指向型言語に向いた実装方法を示す。表１２００に部分領域型のデータを示す。実装の際には、これらのデータをメンバ変数として持つ、クラス名CellUnitの型とすればよい。
【００８８】
CellUnitは、Id、Cells、Targetsの３つのメンバ変数を持つクラスである。
【００８９】
Idは整数型であり、上記式（２）に示したbi,bjから一意に生成した値を保持する（行１２０１）。Idは、たとえばbi,bjをそれぞれ３２ビット整数、Idを６４ビット整数とし、０から３１ビットまでにbiの値を、３２から６３ビットまでにbjの値を格納することによって作成されてもよい。
【００９０】
Cellsは図１３で説明するセル型を格納する固定長配列である（行１２０２）。配列の長さは、１つの部分領域に含まれるセルの数、すなわち、si*sjである。
【００９１】
Targetsは、セル型を格納する可変長配列である（行１２０３）。この変数の初期値はempty、すなわち格納された要素がない配列である。
【００９２】
図１３は、本発明の実施形態のセルのデータ構造を示す説明図である。
【００９３】
表１３００にセル型のデータを示す。セル型（クラス名Cell）は、Glev、Kind、DownDirの３つのメンバ変数を持つクラスである。
【００９４】
Glevは実数型であり、標高を保持する（行１３０１）。
【００９５】
Kindは列挙型であり、未定（０）、流域（１）、流域外（２）または無効（３）の別を示すフラグである（行１３０２）。未定（０）は、セルが有効セルであるが、流域セルまたは流域外セルのいずれであるかがまだ定まっていないことを示す。流域（１）は、セルが有効セルであり、かつ、流域セルであることを示す。流域外（２）は、セルが有効セルであり、かつ、流域外セルである（言い換えると他の流域に属する流域セルである）ことを示す。無効（３）は、セルが無効セルであることを示す。Kindの初期値は、未定（０）である。
【００９６】
DownDirは列挙型であり、水が流れる方向（すなわち隣接下流セルの方向）を示すフラグである（行１３０３）。DownDirの具体的な値については図１４及び図１５を参照して説明する。DownDirの初期値は、隣接下流セルが存在しないことを示す値０である。水が流れる方向を求めるためには、セル勾配を求める必要がある。
【００９７】
図１４は、本発明の実施形態のセル勾配についての説明図である。
【００９８】
図１４には、セル１４００を中心にｉ軸方向に３セル、ｊ軸方向に３セルを示した。セル（i,j）における勾配は、セル（i,j）の標高値と、その格子に隣接するセルにおける標高値との差をセル間の距離で割った値である。１セルには８セルが隣接する。したがって、セル（i,j）における８方向の勾配が算出される。勾配の方向をそれぞれ矢印１４０１から矢印１４０８で示す。矢印１４０１から矢印１４０８に対応する勾配をそれぞれGrad1からGrad8と命名する。変数Grad1からGrad8の値を求める式は以下の通りである。
【００９９】
Grad1=(Glev[i,j]-Glev[i-1,j+1])/hypot(dx,dy) ......... (3-1)
Grad2=(Glev[i,j]-Glev[i,j+1])/dy ......... (3-2)
Grad3=(Glev[i,j]-Glev[i+1,j+1])/hypot(dx,dy) ......... (3-3)
Grad4=(Glev[i,j]-Glev[i-1,j])/dx ......... (3-4)
Grad5=(Glev[i,j]-Glev[i+1,j])/dx ......... (3-5)
Grad6=(Glev[i,j]-Glev[i-1,j-1])/hypot(dx,dy) ......... (3-6)
Grad7=(Glev[i,j]-Glev[i,j-1])/dy ......... (3-7)
Grad8=(Glev[i,j]-Glev[i+1,j-1])/hypot(dx,dy) ......... (3-8)
【０１００】
ただし、Glev[i,j]はセル(i,j)における標高、hypot(x,y)は原点(0,0)と点(x,y)との距離を返す関数である。なお、本実施例では隣接するセルとして８近傍（すなわち隣接する８個のセル）を利用した。これは、隣接セルが増えるほど精度のよい結果が期待できるためである。ただし、隣接するセルとして８近傍ではなく４近傍（すなわち隣接する４個のセル）を使用してもよい。その場合は、上記８方向の勾配のうちGrad2、Grad4、Grad5、Grad7のみを利用すればよい。
【０１０１】
あるセル(i,j)の隣接下流セルは、そのセル(i,j)の勾配Grad1からGrad8から求められる。具体的には、あるセル(i,j)の隣接下流セルは、そのセルの最も急な下り勾配方向にある隣接セルである。最も急な下り勾配とは、勾配Grad1からGrad8の最大値であり、最も急な下り勾配方向とは、勾配Grad1からGrad8の最大値の方向である。この最も急な下り勾配方向は、以下（ａ）から（ｃ）の３ケースに分類できる。
【０１０２】
（ａ）最も急な下り勾配が０より大、かつ１方向の場合。この場合、最も急な下り勾配方向を水が流れる方向とする。
【０１０３】
（ｂ）最も急な下り勾配が０より大、かつ２方向以上の場合。この場合、最も急な下り勾配方向から、あらかじめ決めた方向優先度に従って１方向を選択する。本実施形態では、下記の式（４）の順に優先度の高さが設定される。
【０１０４】
Grad2 > Grad5 > Grad7 > Grad4 > Grad1 > Grad3 > Grad8 > Grad6......... (4)
【０１０５】
例えば、Grad2とGrad3の値が同じであり、かつ、これらが最も急な下り勾配方向である場合、Grad2の優先度がGrad3より高いため、Grad2に対応する方向１４０２のセル(i,j+1)が隣接下流セルである。
【０１０６】
（ｃ）最も急な下り勾配が０以下の場合。この場合、水が流れる方向は存在せず、隣接下流セルは存在しないと判定される。本実施形態では後に説明するように無効セルの標高を負の無限大として扱っているため、最も急な下り勾配方向が０以下であると判定されたセルは窪地または平地である。
【０１０７】
図１５は、本発明の実施形態において水が流れる方向と、それに対応するフラグの値を説明するための図である。
【０１０８】
実装では、セル型Cellのメンバ変数DownDirが、図１５に示す値を保持する。最も急な下り勾配方向が上記（ａ）または（ｂ）の場合、DownDirは１，２，４，８，１６，３２，６４，１２８のいずれかの値になる。たとえばセル(i,j)の水が流れる方向が図１４の方向１４０５である（すなわち、セル(i,j)の隣接下流セルがセル(i+1,j)である）場合、DownDirの値は１となる。最も急な下り勾配方向が上記（ｃ）の場合（すなわち隣接下流セルが存在しない場合）、DownDirは未定を表す値０になる。
【０１０９】
次に、図６を用いて上流探索処理（ステップ５０２）の詳細を説明する。
【０１１０】
流域抽出プログラム１４１は、それぞれの流域セルについてステップ６０１からステップ６１２までの処理を繰り返す。図６の説明において、このループの処理対象のセルをcell1と記載する。実装では、ステップ５０１で部分領域クラスCellUnitのメンバ変数Targetsに開始セルを格納し、Targetsのそれぞれの要素についてこのループを実行する。
【０１１１】
ステップ６０２において、流域抽出プログラム１４１は、cell1を「対象セル」として指定する。
【０１１２】
ステップ６０３において、流域抽出プログラム１４１は、対象セル（cell1）を含む部分領域を読み込む。これによって、標高データ１９２および海域データ１９３が読み込まれる。流域抽出プログラム１４１は、海域データ１９３に基づいて海域と判別されたセルを、無効セルに指定する。さらに、ステップ２０３で無効セルまたは流域外セルが指定されている場合、流域抽出プログラム１４１は、そのセルを無効セルまたは流域外セルに指定する。そして、流域抽出プログラム１４１は、無効セルの標高を負の無限大にする。
【０１１３】
実装では、例えば、下記の手順が実行される。まず、流域抽出プログラム１４１は、メモリ１２０に部分領域クラスCellUnitのインスタンスを生成する。部分領域クラスCellUnitのインスタンスは、変数Idにbi,bjから生成したＩＤを格納し、変数CellsにセルクラスCellのインスタンスをsi*sj個保持する。セルクラスCellのメンバ変数Kind及びDownDirは表１３００に示した初期値に初期化される。
【０１１４】
メンバ変数GlevおよびKindには、次のような値が格納される。海域データ１９３、または、ステップ２０３における指定に基づいて、セルが無効セルであると判定された場合、メンバ変数Glevには標高値として負の無限大が格納され、メンバ変数Kindには無効（３）が格納される。セルが有効セルであると判定された場合、メンバ変数Glevには標高値としてＨＤＤ１９１から読み込まれた標高データ１９２が格納され、メンバ変数Kindには未定（０）が格納される。ただし、セルが流域外セルであると判定された場合、メンバ変数Kindには流域外（２）が格納される。
【０１１５】
次に、流域抽出プログラム１４１は、対象セル（cell1）のそれぞれの隣接セルについてステップ６０４からステップ６１１までの処理を繰り返す。図６の説明において、このループの処理対象のセル（すなわち、cell1に隣接する複数のセルの各々）をcell2と記載する。
【０１１６】
ステップ６０５において、流域抽出プログラム１４１は、cell2の隣接下流セルが対象セル（cell1）であるか否かを判定する。この判定の結果が真である場合、処理はステップ６０６に、偽である場合、処理はステップ６１１に進む。
【０１１７】
cell2の隣接下流セルは、図１４を参照して説明したように、最急勾配法によって求められる。ただし、後述するように、窪地埋め処理によってcell2の下流方向が決定された場合、その下流方向に基づいてcell2の隣接下流セルが求められる。
【０１１８】
実装では、このステップによってcell2のメンバ変数DownDirに水が流れる方向を示す値が格納される。
【０１１９】
ステップ６０６において、流域抽出プログラム１４１は、cell2の種類を判定する。具体的には、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を参照して、cell2が流域セル、流域外セル、無効セルまたは未定セルのいずれであるかを判定する。
【０１２０】
流域の定義によれば、cell2が有効セルであり、cell2の隣接下流セルがcell1であり、かつ、cell1が流域セルである場合、cell2は必ず流域セルである。このことに合致するように、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を更新する（ステップ６０７〜ステップ６１０）。
【０１２１】
cell2に関するセルクラスCellのメンバ変数Kindの値が流域（１）である場合、cell2は既に流域セルとして扱われている。この場合、メンバ変数Kindの値を更新する必要がないため、流域抽出プログラム１４１は、メンバ変数Kindの値を更新せずに（ステップ６０７）、ステップ６１１に進む。
【０１２２】
メンバ変数Kindの値が流域外（２）である場合、cell2は流域外セルである。このことは、cell2が既に他の流域に属する流域セルであると判定されていることを意味する。この場合、流域抽出プログラム１４１は、メンバ変数Kindの値を更新せずに（ステップ６０８）、ステップ６１１に進む。ただし、流域の定義によれば、ステップ６０６においてcell2が有効セルであると判定された場合、cell2は必ず流域セルである。このため、上流探索が正常に実行されている限り、ステップ６０６においてcell2が流域外セルであると判定されることはあり得ない。
【０１２３】
メンバ変数Kindの値が無効（３）である場合、cell2は無効セルである。この場合、cell2は流域セルになり得ないため、流域抽出プログラム１４１は、メンバ変数Kindの値を更新せずに（ステップ６０９）、ステップ６１１に進む。
【０１２４】
メンバ変数Kindの値が未定（０）である場合、cell2は未定セルである。上記のように、流域の定義によれば、ステップ６０６においてcell2が有効セルであると判定された場合、cell2は必ず流域セルである。このため、流域抽出プログラム１４１は、cell2を流域セルに変更して（ステップ６１０）、ステップ６１１に進む。具体的には、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を流域（１）に更新する。さらに、流域抽出プログラム１４１は、部分領域クラスCellUnitのメンバ変数Targetsにcell2を追加する。これによって、cell2は新たな対象セルとなる。
【０１２５】
ステップ６１１では、ステップ６０４のループに戻る。cell1に隣接する全てのcell2についてステップ６０４〜６１１のループが終了するまで、このループが繰り返し実行される。
【０１２６】
ステップ６１２では、ステップ６０１のループに戻る。全ての対象セルについてステップ６０１〜６１２のループが終了するまで、このループが繰り返し実行される。
【０１２７】
次に、図９を用いて下流探索処理（ステップ５０４）の詳細を説明する。
【０１２８】
流域抽出プログラム１４１は、それぞれの流域外セルについて、ステップ９０１からステップ９１２までの処理を繰り返す。図９の説明において、このループの処理対象のセルをcell1と記載する。実装では、ステップ５０３で部分領域クラスCellUnitのメンバ変数Targetsに流域外セルを格納し、Targetsのそれぞれの要素についてこのループを実行する。
【０１２９】
例えば、ステップ５０２が終了した時点で図８に示す複数のセル８０１が流域外セルである場合、これらの全てのセル８０１がメンバ変数Targetsに格納される。そして、全ての流域外セルについて処理が終了するまで、各流域外セルを対象として図９のループが繰り返される。
【０１３０】
なお、図９の説明において、「流域セル」とは、開始セル（図３の例ではアイコン３０２に対応するセル）が属する流域に属するセルを、「他の流域」とは、開始セルが属する流域と異なる流域を、流域外セルとは、他の流域に属するセル（すなわち、開始セルの上流にないセル）を、それぞれ意味する。
【０１３１】
ステップ９０２において、流域抽出プログラム１４１は、cell1を「対象セル」として指定する。
【０１３２】
ステップ９０３において、流域抽出プログラム１４１は、対象セル（cell1）を含む部分領域を読み込む。この動作はステップ６０３と同じである。
【０１３３】
ステップ９０４において、流域抽出プログラム１４１は、cell1の隣接下流セル（図９の説明においてcell2と記載する）を特定し、その種類を判定する。具体的には、流域抽出プログラム１４１は、cell2が存在するか否か、及び、存在する場合、cell2に関するセルクラスCellのメンバ変数Kindの値を参照して、cell2が流域セル、流域外セル、無効セルまたは未定セルのいずれであるかを判定する。cell1の隣接下流セルは、最急勾配法（図１４参照）によって求められる。実装では、cell1のメンバ変数DownDirに、水が流れる方向を示す値が格納される。
【０１３４】
ここで、ステップ９０４の判定結果に基づく処理の概要を説明する。
【０１３５】
流域の定義によれば、ステップ５０３で抽出されたセルが流域外セルであれば、その下流の有効セルは、必ず流域外セルである。図９のcell1は、ステップ５０３で抽出されたセル自体またはその下流のセルであり、cell2はさらにその下流のセルである。したがって、cell1が流域外セルであり、cell１の隣接下流セルがcell２であり、かつ、cell2が有効セルである場合、cell2は必ず流域外セルである。このことに合致するように、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を更新する。
【０１３６】
このような処理において、cell１が流域外セルであるにもかかわらずcell2が流域セルであると判定されることは、ステップ５０３で抽出されたセルが実は流域セルであることを示す。これは、直前の上流探索処理によって取得された流域が誤っていたこと、すなわち、上流探索処理のやり直しが必要であることを意味する。この場合、流域抽出プログラム１４１は、やり直しフラグの値を更新する。
【０１３７】
やり直しフラグは、上流探索処理のやり直しが必要であるか否かを示す。具体的には、やり直しフラグの値がtrue（真）であることは、上流探索処理のやり直しが必要であることを示す。やり直しフラグは、例えば、初期値false（偽）のブール型のグローバル変数Failedである。
【０１３８】
次に、上記の処理の詳細を説明する。
【０１３９】
cell2に関するセルクラスCellのメンバ変数Kindの値が流域（１）である場合、cell2は流域セルである。このことは、cell1が流域外セルであることと矛盾する。すなわち、このことは、既に流域外セルであると判定されているcell1及びその上流の全てのセルが実は流域セルであること、さらに言い換えると、前回の上流探索処理（ステップ５０２）の結果が誤っていることを意味する。このため、流域抽出プログラム１４１は、やり直しフラグの値を真に更新し（ステップ９０５）、ステップ９１２に進む。
【０１４０】
メンバ変数Kindの値が流域外（２）である場合、cell2は流域外セルである。このことは、cell1が流域外セルであることと矛盾しない。言い換えると、これによって、cell2及びその上流の全てのセルが流域外セルであることが確認された。このため、流域抽出プログラム１４１は、やり直しフラグ及びメンバ変数Kindの値を更新せずに（ステップ９０６）、ステップ９１２に進む。この場合、cell2のさらに下流を探索する必要がないため、cell2は新たな対象セルとして選択されない。
【０１４１】
なお、cell2が流域外セルであるか否かは、どのような方法によって判定されてもよい。例えば、過去に実行された別の流域抽出処理によって、cell2が別の流域に属することが確定している場合、cell2に関するメンバ変数Kindの値が流域外（２）であるため、上記のようにcell2が流域外セルであると判定され、処理はステップ９０６に進む。ユーザがあらかじめ流域外の範囲を指定した場合も同様である。あるいは、メンバ変数Kindの値にかかわらず、cell2の標高が所定の標高（例えば、開始セルの標高）より低いと判定された場合に、cell2が流域外セルであると判定され、処理がステップ９０６に進んでもよい。あるいは、開始セルが河川上のセルである場合において、cell2が、開始セルが属するものと別の河川上のセルであると判定された場合、cell2が流域外セルであると判定され、処理がステップ９０６に進んでもよい。各セルがどの河川上にあるかは、地図データ１９１に基づいて判定することができる。
【０１４２】
メンバ変数Kindの値が無効（３）である場合、cell2は無効セルである。このことは、cell1が流域外セルであることと矛盾しない。言い換えると、これによって、cell1及びその上流の全てのセルが流域外セルであることが確認された。このため、流域抽出プログラム１４１は、やり直しフラグ及びメンバ変数Kindの値を更新せずに（ステップ９０７）、ステップ９１２に進む。この場合も、cell2のさらに下流を探索する必要がないため、cell2は新たな対象セルとして選択されない。
【０１４３】
メンバ変数Kindの値が未定（０）である場合、cell2は未定セルである。流域の定義によれば、ステップ９０４においてcell2が有効セルであると判定された場合、cell2は必ず流域外セルである。このため、流域抽出プログラム１４１は、cell2を流域外セルに変更して（ステップ９０８）、ステップ９１２に進む。具体的には、流域抽出プログラム１４１は、cell2に関するセルクラスCellのメンバ変数Kindの値を流域外（２）に更新する。さらに、流域抽出プログラム１４１は、部分領域クラスCellUnitのメンバ変数Targetsにcell2を追加する。これによって、cell2は新たな対象セルとなる。
【０１４４】
cell1に隣接する全てのセルの標高がcell1の標高以上である場合（すなわち、cell1が図１４において説明したケース（ｃ）に該当する場合）、最急勾配法によれば、cell1の下流方向は存在しない（言い換えるとcell1から水が流出しない）。このため、ステップ９０４において、cell2が存在しないと判定される。この場合、流域抽出プログラム１４１は、最急勾配法ではなく、cell1の周囲の複数のセルの標高の配置に基づいてcell1の下流方向を決定するための処理を実行する。
【０１４５】
具体的には、流域抽出プログラム１４１は、cell1を窪地セルに変更し（ステップ９０９）、窪地埋め処理を実行する（ステップ９１０）。ステップ９０９及びステップ９１０において実行される処理については後述する（図１６及び図１７参照）。窪地埋め処理が終了すると、流域抽出プログラム１４１は、窪地セルを流域外セルに変更して（ステップ９１１）、ステップ９１２に進む。
【０１４６】
全ての流域外セルについてステップ９０１からステップ９１２までのループが終了すると、流域抽出プログラム１４１は、下流探索処理を終了する。
【０１４７】
次に、図１６および図１７を用いて窪地埋め処理（ステップ９１０）の詳細を説明する。
【０１４８】
図１６は、本発明の実施形態の窪地のデータ構造を示す説明図である。
【０１４９】
表１６００に窪地型のデータを示す。実装の際には、これらのデータをメンバ変数として持つ、クラス名Sinkの型とすればよい。
【０１５０】
Sinkは、Cells、Outlets、WlevおよびFinishedの４つのメンバ変数を持つクラスである。CellsおよびOutletsはセル型を格納する可変長配列である（行１６０１および１６０２）。CellsおよびOutletsは、それぞれ、図１７で説明する窪地セルおよび流出口セルを格納する。CellsおよびOutletsの初期値はemptyである。図９のステップ９０９は、cell1をメンバ変数Cellsに追加することによって実行される。Wlevは実数型であり、図１７で説明する隣接最小標高を格納する（行１６０３）。Finishedはブール型であり、終了フラグを格納する（行１６０４）。Finishedの初期値はfalseである。
【０１５１】
図１７は、本発明の実施形態の窪地埋め処理（ステップ９１０）の詳細を示すフローチャートである。
【０１５２】
ステップ１７０１において、流域抽出プログラム１４１は、「隣接最小標高」を算出する。隣接最小標高とは、窪地セルに隣接するセルの標高のうち最小の標高である。この窪地埋め処理の開始時点において、窪地セルはステップ９０９で得られたものだけである。したがってその時点の隣接最小標高はステップ９０９で得られた各窪地セルに隣接する８セルの標高の最小値であり、その値はステップ９０９で得られた窪地セルの標高と同じか、またはそれよりも大きい。
【０１５３】
実装では、ステップ９０９の終了時点で、窪地型Sinkのメンバ変数Cellsには、ステップ９０９において取得された窪地セル１つのみが格納されている。さらに、このステップ１７０１では、メンバ変数Cellsに隣接するセルの標高の最小値がメンバ変数Wlevに格納される。
【０１５４】
流域抽出プログラム１４１は、それぞれの窪地セルについてステップ１７０２からステップ１７１０までの処理を繰り返す。図１７の説明において、このループの処理対象のセルをcell1と記載する。実装では、メンバ変数Cellsのそれぞれの要素についてこのループを実行する。
【０１５５】
流域抽出プログラム１４１は、cell1のそれぞれの隣接セルについてステップ１７０３からステップ１７０９までの処理を繰り返す。図１７の説明において、このループの処理対象のセルをcell2と記載する。
【０１５６】
ステップ１７０４において、流域抽出プログラム１４１は、cell2を含む部分領域を読み込む。この動作はステップ６０３と同じである。
【０１５７】
ステップ１７０５において、流域抽出プログラム１４１は、隣接最小標高Wlevとcell2の標高とを比較する。Wlevとcell2の標高とが等しい場合ステップ１７０６に進み、等しくない場合ステップ１７０７に進む。
【０１５８】
Wlevとcell2の標高とが等しい場合、cell2は窪地の一部である。このため、ステップ１７０６において、流域抽出プログラム１４１は、cell2を窪地セルに変更する。実装では、メンバ変数Cellsにcell2を追加する。ステップ１７０６が実行された場合、追加されたcell2を処理するためのステップ１７０２からステップ１７１０までの処理が後に実行されることになる。
【０１５９】
ステップ１７０６が実行された時点で、cell2の標高はメンバ変数Wlevの値に等しく、かつ、その標高の値が窪地セルの中で最も大きい。このため、図１７の説明において、メンバ変数Wlevを窪地最大標高とも記載する。
【０１６０】
ステップ１７０７において、流域抽出プログラム１４１は、窪地最大標高Wlevとcell2の標高とを比較する。Wlevがcell2の標高より大きい場合、cell2は窪地の一部ではない。さらにこの場合、cell2は、cell1を含む窪地に流入した水の流出口である。この場合、流域抽出プログラム１４１はステップ１７０８に進む。一方、Wlevがcell2の標高より小さい場合、cell2は窪地の一部である可能性があるが、そうでない可能性もある。この場合、流域抽出プログラム１４１は、ステップ１７０８を実行せずにステップ１７０９に進む。実装では、流域抽出プログラム１４１は、ステップ１７０８に進む前にcell2をメンバ変数Outletsに追加する。
【０１６１】
ステップ１７０８において、流域抽出プログラム１４１は、終了フラグFinishedを真（true）に更新する。なお、終了フラグの初期値は偽（false）である。つまり、ステップ１７０８が最初に実行されるまで、終了フラグFinishedは偽である。
【０１６２】
ステップ１７０９において、まだ処理されていない隣接セルがある場合、ステップ１７０３のループに戻る。
【０１６３】
ステップ１７１０において、まだ処理されていない窪地セルがある場合、ステップ１７０２のループに戻る。
【０１６４】
ステップ１７１１では、終了フラグFinishedの真偽判定をする。終了フラグが真の場合、窪地に流入した水の流出口が既に特定されている。このことは、窪地の範囲が特定されたことを意味する。すなわち、この時点における窪地セルの範囲が、特定された窪地の範囲である。この場合、処理はステップ１７１２に進む。一方、終了フラグが偽の場合、窪地に流入した水の流出口がまだ特定されていない。この場合、窪地の範囲がまだ特定されていないため、処理はステップ１７０１に戻る。
【０１６５】
ステップ１７１２において、流域抽出プログラム１４１は、すべての窪地セルの標高を隣接最小標高Wlevに変更する。なお、このステップで使用する隣接最小標高Wlevは、直前の回のステップ１７０１で求めた値であり、ステップ１７１２の時点の窪地セルに基づいて新たに隣接最小標高を算出するわけではない。この処理によって、すべての窪地セルの標高が等しくなる。以下の説明において、上記のように標高が変更された窪地セルを平地セルと言い換える。なお、実装ではメンバ変数Cellsに格納されたすべてのセルの標高をWlevに変更する。
【０１６６】
ステップ１７１３において、流域抽出プログラム１４１は、すべての平地セルの下流方向を決定する。具体的には、流域抽出プログラム１４１は、平地セルに隣接する、平地セルよりも低い標高を持つセル（図１７の例では、ステップ１７０７でＴｒｕｅと判定された場合のcell2）を、その平地の流出口セルとする。そして、平地内の流れが流出口セルに向かうように平地内の水が流れる方向（すなわち下流方向）を決定する。
【０１６７】
まず、流域抽出プログラム１４１は、平地セルのうち、流出口セルに隣接し、かつ、水が流れる方向が決定していないセルの下流方向を、流出口セルに向かう方向に決定する。１つの平地セルに複数の流出口セルが隣接している場合には、前述した方向優先度に従って下流方向が決定される。続いて、流域抽出プログラム１４１は、上記のように下流方向を決定したセルを流出口セルと見なし、その新たな流出口セルについて上記の処理を実行する。このように、すべての平地セルの水が流れる方向が決定するまで、同様の処理を繰り返す。実装では、メンバ変数Outletsに格納されたすべてのセルを流出口セルとする。
【０１６８】
なお、上記のような下流方向の決定方法は一例に過ぎない。窪地に流れ込んだ水が流出口セルから流出するように決定される限り、どのように下流方向が決定されてもよい。このように下流方向を特定することによって、全ての窪地セルがその窪地の流出口セルの上流であること、言い換えると、全ての窪地セルが、その窪地の流出口セルが属するものと同一の流域に属することが特定される。
【０１６９】
上記のように決定された下流方向は、その後に実行される上流探索処理（ステップ５０２）において使用される。具体的には、上記のように下流方向が決定されたセルが図６の処理のcell2として選択された場合、その決定された下流方向に基づいてステップ６０５の判定が実行される。
【０１７０】
このようにして、本実施形態ではユーザが図３に示した入力画面から情報を入力すると、プログラムが図７，８，１０に示した進捗画面を提示して、最終的に図４に示した結果表示画面を提示することができる。
【０１７１】
本実施形態では部分領域を使用した場合の実施方法について説明した。しかし、部分領域を使用せずに本発明を実施することもできる。この場合、対象部分領域の読み込み処理（ステップ６０３、ステップ９０３、ステップ１７０４）を削除する。そして、ステップ２０３の直後に、次の処理を追加する。流域抽出プログラム１４１は、最初に、ユーザに解析対象領域を指定させる。次に、指定された領域の標高データ１９２および海域データ１９３を読み込む。次に、海域データ１９３により海域と判別されたセルを、無効セルに指定する。さらに、ステップ２０３で無効セルが指定されている場合は、そのセルも無効セルとする。そして、無効セルの標高を負の無限大にする。
【産業上の利用可能性】
【０１７２】
以上述べたとおり、本発明によれば、流域に関する事前知識を要求しない流域抽出コンピュータプログラムが提供できる。このプログラムを用いることによって、コンピュータが使えるユーザであれば、専門家と同等の品質の流域抽出ができるようになる。
【符号の説明】
【０１７３】
１００ ＰＣ
３１０ 地図
３０２ 下流端
４０１ 水が流れる方向を示す線分
４０２ 分水嶺を示す線分
７０１ 上流探索処理における処理対象セルを示す点
７０２ 標高データ１９２等をメモリに読み込んだ部分領域を示す矩形
１００１ 下流探索処理における処理対象セルを示す点
【特許請求の範囲】
【請求項１】
コンピュータを制御する流域抽出プログラムであって、
前記コンピュータは、
前記流域抽出プログラムが格納されるメモリと、前記メモリに格納された前記流域抽出プログラムを実行するプロセッサと、を備え、
地図上の複数の領域の標高を示す標高データを保持し、
前記複数の領域は、第１領域を含み、
前記流域抽出プログラムは、
前記第１領域に流れ込む水の流域を、前記標高データに基づいて上流方向に探索する第１手順と、
前記第１手順によって特定された流域が正しいか否かを判定する第２手順と、を前記プロセッサに実行させ、
前記第２手順において、前記特定された流域が正しくないと判定された場合、前記第１手順を再び前記プロセッサに実行させることを特徴とする流域抽出プログラム。
【請求項２】
前記複数の領域は、前記第１手順によって特定された流域に含まれない第２領域をさらに含み、
前記流域抽出プログラムは、さらに、前記標高データに基づいて、前記第２領域の下流の前記領域を特定する第３手順を前記プロセッサに実行させ、
前記第２手順は、前記第３手順によって前記第２領域の下流の領域として特定された領域が、前記第１手順によって特定された流域に含まれる場合、前記第１手順によって特定された流域が正しくないと判定する手順を含むことを特徴とする請求項１に記載の流域抽出プログラム。
【請求項３】
前記第３手順は、
前記第２領域の下流の領域から水が流出しないと判定された場合、前記標高データに基づいて、前記水が流出しないと判定された領域を含む窪地の範囲、及び、前記窪地に流れ込んだ水の流出口を特定する第４手順と、
前記窪地に流れ込んだ水が前記特定された流出口から流出するように、前記特定された窪地に含まれる各領域の下流方向を特定する第５手順と、を含み、
前記第３手順が実行された後に実行される前記第１手順において、前記第１領域に流れ込む水の流域を探索するために、前記第５手順によって特定された下流方向が使用されることを特徴とする請求項２に記載の流域抽出プログラム。
【請求項４】
前記第２領域は、前記第１手順によって特定された流域に含まれない領域のうち、前記第１手順によって特定された流域に隣接する領域であることを特徴とする請求項３に記載の流域抽出プログラム。
【請求項５】
前記流域抽出プログラムは、前記第１手順の前に、前記第１領域の指定を受ける手順を前記プロセッサに実行させ、
前記第１手順は、
前記第１領域を対象領域として選択する手順と、
前記標高データから算出された、前記対象領域に隣接する領域と、前記対象領域に隣接する領域にさらに隣接する領域との間の勾配に基づいて、前記対象領域に隣接する領域の下流方向を特定する手順と、
前記勾配に基づいて特定された下流方向、又は、前記第５手順によって特定された下流方向に基づいて、前記対象領域に隣接する領域が前記対象領域の上流であるか否かを判定する手順と、
前記対象領域に隣接する領域が前記対象領域の上流であると判定された場合、前記対象領域に隣接する領域を前記流域内の領域として特定する手順と、
前記対象領域に隣接する領域が前記対象領域の上流であると判定された場合、前記対象領域に隣接する領域を新たな前記対象領域として選択する手順と、を含むことを特徴とする請求項３に記載の流域抽出プログラム。
【請求項６】
前記第３手順は、さらに、
前記第２領域を対象領域として選択する手順と、
前記標高データに基づいて、前記対象領域と、前記対象領域に隣接する領域との間の勾配を算出する手順と、
前記勾配に基づいて、前記対象領域に隣接する領域が前記対象領域の下流であるか否かを判定する手順と、
前記対象領域に隣接する領域が前記対象領域の下流であると判定された場合、前記対象領域に隣接する領域を、前記第２領域の下流の領域として特定する手順と、
前記対象領域に隣接する領域が前記対象領域の下流であると判定された場合、前記対象領域に隣接する領域を、新たな前記対象領域として特定する手順と、
前記対象領域に隣接する複数の領域の全ての前記標高が、前記対象領域の前記標高より高い場合、前記対象領域から水が流出しないと判定する手順と、を含むことを特徴とする請求項３に記載の流域抽出プログラム。
【請求項７】
前記第３手順は、さらに、前記対象領域に隣接する領域が前記第１領域の上流であるか否かを判定する手順を含み、
前記対象領域に隣接する領域が前記対象領域の下流であると判定され、かつ、前記対象領域に隣接する領域が前記第１領域の上流でないと判定された場合、前記流域抽出プログラムは、前記第３手順に含まれる手順のうち、前記対象領域に隣接する領域を前記第２領域の下流の領域として特定する手順を前記プロセッサに実行させないことを特徴とする請求項６に記載の流域抽出プログラム。
【請求項８】
前記第３手順は、さらに、前記対象領域に隣接する領域が海である場合、前記対象領域に隣接する領域の標高が所定の値より低い場合、及び、前記対象領域に隣接する領域が前記第１領域の上流でないことを示す情報が入力された場合、の少なくとも一つの場合に、前記対象領域に隣接する領域が前記第１領域の上流でないと判定する手順を含むことを特徴とする請求項７に記載の流域抽出プログラム。
【請求項９】
前記第４手順は、
前記水が流出しないと判定された領域を前記窪地内の領域として特定する手順と、
前記窪地に隣接する領域の一つを対象領域として選択する手順と、
前記対象領域の標高が、前記窪地に隣接する全ての領域の標高の最低値と同一である場合、前記対象領域を、新たな前記窪地内の領域として特定する手順と、
前記窪地外の領域のうち、前記新たな窪地内の領域に隣接する領域の標高が、前記新たな窪地内の領域の標高より低い場合、前記新たな窪地内の領域に隣接する領域を前記窪地に流れ込んだ水の流出口として特定する手順と、を含むことを特徴とする請求項３に記載の流域抽出プログラム。
【請求項１０】
前記コンピュータには、表示装置が接続され、
前記第１手順は、さらに、前記第１手順が実行されていることを示す情報を前記表示装置に表示させる手順を含み、
前記第３手順は、さらに、前記第３手順が実行されていることを示す情報を前記表示装置に表示させる手順を含むことを特徴とする請求項３に記載の流域抽出プログラム。
【請求項１１】
前記流域抽出プログラムは、さらに、前記対象領域が選択された後、前記選択された対象領域を含む複数の領域の標高データを読み込む手順を含むことを特徴とする請求項５、６又は９のいずれか一つに記載の流域抽出プログラム。
【請求項１２】
水の流域を抽出する流域抽出装置であって、
前記流域抽出装置は、
メモリと、前記メモリに格納されたプログラムを実行するプロセッサと、を備え、
地図上の複数の領域の標高を示す標高データを保持し、
前記複数の領域は、第１領域を含み、
前記流域抽出装置は、
前記第１領域に流れ込む水の流域を、前記標高データに基づいて上流方向に探索し、
前記上流方向の探索によって特定された流域が正しいか否かを判定し、
前記特定された流域が正しくないと判定された場合、前記上流方向への探索を再び実行することを特徴とする流域抽出装置。
【請求項１３】
前記複数の領域は、前記上流方向への探索によって特定された流域に含まれない第２領域をさらに含み、
前記流域抽出装置は、さらに、
前記標高データに基づいて、前記第２領域の下流の前記領域を特定し、
特定された、前記第２領域の下流の領域が、前記上流方向への探索によって特定された流域に含まれる場合、前記上流方向への探索によって特定された流域が正しくないと判定することを特徴とする請求項１２に記載の流域抽出装置。
【請求項１４】
前記流域抽出装置は、さらに、
前記第２領域の下流の領域から水が流出しないと判定された場合、前記標高データに基づいて、前記水が流出しないと判定された領域を含む窪地の範囲、及び、前記窪地に流れ込んだ水の流出口を特定し、
前記窪地に流れ込んだ水が前記特定された流出口から流出するように、前記特定された窪地に含まれる各領域の下流方向を特定し、
前記窪地に含まれる各領域の下流方向が特定された後に実行される前記上流方向への探索において、前記第１領域に流れ込む水の流域を探索するために、前記特定された下流方向を使用することを特徴とする請求項１３に記載の流域抽出装置。
【請求項１】
コンピュータを制御する流域抽出プログラムであって、
前記コンピュータは、
前記流域抽出プログラムが格納されるメモリと、前記メモリに格納された前記流域抽出プログラムを実行するプロセッサと、を備え、
地図上の複数の領域の標高を示す標高データを保持し、
前記複数の領域は、第１領域を含み、
前記流域抽出プログラムは、
前記第１領域に流れ込む水の流域を、前記標高データに基づいて上流方向に探索する第１手順と、
前記第１手順によって特定された流域が正しいか否かを判定する第２手順と、を前記プロセッサに実行させ、
前記第２手順において、前記特定された流域が正しくないと判定された場合、前記第１手順を再び前記プロセッサに実行させることを特徴とする流域抽出プログラム。
【請求項２】
前記複数の領域は、前記第１手順によって特定された流域に含まれない第２領域をさらに含み、
前記流域抽出プログラムは、さらに、前記標高データに基づいて、前記第２領域の下流の前記領域を特定する第３手順を前記プロセッサに実行させ、
前記第２手順は、前記第３手順によって前記第２領域の下流の領域として特定された領域が、前記第１手順によって特定された流域に含まれる場合、前記第１手順によって特定された流域が正しくないと判定する手順を含むことを特徴とする請求項１に記載の流域抽出プログラム。
【請求項３】
前記第３手順は、
前記第２領域の下流の領域から水が流出しないと判定された場合、前記標高データに基づいて、前記水が流出しないと判定された領域を含む窪地の範囲、及び、前記窪地に流れ込んだ水の流出口を特定する第４手順と、
前記窪地に流れ込んだ水が前記特定された流出口から流出するように、前記特定された窪地に含まれる各領域の下流方向を特定する第５手順と、を含み、
前記第３手順が実行された後に実行される前記第１手順において、前記第１領域に流れ込む水の流域を探索するために、前記第５手順によって特定された下流方向が使用されることを特徴とする請求項２に記載の流域抽出プログラム。
【請求項４】
前記第２領域は、前記第１手順によって特定された流域に含まれない領域のうち、前記第１手順によって特定された流域に隣接する領域であることを特徴とする請求項３に記載の流域抽出プログラム。
【請求項５】
前記流域抽出プログラムは、前記第１手順の前に、前記第１領域の指定を受ける手順を前記プロセッサに実行させ、
前記第１手順は、
前記第１領域を対象領域として選択する手順と、
前記標高データから算出された、前記対象領域に隣接する領域と、前記対象領域に隣接する領域にさらに隣接する領域との間の勾配に基づいて、前記対象領域に隣接する領域の下流方向を特定する手順と、
前記勾配に基づいて特定された下流方向、又は、前記第５手順によって特定された下流方向に基づいて、前記対象領域に隣接する領域が前記対象領域の上流であるか否かを判定する手順と、
前記対象領域に隣接する領域が前記対象領域の上流であると判定された場合、前記対象領域に隣接する領域を前記流域内の領域として特定する手順と、
前記対象領域に隣接する領域が前記対象領域の上流であると判定された場合、前記対象領域に隣接する領域を新たな前記対象領域として選択する手順と、を含むことを特徴とする請求項３に記載の流域抽出プログラム。
【請求項６】
前記第３手順は、さらに、
前記第２領域を対象領域として選択する手順と、
前記標高データに基づいて、前記対象領域と、前記対象領域に隣接する領域との間の勾配を算出する手順と、
前記勾配に基づいて、前記対象領域に隣接する領域が前記対象領域の下流であるか否かを判定する手順と、
前記対象領域に隣接する領域が前記対象領域の下流であると判定された場合、前記対象領域に隣接する領域を、前記第２領域の下流の領域として特定する手順と、
前記対象領域に隣接する領域が前記対象領域の下流であると判定された場合、前記対象領域に隣接する領域を、新たな前記対象領域として特定する手順と、
前記対象領域に隣接する複数の領域の全ての前記標高が、前記対象領域の前記標高より高い場合、前記対象領域から水が流出しないと判定する手順と、を含むことを特徴とする請求項３に記載の流域抽出プログラム。
【請求項７】
前記第３手順は、さらに、前記対象領域に隣接する領域が前記第１領域の上流であるか否かを判定する手順を含み、
前記対象領域に隣接する領域が前記対象領域の下流であると判定され、かつ、前記対象領域に隣接する領域が前記第１領域の上流でないと判定された場合、前記流域抽出プログラムは、前記第３手順に含まれる手順のうち、前記対象領域に隣接する領域を前記第２領域の下流の領域として特定する手順を前記プロセッサに実行させないことを特徴とする請求項６に記載の流域抽出プログラム。
【請求項８】
前記第３手順は、さらに、前記対象領域に隣接する領域が海である場合、前記対象領域に隣接する領域の標高が所定の値より低い場合、及び、前記対象領域に隣接する領域が前記第１領域の上流でないことを示す情報が入力された場合、の少なくとも一つの場合に、前記対象領域に隣接する領域が前記第１領域の上流でないと判定する手順を含むことを特徴とする請求項７に記載の流域抽出プログラム。
【請求項９】
前記第４手順は、
前記水が流出しないと判定された領域を前記窪地内の領域として特定する手順と、
前記窪地に隣接する領域の一つを対象領域として選択する手順と、
前記対象領域の標高が、前記窪地に隣接する全ての領域の標高の最低値と同一である場合、前記対象領域を、新たな前記窪地内の領域として特定する手順と、
前記窪地外の領域のうち、前記新たな窪地内の領域に隣接する領域の標高が、前記新たな窪地内の領域の標高より低い場合、前記新たな窪地内の領域に隣接する領域を前記窪地に流れ込んだ水の流出口として特定する手順と、を含むことを特徴とする請求項３に記載の流域抽出プログラム。
【請求項１０】
前記コンピュータには、表示装置が接続され、
前記第１手順は、さらに、前記第１手順が実行されていることを示す情報を前記表示装置に表示させる手順を含み、
前記第３手順は、さらに、前記第３手順が実行されていることを示す情報を前記表示装置に表示させる手順を含むことを特徴とする請求項３に記載の流域抽出プログラム。
【請求項１１】
前記流域抽出プログラムは、さらに、前記対象領域が選択された後、前記選択された対象領域を含む複数の領域の標高データを読み込む手順を含むことを特徴とする請求項５、６又は９のいずれか一つに記載の流域抽出プログラム。
【請求項１２】
水の流域を抽出する流域抽出装置であって、
前記流域抽出装置は、
メモリと、前記メモリに格納されたプログラムを実行するプロセッサと、を備え、
地図上の複数の領域の標高を示す標高データを保持し、
前記複数の領域は、第１領域を含み、
前記流域抽出装置は、
前記第１領域に流れ込む水の流域を、前記標高データに基づいて上流方向に探索し、
前記上流方向の探索によって特定された流域が正しいか否かを判定し、
前記特定された流域が正しくないと判定された場合、前記上流方向への探索を再び実行することを特徴とする流域抽出装置。
【請求項１３】
前記複数の領域は、前記上流方向への探索によって特定された流域に含まれない第２領域をさらに含み、
前記流域抽出装置は、さらに、
前記標高データに基づいて、前記第２領域の下流の前記領域を特定し、
特定された、前記第２領域の下流の領域が、前記上流方向への探索によって特定された流域に含まれる場合、前記上流方向への探索によって特定された流域が正しくないと判定することを特徴とする請求項１２に記載の流域抽出装置。
【請求項１４】
前記流域抽出装置は、さらに、
前記第２領域の下流の領域から水が流出しないと判定された場合、前記標高データに基づいて、前記水が流出しないと判定された領域を含む窪地の範囲、及び、前記窪地に流れ込んだ水の流出口を特定し、
前記窪地に流れ込んだ水が前記特定された流出口から流出するように、前記特定された窪地に含まれる各領域の下流方向を特定し、
前記窪地に含まれる各領域の下流方向が特定された後に実行される前記上流方向への探索において、前記第１領域に流れ込む水の流域を探索するために、前記特定された下流方向を使用することを特徴とする請求項１３に記載の流域抽出装置。
【図１】
【図２】
【図５】
【図６】
【図９】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図３】
【図４】
【図７】
【図８】
【図１０】
【図２】
【図５】
【図６】
【図９】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図３】
【図４】
【図７】
【図８】
【図１０】
【公開番号】特開２０１０−２８２３４９（Ｐ２０１０−２８２３４９Ａ）
【公開日】平成２２年１２月１６日（２０１０．１２．１６）
【国際特許分類】
【出願番号】特願２００９−１３４０６７（Ｐ２００９−１３４０６７）
【出願日】平成２１年６月３日（２００９．６．３）
【出願人】（０００２３３０４４）株式会社日立エンジニアリング・アンド・サービス (276)
【公開日】平成２２年１２月１６日（２０１０．１２．１６）
【国際特許分類】
【出願日】平成２１年６月３日（２００９．６．３）
【出願人】（０００２３３０４４）株式会社日立エンジニアリング・アンド・サービス (276)
[ Back to top ]