(57)【特許請求の範囲】
【請求項１】
ホストコンピュータと、端末側コンピュータとが接続された地図データ検索システムであって、
前記ホストコンピュータは、
地図上の各種区分線である境界線を構成する両端の端点を示すノード座標を少なくとも有する境界データを、地図を所定の区画単位毎に分割することで得られるメッシュ域毎に記憶する第１の記憶手段と、
前記メッシュ域の四方の外縁を示す境界線のうちいずれかの境界線の両端のノード座標を少なくとも有するメッシュ境界データを、前記メッシュ域毎に記憶する第２の記憶手段と、
前記端末側コンピュータからの表示要求により、地図データと共に、前記境界データと前記メッシュ境界データを、前記端末側コンピュータに送信する送信手段と、
前記境界データと前記メッシュ境界データを用いて、前記メッシュ域毎に、前記境界データが前記メッシュ境界データと交わる場合、その交点に新たにノードを設け、このノードによって前記境界データと前記メッシュ境界データを分割する分割手段と、
前記境界データを構成するノード、前記メッシュ境界データを構成するノード、及び前記分割手段で新たに設けられたノードの各ノード毎に、接続される境界データ及び／又はメッシュ境界データを対応付ける、当該ノード座標を示す基準ノードと、前記基準ノードに接続する境界データ及び／又はメッシュ境界データの他方のノード座標を示す少なくとも１つの接続先ノードと、当該ノードに接続する境界データ及び／又はメッシュ境界データの数を示す分岐数と、を少なくとも有するノードデータを生成するノードデータ生成手段と、
前記ノードデータを記憶する第３の記憶手段と、
前記ノードデータを用いて、各メッシュ域毎に、任意の境界データを選び、この境界データの一方の端点である基準ノードを基準として、前記基準ノードに接続される前記境界データの位置情報と前記分岐数に基づいて、時計回りの方向、又は反時計回りの方向にある最初の境界データ／メッシュ境界データを、前記基準ノードに戻るまで順次選択し、選択した複数の前記境界データ及び／又は前記メッシュ境界データから生成した小ポリゴンを構成する前記基準ノード及び複数の前記接続先ノードを有する小ポリゴンデータを生成する小ポリゴン生成手段と、
前記小ポリゴンデータを記憶する第４の記憶手段と、
前記小ポリゴンデータと前記メッシュ境界データを用いて、前記端末側コンピュータから指定された生成したいポリゴン内の任意の内点の座標を含む小ポリゴンデータと、当該小ポリゴンデータが有する前記メッシュ境界データを共有する小ポリゴンデータを取り出し、逐次取り出した前記メッシュ境界データを共有する全ての小ポリゴンデータをグループ化することによりポリゴンデータを生成するポリゴン生成手段と、
を具備することを特徴とする地図データ検索システム。
【請求項２】
前記ホストコンピュータは、
地図上に表示する各種情報を示す各種データを記憶する第５の記憶手段と、
前記ポリゴンデータを用いて、当該ポリゴン内の前記各種データを抽出する抽出手段と、
を更に具備することを特徴とする請求項１に記載された地図データ検索システム。
【請求項３】
前記位置情報は、前記基準ノードにおける複数の前記境界データ及び／又は前記メッシュ境界データの基準線からの角度を示す指標であることを特徴とする請求項１に記載された地図データ検索システム。
【請求項４】
前記位置情報は、前記基準ノードにおける複数の前記境界データ及び／又は前記メッシュ境界データを形成するベクトルの角度を示す指標であることを特徴とする請求項１に記載された地図データ検索システム。
【請求項５】
前記基準線は、ＸＹ平面上で前記境界データを考えた場合、Ｘ軸と−４５度の角度をなす直線であることを特徴とする請求項３に記載された地図データ検索システム。
【請求項６】
前記境界線は、行政区分線、管理界、営業範囲の内のいずれかであることを特徴とする請求項１に記載された地図データ検索システム。
【請求項７】
前記各種データは、道路、ガス管、水道管、下水管、電線、通信ライン等のいずれかを示すラインデータであり、
前記抽出手段はラインデータの長さを求めることを特徴とする請求項２に記載された地図データ検索システム。
【請求項８】
前記各種データは、家屋又は一人暮らしの住宅、マンホール、弁、電柱等のいずれかを示すシンボルデータであり、
前記抽出手段はシンボルデータの個数を求めることを特徴とする請求項２に記載された地図データ検索システム。
【請求項９】
メッシュ単位で保持された境界データを縮小して、複数メッシュに渡って表示させることを特徴とする請求項１に記載された地図データ検索システム。
【請求項１０】
縮小された前記境界データを予め保持する手段を有することを特徴とする請求項９に記載された地図データ検索システム。
【請求項１１】
ポリゴンを一部修正する場合、前記境界データを修正することを特徴とする請求項１に記載された地図データ検索システム。
【請求項１２】
コンピュータを請求項１から請求項１１いずれかに記載の地図データ検索システムとして機能させるプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マッピングシステム等に係り、地図データ検索システム等に関するものである。
【０００２】
【従来の技術】
従来、マッピングシステム等ではホストコンピュータが地図データベースを備え、端末側のコンピュータから地図データベース内の地図を呼び出すと、端末側のコンピュータ画面に街区や水道管等が表示される。
図３１は従来のマッピングシステムでコンピュータ画面に表示された境界データ４１を示す図である。境界データ４１とは通常の境界データであり、例えば、行政区画、上下水道管理界、ガス配管管理界、営業範囲などである。図３１に示されるように境界データ４１が広範囲に渡る場合、地図を構成する複数のメッシュ３１に渡り表示される。
【０００３】
【発明が解決しようとする課題】
しかしながら、マッピングシステム等において、ある領域内の設備を領域ごとに調査するといった要求がある。例えば、図３１に示す境界データ４１で閉じられたポリゴン２１内部にはどれだけの住宅が存在するのかを調べたいという要求がある場合、ポリゴン２１は複数のメッシュに渡るため検索が繁雑である。
【０００４】
本発明は、このような問題に鑑みてなされたもので、その目的とするところは、複数のメッシュに渡る行政区画等の境界データからポリゴンを作成し、更に、作成されたポリゴン内にどのような施設が存在するかを検索し得る地図検索システム等を提供することにある。
【０００５】
【課題を解決するための手段】
前述した目的を達成するために、第１の発明は、ホストコンピュータと、端末側コンピュータとが接続された地図データ検索システムであって、前記ホストコンピュータは、地図上の各種区分線である境界線を構成する両端の端点を示すノード座標を少なくとも有する境界データを、地図を所定の区画単位毎に分割することで得られるメッシュ域毎に記憶する第１の記憶手段と、前記メッシュ域の四方の外縁を示す境界線のうちいずれかの境界線の両端のノード座標を少なくとも有するメッシュ境界データを、前記メッシュ域毎に記憶する第２の記憶手段と、前記端末側コンピュータからの表示要求により、地図データと共に、前記境界データと前記メッシュ境界データを、前記端末側コンピュータに提供する提供手段と、前記境界データと前記メッシュ境界データを用いて、前記メッシュ域毎に、前記境界データが前記メッシュ境界データと交わる場合、その交点に新たにノードを設け、このノードによって前記境界データと前記メッシュ境界データを分割する分割手段と、前記境界データを構成するノード、前記メッシュ境界データを構成するノード、及び前記分割手段で新たに設けられたノードの各ノード毎に、接続される境界データ及び／又はメッシュ境界データを対応付ける、当該ノード座標を示す基準ノードと、前記基準ノードに接続する境界データ及び／又はメッシュ境界データの他方のノード座標を示す少なくとも１つの接続先ノードと、当該ノードに接続する境界データ及び／又はメッシュ境界データの数を示す分岐数と、を少なくとも有するノードデータを生成するノードデータ生成手段と、前記ノードデータを記憶する第３の記憶手段と、前記ノードデータを用いて、各メッシュ域毎に、任意の境界データを選び、この境界データの一方の端点である基準ノードを基準として、前記基準ノードに接続される前記境界データの位置情報と前記分岐数に基づいて、時計回りの方向、又は反時計回りの方向にある最初の境界データ／メッシュ境界データを、前記基準ノードに戻るまで順次選択し、選択した複数の前記境界データ及び／又は前記メッシュ境界データから生成した小ポリゴンを構成する前記基準ノード及び複数の前記接続先ノードを有する小ポリゴンデータを生成する小ポリゴン生成手段と、前記小ポリゴンデータを記憶する第４の記憶手段と、前記小ポリゴンデータと前記メッシュ境界データを用いて、前記端末側コンピュータから指定された生成したいポリゴン内の任意の内点の座標を含む小ポリゴンデータと、当該小ポリゴンデータが有する前記メッシュ境界データを共有する小ポリゴンデータを取り出し、逐次取り出した前記メッシュ境界データを共有する全ての小ポリゴンデータをグループ化することによりポリゴンデータを生成するポリゴン生成手段と、を具備することを特徴とする地図データ検索システムである。
【０００６】
第２の発明は、コンピュータを第１の発明の地図検索システムとして機能させるプログラムを記録した記録媒体である。
【０００８】
【発明の実施の形態】
以下、図面に基づいて本発明の実施の形態を詳細に説明する。図１は、本実施の形態に係る地図データ検索システム１の概略構成を示す図である。
【０００９】
図１において、地図データ検索システム１は、ホストコンピュータ３、地図データベース７、端末側コンピュータ５及びＣＤ−ＲＯＭ９からなる。
地図データベース７はホストコンピュータ３に接続されており、地図データ１３、境界データ４１、メッシュ境界データ５１等を保持する。例えば、地図データ１３は道路等であり、境界データ４１は通常の境界データであり、行政区画、下水道管理界、上水道管理界、営業範囲等のデータである。メッシュ境界データ５１は地図データ１３を構成するメッシュ３１の外縁である。
【００１０】
端末側コンピュータ５はホストコンピュータ３に接続されており、地図データ１３、境界データ４１及びメッシュ境界データ５１は端末側コンピュータ５に読み出され、データ処理が行われる。
ＣＤ−ＲＯＭ９は、地図データ検索システム１のプログラムが記録されており、コンピュータで読取り可能である。
【００１１】
次に、地図データ検索システム１の処理手順の概要を説明する。図２は地図検索システム１による処理手順のフローチャートを示す。尚、ホストコンピュータ３は、制御部と記憶部とを備える。ホストコンピュータ３の制御部が、以降の図２に示すポリゴン作成及び地図データ検索処理を行う。
地図データベース７から地図データ１３、境界データ４１及びメッシュ境界データ５１を読み出し、表示する（ステップ２０１）。
【００１２】
次に、境界データ４１がメッシュ境界データ５１と交わる場合、その交点にノードを設け、そのノードによって境界データ４１及びメッシュ境界データ５１を分割し（ステップ２０２）、各ノード６１においてノードデータ７１を作成する（ステップ２０３）。ノードデータ７１を基にして、各メッシュ３１毎に小ポリゴン３３を生成する（ステップ２０４）。
【００１３】
次にメッシュ境界データ５１を共有する小ポリゴン３３をグループ化して、ポリゴンを生成し（ステップ２０５）、各ポリゴン内における各種データ、例えば家屋や公園等を抽出し、表示する（ステップ２０６）。
【００１４】
以下、図２の各ステップについて説明する。
ステップ２０１
図３は行政区画を示す境界データ４１を示す図である。図３に示すように、境界データ４１で囲まれたポリゴン２１は１２枚のメッシュ３１に渡る。メッシュ境界データ５１はメッシュ３１の外縁であり、点線で示される。尚、小ポリゴン３３は１つのメッシュにおいて境界データ４１とメッシュ境界データ５１に囲まれた領域である。
【００１５】
図４は、境界データ４１を示す図である。図４に示されるように、境界データ４１はその両端にノード６１ａ、６１ｂを有する。
図５は境界データ４１のフォーマットを示す図である。図５に示されるように、境界データ４１はレコード番号４３、名称４５、境界を構成する座標データ数４７、左端ノード座標４８−１、右端ノード座標４８−２及び線種４９から構成される。
【００１６】
レコード番号４３は地図データ検索システム１内で保持された境界データ４１に付けられた通し番号である。名称４５は、境界データ４１の名称であり、例えば行政区画の場合、「○○町３丁目」といったものである。座標データ数４７は境界データ４１を構成するノードの数であり、図４に示す境界データ４１の場合は「２」となる。更に、左端ノード座標４８−１は図４に示すノード６１ａの座標であり、右端ノード座標４８−２は図４に示すノード６１ｂの座標である。線種４９は通常の境界データの場合「１」とし、メッシュ境界データ５１と区別するために設けられる。
【００１７】
図６はメッシュ３１のメッシュ境界データ５１を示す図である。メッシュ境界データ５１はメッシュ３１の外縁を構成する４つの線分のうちの１つを示し、その両端にはノード６１ｃとノード６１ｄを有する。
図７はメッシュ境界データ５１のフォーマットを示す図である。図７に示されるように、メッシュ境界データ５１はレコード番号５３、名称５５、境界を構成する座標データ数５７、左端ノード座標５８−１、右端ノード座標５８−２及び線種５９から構成される。
【００１８】
レコード番号５３は地図データ検索システム１内で保持されたメッシュ境界データ５１に付けられた通し番号である。名称５５は、境界データ５１の名称であり、例えば「メッシュ３１−１の境界１」といったものである。座標データ数５７は境界データ５１を構成するノードの数である。更に、左端ノード座標５８−１は図６に示すノード６１ｃの座標であり、右端ノード座標５８−２は図６に示すノード６１ｄの座標である。線種５９はメッシュ境界データ５１の場合「２」として境界データ４１とは区別する。
【００１９】
図５と図７に示されるように、地図データ検索システム１に保持される境界データ４１とメッシュ境界データ５１のフォーマットは同じであり、線種の違いで区別される。
【００２０】
ステップ２０２
図８は、図３に示すメッシュ３１−１とメッシュ３１−２に渡る境界データ４１−１を示す図である。図８に示されるように、境界データ４１−１の１つのノード６１−１はメッシュ３１−１にあり、他方のノード６１−３はメッシュ３１−２にあり、境界データ４１−１はメッシュ境界データ５１−１を横切る。
【００２１】
図９は、境界データ４１−１とメッシュ境界データ５１−１の分割方法を示す図である。２つのメッシュに渡る境界データ４１−１は、境界データ４１−１とメッシュ境界データ５１−１の交点に新たに設けたノード６１−２によって、境界データ４１−１−１と境界データ４１−１−２に分割される。同様に、メッシュ境界データ５１−１も、ノード６１−２によってメッシュ境界データ５１−１−１とメッシュ境界データ５１−１−２に分割される。
【００２２】
ステップ２０３
図１０は、ノード６１ｅとノード６１ｅに接続する接続先ノード６１ｆ、６１ｇ、６１ｈを示す図である。図１１は基準ノード６１ｅのノードデータ７１のフォーマットを示す図である。ノードデータ７１は、レコード番号７３、分岐数７５、基準ノード６１ｅに関するデータ７７、基準ノード６１ｅに接続する各接続先ノードに関するデータ７９、８１、８３からなる。
【００２３】
レコード番号７３は地図データ検索システム１内で保持されるノードデータ７１に付けられた通し番号である。分岐数７５は基準ノード６１ｅに接続する境界データの数であり、図１０に示す基準ノード６１ｅでは「３」となる。基準ノード６１ｅに関するデータ７７は基準ノード６１ｅの座標（ｘ０，ｙ０）を示す。
【００２４】
接続先ノードに関するデータ７９は、接続先ノード６１ｆに関するものであり、指標ｍ、ノード６１ｆの座標（ｘ１，ｙ１）、角度指標ＮＩ１、フラグＦ１を有する。
指標ｍ＝１は、複数の接続先ノードのうち、角度指標ＮＩの小さい順番を示す指標である。角度指標ＮＩについては後述する。
【００２５】
フラグＦ１に関する説明は後で行う。
接続先ノードに関するデータ８１、８３は、接続先ノードに関するデータ７９と同様の構成となる。
【００２６】
次に、角度指標ＮＩについて説明する。図１２は角度指標ＮＩを求める処理のフローチャートである。図１２に示されるように、基準となる任意のノードの座標（ｘ０，ｙ０）を読み込み（ステップ８０１）、接続先ノードの座標（ｘｉ，ｙｉ）を読み込む（ステップ８０２）。ｘｉ−ｘ０をｘに代入し、ｙｉ−ｙ０をｙに代入し（ステップ８０３）、ｘとｙの絶対値を比較し（ステップ８０４）、更に、ｘ及びｙを０と比較する（ステップ８０６、ステップ８０５）。
【００２７】
このとき、角度指標ＮＩｉは次のように計算される。ここで、ｘの絶対値を［ｘ］、ｙの絶対値を［ｙ］と示す。
［ｘ］＜［ｙ］かつｙ＜０の場合、ＮＩｉ＝７００＋（ｘ／ｙ）×１００（ステップ８０７）
［ｘ］＜［ｙ］かつｙ＞０の場合、ＮＩｉ＝３００−（ｘ／ｙ）×１００（ステップ８０８）。
［ｘ］≧［ｙ］かつｘ＞０の場合、ＮＩｉ＝１００＋（ｘ／ｙ）×１００（ステップ８０９）
［ｘ］≧［ｙ］かつｘ＜０の場合、ＮＩｉ＝５００−（ｘ／ｙ）×１００（ステップ８１０）
【００２８】
図１３は、基準ノード６１ｅに対する接続先ノード６１ｉの位置ベクトルと角度指標ＮＩを示す図である。
角度指標ＮＩは、図１３の水平線８５に対し−π／４の角度をなす基準線８７を基準とし、基準線８７においてＮＩ＝０とする。図１３において、基準ノード６１ｅに対する接続先ノード６１ｉの位置ベクトルが水平線８５となす反時計回りの角度をθｉとすると、
θｉ＝０のとき、ＮＩ＝１００
θｉ＝π／４のとき、ＮＩ＝２００
θｉ＝π／２のとき、ＮＩ＝３００
θｉ＝３π／４のとき、ＮＩ＝４００
θｉ＝πのとき、ＮＩ＝５００
θｉ＝５π／４のとき、ＮＩ＝６００
θｉ＝３π／２のとき、ＮＩ＝７００
θｉ＝７π／４のとき、ＮＩ＝８００（ＮＩ＝０の線と一致）
となる。
【００２９】
図１４は、図１３における角度θｉと角度指標ＮＩとの関係を示す図である。角度指標は単純な増加関数の傾向があり、角度θｉに対して角度指標ＮＩが一位的に決められるのが特徴である。
図１１に示すノードデータ７１において、角度指標ＮＩ１、ＮＩ２、ＮＩ３は、図１２のフローチャートにしたがって計算される。
【００３０】
図１０に示されるように、角度指標は基準線８７と境界データとのなす角度が小さいほど小さくなる。図１１に示すノードデータ７１では角度指標が小さい順に接続先ノードが並べられており、小さい順に指標ｍの値を「１」、「２」、…とする。この指標ｍは境界データを選択して小ポリゴンを抽出する際に使用される。
【００３１】
ノードデータ７１は、境界データ４１やメッシュ境界データ５１を構成するノード、及び図９に示されるノード６１−２のような新たに設けられたノードに対して計算され、ホストコンピュータ３の記憶部に保管される。また、予め全てのノードについて計算し、図１の地図データベース７に保持することも可能である。
【００３２】
図１５はメッシュ３１−１におけるノード６１を示す図である。図１６はノード６１−１におけるノードデータ７１−１を示す図である。図１５及び図１６に示されるように、ノード６１−１における分岐数はＮ＝３であり、角度指標は図１２に示す処理によって計算され、接続先ノード６１−１３に対する指標はｍ＝１、接続先ノード６１−４に対する指標はｍ＝２、接続先ノード６１−２対する指標はｍ＝３である。
【００３３】
図１５及び図１６に示すように、ノード６１−１と接続先ノード６１−１３は境界データ４１−５によって接続される。このように通常の境界データ４１を介して接続される場合、ノードデータ７１−１におけるフラグを「１」とする。従って、接続先ノード６１−１３に対するフラグは「１」となる。また、接続先ノード６１−４、６１−２も境界データ４１−４、４１−１−１によって接続されることから、それぞれのノードに対するフラグは「１」となる。
【００３４】
図１７はノード６１−２におけるノードデータ７１−２を示す図である。図１５及び図１６に示されるように、ノード６１−２における分岐数はＮ＝３であり、接続先ノード６１−１８に対する指標はｍ＝１、接続先ノード６１−１に対する指標はｍ＝２、接続先ノード６１−１７対する指標はｍ＝３である。
【００３５】
図１５に示されるように、ノード６１−２と接続先ノード６１−１８はメッシュ境界データ５１−１−１によって接続され、更にメッシュ境界データ５１−１−１はノード６１−２を基準にするとその左側にメッシュが存在する。即ち、時計回りに小ポリゴンを生成する場合、選択対象となる。このような場合、図１７に示される接続先ノード６１−１８に対するフラグは「３」とする。
【００３６】
また、図１５に示されるように、ノード６１−２と接続先ノード６１−１７はメッシュ境界データ５１−１−２によって接続され、更にメッシュ境界データ５１−１−２はノード６１−２を基準とするとその右側にメッシュが存在する。即ち、時計回りに小ポリゴンを生成する場合、非選択対象となる。このような場合、図１７に示される接続先ノード６１−１７に対するフラグは「２」とする。
【００３７】
図１５に示されるように、ノード６１−２と接続先ノード６１−１は境界データ４１−１−１によって接続されている。境界データ４１−１−１の左右にはメッシュが存在し、境界データ４１−１−１はノード６１−２とノード６１−１のノードデータで定義され、小ポリゴンを生成する際の選択対象となるため、図１７に示す接続先ノード６１−１に対するフラグは「１」とする。
【００３８】
図１８はノード６１−１７におけるノードデータ７１−１７を示す図である。図１５及び図１８に示されるように、ノード６１−１７における分岐数はＮ＝２であり、接続先ノード６１−２に対する指標はｍ＝１、接続先ノード６１−１５に対する指標はｍ＝２である。
【００３９】
図１５に示されるように、ノード６１−１７と接続先ノード６１−２はメッシュ境界データ５１−１−２で接続され、メッシュ境界データ５１−１−２の左側にメッシュが存在することから、図１８に示す接続先ノード６１−２に対するフラグは「３」となる。一方、ノード６１−１７と接続先ノード６１−１５はメッシュ境界データ５１−２で接続され、メッシュ境界データ５１−２の右側にメッシュが存在することから、図１８に示す接続先ノード６１−１５に対するフラグは「２」となる。
【００４０】
ステップ２０４
次に、境界データとメッシュ境界データを選択して小ポリゴンを生成する処理手順について説明する。図１９は１つのメッシュ内での小ポリゴン抽出作業のフローチャートを示す図である。
任意のノード（座標（ｘ０，ｙ０））とその接続先ノード（座標（ｘｉ，ｙｉ））を取り出す（ステップ１１０１）。（ｘ０，ｙ０）をポリゴンの第１の頂点となる座標（Ｘ１，Ｙ１）と、（ｘ１，ｙ１）をポリゴンの第２の頂点となる座標（Ｘ２，Ｙ２）とする（ステップ１１０２）。そして、ｊに２を代入する（ステップ１１０３）。
【００４１】
次に座標（Ｘｊ，Ｙｊ）のノードを取り出す（ステップ１１０４）。取り出したノードの座標（Ｘｊ，Ｙｊ）と最初に取り出したノードの座標（ｘ０，ｙ０）を比較して（ステップ１１０５）、等しければ、最初の座標に戻ってポリゴン抽出が終了したとみなし、当該ポリゴンの座標列を保管する（ステップ１１０７）。
【００４２】
一方、取り出したノードの座標（Ｘｊ，Ｙｊ）と最初に取り出したノードの座標（ｘ０，ｙ０）を比較して（ステップ１１０５）、等しくなければ、取り出した当該ノード（座標（Ｘｊ，Ｙｊ））に対する接続先ノードの座標が（Ｘｊ−１，Ｙｊ−１）である指標ｍを認識する（ステップ１１０６）。
【００４３】
次に、認識した指標ｍと分岐数Ｎとを比較する（ステップ１１０８）。ここで、指標ｍと分岐数Ｎとを比較して指標ｍが小さい場合、ｍ＋１をＫとし（ステップ１１０９）、ｍとＮが等しい場合Ｋ＝１として（ステップ１１１０）、ｍ＝Ｋとなる接続先ノード（座標（ｘｍ，ｙｍ））を当該ノードのノードデータの中から取り出す（ステップ１１１１）。そして、（ｘｍ，ｙｍ）を（Ｘｊ＋１，Ｙｊ＋１）に代入する（ステップ１１１２）。
【００４４】
次に、ｊをｊ＋１とし（ステップ１１１３）、ステップ１１０４に戻り、以上の処理を繰り返す。
ここで、図１９に示すポリゴン抽出処理のフローチャートに従って図２０に示す小ポリゴン３３−１の抽出作業を説明する。
まず、任意のノードとしてノード６１−４（座標（Ｘ１，Ｙ１））を選択し、その接続先ノードとしてノード６１−１（座標（Ｘ２，Ｙ２））を取り出す（ステップ１１０１）。
【００４５】
図１９に示すステップ１１０３においてｊ＝２であるから、ステップ１１０４では座標（Ｘ２，Ｙ２）であるノード６１−１を取り出し、ｘ０≠Ｘｊ，ｙ０≠Ｙｊであるので（ステップ１１０５）、接続先ノードの座標が（Ｘｊ−１，Ｙｊ−１）であるノード６１−４（座標（Ｘ１，Ｙ１））の指標ｍ２＝２を認識する（ステップ１１０６）。
【００４６】
この場合、ｍとＮが等しくない（ステップ１１０９）のでＫ＝ｍ２＋１＝３となり（ステップ１１０９）、ｍ２＝Ｋ＝３となる接続先ノードであるノード６１−２の座標を取り出す（ステップ１１１１）。つまり、図１６及び図２０において接続先ノード６１−２の座標をポリゴンの第３番目の頂点座標（Ｘ３，Ｙ３）として認識する。
【００４７】
次に、図１９に示すステップ１１１３においてｊ＝３となるから、ステップ１１０４では（Ｘ３，Ｙ３）を取り出し、その相手接続の座標が（Ｘ２，Ｙ２）であるようなノード６１−１を取り出し（ステップ１１０４）、指標ｍ３＝２を認識する（ステップ１１０６）。
【００４８】
この場合、ｍとＮが等しくない（ステップ１１０９）のでＫ＝ｍ３＋１＝３となり（ステップ１１０９）、ｍ３＝Ｋ＝３となる接続先ノードであるノード６１−１７の座標を取り出す（ステップ１１１１）。つまり、図１７及び図２０において接続先ノード６１−１７の座標をポリゴンの第４番目の頂点座標（Ｘ４，Ｙ４）として認識する。
【００４９】
次に、図１９に示すステップ１１１３においてｊ＝４となるから、ステップ１１０４では（Ｘ４，Ｙ４）を取り出し、その相手接続の座標が（Ｘ３，Ｙ３）であるようなノード６１−２を取り出し（ステップ１１０４）、指標ｍ４＝１を認識する（ステップ１１０６）。
【００５０】
この場合、ｍとＮが等しくない（ステップ１１０９）のでＫ＝ｍ４＋１＝２となり（ステップ１１０９）、ｍ４＝Ｋ＝２となる接続先ノードであるノード６１−１５の座標を取り出す（ステップ１１１１）。つまり、図１８及び図２０において接続先ノード６１−１５の座標をポリゴンの第５番目の頂点座標（Ｘ５，Ｙ５）として認識する。
【００５１】
次に、図１９に示すステップ１１１３においてｊ＝５となるから、ステップ１１０４では（Ｘ５，Ｙ５）を取り出し、その相手接続の座標が（Ｘ４，Ｙ４）であるようなノード６１−１７を取り出し（ステップ１１０４）、指標ｍ５＝２を認識する（ステップ１１０６）。
【００５２】
この場合、ｍとＮが等しいので（ステップ１１０８）、Ｋ＝１となり（ステップ１１１０）、ｍ５＝Ｋ＝１となる接続先ノードであるノード６１−６の座標を取り出す（ステップ１１１１）。つまり、接続先ノード６１−６の座標をポリゴン１２０１の第６番目の頂点座標（Ｘ６，Ｙ６）として認識する。
【００５３】
以下同様の処理を行い、ノード６１−４を認識したときに、図１９に示すステップ１１０５にて最初のノードに戻ったことが認識され、小ポリゴン３３−１の抽出の作業は終了する。
【００５４】
以上の処理を要約すると、図２０においてまず境界データ４１−４を選び、次に境界データ４１−１の左端のノード６１−１において、境界データ４１−１を基準として反時計回りで最初に到達する境界データ４１−１−１を選択する。そしてこの境界データ４１−１−１の左端のノード６１−２において、境界データ４１−１−１を基準として反時計回りで最初に到達するメッシュ境界データ５１−１−２を選択する。
以下ノード６１−４に至るまで同様の処理を繰り返す。
【００５５】
尚、前述した処理は図２０に示すように、時計回りで小ポリゴン３３−１を生成したが、反時計回りでポリゴンを生成してもよい。この場合、例えば境界データ４１−４を選択し、その右端のノード６１−４において、境界データ４１−４を基準として時計回りで最初に到達する境界データ４１−３を選択し、以下同様の処理を繰り返す。
【００５６】
尚、前述した実施の形態では角度指標ＮＩを用いてこのような処理を行ったが、各ノードにおいて境界データのなす角度をベクトルの内積を利用して求め、その角度を基準にして小ポリゴンを生成するようにしてもよい。
また、各ノードのノードデータ７１を全て計算しておくのではなく、小ポリゴンを抽出する処理においてノードを認識する際にノードデータを計算してもよい。
【００５７】
図２１は、小ポリゴンデータ１５０１のフォーマットを示す図である。以上のような抽出処理によって生成された小ポリゴンは、小ポリゴンデータ１５０１として、地図データ検索システム１のホストコンピュータ３の記憶部に保管される。小ポリゴンデータ１５０１は小ポリゴンレコード番号１５０３、名称１５０５、座標数１５０７、小ポリゴン構成点座標列１５０９からなる。小ポリゴンレコード番号１５０３は地図データ検索システム１で保持される小ポリゴンに付けられる通し番号である。名称１５０５は小ポリゴンの名称である。
【００５８】
座標数１５０７は小ポリゴンを構成する頂点の数であり、図２０に示す小ポリゴン３３−１では「７」となる。小ポリゴン構成点座標列１５０９は小ポリゴンの頂点の座標であり、即ち、図１９に示すポリゴン抽出処理手順に従って求められた座標（Ｘｊ，Ｙｊ）群である。
【００５９】
ステップ２０５
次に、各小ポリゴン３３からポリゴン２１−１を生成する方法について説明する。
図２２はポリゴン２１と小ポリゴン３３を示す図である。図１９の小ポリゴン抽出処理に従って、メッシュ毎に小ポリゴンを生成する。図２２に示されるように、ポリゴン２１−１は小ポリゴン３３−１、３３−５、３３−８、３３−１０、３３−１３、３３−１１、３３−１５、３３−１８、３３−１９、３３−２４、３３−２５からなる。また、ポリゴン２１−２は小ポリゴン３３−７、３３−９、３３−２から、ポリゴン２１−３は小ポリゴン３３−１６、３３−１７、３３−２０、３３−２２、３３−２３、３３−２４から、ポリゴン２１−４は小ポリゴン３３−４、３３−６、３３−１２、３３−１４、３３−２１からなる。
【００６０】
図２３に示すように、生成したいポリゴン２１−１の境界内部に任意の境界データ内点９９１を設ける。図２４は、境界データ内点９９１を含む小ポリゴン３３−１１に隣接する小ポリゴンを示す図である。小ポリゴン３３−１１は、メッシュ境界データ５１−１１、５１−１２、５１−１３、５１−１４を有する。地図データ検索システム１では、第１段階として、境界データ内点９９１を含む小ポリゴン３３−１１とメッシュ境界データ５１−１１、５１−１２、５１−１３、５１−１４を共有する、ポリゴン２１−１内の小ポリゴン３３−１、３３−８、３３−１３、３３−１８、３３−１９を取り出す。
【００６１】
図２５は第２段階で取り出す小ポリゴンを示す図である。図２５に示されるように、地図データ検索システム１では、第１段階で取り出された小ポリゴン３３−１、３３−８、３３−１３、３３−１８、３３−１９とそれらの有するメッシュ境界データ５１−１５、５１−１６、５１−１７、５１−１８、５１−１９、５１−２０、５１−２１、５１−２２を共有する、小ポリゴン３３−５、３３−１０、３３−１５、３３−１９、３３−２４、３３−２５を取り出す。
以上のような方法で、ポリゴン２１−１を生成する。
【００６２】
ステップ２０６
次に、ポリゴン２１内部の各種データの検索方法について説明する。検索の対象となるデータには、道路、ガス配管、上下水道管、電線、通信ライン等に相当するラインデータや住宅、一人暮らしの老人宅、マンホール、弁、電柱等に相当するシンボルデータ等がある。
図２６はポリゴン内のラインデータの検索処理のフローチャートを示す。
検索するラインデータを指定し（ステップ２６０１）、検索するポリゴンを指定する（ステップ２６０２）。指定したポリゴンを含むすべてのメッシュを読み出す（ステップ２６０３）。
【００６３】
次に、読み出したメッシュの内、最初のメッシュを取り出す（ステップ２６０４）。このメッシュ内のポリゴンに含まれる全てのラインデータを抽出し、表示色を変える（ステップ２６０５）。次に、抽出したラインデータの長さを累積し（ステップ２６０６）、指定したポリゴンを含むメッシュがあるかどうかを判定し（ステップ２６０７）、ポリゴン内にまだ取り出していないメッシュがある場合、次のメッシュを取り出す（ステップ２６０７）。以上の処理をステップ２６０３で取り出したメッシュ全てに行い、処理を終了する。
【００６４】
図２７はポリゴン２１−５とラインデータを示す図である。図２６に示すフローチャートに従って、ポリゴン２１−５内のラインデータ３０１を検索する。まず、検索するラインデータ３０１を指定し（ステップ２６０１）、ポリゴン２１−５を指定する（ステップ２６０２）。指定したポリゴン２１−５を含むメッシュ３１−３、３１−４を読み出し（ステップ２６０３）、メッシュ３１−３を取り出す（ステップ２６０４）。
【００６５】
次に、メッシュ３１−３内の小ポリゴン３３−１０１に含まれるラインデータを抽出する。この場合、図２７に示されるようにラインデータ３０１−２が境界データ３１−１０１と交わるため、その交点３３３−１を求め、交点３３３−１からのラインデータ３０１−２、３０１−３を抽出し、表示色を変え（ステップ２６０４）、その長さを累積する（ステップ２６０６）。
【００６６】
次に、メッシュ３１−４を取り出し（ステップ２６０８）、小ポリゴン３３−１０２に含まれるラインデータを抽出する。図２７に示されるように、ラインデータ３０１−６が境界データ３１−１０２と交わるため、その交点３３３−２を求め、交点３３３−２からのラインデータ３０１−６、３０１−５、３０１−４を抽出し、表示色を変え（ステップ２６０４）、メッシュ３１−３で抽出したラインデータの長さに累積する（ステップ２６０６）。このようにして、ポリゴン２１−５内のラインデータが検索される。
【００６７】
図２８はポリゴン内のシンボルデータの検索処理のフローチャートを示す。
検索するシンボルデータを指定し（ステップ２７０１）、検索するポリゴンを指定する（ステップ２７０２）。指定したポリゴンを含むすべてのメッシュを読み出す（ステップ２７０３）。
【００６８】
次に、読み出したメッシュの内、最初のメッシュを取り出す（ステップ２７０４）。このメッシュ内のポリゴンに含まれる全てのシンボルデータを抽出し、表示色を変える（ステップ２７０５）。抽出したシンボルデータの個数を累積する（ステップ２７０６）。指定したポリゴンを含むメッシュがあるかどうかを判定し（ステップ２７０７）、ポリゴン内にまだ取り出していないメッシュがある場合、次のメッシュを取り出す（ステップ２７０８）。以上の処理をステップ２７０３で取り出したメッシュ全てに行い、処理を終了する。
【００６９】
図２８に示すステップ２７０５において、シンボルデータがポリゴンの内部に含まれるかどうかを判断する方法について説明する。
図２９は点とポリゴンの包含関係を示す図である。ポリゴン１００３内に含まれる点１００５から下方に伸ばした鉛直線１００９とポリゴン１００３の境界線との交点の数は「３」、即ち奇数である。一方、ポリゴン１００３外の点１００７から下方に伸ばした鉛直線１０１１とポリゴン１００３の境界線との交点の数は「２」、即ち偶数である。
【００７０】
このように、ある点を通る鉛直線を引いて、ポリゴンとの交点数を算出し、奇数であればその点がポリゴン内に含まれ、偶数であればその点はポリゴン内に含まれないことを利用して、その点がポリゴン内に存在するか否かを判定する。
【００７１】
このような方法は「鉛直線算法」といわれるもので、点とポリゴンの包含関係を判定する方法として、「計算幾何学と地理情報処理、（昭和６１年、共立出版会社発行）」に開示されている。
図２９に示される点をシンボルデータとすれば、「鉛直線算法」を用いてシンボルデータとポリゴンの包含関係が判る。
【００７２】
図３０はポリゴン２１−５とシンボルデータ４０１を示す図である。図２６に示すフローチャートに従って、ポリゴン２１−５内のシンボルデータ４０１を検索する。検索するシンボルデータ４０１を指定し（ステップ２７０１）、検索するポリゴン２１−５を指定する（ステップ２７０２）。指定したポリゴン２１−５を含むメッシュ３１−３、３１−４を読み出す（ステップ２７０３）。
【００７３】
次に、メッシュ３１−３を取り出し（ステップ２７０４）、メッシュ３１−３内の小ポリゴン３３−１０１に含まれるシンボルデータ４０１を抽出し、表示色を変え（ステップ２７０５）、累積する（ステップ２７０６）。次に、メッシュ３１−４を取り出し（ステップ２７０８）、メッシュ３１−４内の小ポリゴン３３−１０２に含まれるシンボルデータ４０１を抽出し、表示色を変え（ステップ２７０５）、メッシュ３１−４のデータに累積する（ステップ２７０６）。このようにして、ポリゴン２１−５内のシンボルデータ４０１の個数を算出する。
【００７４】
このように本発明の実施の形態を用いれば、広範囲の特定の領域における配管、住宅等のデータを検索、表示することが可能となり、配管の長さや住宅の個数等容易に算出することができる。これにより、各領域におけるデータの検索が容易にでき、領域毎のデータの比較等も効率良く行える。
又、領域の境界を修正する際も、境界データのみを修正するだけでよく、システムの保守管理が容易となる。
【００７５】
本発明の実施の形態では境界データからノードデータを計算したが、ノードデータを予め計算しておき地図データベースに保持しておいてもよい。また、小ポリゴンの生成処理において、ノードを選択する度に計算してもよい。
更に、ノードデータにおいて角度指標を保管するようにしたが、角度指標の小さい順に接続先ノードを並べておけば、角度指標を保管する必要はない。
また、本発明における境界データとしては、行政区画、上水道設備管理界、下水道設備管理界、ガス設備管理界、電気設備管理界等様々なものが含まれる。
【００７６】
尚、図２のステップ２０１の処理で、境界データ４１等を縮小して表示させてもよい。この場合、地図データベース７に境界データ４１を縮小させたものを予め作成しておいてもよい。
このようにすると、多メッシュに渡る境界データ４１を画面上に一度に表示できる。
【００７７】
【発明の効果】
以上、詳細に説明したように本発明によれば、複数のメッシュに渡る行政区画等の境界データからポリゴンを作成し、更に作成されたポリゴンの中にどのような施設が存在するかを検索し得る地図データ検索システム、地図データ検索方法、記録媒体を提供することができる。
【図面の簡単な説明】
【図１】  本発明の１実施の形態に係る地図データ検索システム１を示す図
【図２】  地図データ検索システム１による処理手順を示すフローチャート
【図３】  行政区画を示す境界データ４１を示す図
【図４】  境界データ４１を示す図
【図５】  境界データ４１のフォーマットを示す図
【図６】  メッシュ境界データ５１を示す図
【図７】  メッシュ境界データ５１のフォーマットを示す図
【図８】  メッシュ３１−１、３１−２に渡る境界データ４１−１を示す図
【図９】  境界データ４１−１と境界データ５１−１の分割方法を示す図
【図１０】  基準ノード６１ｅとその接続先ノードを示す図
【図１１】  ノードデータ７１のフォーマットを示す図
【図１２】  角度指標を求めるフローチャートを示す図
【図１３】  接続先ノードの位置ベクトルと角度指標の関係を示す図
【図１４】  角度と角度指標の関係を示す図
【図１５】  メッシュ３１−１にノードを示す図
【図１６】  ノード６１−１におけるノードデータ７１−１を示す図
【図１７】  ノード６１−２におけるノードデータ７１−２を示す図
【図１８】  ノード６１−１７におけるノードデータ７１−１７を示す図
【図１９】  小ポリゴンの生成処理のフローチャートを示す図
【図２０】  小ポリゴン３３−１を示す図
【図２１】  小ポリゴンデータ１５０１を示す図
【図２２】  ポリゴンと小ポリゴンを示す図
【図２３】  ポリゴン内の境界データ内点９９１を示す図
【図２４】  ポリゴンの生成方法を示す図
【図２５】  ポリゴンの生成方法を示す図
【図２６】  ポリゴン内のラインデータの検索処理のフローチャートを示す図
【図２７】  ポリゴン２１−５内のラインデータ３０１を示す図
【図２８】  ポリゴン内のシンボルデータの検索処理のフローチャートを示す図
【図２９】  点とポリゴンの包含関係を示す図
【図３０】  ポリゴン２１−５内のシンボルデータ４０１を示す図
【図３１】  従来の地図データ検索システム１におけるポリゴン２１を示す図
【符号の説明】
１………地図データ検索システム
３………ホストコンピュータ
５………端末側コンピュータ
７………地図データベース
９………ＣＤーＲＯＭ
１３………地図データ
４１………境界データ
【図１】
0003704235.tif 000002
【図２】
0003704235.tif 000003
【図３】
0003704235.tif 000004
【図４】
0003704235.tif 000005
【図５】
0003704235.tif 000006
【図６】
0003704235.tif 000007
【図７】
0003704235.tif 000008
【図８】
0003704235.tif 000009
【図９】
0003704235.tif 000010
【図１０】
0003704235.tif 000011
【図１１】
0003704235.tif 000012
【図１２】
0003704235.tif 000013
【図１３】
0003704235.tif 000014
【図１４】
0003704235.tif 000015
【図１５】
0003704235.tif 000016
【図１６】
0003704235.tif 000017
【図１７】
0003704235.tif 000018
【図１８】
0003704235.tif 000019
【図１９】
0003704235.tif 000020
【図２０】
0003704235.tif 000021
【図２１】
0003704235.tif 000022
【図２２】
0003704235.tif 000023
【図２３】
0003704235.tif 000024
【図２４】
0003704235.tif 000025
【図２５】
0003704235.tif 000026
【図２６】
0003704235.tif 000027
【図２７】
0003704235.tif 000028
【図２８】
0003704235.tif 000029
【図２９】
0003704235.tif 000030
【図３０】
0003704235.tif 000031
【図３１】
0003704235.tif 000032