Алгоритм расчета точек на карте Google Route для Android

Question

Я разрабатывал приложение для Android для компании, занимающейся заправкой. Приложение использует карту Google.

Пользователь выбирает две точки на карте, и я показываю маршрут между выбранными точками. Приложение должно показывать ближайшие (в радиусе 2 миль) заправочные станции на выбранном маршруте.

Маршрут представляет собой массив координат, такой как: Route [5000] = {"lon1, lat1", "lon2, lat2", "lon3, lat3", "lon4, lat5" ...}

И у меня есть список заправок, который состоит из координат. GasStations [200] = {"lon1, lat1", "lon2, lat2", "lon3, lat3", "lon4, lat5" ...}

Можете ли вы предложить мне высокопроизводительный алгоритм для расчета ближайших заправок на маршруте.

Спасибо.

Answer 1

Я не знаком с Android. Здесь метод C # для расчета расстояния между двумя парами местоположения. Если расстояние в радиусе 2 миль, выберите эту станцию.

Да, вам придется пройти через 5000x200 = 1 000 000, но это довольно быстро.

Надеюсь, это поможет.

decimal distance = CalculateDistance(stationLatitude, stationLongitude, routeLatitude, routeLongitude);

private static double ToRadian(double val)
{
    return (Math.PI / 180) * val;
}

private static double ToXAxis(decimal lat, decimal lng)
{
    return (Math.Cos(4 * (4 * Math.Atan2(1, 5) - Math.Atan2(1, 239)) / 180 * (double)lat) *
        Math.Cos(4 * (4 * Math.Atan2(1, 5) - Math.Atan2(1, 239)) / 180 * (double)lng));
}

private static double ToYAxis(decimal lat, decimal lng)
{
    return (Math.Cos(4 * (4 * Math.Atan2(1, 5) - Math.Atan2(1, 239)) / 180 * (double)lat) *
        Math.Sin(4 * (4 * Math.Atan2(1, 5) - Math.Atan2(1, 239)) / 180 * (double)lng));
}

private static double ToZAxis(decimal lat)
{
    return Math.Sin(4 * (4 * Math.Atan2(1, 5) - Math.Atan2(1, 239)) / 180 * (double)lat);
}

private static decimal CalculateDistance(decimal lat1, decimal lng1, decimal lat2, decimal lng2)
{
    double cntXAxis = Math.Cos(ToRadian((double) lat1))*Math.Cos(ToRadian((double) lng1));
    double cntYAxis = Math.Cos(ToRadian((double) lat1))*Math.Sin(ToRadian((double) lng1));
    double cntZAxis = Math.Sin(ToRadian((double) lat1));

    return (decimal) (3961*Math.Acos(ToXAxis(lat2, lng2)*cntXAxis + ToYAxis(lat2, lng2)*cntYAxis + ToZAxis(lat2)*cntZAxis));
}