algorithm - 确定给定的纬度/经度是否在美国境内

Question

如何确定给定的纬度/经度是否在美国境内？我希望后端代码在美国境内以一种方式运行，在美国境外以另一种方式运行。由于应用程序的要求，此处不提供 IP 地理定位。

理想情况下，我希望在不影响外部服务的情况下发生这种情况。

Answer 1

如果您将美国表示为多边形，则可以使用“多边形中的点”算法，例如 crossing number test , 以测试该点是否位于多边形内。对于具有 n 个边的多边形，这种类型的查询在 O(n) 时间内运行。

如果您想要更快但近似的东西，您可以通过四叉树之类的东西对多边形进行(离线)空间分解，并确定树中的哪些叶盒位于边界内。对于具有 n 个框的树，找到一个点的封闭叶框的平均(在线)运行时间将为 O(log(n))。

希望这对您有所帮助。