房屋之间的距离，Google Directions API 查询限制太低，需要更好的算法

Question

我需要租两套房子。我希望他们尽可能接近。约有300间房屋可供出租。我希望使用 Google 地图方向 API 来计算任意两座可用房屋之间的步行距离，这样我就可以对列表进行排序并选择两座距离较近的房屋。

一切都运行良好，只是 Google 设置了每天 2,500 次查询的理论限制（而实际上该限制要低得多，每天仅为 250 次）。我有 300²/2 - 300 = 44,700 个查询要做，显然这个限制对我来说是不够的。

这将是一次性的事情，关于如何使用 Google Maps API 完成我所需要的任何提示？我可以以某种方式运行分布式程序，这样限制只会影响一个实例吗？ Google App Engine 有帮助吗？

我也欢迎提出改进算法的建议。如果两栋房子相距较远，而另一栋房子靠近其中一栋，则意味着不必将第三栋房子与剩余的房子进行检查，因为它们可能相距很远。我也更关心算法的定性本质，而不是确切的距离，所以也许我可以做一个简单的近似，这将导致更少的查询。

谢谢，

Answer 1

任何两栋房子之间的地理距离（直线距离）将成为步行距离的严格下限。因此，我将从 300 个查询开始，为了获取每个房屋的经度/纬度，将它们代入半正弦公式（例如）以获取 45,000 个无序对之间的距离，并对它们进行排序以按地理距离获取最近的对。然后与
手头有一些可能的候选人，您可以开始通过另一组对 Google API 的调用来检查步行距离。

Answer 2

假设您是披萨送货员，并且想要计算您的有效范围（您可以在 30 分钟内到达的范围）。您想要制作该时间数据的 N 到 E 部分的彩色条形 3D 图表，例如（带有虚假数据）：

并且您想要包括大约 100k 栋房屋...至少我听说，像这样的程序是在 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));
}

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

我不知道这是否适用于方向方法，但您希望将方向查询交错（嵌套）到单个查询中。一个 google 块最多可以容纳 24 个方向。因此，您可以将查询增加到每天最多 250 * 24（6000 个方向）。也许您想在 6000 次查询后更改您的 IP 地址？也许 Google 让您每天查询超过 6000 个路线？我从 geweb tsp 求解器中得到了交错的想法，他将查询矩阵中的 24 个城市交错成 1 个块，最多可节省 22 个单个查询，从而减少带宽和 Google 的 API 限制。