データから距離が近い市3位までを求めるプログラムを実装したい

Question

C言語、距離関数を使ったプログラムの実装方法が分からず困っています。
都市名name，緯度lat，経度lngをメンバに持つCity構造体の配列citiesを作成し、八王子市（35.67，139.32）との距離が近い市3位までを求めるプログラムを実装したいのですが、「2都市間の距離を求める」というおそらくポインタを使うであろうコードの書き方がわからず八方塞がりになっています。どうかご教授お願いいたします。

[条件]
・3つの距離関数を定義し，各距離定義に基づき近い市を求める
・各距離関数は，2つのCity構造体を引数として受け取るようにする
・原点(0,0)からの距離を求める関数ではなく，2都市間の距離を求める必要がある点に注意する．
・実装した距離関数へのポインタを使用する

---

実装したい実行結果
./nearest_city data/coord.dat 八王子市 35.66657 139.3161(実行コマンド)

マンハッタン距離ランキング：
1番目に近い都市：東京都昭島市(距離：0.076847)
2番目に近い都市：東京都福生市(距離：0.082638)
3番目に近い都市：東京都日野市(距離：0.083683)
ユークリッド距離ランキング：
1番目に近い都市：東京都昭島市(距離：0.054349)
2番目に近い都市：東京都あきる野市(距離：0.066186)
3番目に近い都市：東京都福生市(距離：0.072809)
チェビシェフ距離ランキング：
1番目に近い都市：東京都昭島市(距離：0.039143)
2番目に近い都市：東京都あきる野市(距離：0.062389)
3番目に近い都市：神奈川県相模原市(距離：0.070930)

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

typedef struct{
  char name;
  double lat;
  double lng;
}City;

City *cities;



void monte_simu(int n, double (*distance)(double, double)){
  int m = 0;
  for(int i = 0; i < n; i++){
    double x = 1.0*rand()/RAND_MAX;
    double y = 1.0*rand()/RAND_MAX;
    if(distance(x, y) < 1.0) m += 1;
 }
  printf("1番目に近い都市：%d = %f\n", m);
　printf("2番目に近い都市：%d = %f\n", m);
  printf("3番目に近い都市：%d = %f\n", m);
}

double euclid(double x, double y){ return sqrt(x*x + y*y); }
double manhattan(double x, double y){ return fabs(x)+fabs(y); }
double chebyshev(double x, double y){ return (x > y)? x : y; }

int main(int argc, char *argv[]){
  srand((unsigned) time(NULL));
  int N = atoi(argv[1]);
  printf("マンハッタン距離ランキング：\t"); monte_simu(N, manhattan);
  printf("ユークリッド距離ランキング：\t"); monte_simu(N, euclid );
  printf("チェビシェフ距離ランキング：\t"); monte_simu(N, chebyshev);
}

---

data/coord.datの中身
107
埼玉県さいたま市 35.86151 139.6455
埼玉県川越市 35.92511 139.4858
埼玉県熊谷市 36.14736 139.3887
埼玉県川口市 35.80774 139.7242
埼玉県行田市 36.13895 139.4556
埼玉県秩父市 35.99168 139.0855
埼玉県所沢市 35.79967 139.4686
埼玉県飯能市 35.85576 139.3278
埼玉県加須市 36.13144 139.6018
埼玉県本庄市 36.24333 139.1906
埼玉県東松山市 36.04216 139.3999
埼玉県春日部市 35.9753 139.7524
埼玉県狭山市 35.85291 139.4122
埼玉県羽生市 36.17267 139.5486
埼玉県鴻巣市 36.06576 139.5222
埼玉県深谷市 36.19747 139.2815
埼玉県上尾市 35.97741 139.5932
埼玉県草加市 35.82537 139.8053
埼玉県越谷市 35.89109 139.7909
埼玉県蕨市 35.82558 139.6798
埼玉県戸田市 35.81764 139.6779
埼玉県入間市 35.83577 139.3911
埼玉県朝霞市 35.79725 139.5939
埼玉県志木市 35.83661 139.5802
埼玉県和光市 35.7811 139.6057
埼玉県新座市 35.7935 139.5653
埼玉県桶川市 36.00297 139.5582
埼玉県久喜市 36.06206 139.6668
埼玉県北本市 36.02703 139.5302
埼玉県八潮市 35.82254 139.8392
埼玉県富士見市 35.85676 139.5491
埼玉県三郷市 35.83013 139.8722
埼玉県蓮田市 35.9945 139.6622
埼玉県坂戸市 35.95726 139.403
埼玉県幸手市 36.07809 139.7258
埼玉県鶴ヶ島市 35.93452 139.3931
埼玉県日高市 35.90775 139.3391
埼玉県吉川市 35.89112 139.8413
埼玉県ふじみ野市 35.8794 139.5198
埼玉県白岡市 36.01907 139.6769
東京都千代田区 35.694 139.7536
東京都中央区 35.67059 139.772
東京都港区 35.65807 139.7516
東京都新宿区 35.69389 139.7035
東京都文京区 35.70798 139.7525
東京都台東区 35.71261 139.78
東京都墨田区 35.71072 139.8015
東京都江東区 35.67286 139.8174
東京都品川区 35.60907 139.7303
東京都目黒区 35.64141 139.6981
東京都大田区 35.56126 139.716
東京都世田谷区 35.64648 139.6532
東京都渋谷区 35.66398 139.6979
東京都中野区 35.70727 139.6637
東京都杉並区 35.69955 139.6364
東京都豊島区 35.73244 139.7155
東京都北区 35.75281 139.7337
東京都荒川区 35.73608 139.7834
東京都板橋区 35.75124 139.7092
東京都練馬区 35.7356 139.6517
東京都足立区 35.77495 139.8046
東京都葛飾区 35.74343 139.8472
東京都江戸川区 35.70665 139.8683
東京都八王子市 35.66657 139.3161
東京都立川市 35.71398 139.4078
東京都武蔵野市 35.71784 139.5659
東京都三鷹市 35.68331 139.5599
東京都青梅市 35.78817 139.275
東京都府中市 35.66892 139.4777
東京都昭島市 35.70571 139.3538
東京都調布市 35.65063 139.5407
東京都町田市 35.54656 139.4385
東京都小金井市 35.69948 139.503
東京都小平市 35.7285 139.4775
東京都日野市 35.67135 139.395
東京都東村山市 35.75462 139.4685
東京都国分寺市 35.71094 139.4623
東京都国立市 35.68391 139.4414
東京都福生市 35.7386 139.3267
東京都狛江市 35.63481 139.5787
東京都東大和市 35.74533 139.4266
東京都清瀬市 35.78576 139.5264
東京都東久留米市 35.75799 139.5297
東京都武蔵村山市 35.75491 139.3874
東京都多摩市 35.63696 139.4464
東京都稲城市 35.63794 139.5046
東京都羽村市 35.76717 139.311
東京都あきる野市 35.72896 139.294
東京都西東京市 35.7255 139.5382
神奈川県横浜市 35.44403 139.638
神奈川県川崎市 35.53081 139.703
神奈川県相模原市 35.59564 139.3376
神奈川県横須賀市 35.28128 139.6723
神奈川県平塚市 35.3355 139.3494
神奈川県鎌倉市 35.31923 139.5467
神奈川県藤沢市 35.33894 139.4911
神奈川県小田原市 35.26469 139.1524
神奈川県茅ヶ崎市 35.33388 139.4047
神奈川県逗子市 35.29559 139.5804
神奈川県三浦市 35.14418 139.6208
神奈川県秦野市 35.3748 139.2199
神奈川県厚木市 35.44305 139.3624
神奈川県大和市 35.48752 139.458
神奈川県伊勢原市 35.40299 139.3149
神奈川県海老名市 35.44645 139.3908
神奈川県座間市 35.48864 139.4076
神奈川県南足柄市 35.32063 139.0997

Comments

[y_waiwai]

実行することができないとはどうなるんでしょうか。

また、コードは全文を提示しましょう。今のままでは意味不明です

[coco_bauer]

距離関数のコードが見当たりませんが、３種類の距離関数のコードは書けていますか？
City構造体の緯度・経度の２メンバーはintではなくdoubleですよね。
都市データの個数 N をコマンド引数(argv[1])から得ているようですが、data/coord.datファイルの１行目が都市データの個数なのではありませんか？
そうだとすると、
1) data/coord.datファイルから、Nと都市データを読みこむ。都市データはCity構造体の配列に入れる。
2) 八王子と各都市との距離を計算して、（距離計算方式ごとの）配列に入れる。
3) 配列の中で値が小さい順（距離が近い順）に１，２，３位のデータがある位置(index)を求めて、都市データ配列の同じindexの値(都市名、緯度、経度)を表示する。
という手順が素直ではないでしょうか。

[rft3]

返信が遅れてしまい申し訳ございません。距離関数は作ってみたのですが、八王子と各都市との距離を計算する、という部分がどうしてもわからないです…

[episteme]

球面上の2点間の距離なら
https://ja.wikipedia.org/wiki/%E5%A4%A7%E5%86%86%E8%B7%9D%E9%9B%A2

Answer 1

都市名name，緯度lat，経度lngをメンバに持つCity構造体の配列citiesを作成し、

ここまでできますか? それができたら

八王子市（35.67，139.32）との距離が近い市3位までを求めるプログラムを実装せよ、

cities[0]～cities[市の数-1] の中から 八王子市（35.67，139.32）に最も近い
cities[x]を見つけ、cities[0]と交換する

cities[1]～cities[市の数-1] の中から 八王子市（35.67，139.32）に最も近い
cities[x]を見つけ、cities[1]と交換する

cities[2]～cities[市の数-1] の中から 八王子市（35.67，139.32）に最も近い
cities[x]を見つけ、cities[2]と交換する

これだけやれば、距離が近い市3位までを cities[0],cities[1],cities[2] に求めたことになります。

[追記] 15分で書いたやつ：

#define _CRT_SECURE_NO_WARNINGS /* disable warning only for VC++ */
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

typedef struct {
    char name[32];
    double lat;
    double lng;
} City;

// ファイル:path を読み、City列を *pcities に求める
// 都市の数を返す
int build_cities(const char* path, City** pcities) {
  int n;
  City* c;
  FILE* fp = fopen(path,"r");
  if ( fp == NULL ) return 0;
  fscanf(fp, "%d", &n);
  c = (City*)malloc(sizeof(City)*n);
  if ( c != NULL ) {
    int i;
    *pcities = c;
    for ( i = 0; i < n; ++i ) {
      fscanf(fp, "%s %lf %lf", c[i].name, &c[i].lat, &c[i].lng);
    }
  }
  fclose(fp);
  return n;
}

void print_city(const City* city) {
  printf("%s %lf %lf\n", city->name, city->lat, city->lng);
}

void print_cities(const City* cities, int ncities) {
  int i;
  for (i = 0; i < ncities; ++i) {
    print_city(&cities[i]);
  }
}

// cities[begin]～cities[ncities-1] の中からtargetに最も近い cities[n] を求め n を返す。
// 2都市間の距離は fdistance により算出する
int nearest_city(const City* cities, int ncities, int begin, 
                 const City* target, double (*fdistance)(const City*, const City*) ) {
  int i;
  int nearest = 0;
  double nearest_distance = 0.0;
  for ( i = begin; i < ncities; ++i ) {
    double distance = fdistance(&cities[i], target);
    if ( i == begin || nearest_distance > distance ) {
      nearest = i;
      nearest_distance = distance;
    }
  }
  return nearest;
}

// 都市 a と b を交換する
void swap_city(City* a, City* b) {
  City tmp = *a;
  *a = *b;
  *b = tmp;
}

// (なんちゃって)マンハッタン距離
double manhattan_distance(const City* a, const City* b) {
  return fabs(a->lng - b->lng) + fabs(a->lng - b->lng);
}

int main(int argc, char* argv[]) {
  City target;
  City* cities;
  int   ncities;
  int n;
/*
  const char* path = argv[1];
  strcpy(target.name, argv[2]);
  target.lat = atof(argv[3]);
  target.lng = atof(argv[4]);
*/
  const char* path = "data/coord.dat";
  strcpy(target.name, "八王子市");
  target.lat = 35.66657;
  target.lng = 139.3161;

  ncities = build_cities(path, &cities);
//print_cities(cities, ncities);

  // nearest 3
  n = nearest_city(cities, ncities, 0, &target, manhattan_distance);
  swap_city(&cities[0], &cities[n]);
  n = nearest_city(cities, ncities, 1, &target, manhattan_distance);
  swap_city(&cities[1], &cities[n]);
  n = nearest_city(cities, ncities, 2, &target, manhattan_distance);
  swap_city(&cities[2], &cities[n]);

  printf("nearest 3 cities from: ");
  print_city(&target);
  puts("---------------");
  print_cities(cities, 3);

  free(cities);
  return 0;
}

Comments

[rft3]

返信遅れてもうしわけございません、ありがとうございます。やってみます。

[rft3]

情けなく、おこがましいことなのですが、自分はC言語の基礎が疎かになっているようでどうしてもコードを完成まで書き上げることができません…。どうかサンプルコードという形でソースコードを書いたものをいただけないでしょうか。

[episteme]

完成まで書き上げなくてもいいよ、回答者がフォローしてくれるから。
少なくとも 「1:都市名name，緯度lat，経度lngをメンバに持つCity構造体の配列citiesを作成」
および 「2:できたcities をプリント」(どっちみち必要だろうし)
それとキモとなる 「3:citiesをソート」こいつはとりあえず 緯度lat の小さい順でいい。比較してるとこを"まじもん"と取り換えればいいから。

1と2くらいは自力で書き上げてほしい。どんなアプリつくるにしても必要なスキルだから。

[episteme]

書けた。欲しけりゃあげる(自力でやってほしくはあるけど)

[rft3]

1は追加修正の際に書きました(間違っていたらすみません)。重ねて申し訳ないのですが書いていただいたコードをいただきたいです。C言語について１からまた勉強します。

[episteme]

追記した。持ってってー

[rft3]

本当にありがとうございます。いただいたコード、参考にさせていただきます。

Answer 2

距離を計算するには、角度（緯度、経度）を距離に換算する必要があります。
課題に出てくるのは、緯度３６度近辺の都市ですから、緯度３６度の緯度１度あたりの距離110959m、経度１度あたりの距離を90163mとします。
これらの数値は、緯度・経度の 1度はどれくらいの長さがあるのかの記事から引用したものです。(記事には、１度あたりの距離を計算したプログラムも載っているので、興味のある方は見てください)

例えば、「神奈川県南足柄市 35.32063 139.0997」と「東京都八王子市 35.66657 139.3161」だと、緯度が 35.66657 - 35.32063 = 0.34594(度)違い、経度が 130.3161 - 130.0997= 0.2164(度)違います。これらに、110959と90163をそれぞれ掛けると、南北に 0.34594 * 110959 = 38385.15646 m 、東西に 0.2164 * 90163 = 19511.2732 m、離れていることになります。

南北の距離と東西の距離を加えれば、マンハッタン距離。
南北の距離の二乗と、東西の距離の二乗を加えて、平方根を取れば、ユークリッド距離。
南北の距離と、東西の距離の大きいほうをとれば、チェビシェフ距離。

緯度・経度が２つのCity構造体に入っていても、緯度の差、経度の差を計算できますよね？

あとは、Cのプログラムにまとめるだけです。