在圖形學(xué)中判斷一個(gè)點(diǎn)是否在多邊形內(nèi)迷雪，若多邊形不是自相交的诈乒，那么可以簡(jiǎn)單的判斷這個(gè)點(diǎn)在多邊形內(nèi)部還是外部；若多邊形是自相交的梧奢，那么就需要根據(jù)非零環(huán)繞數(shù)規(guī)則或者奇-偶規(guī)則判斷。
判斷多邊形是否是自相交的：多邊形在平面內(nèi)除頂點(diǎn)外還有其他公共點(diǎn)
-
奇-偶規(guī)則（Odd-even Rule）：奇數(shù)表示在多邊形內(nèi)钧椰，偶數(shù)表示在多邊形外粹断。
從該點(diǎn)p任意方向的一條射線，若與該射線相交的多邊形邊的數(shù)目為奇數(shù)嫡霞，則p是多邊形內(nèi)部點(diǎn)，否則是外部點(diǎn)希柿。
-
非零環(huán)繞數(shù)規(guī)則（Nonzero Winding Number Rule）：若環(huán)繞數(shù)非零則表示在多邊形內(nèi)诊沪，否則是外部點(diǎn)。
首先使多邊形的邊變?yōu)槭噶吭贰h(huán)繞數(shù)初始化為零端姚。再?gòu)脑擖c(diǎn)p作任意方向的一條射線。當(dāng)從p點(diǎn)沿射線方向移動(dòng)時(shí)挤悉，對(duì)在每個(gè)方向上穿過射線的邊計(jì)數(shù)渐裸，每當(dāng)多邊形的邊從左到右穿過射線時(shí)，環(huán)繞數(shù)加1装悲，從右到左時(shí)昏鹃，環(huán)繞數(shù)減1。處理完多邊形的所有相關(guān)邊之后诀诊，若環(huán)繞數(shù)為非零洞渤，則p為內(nèi)部點(diǎn)，否則属瓣，p是外部點(diǎn)载迄。
舉例
-
判斷點(diǎn)p是否在多邊形內(nèi)讯柔，從點(diǎn)p向外作任意方向的一條射線，多邊形的邊從左到右經(jīng)過射線時(shí)環(huán)數(shù)減1护昧，多邊形的邊從右往左經(jīng)過射線時(shí)環(huán)數(shù)加1魂迄，最后環(huán)數(shù)不為0，即表示在多邊形內(nèi)部惋耙。
-
如下圖所示极祸，左側(cè)表示用奇-偶規(guī)則判斷繞環(huán)數(shù)為2 ，表示在多邊形外怠晴，所以沒有填充遥金。右側(cè)圖用非零繞環(huán)規(guī)則判斷出繞數(shù)為2，非0表示在多邊形內(nèi)部蒜田，所以填充稿械。
-
左側(cè)為奇-偶規(guī)則，右側(cè)為非零環(huán)繞數(shù)規(guī)則冲粤，實(shí)心區(qū)域表示在多邊形內(nèi)部美莫，空心區(qū)域表示在多邊形外部。
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. |
非零環(huán)繞數(shù)規(guī)則和奇-偶規(guī)則（Non-Zero Winding Number Rule&&Odd-even Rule）在iphone中應(yīng)用:
1.CGContextClip 使用非零環(huán)繞數(shù)規(guī)則來判斷當(dāng)前路徑和裁剪路徑的交集梯捕。
2.CGContextEOClip 使用奇-偶環(huán)繞數(shù)規(guī)則來判斷當(dāng)前路徑和裁剪路徑的交集厢呵。
注意下圖中起點(diǎn)到終點(diǎn)的虛線可看作是多邊形的一條邊：
UIBezierPath的userEvenOddFillRule 是對(duì)路徑來說的，對(duì)于CAShapeLayer的填充效果是沒有作用的傀顾，CAShapeLayer的填充效果只和自己的自己的fillRule和其內(nèi)部路徑的走向有關(guān)襟铭，其fillRule 有 even-odd 和 non-zero。
