【转】详谈判断点在多边形内的七种方法

news/2024/5/19 4:51:58/文章来源:https://www.cnblogs.com/lmst-ytt/p/16720595.html

原帖地址: https://blog.csdn.net/WilliamSun0122/article/details/77994526

射线法
时间复杂度：O（n）适用范围：任意多边形
算法思想：
以被测点Q为端点，向任意方向作射线（一般水平向右作射线），统计该射线与多边形的交点数。
如果为奇数，Q在多边形内；
如果为偶数，Q在多边形外。计数的时候会有一些特殊情况，如图

图片已经把特殊情况和算法实现说的很清楚，具体可看代码注释。

hdu1756-射线法代码

角度和判断法
时间复杂度：O（n）适用范围：任意多边形
感觉这个方法和之后要介绍的转角法类似，个人感觉转角法就是这个方法的优化变形。不推荐这个算法。这个算法对精度的要求很高（会造成很大精度误差），不强调多边形点给出顺序，我用这个算法没过hdu1756(http://acm.hdu.edu.cn/showproblem.php?pid=1756)。

算法思想：
连接被测点与多边形所有顶点所形成的所有角的角度和在精度范围内等于则该点在多边形内，否则在多边形外。

转角法
时间复杂度：O（n）适用范围：任意多边形
个人感觉是O（n）算法的第二推荐，该算法本来对精度要求较高，之后会有一个改进让其不用考虑精度误差，不过该算法要强调多边形点给出的顺序。
一般博客都以多边形正向即逆时针介绍，我这里也主要介绍逆时针，但hdu1756是顺时针给出，我会在括号中介绍一下顺时针（其实本质是一样的），顺时针具体在代码注释中提一下。不会画图，希望大家看了思想自己画图体会一下。

算法思想：
转角法非常简单，按照多边形顶点逆时针顺序，从P点到顶点Vi分别做连线，其中αi为Vi和Vi+1之间的夹角。其中α角度逆时针为正，顺时针为负，这样所有到顶点做连线之间夹角和为(环绕数)0，这点P在多边形外部，否则在内部。（感觉和角度和判断法本质一样，加了个方向）
（顺时针就是角度顺时针为正，逆时针为负）

直接环绕数的推导会需要用到反三角函数，这样即会耗时又会造成较大的精度误差，所以这里有一个优化。
从P点向右做射线R，如果边从射线R下方跨到上方，那么穿越+1，如果从上方跨到下方，则是-1。最终和为wn环绕数。如下图所示：
（写博客的时候才发现其实本质不就是射线吗，不过理解后代码会感觉写的比射线简单）

这种方法不必去计算射线和边的交点，但需要判断点P和边的左右关系，而且对于方向向上和向下的边的判断规则不同。对于方向向上的边，如果穿过射线，那么P是在有向边的左侧；

方向向下的边如果穿过射线，那么P在有向边的右边（意思是说判断点P与边的关系，而不是相对坐标系内位置）。

这里有一点要注意，如下图

这里射线经过了BC和CD并穿过C点，但是要计算两次，一次+1一次-1，代码中会有体现。

改进弧长法
时间复杂度：O（n）适用范围：任意多边形
该算法感觉是转角法的另一种优化，也解决了传统转角法的精度问题，也要求多边形点给出的顺序。

算法思想：
以被测点O为坐标原点，将平面划分为4个象限，对每个多边形顶点P[i]，计算其所在的象限，然后顺序访问多边形的各个顶点P[i]，分析P[i]和P[i+1]，有下列三种情况：
1. P[i+1]在P[i]的下一象限。此时弧长和加；（代码中+1）
2. P[i+1]在P[i]的上一象限。此时弧长和减；（代码中-1）
3. P[i+1]在Pi的相对象限。利用叉积res=OP[i]xOP[i+1]计算OP[i]与OP[i+1]的关系。
若f=0，OP[i]与OP[i+1]共线，点在多边形边上；若f<0，OP[i]在OP[i+1]逆时针方向，弧长和减（代码中-2）；若f>0，OP[i]在OP[i+1]顺时针方向，弧长和加（代码中+2）。

叉积（点线）判断法
时间复杂度：O（n）适用范围：凸多边形

对于多边形（正向，即逆时针），如果一个点它的所有有向边的左边，那么这个点一定在多边形内部。利用叉积正好可以判断点与给定边的关系，即点是在边的左边右边还是边上。
这里说一下，（P叉乘Q）P^Q>0说明P在Q的顺时针方向，<0说明P在Q的逆时针方向，=0说明P和Q共线。

面积法
时间复杂度：O（n）（但是时间应该会比之前的O（n）的长一点）
适用范围：凸多边形

了解即可，有精度要求，强调多边形点给出的方向（逆时针）。
算法思想：
如果点在多边形内部或者边上，那么点与多边形所有边组成的三角形面积和等于多边形面积。多边形的面积可以用叉积计算即连接坐标原点和各顶点形成向量，所有向量叉积的0.5的和即为多边形面积。不过计算面积是会有一定误差的，需要设置精度的误差范围。

二分
时间复杂度：O（）适用范围：凸多边形
强掉多边形给出的方向。

这种方法以hrbust1429为例。题目链接
这道题的题意是已知构成凸多边形A的n个点的坐标，和点集B的m个点的坐标，求这B的m个点是否都在凸多边形A内（严格内部，就是点不能在多边形边上）。

算法思想：
1. 选择多边形其中一个点为起点，连接其它点作射线。

2. 判断给定的点是否在所有射线包围的区域之内，即判断给定点是否在最左侧射线的左边，或者在最右侧射线的右边。
3. 如果在射线包围的区域之内，选择构成最两侧的射线的点为left和right，则mid = (left+right)/2，连接给顶点和起点作射线，判断该射线在mid点和起点的哪一边，不断循环，如此用二分法最后求出给定点所在的三角形区域，由此确定了除起点外的一条边。