在图形学中判断一个点是否在多边形内，若多边形不是自相交的，那么可以简单的判断这个点在多边形内部还是外部；若多边形是自相交的，那么就需要根据非零环绕数规则或者奇-偶规则判断。
判断多边形是否是自相交的：多边形在平面内除顶点外还有其他公共点
-
奇-偶规则（Odd-even Rule）：奇数表示在多边形内，偶数表示在多边形外。
从该点p任意方向的一条射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。
-
非零环绕数规则（Nonzero Winding Number Rule）：若环绕数非零则表示在多边形内，否则是外部点。
首先使多边形的边变为矢量。将环绕数初始化为零。再从该点p作任意方向的一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，每当多边形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。**。处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点。
举例
-
判断点p是否在多边形内，从点p向外作任意方向的一条射线，多边形的边从左到右经过射线时环数减1，多边形的边从右往左经过射线时环数加1，最后环数不为0，即表示在多边形内部。
image -
如下图所示，左侧表示用奇-偶规则判断绕环数为2 ，表示在多边形外，所以没有填充。右侧图用非零绕环规则判断出绕数为2，非0表示在多边形内部，所以填充。
image -
左侧为奇-偶规则，右侧为非零环绕数规则，实心区域表示在多边形内部，空心区域表示在多边形外部。
image
PS
- Winding rules
| Winding rule | Description |
|---|---|
| NSNonZeroWindingRule | Count each left-to-right path as +1 and each right-to-left path as -1. If the sum of all crossings is 0, the point is outside the path. If the sum isnonzero, the point is inside the path and the region containing it is filled. This is the default winding rule. |
| NSEvenOddWindingRule | Count the total number of path crossings. If the number of crossings is even, the point is outside the path. If the number of crossings is odd, the point is inside the path and the region containing it should be filled. |
非零环绕数规则和奇-偶规则（Non-Zero Winding Number Rule&&Odd-even Rule）在iphone中应用:
1.CGContextClip 使用非零环绕数规则来判断当前路径和裁剪路径的交集。
2.CGContextEOClip 使用奇-偶环绕数规则来判断当前路径和裁剪路径的交集。
注意下图中起点到终点的虚线可看作是多边形的一条边：
UIBezierPath的userEvenOddFillRule 是对路径来说的，对于CAShapeLayer的填充效果是没有作用的，CAShapeLayer的填充效果只和自己的自己的fillRule和其内部路径的走向有关，其fillRule 有 even-odd 和 non-zero。
参考：
Cocoa Drawing Guide
非零环绕数规则和奇-偶规则
作者：MichaelLedger
链接：//www.greatytc.com/p/9fd7b2fc51c7
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
