Question

怎样判断一个点在多边形内

Answer 1

如何判断一个点是否在多边形内部？
（1）面积和判别法：判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形，相等则在多边形内部。
（2）夹角和判别法：判断目标点与所有边的夹角和是否为360度，为360度则在多边形内部。
（3）引射线法：从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。
具体做法：将测试点的Y坐标与多边形的每一个点进行比较，会得到一个测试点所在的行与多边形边的交点的列表。在下图的这个例子中有8条边与测试点所在的行相交，而有6条边没有相交。如果测试点的两边点的个数都是奇数个则该测试点在多边形内，否则在多边形外。在这个例子中测试点的左边有5个交点，右边有三个交点，它们都是奇数，所以点在多边形内。

Answer 2

对于凸多边形而言（以三角形ABC为例），假设存在一个点D，若这个点在三角形的内部，则以该点为起点，和原多边形的任意两个连续的且尊照多边形组成方向
的点（如DAB、DBC、DCA）组成的三角形讲都是一个方向，如DAB和DBC都是顺时针方向。若这个点在三角形的外部，则会出现DAB、DBC、DCA三个三角形方向不一致的情形，即其中有一个不同于另外两个（如一个顺，两个逆）。到这里我们就知道了如何判断一个点在一个三角形内部的算法，总结一下就是通过判断该点同三角形连续两点组成三角形的顺逆性（归于面积的正负）来得到结果的。
实际上，对于其他的凸多边性也可以用一样的方法，只是这个时候判断的三角形的数目增加了，不管怎么样，只要点在多边形内部他们的顺逆都是一样的。对于凹多边形而言，情况就要相对复杂一些了。此时，判断一个点是否在其内部的计算量会增加比较多。具体算法如下：此时三角形一个个的判断可能会失效，我们应当两个同时判断。即判断该点是否同时在多边形的连续两个三角形之中，相当于是求两个三角形的交集，直到完成多边形封闭。例如，判断P点是否在多边形ABCD之中，依次判断P是否在ABC-BCD、BCD-CDA、CDA-DAB、DAB-ABC各个成对三角形中，P在ABC-BCD中表示P在ABC-BCD的交集之中。这样就可以判断一个点是否在一个凹多边形内部了。
以上说的仅仅是简单多边形而已，在复杂多变形之中（如内洞、飞地等），还要通过多边形的拓扑运算来得到结果。另外，在凸边形中，还可以进行优化：可以以一个点为中心，分裂多边形为最少个数的三角形，从而得到改进。