緯度、軽度の点からなる鉄道路線のCSVデータがあるのですが、これが線の順番に並んでおらず、バラバラの順番になっています。このcsvファイルを線の順番に並び替えるGo言語プログラムを作成して下さい。

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)を行う
という処理をしているため、使われていないノードが、候補として残ってしまうという問題が生じる。

で、終端に至ったノードは使われていないノードの中から、一番近いノードを探してくるため、このような問題が発生してしまう、ということだろう。

対策は結構簡単で、ノード距離が異様に大きい場合は、そこで打ち切る、という処理を入れれば足る
(面倒なので、今回は、手動で削除した)

以上