Next: 1.3 データファイル読み書き Up: 1 カー・ナビゲーション Previous: 1.1 はじめに

1.2 ナビゲーション・システムに必要なデータ構造

実際に販売されているナビゲーション・システムでは，最短距離経路を捜し出 し，衛星などを利用して現在いる場所を地図上に表示する機能を持っています． 本演習では，衛星に関する機能以外について，次のような課題を設定していま す．

1. 地図上の指定した交差点の探索，ある地点から距離に応じて交差点を並 べ替える．

2. コンピュータ・グラフィックスにより地図を表示する．

3. 地図の指定した2点間の最短距離，及び最短時間経路を探す．

4. 地図上を移動する車を想定し，指定した2点間を移動する様子をコンピュータ・グラフィックスによりシミュレーションする．

5. 現在の道路の混み具合(時間とともに変化する)を考慮に入れた上で最短時間経路を捜し出し，車が移動する様子をコンピュータ・グラフィックスによりシミュレーションする．

4番目の課題は実機にはない機能ですが，現在地点を地図に表示する機能の代 わりとして，設定しています．さらに，高度な課題として，5番目の課題も設定 されています．現在販売されている実機には5番目の機能はありません．なぜ なら，道路の混み具合のような道路情報を時々刻々と入手する手段がないから です．今後，道路情報を入手できるシステムが整ってくれば，現在地から目 的地まで道路の混み具合を考慮して最も時間のかからない経路を捜し出すナビ ゲーション・システムが現れることでしょう．

  
Figure 1: 仙台市中心部の概略地図

さて，このような課題を進めていく上で，どんなデータが必要となるか見てみ ましょう．図１は仙台中心街の概略地図です．地図を眺めて いてまず，位置を表す「位置データ」が必要であることに気がつきます．位置 は地図の東方向をx，北方向をyで表すことにすると，

double x, y; /*位置*/

double x[CrossingNumber]; /* 位置x */
double y[CrossingNumber]; /* 位置y */

ここで，CrossingNumberは記憶すべき交差点の個数です．このように配列を宣言すると，図３に示すようなデータ構造となります．配列の行はあらかじめ決めた交差点の番号に対応しています．それでは，実際の地図の位置データを配列に格納してみましょう．

 
Figure 2: 単一変数の構造

  
Figure 3: 配列の構造

さてここで，上記のように配列で作成した交差点のデータ構造について考えて みましょう．例えば，交差点3番目の位置xはx[2]ですから「配列xの3番目の要 素」ということになります．このように，配列でデータを作成すると，データ は「配列****の****の要素」というように参照されます．ここで，ちょっと考 えてみてください．どこにも交差点という意味が入っていませんね．これでは， 交差点に関する位置データなのか何か建物に関するものなのか区別が付きませ ん．これから，交差点以外のデータを作成していこうとすると，何に対するデー タであるかを明記しておかなければなりません．区別を付けるとすると，例えば， 次のように配列名に交差点のデータであるという意味を持たせることになります．

double crossing_x[CrossingNumber]; /* 交差点の位置x */ 
double crossing_y[CrossingNumber]; /* 交差点の位置y */

交差点以外の位置データについてもこのような宣言をしていたら，宣言する変 数名の数が多くなり，あまりスマートではありませんね． そこで，構造体を使うことを考えてみましょう．上記のデータを構造体を用い て定義するとまず，位置を表す構造体を定義して，

typedef struct {
    double x, y;    /* 位置x, y */
} Position;         /* 位置を表す構造体 */

typedef struct{
    Position pos;  /* 位置を表す構造体 */
} Crossing;        /* 交差点を表す構造体 */

構造体Crossingのデータ構造は図 5です．そして， 交差点の数だけ格納できる構造体の配列として，

Crossing cross[CrossingNumber]; /* 交差点の変数宣言 */

  
Figure 4: 構造体Positionの構造

  
Figure 5: 構造体Crossingの構造

  
Figure 6: 構造体変数crossの構造

このようにすると，例えば，交差点3番目の位置xはcross[2].pos.xとなり， 「構造体crossの配列3番目の要素である構造体posの要素x」というように参照 できます．配列の時よりも参照方法はややこしくなったように見えますが，変 数をみれば，一目で何のどんなデータであるかがわかります．さらに今後，デー タにいろいろな情報を付け加えていくとき，構造体の威力が発揮されます．そ れについては，この後でみてみましょう．

本演習では構造体を用いて演習を進めていきます．もし，構造体の使い方やデー タ構造についてわからない人は，教科書をみてしっかり理解しておいてくださ い．

それでは，交差点を例にしてデータに位置以外の情報も付け加えてみましょう． 交差点で位置データの他に必要な情報として，交差点の名前や交差点で信号に より待たなければならない時間(ここでは，平均待ち時間)の情報があります． さらに，交差点番号も加えてみましょう．先程の構造体Crossingに，これら のデータを付け加えると，

typedef struct {
    int id;              /* 交差点番号 */
    Position pos;        /* 位置を表す構造体 */
    char name[MaxName];  /* 交差点名 */
    double wait;         /* 平均待ち時間 */
} Crossing;

ここで，MaxNameは交差点名の最大文字数です．また，変数の宣言は 先と同じように，

Crossing cross[CrossingNumber]; /* 交差点の変数宣言 */

  
Figure 7: データを追加した構造体変数crossのデータ構造

  
Figure 8: 交差する交差点の決め方

さて，構造体Crossingを用いることで，交差点の「点」としての情報は作成す ることができました．しかしながら，この情報で先に示した課題をやろうとす ると，交差点の探索，並べ替えはできますがそれ以外の課題はできないことがわ かります．なぜなら，交差点と交差点との間に走っている道路の情報がないか らです．すなわち，交差点と交差点の結び付きがどのようになっているかを 示してやる必要があります．このような結び付きを「リンク情報」と呼びます． ナビゲーションシステムのみならず，一般のデータベースシステムではこのよ うなリンク情報が大変重要な役割を果たしています．この「リンク情報」はい ろいろな表し方がありますが，ここでは次のようにしてみましょう．

typedef struct {
    int id;              /* 交差点番号 */
    Position pos;        /* 位置を表す構造体 */
    double wait;         /* 平均待ち時間 */
    char name[MaxName];  /* 交差点名 */
    int points;          /* 交差道路数 */
    int next[5];         /* 隣接する交差点番号 */
} Crossing;

交差道路数は，T字路ならば3，四つ角ならば4となります．隣接する交差点番 号は図 8のように，東から反時計回りに見て、出ている道 路を0番から順に付けていきます．また，交差点番号は 構造体配列の番号をいれてやります．では，地図(図 1)から リンク情報を構造体にいれてみましょう．

以上より，本演習で行う全ての課題を実行できるデータを作成することができ ました．このように，プログラミングをするにあたって，扱うデータ構造を決 めて，それについて何らかの処理を施すという方法を「オブジェクト指向」の プログラミングといいます．「オブジェクト」とは扱うデータそのものを指し ます．現在ではこのオブジェクト指向プログラミングが主流となっており，そ れ専用の言語も開発されています．その代表的なものとして，C言語をより発 展させたC++言語、SmallTalk、JAVAがあります．興味ある人は，ぜひ挑戦してみてく ださい．(参考文献参照)

練習問題 1-1

地図(図 1)から適当な交差点を5カ所選び，仙台駅を原点とした位置(x, y)を測定しなさい. 次に，測定した数値を配列に格納し，データの値を画面に表示しなさい．

-----------------------

/* arrary.c --- 配列の格納と表示 */
#include <stdio.h>

#define CrossingNumber 5    /* 交差点数=5 */

double x[CrossingNumber];    /* 配列の宣言(位置x) */
double y[CrossingNumber];    /* 配列の宣言(位置y) */

void main(void)
{
    int i;

    ...    /* <- 配列に変数を入力するプログラムを記入しなさい */
    
    for (i = 0; i < CrossingNumber; i++)    /* データの表示 */
        printf("配列[%d] x(%lf), y(%lf)\n", i, x[i], y[i]);
}

-----------------------

練習問題 1-2

1. 構造体Crossingを定義し，変数crossを宣言し，練習問題1-1で作成した配列x, yのデータを構造体へ移しなさい．
2. 図 1の地図から5カ所の交差点の名前，平均待ち時間を構造体crossに格納し，画面に表示しなさい．ただし，交差点番号，平均待ち時間には適当な数値をいれなさい．

-----------------------

/* Crossing1.c --- 構造体の格納と表示 */
#include <stdio.h>

#define CrossingNumber  5   /* 交差点数=5 */
#define MaxName        50   /* 最大文字数50文字(半角) */

typedef struct {
    double x, y;            /* 位置x, y */
} Position;                 /* 位置を表す構造体 */

typedef struct {            /* 構造体の定義 */
    int id;                 /* 交差点番号 */
    Position pos;           /* 位置を表す構造体 */
    char name[MaxName];     /* 交差点名 */
    double wait;            /* 平均待ち時間 */
} Crossing;

Crossing cross[CrossingNumber];    /* 交差点の変数宣言 */ 

void main(void)
{
    int i;

    ...    
    /* 配列x, yから構造体posへデータを転送するプログラムを記入しなさい */
    ... 
    /* 交差点番号，交差点名，平均待ち時間を代入するプログラムを記入しなさい */
    
    for (i = 0; i < CrossingNumber; i++)    /* データの表示 */
        printf("配列[%d] 番号(%d), x(%lf), y(%lf), 名(%s), 待ち(%lf)\n",
               i, cross[i].id, cross[i].pos.x, cross[i].pos.y,
               cross[i].name, cross[i].wait);
}

-----------------------

練習問題 1-3

1. 地図(図 1)から各交差点の交差道路数，隣接する交差点番号を読みとりデータを構造体へ格納し，画面に表示しなさい．

-----------------------

/* Crossing2.c --- 構造体の格納と表示 */
#include <stdio.h>

#define CrossingNumber  5   /* 交差点数=5 */
#define MaxName        50   /* 最大文字数50文字(半角) */

typedef struct {
    double x, y;            /* 位置x, y */
} Position;                 /* 位置を表す構造体 */

typedef struct {            /* 構造体の定義 */
    int id;                 /* 交差点番号 */
    Position pos;           /* 位置を表す構造体 */
    double wait;            /* 平均待ち時間 */
    char name[MaxName];     /* 交差点名 */
    int points;             /* 交差道路数 */
    int next[5];            /* 隣接する交差点番号 */
} Crossing;

Crossing cross[CrossingNumber];    /* 交差点の変数宣言 */ 

void main(void)
{
    int i, j;

    ...    /* 構造体crossへデータを代入するプログラムを記入しなさい */
    
    for (i = 0; i < CrossingNumber; i++) {    /* データの表示 */

        printf("配列[%d] 番号(%d), x(%lf), y(%lf), 名(%s), 待ち(%lf)\n",
               i, cross[i].id, cross[i].pos.x, cross[i].pos.y,
               cross[i].name, cross[i].wait);
        printf("\t交差数(%d)\t", cross[i].points);
        for (j=0; j<5; j++)
            printf("No.%d(%d) ", j, cross[i].next[j]);
        puts("");
    }
}

-----------------------

Next: 1.3 データファイル読み書き Up: 1 カー・ナビゲーション Previous: 1.1 はじめに