Q: 緯度、軽度の点からなる鉄道路線のCSVデータがあるのですが、これが線の順番に並んでおらず、バラバラの順番になっています。このcsvファイルを線の順番に並び替えるGo言語プログラムを作成して下さい。
点画にすれば、こんな感じ
でも、線画にすると、こんな感じになる
で、このcsvのファイル名を、"your_csv_file.csv"として、以下のプログラムに放り込む
package main
import (
"bufio"
"encoding/csv"
"fmt"
"io"
"math"
"os"
"strconv"
)
// 座標を表す構造体
type Coordinate struct {
Latitude float64
Longitude float64
}
func main() {
// CSVファイルのパス
filePath := "your_csv_file.csv"
// CSVファイルを読み込む
coordinates, err := readCoordinatesFromFile(filePath)
if err != nil {
fmt.Println("Error reading CSV file:", err)
return
}
// 座標を線の順番に並び替え
sortedCoordinates := sortCoordinates(coordinates)
// 結果を表示
for _, coord := range sortedCoordinates {
fmt.Printf("%f, %f\n", coord.Latitude, coord.Longitude)
}
}
// CSVファイルから座標を読み込む関数
func readCoordinatesFromFile(filePath string) ([]Coordinate, error) {
var coordinates []Coordinate
file, err := os.Open(filePath)
if err != nil {
return nil, err
}
defer file.Close()
reader := csv.NewReader(bufio.NewReader(file))
for {
line, err := reader.Read()
if err == io.EOF {
break
} else if err != nil {
return nil, err
}
// CSVの各行から緯度と経度を抽出
latitude, err := strconv.ParseFloat(line[0], 64)
if err != nil {
return nil, err
}
longitude, err := strconv.ParseFloat(line[1], 64)
if err != nil {
return nil, err
}
coordinates = append(coordinates, Coordinate{Latitude: latitude, Longitude: longitude})
}
return coordinates, nil
}
// 座標を線の順番に並び替える関数
func sortCoordinates(coordinates []Coordinate) []Coordinate {
// 最初の座標をスタート地点として選択
startIndex := 0
sortedCoordinates := []Coordinate{coordinates[startIndex]}
coordinates = append(coordinates[:startIndex], coordinates[startIndex+1:]...)
// 座標を距離に基づいてソート
for len(coordinates) > 0 {
minIndex := findNearestCoordinateIndex(coordinates, sortedCoordinates[len(sortedCoordinates)-1])
sortedCoordinates = append(sortedCoordinates, coordinates[minIndex])
coordinates = append(coordinates[:minIndex], coordinates[minIndex+1:]...)
}
return sortedCoordinates
}
// 最も距離の近い座標のインデックスを検索する関数
func findNearestCoordinateIndex(coordinates []Coordinate, reference Coordinate) int {
minDistance := math.MaxFloat64
minIndex := 0
for i, coord := range coordinates {
distance := calculateDistance(coord, reference)
if distance < minDistance {
minDistance = distance
minIndex = i
}
}
return minIndex
}
// Haversine式を使用して座標間の距離を計算する関数
func calculateDistance(coord1, coord2 Coordinate) float64 {
earthRadius := 6371.0 // 地球の半径（キロメートル）
// 度数法からラジアンに変換
lat1 := degToRad(coord1.Latitude)
lon1 := degToRad(coord1.Longitude)
lat2 := degToRad(coord2.Latitude)
lon2 := degToRad(coord2.Longitude)
// Haversine式による距離計算
dlon := lon2 - lon1
dlat := lat2 - lat1
a := math.Pow(math.Sin(dlat/2), 2) + math.Cos(lat1)*math.Cos(lat2)*math.Pow(math.Sin(dlon/2), 2)
c := 2 * math.Atan2(math.Sqrt(a), math.Sqrt(1-a))
distance := earthRadius * c
return distance
}
// 度数法をラジアンに変換する関数
func degToRad(deg float64) float64 {
return deg * (math.Pi / 180)
}でてきたcsvをファイルにして表示すると、こんな感じになった。
だいぶ良くなったんだけど、変な直線が一本引かれている。
考察した結果、このプログラムは、
(Step.1) 出発点に一番近いノードを探す。
(Step.2)そのノードを次の出発点にして(Step.1)を行う
という処理をしているため、使われていないノードが、候補として残ってしまうという問題が生じる。
で、終端に至ったノードは使われていないノードの中から、一番近いノードを探してくるため、このような問題が発生してしまう、ということだろう。
対策は結構簡単で、ノード距離が異様に大きい場合は、そこで打ち切る、という処理を入れれば足る
(面倒なので、今回は、手動で削除した)
以上
