Вот ваша отправная точка:
/**
* Source: https://introcs.cs.princeton.edu/java/12types/GreatCircle.java.html
* @author David Buzatto
*/
public class SphericalDistance {
/**
* Calculates the spherical distance between two geographical coordinates.
*
* @param lat1 The latitude of the first geographical coordinate in degrees.
* @param lng1 The longitude of the first geographical coordinate in degrees.
* @param lat2 The latitude of the second geographical coordinate in degrees.
* @param lng2 The longitude of the second geographical coordinate in degrees.
* @param degreeRatio The ratio between one degree and the metric unit. For example, one degree variation in the Earth (considering it's a sphere) corresponds to 111120 meters.
* @return The distance between two geographical coordinates using the degreeRatio.
*/
public static double sphericalDistance( double lat1, double lng1, double lat2, double lng2, double degreeRatio ) {
double x1 = Math.toRadians( lat1 );
double y1 = Math.toRadians( lng1 );
double x2 = Math.toRadians( lat2 );
double y2 = Math.toRadians( lng2 );
double a = Math.pow( Math.sin( ( x2 - x1 ) / 2 ), 2 )
+ Math.cos( x1 ) * Math.cos( x2 ) * Math.pow( Math.sin( ( y2 - y1 ) / 2 ), 2 );
double angle = 2 * Math.asin( Math.min( 1, Math.sqrt( a ) ) );
return degreeRatio * Math.toDegrees( angle );
}
public static void main( String[] args ) {
double degreeRatio = 111120; // meters per degree
double lat1 = -20;
double lng1 = -50;
double lat2 = -20;
double lng2 = -54.7885801;
System.out.printf( "Distance between (%f, %f) and (%f, %f): %fkm\n",
lat1, lng1, lat2, lng2,
sphericalDistance( lat1, lng1, lat2, lng2, degreeRatio/1000 ) );
}
}
Этот код является приблизительным, поскольку Земля - это не сфера, а эллипсоид.
РЕДАКТИРОВАТЬ
Предположим, у вас есть сетчатая плоскость, покрывающая круг, ограничивающий географические координаты источника и цели.В этом примере сетка равномерно разделена на 250 строк и 250 столбцов, чтобы не получить слишком большую картину.В вашем случае вам понадобится двойная часть.Предположим, что каждая параллельная линия далека от следующей на расстояние 1 км.
Рассмотрим эту сетку в виде графика.Каждое пересечение линии - это вершина / узел графа.Ответ, который вам нужен, примерно такой: какой путь я должен выбрать, чтобы пересечь 1000 ребер, выходя из источника и достигая цели?
На этот ответ почти получен ответ с использованием алгоритма поиска в ширину с некоторой модификацией для выбора путей с определенным размером, поскольку вы не сможете получить это точное значение, поскольку структура графа является ретикулярной.Этот алгоритм приведет к одному из самых коротких путей / переходов внутри этого графика, но вам нужно изменить его, чтобы получить пути с некоторым размером.Чтобы получить лучшее приближение, вам нужно построить лучшую структуру, которая не имеет такого хорошего поведения.В моем примере это упрощено, потому что есть только 4 степени свободы для краев, то есть 0, 90, 180 и 270 градусов.В вашей реальной задаче путь, соединяющий пару вершин, можно повернуть на 360 градусов.Если вы перечислите каждый путь 1000 км, который существует на этом графике (с 360 степенями свободы), у вас будет 360 ^ 1000 возможностей!Вы, конечно, можете получить что-то действительно очень огромное, если ваше вращение может использовать минуты и секунды!Точный ответ почти невозможен, поэтому вам понадобится какой-то метод аппроксимации / оптимизации, такой как обоснование, которое я вам представил.
Вам также нужно учитывать, что вы имеете дело с географическими координатами, а не с картезианскими.Теперь, зачем вам это?Мне действительно любопытно.
Удачи, я думаю, вам действительно понадобится !!!
РЕДАКТИРОВАТЬ 2
Как я уже подозревал, выпроблема NP-завершения, так как вам нужен путь с точным размером.Посмотрите здесь: Как найти путь точной длины на графике
Я отредактирую ваш вопрос, чтобы пометить его с помощью алгоритма графа.Может быть, какой-то специалист может помочь вам и исправить какое-то неправильное представление, которое я могу сказать.