如何使用Racket查找点是否在多边形内部
我正在开发一个项目,给定一个特定的纬度和经度坐标,输出该点所在的邻域.我有一个纬度和经度坐标,构成一个城市内几个街区的边界.我必须从文件中读取邻域数据,并从文件中读取测试点.我正在使用Racket编程语言.
到目前为止,我已经能够读取文件并为每个社区创建一个点列表,现在我被卡住了.我想为每个邻域创建一个多边形,然后有一个方法检查一个点是否位于该多边形内.但是,我无法弄清楚如何使用Racket这样做.
任何人都可以帮我找到如果一个点在该多边形内部如何解决,或者可能是解决问题的更好方法？
我现在不会发布任何代码,因为我不想解决作业/作业.但是,我会发布一些提示.
看下面的图片:
我们怎样才能知道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如果测试是谓词,则可以使用a来执行此操作.
注意:这仅在多边形为凸面时才有效.对于凹多边形,您需要添加更多测试.
二注:在图中,会发生什么,如果D还是C或者两者都是低于OA行？考虑一下,检查它是否意味着对上述fold方法进行了一些更改.
最后一点:几周后,我会发布一个完整的代码,假设作业结束了.此外,那时我将回答上述说明中的问题.