文章程式碼顯示

2018年7月4日 星期三

一起學 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 行的交點計算。


圖(7)


圖(8)


圖(9)

第 51 行的地方是求出向左水平射線與線段的交點,使用到一個幾何概念如 圖(10)


圖(10)

第 53 行判斷交點 x 是否在 Px 的左側,是的話 count = count +1

第 60 行判斷點是否在多邊形上(在多邊形上也被認為不在多邊形內部)

最後,在第 68~71 行判斷交點的數量,若為奇數則回傳 True (代表點在多邊形内)

執行結果 : 

待測點為(2,0)



待測點為(3,1)



待測點為(5,-1)



待測點為(4.5,5)



待測點為(4,4)



待測點為(3.5,5)


補充 :

實際上我這篇文的目的是要幫助我篩選資料的,如下圖展示,效果很不錯


原始資料


判斷後


參考連結

判斷一個座標點是否在不規則多邊形內部的算法
判斷點是否在多邊形內 (附C實現代碼)
python 实现 射线法 判断一个点在图形区域内外
python3射线法判断点是否在多边形内
判断点是否在多边形内的算法



↓↓↓ 連結到部落格方針與索引 ↓↓↓

Blog 使用方針與索引