基于耳切法的三維模型區域標繪

韓曉明，馮孟奇，褚飛黃，白瑞婷

（國能數智科技開發（北京）有限公司，北京 100011）

三維綜合集成展示系統項目在當前的安全監控領域中具有重要的應用價值。為了實現對設備的有效管理和監控，準確而高效的區域標繪與設備框選技術成為項目中的關鍵環節。然而，現有的安防標繪方法和設備框選技術在處理復雜場景、準確性和效率等方面仍然存在一定的挑戰。耳切法作為一種經典的計算幾何算法[1]，通過用戶標記的方式，可以構建出精確的區域模型來框住設備，同時具有較高的計算效率。本文將探索如何將耳切法應用于智能安防項目中，并評估其在實際應用中的性能和效果。本文的主要目的是設計和實現一個基于耳切法[2]的三維綜合集成展示系統三維區域標繪與設備框選系統。本文將詳細介紹耳切法的原理和算法，并提出相應的改進和優化方法以適應實際應用場景。通過大量的實驗和評估，驗證該系統在準確性、效率和用戶體驗等方面的優勢，并與其他相關方法進行比較分析，期望能為三維綜合集成展示系統三維區域標繪與設備框選提供一種高效準確的解決方案，促進三維綜合集成展示系統領域的進一步發展。

1 三維區域標繪的意義

在三維數字仿真系統中，區域標繪和設備框選是其中最為重要的一部分。通過三維區域標繪，可以以直觀的方式清晰地呈現復雜的工廠三維實景，提供直觀的信息剖析。通過精確的標繪和設備框選，可以準確地定位設備的位置并提供精確的區域信息，有助于系統的快速定位和監控設備。此外，通過建立三維區域模型，還可以進行區域設備之間的空間關聯性分析，有效幫助優化布控和安防策略。

2 技術研究思路

在現有的三維系統中，區域標繪和設備框選主要使用手動標繪、基于深度學習的目標檢測和基于點云處理的算法。

手動標繪是通過人工方式在三維場景中繪制區域標記和設備框選。雖然具備靈活性，但占用一定的人力和時間。

基于深度學習的目標檢測是利用深度學習技術，如卷積神經網絡（CNN）和目標檢測算法，自動檢測和框選設備。這種方法可以實現自動化和高效性，但對于復雜場景和低質量數據存在一定挑戰。

基于點云處理的算法利用點云數據處理和分析技術，如點云分割、點云配準等進行區域標繪和設備框選。這種方法適用于三維點云數據，可以提取特定形狀和特征進行標繪和框選。

結合三維綜合集成展示系統的實際應用情況和對標繪算法的研究與比較，本文選擇了耳切法作為標繪的技術方案。

3 區域標繪

在三維仿真系統中，區域標繪的操作方式一般是用戶通過在場景中標繪點，然后系統根據這些點迅速構建出一個多邊形或者多邊體。通常情況下，用戶標繪的點數通常是四個，以構建一個規整的矩形，系統在標繪結束后才會進行繪制。在我們的拓展中，用戶可以任意標繪，且當用戶標繪的點數達到可以構建一個三角面時，系統就開始進行繪制，并支持增刪改的操作。各種多邊形，在三維中都是通過用戶輸入的點構建非鏤空的面。構建簡單多邊形的主要因素是通過點構建三角面，再通過組合三角面形成簡單多邊形。因此，最關鍵的是構建三角面，而構建三角面最重要的是對三角面頂點的排序。要實現通過標繪的點實時有序地構建一個非鏤空的多邊形是一項非常復雜的任務。耳切法恰好是解決三維圖形頂點排序的一種算法。[3]

4 耳切法

4.1 簡介

在本算法中有一個問題，就是將簡單多邊形進行轉化，變為一組的三角形集合，三角形的所有頂點與原頂點相同。

簡單多邊形的簡介如下：由一組有序點構成頂點，頂點設為P0 至Pn-1。兩兩頂點間均由邊（Pi，Pi-1）依次相連，并且最后一條邊（Pn-1，P0）將連接第一個點，每個頂點有且僅有連接兩條邊，邊與邊的交點均為頂點，如此組成的一個形狀為簡單多邊形。如圖1，圖中的三個圖形解釋了這個概念。可以看出，只有第一個是簡單多邊形，其他部分只是多邊形。我們需要將一個完整的多邊形拆分為多個小的三角形，由n 個頂點組成的簡單多邊形能夠根據幾何學原理劃分為n 減2個三角形[4-6]。耳切法（Ear Clipping）就是用來實現這個目標的算法，其復雜度為O(n^2)。

圖1 簡單多邊形實例

4.2 Ear Clipping

簡單多邊形的“耳朵”是一個特定的三角形。該三角形由多邊形中相鄰的三個頂點Pn、Pn+1 和Pn+2組成的，并且在該三角形內部不包含其他頂點。Pn 和Pn+2 之間的連線被稱為多邊形的對角線，其中點Pn+1則被稱為耳尖。根據這個特性，我們可以將大的簡單多邊形拆分為n-2 個小三角形，然后通過查找耳尖并將其所代表的三角形移除來實現拆分過程。

在耳切法的具體實現中，第一步是存儲多邊形的數據，在此采用的是雙向鏈表[7]結構，雙向鏈表的結構可以減少移除耳朵的時間復雜度，構建鏈表的所占的復雜度為O(n)。第二步是對所有頂點進行遍歷以查找出所有耳朵，需對每個頂點Pi 所在的圍繞該頂點的三角形進行檢測，判斷是否有頂點在三角形內部。如果沒有，則Pi 是一個耳朵，否則不是。在實際計算中，需要構建四個鏈表，其中兩個是線性鏈表，兩個是循環鏈表。其中線性鏈表用于存儲凹頂點和凸頂點。通過計算兩邊的夾角來確定頂點的類型，夾角大于180 度則為凹頂點，小于180 度則為凸頂點。另外兩個循環鏈表一個用于存儲所有頂點的數據，另一個用于存儲所有耳尖頂點。

首先計算凹凸頂點，將耳尖與凸頂點相同，然后移除耳尖。如果通過耳尖構建的三角形中存在其他頂點，則將該頂點從耳尖列表中移除。然后對耳尖進行遍歷，每次遍歷都移除一個耳尖。由于移除一個耳尖后，其相鄰的點會發生變化，因此需要判斷相鄰的點是否發生改變，如果發生改變，則需要更新相關列表。

通過圖1 中的簡單多邊形，我們可以演示耳切法的實現過程和構建。首先通過計算得到兩個凹頂點集合R={0,1,3,4,6,9}和C={2,5,7,8}，它們與耳尖相同。然后計算不屬于耳尖的頂點，最后得到耳尖集合E={3,4,6,9}。

遍歷循環依次移除耳尖頂點。移除耳尖3 后，我們可以觀察到耳尖所代表的三角形T1=<2,3,4>被移除，然后對與頂點3相關聯的頂點進行判斷是否為耳尖，并更新列表，再次移除耳尖。重復這個過程直到耳尖列表為空，最后我們可以看到將圖1 中的簡單多邊形根據耳尖拆分為多個三角形。圖2 展示了耳切法移除耳尖的過程：

圖2 耳切法的實現表現過程

在三維物體的構建過程中，每個需要顯示的物體都由多個頂點（點的數量大于等于3）構建基本的三角面，然后通過組合這些面構建整個物體。簡單的平面三維物體由四個點構成的兩個三角面組合而成。通過耳切法的處理，通過對多個頂點進行計算，我們可以獲得多個三角形以及三角形頂點的排列順序。這樣就可以在三維空間中構建一個簡單多邊形的三維物體。（如圖3 所示）

圖3 耳切法最終結果

5 耳切法在三維展示系統中的應用

在三維展示系統中，區域標繪是一個不可或缺的組成部分，其主要功能是通過用戶點擊的點來構建一個立體的區域，并將其以三維形式展示出來。通過應用耳切法對用戶標繪的點進行計算，可以快速獲得簡單多邊形的頂點排列順序，從而能夠迅速地繪制用戶標繪的區域。這種方法可以實現實時展示和實時編輯修改功能。（如圖4 所示）

圖4 耳切法在三維展示系統的應用

6 結語

通過本次研究和應用，我們充分利用了耳切法來解決三維展示系統中區域標繪的多邊形構建問題，極大地提高了拆分三角形的效率。在區域標繪設備的框選功能中，大大增強了標繪的效率，解決了用戶在標繪過程中受限于規定的點數和形狀的限制，為用戶提供了更好的標繪體驗。這種方法大大增強了三維展示系統的豐富性和實用性。

通過以上研究成果，我們為三維展示系統的區域標繪功能提供了一種高效且靈活的解決方案，為用戶提供了更好的操作體驗。在未來的研究和應用中，我們可以進一步探索耳切法在其他領域的應用，并不斷改進和優化算法，以滿足不同場景下的需求。