如何找到一个点是否在使用球拍的多边形内

Question

我正在开发一个项目，在特定的纬度和经度坐标下输出该点所在的邻域。我有经纬度坐标在一个城市内的几个街区的边界。我必须从文件中读取邻域数据，并从文件中读取测试点。我正在使用Racket编程语言。

到目前为止，我已经能够读取文件并为每个邻域创建一个点列表，现在我被卡住了。我想为每个邻域创建一个多边形，然后有一个方法来检查点是否位于该多边形内。但是，我无法弄清楚如何使用Racket来做到这一点。

任何人都可以帮助我找出如何解决，如果一个点是在多边形内，或者更好的方法来解决问题？

Answer 1

我现在不会发布任何代码，因为我不想解决作业/任务。不过，我会发布一些提示。

看看下面的图片：

我们怎样才能知道C是边缘OA和OB和D是外部之间？它很简单：我们比较一些角度：如果OC和OA之间的角度小于OB和OA之间的角度，那么C明显更接近于OA，而不是OB。

现在，我们如何才能知道只有一些向量的角度？我们可以使用单调的余弦：它随着参数的增加而减小。因此，OC和OA之间的角度的余弦大于OB和OA之间的角度的余弦，这又大于OD和OA之间的角度的余弦。

下一步是弄清楚如何计算余弦。矢量点产品有助于：它的值是角度乘积的余弦值，大于操作数长度的乘积。那就是：

cos(OC; OA) = dotproduct(OC; OA)/(length(OA) * length(OC)) 

在2D的dotproduct很简单：

dotproduct(OC; OA) = (C.x - O.x) * (A.x - O.x) + (C.x - O.x) * (A.x - O.x) 

结合上述所有你应该有一个简单的测试，以检查你的观点是否在同样的情况C或D ：比上一个边更靠近一个边。

现在，您必须对多边形的每个边重复此操作，然后完成。如果测试是谓词，则可以使用fold执行此操作。

注意：这只适用于多边形是凸的。对于凹多边形，您需要添加更多测试。

秒注意：在图中，会发生什么，如果D或C或者两者都是OA线以下？想想这个，并检查它是否意味着对上述fold方法进行了一些更改。

后记：在几周内，我会发布一个完整的代码，假设任务结束。另外，那时我会在上面的注释中回答这个问题。