最近遇到的一个需求是判断点是否在任意多边形内部，其实这是计算机几何比较基础的问题，一般处理涉及图形、图像的库都会有这功能实现，有射线法、角度法；由于不打算引入第三方库就打算自己动手实现，使用射线法完成。
这次打算先介绍算法，再附上源码和注解。
射线法就是，从待判断的点引出一条射线，记录射线与多边形边界的交点的个数为n，如果n是奇数，则点在内部，如果n是偶数，则点在外部，第一次是比较迷糊的，因为有个隐含条件是，在无穷远处是多边形的外部。那知道点最后的状态和点穿越的次数，就可以推断出初始的位置转态了。
理解完算法的思想之后，剩下的就是实施过程中的细节及特殊情况（点在边界上、射线经过多边形顶点、多边形某条边与射线重合。。。）的处理了。其实多边形是由多条线段首尾相连形成的闭合形状，线段是由两个不重合的点及两点之间组成的，如果我们定义，射线与**“线段”**内部和上端点相交时计数一次，那么就没有所谓的特殊情况了，如图。

python 源码

//判断点是否在多边形内
class Point():
	def __init__(x,y):
		self.x = x
		self.y = y
	def isInPolygon(polygon):
		// 使用水平射线检测
		n = len(polygon.pointList)
		nCross = 0
		for i in range(n):
			p1 = polygon.pointList[i]
			p2 = polygon.pointList[(i+1)%n]
			// 特殊情况：边界p1p2 与 y=p0.y平行，不计数
    		if (p1.y == p2.y) continue;  
    		// 交点在p1p2延长线上，注意是小于，不计数
    		if (self.y < min(p1.y, p2.y)) continue;  
    		// 交点在p1p2延长线上，注意是大于等于，不计数  
    		if (self.y >= max(p1.y, p2.y)) continue;  
    		// 求交点的 X 坐标；根据相似三角形计算
    		crossx = (self.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;  
		   // 只统计单边交点  
		    if (x >= self.x)  
		      nCross++;    
		 return (nCross % 2 == 1); 
		      
class Polygon():
	def __init__(pointList):
		// 逆时针或者顺时针点集合
		self.pointList = pointList