我花了一段时间寻找一个可靠的算法,在球体上进行时区查找,但是我甚至没有找到好的伪代码,更不用说c/c++了。我将讲述我所发现的内容,并提供可以相对容易地组合在一起的资源。
这个问题被称为
"点在多边形内"。
一个经常使用的简单POP算法是
"射线投射"。在二维平面上的POP依赖于一个无限远点。在平面上,这非常容易。有无数个无限远点。随便选一个!但是在球体上却没有这样的点。
如果你有一个已知的点位于任何给定查询多边形的内部或外部,那么你就可以摆脱这个问题。考虑到你的使用情况,这并不是一个繁琐的要求:你可以轻松地选择海洋中的任何一个
单独的点,这将位于
所有陆地多边形之外。
我认为"绕数"POP算法也会失败,因为在球面上你可以从两个方向接近任何边缘。
一个算法
我想要一种不需要辅助点和启发式方法(用于从边缘数据生成辅助点)的方法。如果我很诚实,我之所以想要这样做,是因为我相信这应该是可能的,而不是因为我真正需要它。
对于您的用例,您可以使用通常的射线投射算法和已知在海洋中的单个点,因此您不需要依赖于启发式方法,尽管它们可能仍然有效。
我提出的方法如下...
- 您需要自己循环遍历多边形。对于每个多边形...
- 找到一个通过查询点并穿过多边形的至少一条边缘的大圆(两个角之间的中点即可)。
- 将大圆与多边形的边缘相交。
- 当您按顺序沿其边缘行走时,多边形内部在您的右侧(如果您喜欢,则在左侧)。这使得每个交点都具有足够的信息,以知道内部或外部在哪一侧。
- 从最近的交点,您可以确定查询点是内部还是外部。
实现提示
如果您打算实现此算法(或任何其他POP算法),请不要尝试使用正弦或余弦。
将您的点(多边形角和查询点)表示为单位向量。将您的大圆(多边形边缘和查询点所在的圆)表示为垂直于大圆所在平面的单位向量。使用点积和叉积。不要考虑角度。请考虑向量。
这应该不会太难 - 我没有完全需要实现它。如果您希望进行自由职业编写,请联系我!
可用于构建解决方案的链接
c++ boost库有一个POP实现,但我不是很喜欢,这主要是因为我是个完美主义者——我想它在几乎所有情况下都能满足需求。
tz_world数据库包含陆地多边形,还有GeoJSON变体。您可以使用内置的NSJSONSerialization
类来很好地解析它。
这里有一些NASA的点和球的算法(虽然我不喜欢他们的POP)。