点在地球地球上的多边形

Question

我有一个定义多边形的坐标列表(纬度,经度).它的边缘是通过将两个点与弧相连接而创建的,弧是这些点之间的最短路径.

我的问题是确定是否有另一个点(让我们称之为U)放入或放出多边形.我一直在寻找网络几个小时寻找一个完整的算法,不会有任何缺陷.这就是我希望我的算法支持和接受什么(就可能的弱点而言):

1. 地球可以被视为一个完美的球体(据我所知,它导致0.3%的精度损失,我很好).
2. 它必须正确处理跨越国际日期变更线的多边形.
3. 它必须正确处理跨越北极和南极的多边形.

我决定实施以下方法(作为适用于2D场景的光线投射算法的修改).

1. 我想选择多边形之外的点S(纬度,经度).
2. 对于定义单个边的每对顶点,我想计算大圆(让我们称之为G).
3. 我想计算一对点S和U的大圆.
4. 对于第2点中定义的每个大圆,我想计算这个大圆是否与G相交.如果是这样,我将检查交叉点是否位于多边形的边缘.
5. 我将计算有多少个交叉点,并根据它(偶数/奇数)我将决定点U是否在多边形的内部/外部.

我知道如何实现计算从点2到5,但我没有线索如何选择起点小号.它在2D平面上并不那么明显,因为我不能只选择最左边点左边的点.

关于如何选择这一点(S)以及我的方法是否合理且最佳的任何想法？

感谢您的任何意见!

Answer 1

如果你的多边形是局部的，你可以只取与地球球体在B点相切的平面，然后计算多边形顶点在该平面上的投影，这样问题就变成了二维问题。

当您在投影中用直线逼近球面弧时，此方法会引入一个小误差。如果你的多边形很小，它可能是微不足道的，否则，你可以在进行投影时沿着圆弧添加中间点。

您还应该考虑B对跖点上的多边形，但考虑到多边形方向或检查B和某个多边形顶点之间的距离，这些多边形可能会被丢弃。

最后，如果您必须为此查询太多点，您可能需要选择一些固定的投影平面（例如，形成包裹球体的八面体的投影平面）并预先计算多边形在其上的投影。您甚至可以为每个索引创建一些二维索引结构作为四叉树，以加快查找速度。