半工室 Arduino Python NodeMCU: 一起學 Python 100 : 判斷(待測)點是否在一個任意多邊形內部

def isPointinPolygon(point, rangelist):  #[1,0.8] [[0,0],[1,1],[0,1],[0,0]] 
    # 判断是否在多邊形内，如果不在， 返回false
    Xlist = []
    Ylist = []
    Px = point[0]
    Py = point[1]


    # 初步判定法(是否在矩形框內)
    for i in range(len(rangelist)):
        Xlist.append(rangelist[i][0]) #抓X
        Ylist.append(rangelist[i][1]) #抓Y
    maxX = max(Xlist)
    minX = min(Xlist)
    maxY = max(Ylist)
    minY = min(Ylist)    
    print( "(%1.1f,%1.1f) -> (%1.1f,%1.1f)" % (minX, minY, maxX, maxY) )    
    if (Px > maxX or Px < minX or #判斷X
        Py > maxY or Py < minY):  #判斷Y
        return False


    # 射線法(以左射線共奇數個交點為例)
    count = 0
    point1 = rangelist[0] #假設第一個點 
    for i in range(1, len(rangelist)):
        
        point2 = rangelist[i]
        print("i=%d, p1 = (%1.1f,%1.1f), p2 = (%1.1f,%1.1f)" % (i,point1[0],point1[1],point2[0],point2[1]) )
        
        # 在頂點上
        if (Px == point1[0] and Py == point1[1]) or (Px == point2[0] and Py == point2[1]):
            print("在某個頂點上")
            return False
        

        # 水平射線穿過兩頂點之一，忽略不重新計算(若沒這步會使得這個點被認為是2個交點)
        elif ( Py == min ( point1[1],point2[1] )):
            print("pass")
            point1 = point2
            continue

        # 判斷水平射線是否會穿過兩點之間，若有則繼續算
        if (point1[1] < Py and point2[1] >= Py) or (point1[1] >= Py and point2[1] < Py):
            # 求水平射線跟 p1,p2 連線 之交點的 x
            # x = p2.x - d
            # d = a*b/c
            # a = p2.y-Py
            # b = p2.x - p1.x
            # c = p2.y - p1.y
            x = point2[0] - (point2[1] - Py) * (point2[0] - point1[0])/(point2[1] - point1[1])
            print("Intersection : (%d,%d)" % (x,Py) )
            if ( x < Px): # 若左水平射線與p1,p2連線的交點，在待測點左側，則 count = count +1
                print("count++")
                count +=1
            elif ( x > Px):
                print("another side")
            
            # 點在多邊形上
            if ( x == Px):
                print("點在多邊形上")
                return False
            
                
        point1 = point2
        
    print("Number of intersection point = %d"%count)
    if count%2 == 0:
        return False
    else:
        return True


if __name__ == '__main__':
    print(isPointinPolygon([4,4], [ [0,0],[1,0],[2,1],[3,0],[4,-1],[5,0],[5,5],[4.5,6],[4,5],[3,4],[2.5,6],[2,5],[0,5],[0,0] ] ))

首先，我們先畫出一個任意多邊形

圖(1)

我們的任務是給一個待測點座標 (Px,Py) ，判斷這個點是否在這個多邊形內，主要採用的演算法為"射線法"

射線法指出，當某一個待測點往左(或往右)射出一條無限長的水平射線，若這個射線與整個多邊形具有 "奇數" 個交點，則待測點在多邊形內；若為 "偶數" 個交點(包含0個) 則待測點在多邊形外部。

我們可以藉由將任意 N 邊形分解成為 N 個線段，去計算每一個線段跟待測點的交點(也有可能不存在交點)，最後加總起來就能算出待測點跟這個任意 N 邊形有幾個交點(只計算待測點水平向左射線)

程式碼 9~20 行指出，先抓出多邊形的所有頂點，接著找出最大(最小) X 以及最大(最小) Y ，這樣我們可以構成一個矩形窗如下圖

圖(2)

程式碼中 18~20 行判斷了待測點是否在這個初步判定矩形窗內，若否則回傳 False (也就是待測點不在多邊形內)

程式碼第 26 行以一個 for 迴圈為主體，將 N 邊形的每個線段(由兩個座標點 P1 、 P2組成) 抓來獨立計算。

程式碼第 31~34 行很好理解，我們判斷待測點 (Px,Py) 與 P1、P2 是否相等，若相等則代表待測點在頂點上。

程式碼第 37~41 行為一個特別的 Case 。，其向左水平射線這好穿過某個 "頂點"

圖(3) 可以想像成圖(2) 的 (4,5) 到 (3,4) 的線段

圖(4) 可以想像成圖(2) 的 (3,4) 到 (2.5,6) 的線段

例如在圖(3)、圖(4) 我們發現待測點的向左水平射線都會穿過線段的頂點，若以圖(2) 來說就是都穿過 (3,4)

在後續的演算法(44行後)我們將去判斷水平射線與線段的交點，但在此我們就先做一個前置判斷。若情況如圖(3) 或圖 (4) 的情況，我們將使用 continue 來略過後續 for 迴圈的計算(也就是不計算交點了)

而如果情況是圖(5) 及圖(6)

圖(5) 可以想像成圖 (2) 的 (1,0) 到 (2,1) 的線段

圖(6) 可以想像成圖 (2) 的 (2,1) 到 (4,-1) 的線段

則會繼續後續的求交點演算法(44行後)，得到交點數量 = 2
但因為射線法是判定交點數量是否是奇數，所以不會出現誤判的狀況

hint : 奇數+偶數(2) = 奇數 ; 偶數 + 偶數(2) = 偶數

程式碼第 44~52 行就是求交點的算法，首先在 44 行進行一個判斷式，該判斷式判斷了水平射線是否會穿過某個線段如圖(7) ，若為圖(8) 或 (9) 的狀況，就不會進行 51~62 行的交點計算。