确定重叠地理区域的算法

Question

我有一个点的纬度和经度，使用半径计算出一个圆圈范围。我还有地理区域（在本例中是州）的纬度和经度边界。我想知道圆的任何区域是否与任何地区相交。

基本上我想要的结果是，如果一个点（地理编码地址）距离任何一个州的中心小于x英里，那么它将返回该州。

我相信有一种算法可以找到这个，但我不知道从哪里开始寻找。

- Josh

---

你如何表示你的状态？ - Nobody moving away from SE

州的数据来自谷歌的地理编码 API。例如，伊利诺伊州的数据将来自此 URL：http://maps.googleapis.com/maps/api/geocode/xml?address=IL,%20United%20States&sensor=false - Josh

Answer 1

使用Haversine公式：

a = sin²(Δlat/2) + cos(lat1)*cos(lat2)*sin²(Δlong/2)
c = 2*atan2(√a, √(1−a))
d = R*c

JavaScript：

var R = 6371; // km
var dLat = (lat2-lat1)*Math.PI / 180;
var dLon = (lon2-lon1)*Math.PI / 180;
var lat1 = lat1*Math.PI / 180;
var lat2 = lat2*Math.PI / 180;

var a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

这将为您提供任意两点之间的大圆距离。其余部分取决于您如何表示状态。

- tskuzzy

---

这是一些疯狂的公式。我从未考虑过地球的曲率，本以为它是平的，但这绝对很棒。给你点赞。 - Mike

我检索到的状态是近似矩形边界，不必精确到100％，但Google的地理编码API返回边界为：<southwest> <lat>36.9702980</lat> <lng>-91.5130789</lng> </southwest> <northeast> <lat>42.5083379</lat> <lng>-87.0199349</lng> </northeast> 我不认为Haversine在这种情况下适用，因为我不是要确定点之间的距离，而是要确定给定半径内的任何点是否落在矩形边界内。 - Josh

@Josh：你可以测试点到矩形每个点的距离，如果每个点都不符合条件，你可以测试该点是否在矩形内（这些步骤可以交换）。如果两者都失败了，你可以计算与给定距离相隔的点，并且正好位于你的点的北、南、西、东方向，并测试它们是否在矩形内。如果所有这些测试都失败了，则该状态不在你的点的范围内。如果其中一个测试没有失败，则该状态在范围内。 - Nobody moving away from SE

Answer 2

如果您的帖子被标记为Java而不是PHP，我就不会试图重新发明轮子，而只需使用JTS（Java拓扑套件），创建一个几何体并调用该方法。

public boolean intersects(Geometry g)

我对PHP不是很了解，所以无法告诉您是否有类似的PHP库。

这些几何图形来自哪里？如果您的几何图形存储在像PostGIS这样的数据库中，您也可以尝试调用一些底层函数，例如数据库调用。

- EPSG31468

Answer 3

http://en.wikipedia.org/wiki/Quad_tree

这是任何类型的二维空间关系相关问题的绝佳起点。

- joshx0rfz

---

地球不是二维欧几里得空间，因此四叉树不适用于此。 - tskuzzy

Answer 4

如果您想确定一个点是否在圆内，可以使用勾股定理。在下面的代码中，传递您的圆的centre_x、centre_y和半径，然后是您要评估的点的x、y坐标。

def in_circle(centre_x, centre_y, radius, x, y):
    square_dist = (centre_x - x) ** 2 + (centre_y - y) ** 2
    return square_dist <= radius ** 2

- Ina

---

这并没有考虑到地球的曲率。 - tskuzzy