判断点在凸多边形内

方法有很多。主要看的是射线法和二分判断的方法。大多数解决此类问题的方法的时间复杂度是O(n), n是顶点的个数。

射线法的思路挺清晰,首先任意一条直线与任意一个多边形相交的话,其交点都为偶数个然后我们就可以用一条起点是待测点,向左方向(也就是x负方向)的射线,求它与多边形的交点个数,若为奇数个则在多边形内,否则在多边形外。如下图,左边的那个射线与多边形有5个交点,说明该测试点在多边形内,事实也是如此。
《判断点在凸多边形内》

而二分判断则可以如图所示做一个三角剖分,然后二分出点在哪个三角区域内,再判断是否在三角形内。

另外注意套模板的时候,给的多边形的点的方向是顺时针还是逆时针。
《判断点在凸多边形内》

先简单补一些基础知识:

判断两个向量之间夹角是顺时针还是逆时针。利用平面向量的叉乘:a = (x1,y1) b = (x2,y2) a×b = x1y2 – x2y1 若结果为正,则向量b在a的顺时针方向;否则,在a的逆时针方向;若结果为0,则a与b共线 注:两向量之间夹角以小于180度计算

以一道例题为例。

射线法(TLE)代码:

二分后的AC代码

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注