多邊形內外點判斷算法在電力智慧工地中的應用

王迎春，王義春，侯艷權，郭樹強，張 帆

(1.國網黑龍江省電力有限公司七臺河供電公司，黑龍江 七臺河 154600; 2.東北電力大學 計算機學院，吉林 吉林132012)

0 引 言

近年來，電網規模不斷擴大，工程安全性問題也成為了重中之重。為了滿足日益增長的安全性需求，智慧工地在電網行業得到了廣泛的應用。智慧工地即通過物聯網技術獲取工地中的現場視頻等實時數據進行提取分析，以達到降低事故發生概率等目的。其提取處理的內容包括對獲取的視頻中的人物進行目標檢測、越界檢測等。越界檢測是防止施工現場的工人走出安全區產生危險的一個解決辦法，但傳統的越界檢測中，安全區域一般固定為矩形，不能滿足電力工程中復雜的施工環境，難以解決工地中工人走出安全區進入高壓危險區域的問題，所以提出將多邊形內外點判斷算法應用于電網智慧工地中的越界檢測，將多邊形作為安全區域的邊界，通過目標檢測確認目標工人的一點，通過該點是否在多邊形內部的判斷實現工人是否越界的判斷，完成安全區域內工人的越界檢測，提高電力施工的安全性。

判斷目標點是否在多邊形內是計算機視覺中的傳統問題，主要應用于地理信息系統等方面。該問題自提出后，得到了眾多學者的關注。目前主要有文獻[1-2]提出的射線法、文獻[3]提出的夾角之和檢驗法、文獻[4]提出的面積和法等，這些算法雖過程簡單、空間復雜度較低，但是算法的時間復雜度較高，應用到實際項目中時耗時嚴重。因此，在二叉空間分隔(Binary Space Partitioning, BSP)樹的基礎上進行多邊形內外點判斷算法的改進，提高判斷速度以應用于實際問題中。

1 傳統多邊形內外點判斷算法

1.1 射線法

射線法是最早提出的多邊形內外點判斷算法，判斷過程如下[5]：

1)判斷目標點A(x0,y0)與多邊形的頂點P(xi,yi),(i=1,2,...,n)是否相同或目標點是否在多邊形的邊上，若都不在則進行下一步。

2)計算|y0-yi|的最小非0值，記為my；計算|x0-xi|的最大值，記為Mx。

3)由目標點引出1條射線，為了避免射線與多邊形頂點相交，將射線斜率定為my/2Mx。所以射線參數方程為R=(x0,y0)+k(2Mx,my),(0

4)將應用射線法將判斷點與多邊形的關系轉換為判斷該射線和多邊形的邊的交點數。計算交點數需計算D1(D-D1)>0和D2(D-D2)>0，其中：

5)算出交點個數，若為奇數則點在多邊形內，若為偶數則點在多邊形外。

1.2 傳統基于BSP樹的多邊形內外點判斷算法

1.2.1 BSP樹的原理和構建

BSP樹是一種空間分割樹，它主要用于游戲中的場景管理，尤其是室內場景的管理。它的本質是二叉樹，也就是用一個面把空間分割成兩部分，分割出的空間則繼續用面分割，以此類推，直到達到特定遞歸深度，或者空間中不再有物體或只剩下1個物體。

應用于二維空間的BSP的基本原理是將所有平面建成一棵樹，每個平面都將它所在的空間分為2個部分，空間位于平面的前后位置決定了代表空間的節點在樹中的位置。

傳統基于BSP樹進行點在多邊形內外判斷的算法將BSP樹應用于二維空間進行分區[6]：假設給出平面P及直線方程ax+by+c=0，該直線穿過平面并將平面分成兩個部分,直線的法向量n(a,b)指向的一側為正，而另一側為負。用BSP樹來表示分區結果：樹中的每1個節點表示1條分割平面的直線，節點的左子樹表示正側，右子樹表示負側；每1個分割的區域都可以由另外的直線再次分割，遞歸下去最后得到的區域由樹的葉子節點表示。如圖1的多邊形分區后由圖2的二叉樹表示，多邊形中a代表分區直線，p代表所分區域。

圖1 多邊形分區結果

圖2 BSP樹表示結果

1.2.2 算法流程

傳統基于BSP樹的多邊形內外點判斷算法的流程如下所述：

1)給定1個任意的簡單多邊形，根據多邊形的具體形狀以及頂點坐標進行垂直分解，形成多條垂直掃描線，每2條掃描線形成1個垂直區域并結合BSP樹構建的方法構建1顆BSP樹以表示這些垂直區域。

2)利用多邊形的邊作為劃分直線，基于劃分直線兩邊的區域個數構成1棵與多邊形的邊有關的BSP樹。

3)在判斷目標點是否在給定的多邊形中時，用建好的垂直區域部分的BSP樹查找目標點所在的垂直范圍，如果查找到，利用邊部分的BSP樹確定目標節點所在的具體區域，從而可以判斷出目標點是否在多邊形內部。

傳統算法的時間復雜度不穩定，當BSP樹的每個節點只有左子樹或右子樹時，樹結構會退化為鏈表，時間復雜度會上升。

2 多邊形內外點判斷算法的改進及應用

2.1 改進多邊形內外點判斷算法的流程

為了防止BSP樹退化為鏈表，首先對多邊形各個頂點的橫坐標值進行歸并排序，其次用二分法遍歷已經有序頂點的垂直直線，最后建立垂直區域的BSP樹。經過排序再遍歷可以使最后形成的BSP樹為平衡二叉樹，不會退化為鏈表，具體流程如下。

1)假定給出任意的簡單多邊形Q，如圖3所示。

圖3 簡單多邊形Q

2)根據多邊形的最大及最小坐標值，建立多邊形的外包圍盒，如圖4所示。

3)對多邊形Q的各個頂點的橫坐標值進行歸并排序并用二分法對有序的豎直直線進行遍歷，構建垂直區域的平衡二叉樹。由于使用二分法進行遍歷，所以從邊a7開始處理。a7的x1將多邊形劃分為2個區域，而a7的x2將其中1個區域又劃分為2個部分，如圖5所示。

圖4 簡單多邊形的外包圍盒

圖5 被x1與x2分割后的包圍盒

4)劃分完1個垂直區域后，將這個區域之中的多邊形的邊插入，使得1個區域被劃分為若干個梯形區域。如圖6所示，劃分完垂直區域后，生成垂直區域的BSP樹，再將邊a7插入，即將a7按其所對應的區域插入BSP樹中。

圖6 插入邊a7的結果

5)對于余下各邊，均采取同樣的方式進行處理，將每一個垂直區域和垂直區域內的若干梯形區域都使用BSP樹進行管理，多邊形的處理結果如圖7所示，所構建的二叉樹如圖8所示。

6)構建好二叉樹后，判斷點和多邊形的關系，首先在垂直區域的BSP樹查找目標點所在的垂直區域，確定了垂直區域后，再查找相應邊的BSP樹，最后確定點是否在多邊形內部。

圖7 插入所有邊的結果

圖8 改進算法后構建的二叉查找樹

2.2 改進多邊形內外點判斷算法的實現

算法的輸入為任意簡單多邊形，輸出為判斷點是否在多邊形內的結果，具體步驟如下：

1)讀入離散點和多邊形；

2)構造多邊形的外包圍盒；

3)對多邊形的端點橫坐標值排序；

4)用二分法遍歷排序后端點的垂直分割線，構建垂直區域的BSP樹；

5)遍歷多邊形的邊，將邊插入到對應垂直區域的BSP樹中，生成與邊有關的BSP樹；

6)在BSP樹中查找目標點并給出結果。

2.3 算法的特殊情況

當要查詢的目標點正好位于劃分直線上，即多邊形的邊上時，將該點進行單獨處理。將該點分別左移、右移一小段距離，兩次移動后分別對移動后的點是否在多邊形內再次進行判斷。若兩次結果都在多邊形內(外)部，則說明移動前該點在多邊形內(外)部；若兩次結果不一致，則采用其他方法進行判別。

2.4 算法的實驗結果及應用

所提算法在研究點是否在多邊形內時，分為創建BSP樹和查找兩個階段。在創建BSP樹時，對多邊形各個頂點的橫坐標值進行排序，由于使用的是歸并排序，所以時間復雜度為O(nlgn)；創建多邊形對應的BSP樹的時間復雜度為O(nlgn)；所以，創建BSP樹的時間復雜度是O(nlgn)。創建完成后，對點是否在多邊形內部進行判斷，在垂直區域的BSP樹中查找目標點所在的垂直區域，由于排序之后是平衡二叉樹，所以時間復雜度為O(lgn)；確定點屬于的垂直區域后，對確定的垂直區域對應的邊的BSP樹進行查找，假定每個垂直區域包含m條邊(一般m

將算法應用到電力智慧工地中時，根據應用場景的實際情況，選擇在能拍到目的區域的點處安裝攝像頭，并提前對攝像頭能拍攝到的區域圖像做劃分處理，用坐標的方法在圖像中劃分出安全區。以圖9場景為例進行越界檢測，畫線區域內部為安全區，畫線外部為危險區域。

圖9 越界檢測實驗場景

在對工人的目標檢測方面，首先，把VGG16卷積神經網絡模型在ImageNet數據集上進行參數初始化；其次，在CVC行人數據庫的數據集(數據集地址：http://www.cvc.uab.es/adas/site/?q=node/7)上訓練基于VGG16的SSD檢測模型；最后，在攝像頭傳輸的視頻中，每秒抽取24幀圖像作為檢測圖像，對工人進行目標檢測。將檢測結果返回回歸框的左上角和右下角的坐標點，提取回歸框下邊界的中心點，再進一步利用改進多邊形內外點判斷算法判斷工人是否越過安全區。

射線法、傳統多邊形內外點判斷算法與改進多邊形內外點判斷算法的時間對比結果如表1所示，表中數據為各個算法的相對運行時間。根據表1可知，改進多邊形內外點判斷算法的判斷速度更快。將改進多邊形內外點判斷算法應用于電力智慧工地中進行工人是否越過安全區的判斷，試驗結果表明，該算法能有效地解決工人越界問題，使電力智慧工地中的安全區域劃分更加精準，并提高施工安全性。

表1 不同算法的判斷時間對比Table 1 Comparison of judgment time under different algorithms ms

3 結 語

對改進多邊形內外點判斷算法進行闡述，并將改進算法與傳統算法等進行對比實驗，比較判斷時間后給出實驗結果，結果表明改進算法比傳統算法的判斷速度快。同時，將改進算法應用到電力工程領域，用于實際的行人越界檢測，檢測結果表明該算法可以有效判斷行人是否跨出安全區，提高了電力工程的安全性，有較大的實用價值。