4

我需要租两间房子。我希望他们尽可能接近。大约有300间房屋可供出租。我希望使用 Google Maps Directions API 来计算任何两个可用房屋之间的步行距离，这样我就可以对列表进行排序并选择两个靠近的。

一切都很好，除了谷歌设定了每天 2,500 个查询的理论限制（实际上这个限制要低得多，每天只有 250 个）。我有 300 2 /2 - 300 = 44,700 个查询要进行，所以显然这个限制对我来说是不够的。

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

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

谢谢，

4

4 回答 4

4

任何两所房子之间的地理距离，如乌鸦飞过，将是步行距离的严格下限。所以我会从 300 个查询开始，获取每所房子的经纬度，将它们代入 Haversine 公式（例如）以获取 45,000 个无序对之间的距离，然后对它们进行排序以按地理距离获得最近的对. 然后，有了一些可能的候选人，您可以开始通过另一组对 Google API 的调用来检查步行距离。

于 2011-04-08T23:44:29.333 回答
1

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

于 2011-04-09T13:24:06.513 回答
1

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

在此处输入图像描述

而且你想包括大约 100k 的房子......好吧，至少我听说，像这样的程序是在谷歌地图中引入的限制之前制作的。在这种情况下，限制只会咬紧牙关。

如果您有所有房屋的地理位置，那么当您像鸟一样飞翔时，您可以根据地球上的点有多远来预测。基于此对它们进行排序，并找到最佳预测的结果。

编辑：添加了 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));
}
于 2011-04-09T00:18:24.500 回答
1

我会使用这个公式：

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

在乌鸦飞翔时按距离对所有 45,000 所房屋进行排名。然后，我将获取按最短距离排名的前 250 个结果，并通过谷歌运行它们以获得准确的步行距离并重新排名。

于 2011-04-09T09:23:55.450 回答