Расстояния между домами, лимит запросов Google Directions API слишком мал, нужен лучший алгоритм

Question

Мне нужно арендовать два дома. Я хочу, чтобы они были как можно ближе. Есть около 300 домов, доступных для аренды. Я хочу использовать API Google Maps Directions API для вычисления расстояния между любыми двумя доступными домами, чтобы затем можно было отсортировать список и выбрать два близких.

Все отлично работает, за исключением того, что Google устанавливает теоретический лимит в 2500 запросов в день (и на практике этот предел намного ниже, всего 250 в день). У меня есть 300 ² / 2 - 300 = 44 700 запросов, поэтому очевидно, что для меня этого ограничения недостаточно.

Это будет один раз, есть какие-нибудь советы о том, как мне добиться того, что мне нужно, с помощью API Карт Google? Можно ли как-то запустить распространяемую программу, чтобы ограничение влияло только на один экземпляр? Поможет ли Google App Engine?

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

Спасибо

Answer 1

Географическое расстояние между любыми двумя домами по прямой линии будет строго нижней границей расстояния ходьбы.Поэтому я бы начал с 300 запросов, чтобы получить long / lat для каждого дома, подключить их к формуле Haversine (например), чтобы получить расстояния между 45 000 неупорядоченных пар, и отсортировать их, чтобы получить ближайшие пары по географическому расстоянию.,Затем с некоторыми вероятными кандидатами в руки вы можете начать проверять пешеходные расстояния с помощью другого набора вызовов в API Google.

Answer 2

Я не знаю, работает ли это с методом указаний, но вы хотите чередовать (вкладывать) запрос указаний в один запрос. Блок Google может содержать до 24 направлений на блок. Таким образом, вы можете увеличить ваш запрос до 250 * 24 (6000 направлений) в день. Может быть, вы хотите изменить свой IP-адрес после 6000 запросов? Может быть, Google позволит вам запросить более 6000 направлений в день? Я получил идею чередования от geweb tsp solver, где он чередует 24 города из матрицы запросов в один блок, сохраняя до 22 отдельных запросов и, таким образом, уменьшая пропускную способность и ограничения API Google.

Answer 3

Я бы использовал эту формулу:

distance = Math.acos(Math.sin(lat1)*Math.sin(lat2) + 
           Math.cos(lat1)*Math.cos(lat2) *
           Math.cos(lon2-lon1)) * 6371;

, чтобы расставить все 45 000 домов на расстоянии по прямой линии.Затем я взял бы 250 лучших результатов, ранжированных по кратчайшему расстоянию, и проверил их через Google, чтобы получить точное расстояние и пересчитать рейтинг.

Answer 4

Учтите, что вы являетесь поставщиком пиццы и хотите рассчитать эффективный диапазон (куда вы можете пойти в течение 30 минут). И вы хотите сделать цветную гистограмму 3d-графика из данных от N до E того времени, что-то вроде (с поддельными данными):

И вы хотите включить около 100 тыс. Домов ... Ну, по крайней мере, я слышал, что такая программа была создана до того, как была введена в карту Google. В этом случае ограничения просто сильно кусаются.

Если у вас есть географическое положение из всех домов, то вы можете найти прогноз на основании того, как далеко находятся точки на земле, когда вы летите, как птица. Отсортируйте их на основании этого и найдите результаты для лучших прогнозов.

Редактировать: Добавлен пример кода Java, который может быть полезен при создании прогнозов:

/**
 * Thaddeus Vincenty's inverse method formulae implementation for
 * geographical distance between two given points on earth.
 * @param L1
 *        geographical latitude of standpoint in decimal degrees
 * @param G1
 *        geographical longitude of standpoint in decimal degrees
 * @param L2
 *        geographical latitude of destination in decimal degrees
 * @param G2
 *        geographical longitude of destination in decimal degrees
 * @return Geographical distance in kilometeres
 */
public static double getDistance(final double L1, final double G1,
        final double L2, final double G2) {
    double delta, p0, p1, p2, p3;
    // The average radius for a spherical approximation of Earth
    double rEarth = 6371.01d;

    delta = G1 - G2;
    p0 = Math.cos(L2) * Math.cos(delta);
    p1 = Math.cos(L2) * Math.sin(delta);
    p2 = Math.cos(L1) * Math.sin(L2) - Math.sin(L1) * p0;
    p3 = Math.sin(L1) * Math.sin(L2) + Math.cos(L1) * p0;

    return rEarth * Math.atan2(Math.sqrt(p1 * p1 + p2 * p2), p3);
}

/**
 * Rounds double to nr number of decimal places
 * @param d
 *        floating-point number
 * @param nr
 *        decimal places to keep
 * @return rounded number with nr decimal places
 */
public static double round(double d, int nr) {
    return new java.math.BigDecimal(Double.toString(d)).setScale(nr,
        java.math.BigDecimal.ROUND_HALF_UP).doubleValue();
}

public static void main(String[] args) {
    double L1 = Math.toRadians(Double.parseDouble(args[0]));
    double G1 = Math.toRadians(Double.parseDouble(args[1]));
    double L2 = Math.toRadians(Double.parseDouble(args[2]));
    double G2 = Math.toRadians(Double.parseDouble(args[3]));

    System.out.println(round(getDistance(L1, G1, L2, G2), 2));
}