最も近い座標を探す

2021.03.10

１番近い座標は？

ここでは、基準とする座標に最も近い座標を複数の座標から探す方法を解説します。

以下の図は、そのイメージです。

１番近い座標を探す方法

基準の座標からの近さの判定には直線距離を使います。基準の座標と結んだ直線距離が最短の座標が最も近い座標です。

具体的には以下のようなプログラムになります。

①基準の座標を決めます。(ox,oy)

②探索する座標列を配列に格納します。(x0,y0)～(xn,yn)

③基準の座標(ox,oy)から探索座標(x0,y0)～(xn,yn)の直線距離の２乗を計算します。

④③で計算した値のうち、１番小さい値を格納する配列の添え字を結果として出力します。x[添え字]とy[添え字]が求める座標です。

Javaソースコード

以下が、上記の内容をJavaのソースコードにしたものです。

このソースは基準の座標(500.0,500.0)から１番近い座標を求めるものです。探索する座標は、乱数を使ってｘｙそれぞれ0.0以上、1000.0未満の範囲で自動作成しています。

ClosestCoordinates1.java

ダウンロード

public class ClosestCoordinates1 {
	// 最も近い座標の配列の添え字を戻すメソッド
	// (ox,oy)が基準座標
	// (x[],y[])が探索座標
	static int closest_coordinates( double ox, double oy, double[] x, double[] y )
	{
		// 引数に不備がある場合、-1を戻す
		if ( null == x ) return -1;
		if ( null == y ) return -1;
		if ( 1 > x.length ) return -1;
		if ( 1 > y.length ) return -1;
		if ( x.length != y.length ) return -1;

		// 調べる座標数
		int crdnum = x.length;

		// 調べる座標が１つの場合、0を戻す。
		if ( 1 == crdnum ) return 0;

		// 距離の最小値を格納する変数
		// 初期値 : doubleの最大
		double dist2_min = Double.MAX_VALUE;

		// 距離の最小値が格納される配列の添え字を格納する変数
		// 初期値 : -1
		int crd_min = -1;

		// 最も近い座標を求める
		for ( int i = 0; i < crdnum; i++ ) {
			// 距離の２乗を計算
			double dx = x[ i ] - ox;
			double dy = y[ i ] - oy;
			double dist2 = dx * dx + dy * dy;

			//　距離の最小値の比較
			if ( dist2 < dist2_min ) {
				// 距離の最小値を配列の添え字の更新
				dist2_min = dist2;
				crd_min = i;
			}
		}

		// 距離の最小値が格納される配列の添え字を戻す
		return crd_min;
	}


	// メイン
	public static void main(String[] args) {
		// 調べる座標を配列に格納
		// x,yは0.0以上～1000.0の乱数で作成
		double[] x = new double[ 10 ];
		double[] y = new double[ 10 ];

		for ( int i = 0; i < x.length; i++ ) {
			x[ i ] = Math.random() * 1000.0;
			y[ i ] = Math.random() * 1000.0;
		}

		// 基準の座標を設定
		double ox = 500.0;
		double oy = 500.0;
		int ans = closest_coordinates( ox, oy, x, y );
		if ( 0 > ans ) {
			System.out.println( "配列番号の取得に失敗しました！" );
		}

		// 結果を出力
		System.out.println( "最も近い座標の配列番号 : " + ans );
		System.out.println( "最も近い座標 : " + x[ ans ] + " " + y[ ans ] );
		System.out.println();

		// 調べた座標を出力
		for ( int i = 0; i < x.length; i++ ) {
			System.out.println( i + " " + x[ i ] + " " + y[ i ] );
		}
	}
}

コンパイルソースコードが「ANSI」の場合

C:\talavax\javasample>javac -encoding sjis ClosestCoordinates1.java

コンパイルソースコードが「UTF-8」の場合

C:\talavax\javasample>javac ClosestCoordinates1.java

実行

C:\talavax\javasample>java ClosestCoordinates1

出力結果

最も近い座標の配列番号 : 5
最も近い座標 : 522.6032407893074 529.1182157580057

0 877.7147009243795 718.844711996419
1 526.6243989932896 972.9817185296182
2 918.0303176324935 178.36544193189474
3 327.8529222496893 98.33227058715333
4 864.9148502306463 293.97241655453996
5 522.6032407893074 529.1182157580057
6 556.547189361226 99.08534083354937
7 507.57394473692665 420.918431684552
8 478.02958653506147 933.9869793183221
9 334.80064599857684 252.08397376586979

基準の座標(500.0,500.0)に１番近い座標を格納した配列の添え字と座標、探索した全ての座標を出力しています。

探索する座標は乱数なので、実行する毎に結果は変わります。

Javaソースコードの解説

ここからは、このJava ソースコードを上から順番に解説していきます。

public class ClosestCoordinates1 {

クラス名を、ClosestCoordinates1としています。

	// 最も近い座標の配列の添え字を戻すメソッド
	// (ox,oy)が基準座標
	// (x[],y[])が探索座標
	static int closest_coordinates( double ox, double oy, double[] x, double[] y )

基準座標(ox,oy)から探索座標(x[],y[])の直線距離が最も近いものを戻すメソッドです。結果は配列の添え字を戻します。

		// 引数に不備がある場合、-1を戻す
		if ( null == x ) return -1;
		if ( null == y ) return -1;
		if ( 1 > x.length ) return -1;
		if ( 1 > y.length ) return -1;
		if ( x.length != y.length ) return -1;

引数の検査です。引数に不備がある場合は、処理を中断して-1をreturn文で戻します。ここでは、探索座標xyの有無／xy配列要素数の一致を確認しています。

014
015

		// 調べる座標数
		int crdnum = x.length;

探索する座標の個数をint型の変数crdnumに代入しています。引数の検査でxとyの配列の要素数が同じことがわかっているので配列xの要素数を座標の個数としています。

017
018

		// 調べる座標が１つの場合、0を戻す。
		if ( 1 == crdnum ) return 0;

探索する座標の個数crdnumが1の場合、return文で0を戻してメソッドを抜けています。この0は配列の添え字番号のことでx[0],y[0]が最も近い座標ということです。個数が1の場合、その１つが１番近い座標です。

020
021
022

		// 距離の最小値を格納する変数
		// 初期値 : doubleの最大
		double dist2_min = Double.MAX_VALUE;

距離の最小値を格納するdouble型の変数dist2_minの初期値にdouble型の変数が持てるの最大値を代入しています。

変数の最小値／最大値はこちらの記事を参考にしてください。

変数の最小値・最大値

数値型の変数の最小値・最大値がプログラムで取得でします。

2016.01.20

024
025
026

		// 距離の最小値が格納される配列の添え字を格納する変数
		// 初期値 : -1
		int crd_min = -1;

距離の最小値が格納される配列の添え字を格納するinte型の変数crd_minの初期値に-1を代入しています。

028
029

		// 最も近い座標を求める
		for ( int i = 0; i < crdnum; i++ ) {

for文で探索座標xyの個数回のループを作成しています。

			// 距離の２乗を計算
			double dx = x[ i ] - ox;
			double dy = y[ i ] - oy;
			double dist2 = dx * dx + dy * dy;

基準座標(ox,oy)と探索座標(x[i],y[i])の直線距離の２乗を計算しています。

このプログラムは一番近い座標を探すものなので、直線距離の２乗でも比較することができます。もちろん直線距離で比較することもできますが、直線距離を求めるには平方根を計算する必要があり余分な処理時間がかかります。

直線距離の計算は、以下の図を参考にしてください。

$ピタゴラスの定理$

			//　距離の最小値の比較
			if ( dist2 < dist2_min ) {
				// 距離の最小値を配列の添え字の更新
				dist2_min = dist2;
				crd_min = i;
			}

計算で得られた距離の２乗の値dist2と現在の距離の最小値を格納した変数dist2_minを比較して、変数dist2の値が小さければ、変数dist2_minにdist2の値を代入します。さらに配列の添え字crd_minに変数iの値を代入します。

この処理によって、最も近い座標を格納した配列の添え字crd_minと、その距離の２の乗を格納した変数dist2_minが更新されていきます。

ちなみに変数i=0のとき、変数dist2_minの値はdouble値の最大なのでif文の条件( dist2 < dist2_min )を満たします。

043
044

		// 距離の最小値が格納される配列の添え字を戻す
		return crd_min;

return文で最も近い座標を格納した配列の添え字crd_minを戻してメソッド終了です。

048
049

	// メイン
	public static void main(String[] args) {

このmainメソッドからプログラムを実行します。

		// 調べる座標を配列に格納
		// x,yは0.0以上～1000.0の乱数で作成
		double[] x = new double[ 10 ];
		double[] y = new double[ 10 ];

		for ( int i = 0; i < x.length; i++ ) {
			x[ i ] = Math.random() * 1000.0;
			y[ i ] = Math.random() * 1000.0;
		}

探索座標xyを10個作成しています。配列xyにはそれぞれ乱数を使って0.0以上1000.0未満の値を代入しています。

Math.randomメソッド

public static double Math.random()

・乱数を返します。

  パラメータ なし

  戻り値     0.0以上、1.0未満の乱数

		// 基準の座標を設定
		double ox = 500.0;
		double oy = 500.0;
		int ans = closest_coordinates( ox, oy, x, y );
		if ( 0 > ans ) {
			System.out.println( "配列番号の取得に失敗しました！" );
		}

基準座標(ox,oy)と探索座標(x[],y[])をclosest_coordinatesメソッドに渡しています。戻り値ansに配列の添え字が戻ります。

変数ansの値が0未満の場合、エラーで結果が得られなかったことを意味しています。

		// 結果を出力
		System.out.println( "最も近い座標の配列番号 : " + ans );
		System.out.println( "最も近い座標 : " + x[ ans ] + " " + y[ ans ] );
		System.out.println();

		// 調べた座標を出力
		for ( int i = 0; i < x.length; i++ ) {
			System.out.println( i + " " + x[ i ] + " " + y[ i ] );
		}

結果をprintlnで出力しています。

戻り値ansの配列の添え字の値、x[ ans ]とy[ ans ]が基準座標から１番近い座標です。

以上です。