一種基於概率統計的任意多邊形相交面積計算方法與流程
2023-10-05 13:18:59 1
本發明涉及計算機圖形圖像處理面積計算領域，具體涉及一種基於概率統計的任意多邊形相交面積計算方法。
背景技術：
平面多邊形相交面積的應用非常廣泛，在計算機圖形學、計算幾何學及計算流體力學等領域都需要計算相交多邊形共同覆蓋區域的面積。
現有的多邊形相交面積計算方法一般是是由計算機的通用處理器(CPU)以串行處理方式來實現。近年來，在計算機動畫、虛擬實境等領域，為了表現更豐富的細節，現有基於CPU的串行處理方法在多邊形相交面積計算應用中已無法滿足快速實時的需求。
目前，GPU即圖形處理器，以其強大的運算能力在圖形處理方面得到了廣泛應用，與CPU的串行處理方法不同，GPU的優勢在於其並行處理機制，因此在處理速度方面優勢明顯。但是，現有技術中，針對多邊形相交面積計算，尚缺乏基於GPU處理完成多邊形相交面積的工程實現方法。
另外，從相交多邊形的形狀來看，現有的多邊形相交面積計算方法大多針對凸多邊形的相交面積進行計算，而對於凹多邊形的相交，多數計算方法需要先對凹多邊形進行三角化或凸化細分。由於細分工作本身較複雜且會帶來更多的邊做相交測試，這大大增加了計算量，尤其是對於含有較多凹點或交點數量較多的多邊形更是如此。因此，現有技術在進行凹多邊形相交面積計算時耗時多、工作量大、效率低，與凸多邊形相交面積計算相比，對凹多邊形相交面積的計算顯得力不從心。。
技術實現要素：
本發明的目的是針對上述現有技術的不足，而提供一種基於概率統計的任意多邊形相交面積計算方法，既提高多邊形相交面積計算的處理速度，又可以不受多邊形形狀的限制，可以針對任意形狀和數量的多邊形相交而計算相交面積。
為解決上述技術問題，本發明採用的一個技術方案是：提供一種基於概率統計的任意多邊形相交面積計算方法，所述計算方法包括如下步驟：
(1)在柵格場中確定一個柵格區域，並對所述柵格區域初始化，將所述柵格區域內各柵格對應的位置標示符的值均預設為初始值a，a≥0；
(2)在所述柵格區域內生成第一個多邊形柵格圖像，將以頂點坐標表示的第一個多邊形對應轉換為由GPU處理的以柵格表示的第一個多邊形柵格圖像，若所述柵格區域內任一柵格位於所述第一個多邊形柵格圖像的內部或邊線上，則將所述柵格對應的位置標示符的值累加b變為a+b，b≥1，否則，若所述柵格區域內任一柵格位於所述第一個多邊形柵格圖像的外部，則所述柵格對應的位置標示符的值不作累加；
(3)繼續生成第2～n個多邊形柵格圖像，按照步驟(2)所述方法順次在所述柵格區域內繼續生成其餘n-1個多邊形柵格圖像，n≥2，其中，在生成每一個當前多邊形柵格圖像時，若所述柵格區域內任一柵格位於所述當前多邊形柵格圖像的內部或邊線上，則將所述柵格對應的位置標示符的值累加b，否則，若所述柵格區域內任一柵格位於所述當前多邊形柵格圖像的外部，則所述柵格對應的位置標示符的值不作累加；
(4)統計n個多邊形柵格圖像的相交柵格數count'，在所述柵格區域內隨機獨立選取m個柵格，統計這m個柵格中位置標示符的值為a+nb的柵格的數目count'；
(5)計算n個多邊形的相交面積S，將所述相交柵格數count'除以所述隨機獨立選取的柵格數m，然後再乘以所述柵格區域的面積，即得到所述n個多邊形的相交面積S。
在本發明另一個實施例中，步驟(1)中的所述柵格區域為所述的整個柵格場，所述柵格場的面積為SArea，則所述n個多邊形的相交面積S為：
在本發明另一個實施例中，確定所述n個多邊形柵格圖像在所述柵格場中所佔用的柵格圖幅是由GPU處理完成的，具體方法是：確定所述n個多邊形在X方向坐標的最大值Vxmax和最小值Vxmin，以及所述n個多邊形在Y方向坐標的最大值Vymax和最小值Vymin，則由Vxmax、Vxmin和Vymax、Vymax確定的柵格範圍即為所述的柵格圖幅；且所述n個多邊形在X方向坐標的最小值Vxmin柵格化後位於所述柵格圖幅從左至右的第一列，最大值Vxmax柵格化後位於所述柵格圖幅從左至右的最後一列，所述n個多邊形在Y方向坐標的最小值Vymin柵格化後位於所述柵格圖幅從下至上的第一行，最大值Vymax柵格化後位於所述柵格圖幅從下至上的最後一行。
在本發明另一個實施例中，所述步驟(4)中統計m個柵格中位置標示符的值為a+nb的柵格的數目由GPU處理完成，或者由GPU通過軟體環境OpenGL中的像素讀取函數將隨機選取的m個柵格及其對應的位置標示符的值傳送到CPU後由CPU處理完成。
在本發明另一個實施例中，所述CPU為Inter Core(TM)i5-3337U處理器，所述GPU為NVIDIA GeForce GT 620M，作業系統為Microsoft Windows 7、軟體環境OpenGL為OpenGL 4.4.0。
在本發明另一個實施例中，所述步驟(2)和(3)中將以頂點坐標表示的多邊形對應轉換為由GPU處理的以柵格表示的多邊形柵格圖像的方法為：在OpenGL軟體環境中構建轉換處理函數，向所述轉換處理函數順次輸入所述多邊形所有順序排列的頂點坐標，所述轉換處理函數輸出的即為所述各頂點坐標按照輸入順序首尾相連構成的所述以柵格表示的多邊形柵格圖像。
在本發明另一個實施例中，所述柵格場的解析度包括256×256、512×512、1024×1024、2048×2048，所述隨機獨立選取的柵格數m為所述柵格場解析度的40％、50％或者60％。
在本發明另一個實施例中，所述初始值a＝0，b＝1。
本發明的有益效果是：本發明基於概率統計的任意多邊形相交面積計算方法是一種新穎高效的多邊形相交面積計算方法，該方法藉助於GPU來實現任意多邊形的柵格化，將以頂點坐標表示的多邊形轉換為以柵格表示的多邊形柵格圖像，再根據圖像的相交情況對所有柵格的位置標示符進行賦值、修正，再在柵格區域中隨機選取m個隨機柵格來模擬整個柵格場，統計m個隨機柵格中相交柵格的數目，最後再計算相交面積。該方法的優點如下：
(1)將多邊形柵格化，利用柵格數據進行處理，不受多邊形凹凸性的限制；另外，由於柵格數據是將幾何空間作為整體進行描述，它以規則的陣列來表示空間對象，數據直接記錄柵格的顯示特徵，而所在位置則根據行列號轉換為相應的坐標，不受空間對象形狀的影響，具體空間對象的複雜程度不影響數據量的大小，因此處理起來也更簡便；
(2)利用了GPU的並行特性，與藉助於CPU的計算方法相比，大大提升了處理速度，並且原理簡單，實現方便；
(3)利用少量隨機柵格來模擬柵格區域進一步提高了時間性能。
經過實驗結果表明，本發明的計算方法適用於任意複雜多邊形，計算方法在相交測試部分很好的避免了傳統計算方法所遇到的邊界問題，從而具有較好的魯棒性。
附圖說明
圖1為本發明基於概率統計的任意多邊形相交面積計算方法一實施例的流程圖；
圖2為本發明基於概率統計的任意多邊形相交面積計算方法另一實施例中兩個多邊形柵格圖像相交實施例的示意圖；
圖3為本發明基於概率統計的任意多邊形相交面積計算方法另一實施例中運用的蒙特卡羅計算定積分的原理示意圖；
圖4為本發明基於概率統計的任意多邊形相交面積計算方法另一實施例中實驗驗證採用的有「洞」多邊形示例圖。
具體實施方式
為了便於理解本發明，下面結合附圖和具體實施例，對本發明進行更詳細的說明。附圖中給出了本發明的較佳的實施例。但是，本發明可以以許多不同的形式來實現，並不限於本說明書所描述的實施例。相反地，提供這些實施例的目的是使對本發明的公開內容的理解更加透徹全面。
需要說明的是，除非另有定義，本說明書所使用的所有的技術和科學術語與屬於本發明的技術領域的技術人員通常理解的含義相同。在本發明的說明書中所使用的術語只是為了描述具體的實施例的目的，不是用於限制本發明。本說明書所使用的術語「和/或」包括一個或多個相關的所列項目的任意的和所有的組合。
圖1是本發明基於概率統計的任意多邊形相交面積計算方法一實施例的流程圖。
首先，需要說明的是，圖1所示實施例是基於GPU處理實現對圖形圖像的處理，而GPU處理直接與圖形圖像的顯示場景密切相關，因此本發明實施例相應涉及到柵格、柵格場等概念。這裡的柵格是指對圖形圖像進行數位化處理後的最小顯示單元，每一個柵格對應一個顯示像素，眾多柵格以縱橫陣列形式所構成的顯示區域稱之為柵格場，因此柵格場通常也是指顯示屏幕。例如，像素為248×248的顯示屏就對應指有248×248個柵格的柵格場。
另外，本發明實施例的優勢還在於柵格場中是對柵格數據進行處理的基礎，而柵格數據是一種面向空間的表示方法，柵格數據結構要比矢量數據結構(這裡的矢量數據是一種面向實體的表示方法，它是以坐標的形式來表示空間物體)更加適合計算機進行處理。柵格數據是將幾何空間作為整體進行描述，它以規則的陣列來表示空間對象，數據直接記錄柵格的顯示特徵，而所在位置則根據行列號轉換為相應的坐標，不受空間對象形狀的影響，空間對象的複雜程度不影響數據量的大小。而矢量數據結構是通過記錄坐標的方式儘可能精確地表示點、線和多邊形等具體的空間物體，但是物體越複雜，描述就越困難，數據量也隨之增大。因此，比較而言，柵格數據要比矢量數據結構簡單得多，基於空間的幾何分析也相對容易。
本發明實施例中，將以矢量數據表示的多邊形轉化為以柵格數據表示的多邊形柵格圖像的過程即為柵格化。本實施例要利用GPU進行相交面積計算也是基於柵格數據實現的。
如圖1所示，該實施例的方法包括如下步驟：
步驟S1:在柵格場中確定一個柵格區域，並對該柵格區域初始化，將柵格區域內各柵格對應的位置標示符的值均預設為初始值a，a≥0。
這裡，步驟S1的目的是完成對柵格場的初始化。如上所述，柵格場是指整個顯示區域或顯示屏幕，而在對圖形相交面積計算中，相交圖形在顯示屏幕上顯示並不一定佔據整個屏幕，因此只需選定一個合理的區域即可，這個顯示區域實際上是由各個相交多邊形佔有的顯示區域共同決定的，在該顯示區域內能夠包括各個相交多邊形，同時這個顯示區域儘可能小，這樣有利於提高處理速度。這個顯示區域就是步驟S1中需要確定的柵格區域。
另外，步驟S1中柵格對應的位置標示符的含義是指在柵格場中的每一個柵格都對應一個位置標識符，該位置標識符屬於一種柵格數據。例如，在一個有248×248個柵格的柵格場中，若將左下角頂點的第一個柵格對應的位置標識符表示為rct(0，0)，其中第一個0表示橫向坐標，第二個0表示縱向坐標，因此臨近該頂點柵格的上方一個柵格的位置標識符表示為rct(0，1)，而臨近該頂點柵格的右方一個柵格的位置標識符表示為rct(1，0)，以此類推。對柵格對應的位置標示符進行賦值是為了表示該柵格的顯示特徵，例如rct(0，0)＝0可以表示該頂點柵格沒有顯示任何內容，即空白顯示，而rct(0，0)＝1可以表示該頂點柵格有顯示內容。優選的，在本發明實施例中我們可以規定若一個柵格位於一個多邊形柵格圖像所圍成的區域內或者在該多邊形柵格圖像的邊線上，則該柵格的位置標識符的值為1或者在原有值的基礎上加1，若該柵格位於該多邊形柵格圖像所圍成的區域外部(即不在該多邊形柵格圖像的內部和邊線上)，則該柵格的位置標識符的值為0或者對原有值不做任何運算。
步驟S1中只是對確定的柵格區域內各柵格對應的位置標示符的值進行了初始賦值，並且預設為初始值a，a≥0。優選的，a＝0。
進一步的，我們可以看出，對於步驟S1，需要確定一個合理的柵格區域，這個柵格區域既可以是整個柵格場，也可以是通過GPU根據待計算相交面積的所有多邊形所確定的柵格圖幅。這裡，柵格圖幅為由待計算相交面積的所有這些多邊形經過柵格化後在柵格場中所確定的柵格範圍。
為此，本發明實施例提供一個確定柵格圖幅的優選實施例：首先，對於以矢量數據表示的這些多邊形的所有頂點的坐標，確定這些多邊形在X方向上坐標的最大值和最小值分別為Vxmax、Vxmin，在Y方向上坐標的最大值和最小值分別為Vymax、Vymin；然後，在這些相交多邊形柵格化過程中，X方向坐標的最小值Vxmin柵格化後位於柵格圖幅從左至右的第一列，最大值Vxmax柵格化後位於柵格圖幅從左至右的最後一列，Y方向坐標的最小值Vymin柵格化後位於柵格圖幅從下至上的第一行，最大值Vymax柵格化後位於柵格圖幅從下至上的最後一行。
對於該柵格圖幅的面積，則為(Vxmax-Vxmin)x(Vymax-Vymin)。
圖1中，完成步驟S1後進入步驟S2：對計算任意多邊形相交面積的第一個多邊形柵格化，在柵格區域內生成第一個多邊形柵格圖像，即將以頂點坐標表示的第一個多邊形轉換為由GPU處理的以柵格表示的第一個多邊形柵格圖像，並修正該多邊形柵格圖像對應各柵格的位置標示符的值，若該柵格區域內任一柵格位於第一個多邊形柵格圖像的內部或邊線上，則將該柵格對應的位置標示符的值在初始值a的基礎上進行一次累加操作變為a+b，b≥1；否則，若該柵格區域內任一柵格位於第一個多邊形柵格圖像的外部，則該柵格對應的位置標示符的值不變。
步驟S2開始對第一個相交多邊形進行處理，包含兩個過程，第一個過程是柵格化的過程，即以頂點坐標表示的第一個多邊形轉化為柵格數據表示的第一個多邊形柵格圖像，這裡，頂點坐標屬於一種矢量數據，而柵格數據是指柵格顯示的像素特徵數據，比如由灰度、亮度、色彩等特徵數據；第二個過程是柵格的位置標示符賦值的過程，主要是針對第一個多邊形柵格圖像的內部(包括邊線)和外部加以區分，在其內部的柵格對應的位置標示符進行累加操作而改變這些位置標示符的值，在其外部的柵格對應的位置標示符不進行任何操作而保持另外這些位置標示符的值不變。
這裡，第一個柵格化的過程是由GPU處理完成的，實際應用中可以通過圖形圖像開發軟體環境OpenGL中的glBegin、glEnd專用函數來實現，其過程是通過這些專用函數將第一個多邊形的頂點坐標順次輸入。優選的，這裡的多邊形是指由同一平面上不同的點首尾順次連接，任一個頂點都在邊上，且任意不相鄰的兩條邊不相交所構成的空間圖形，因此包括了凸多邊形和凹多邊形。這樣，經過柵格化之後，第一個多邊形就轉化為柵格圖像，即第一個多邊形對應的第一個多邊形柵格圖像。
優選的，步驟S2中累加操作值b為1，當步驟S1中的a值為0時，則經過步驟S2之後，在第一個多邊形柵格圖像內部(包括邊線)的所有柵格對應的位置標示符的值為1，而在第一個多邊形柵格圖像外部的柵格對應的位置標示符的值為0。
以下一段處理程序示例是在OpenGL軟體開發環境下實現對多邊形的柵格化處理：
glBegin(GL_POLYGON)；
glVertex2d(pPoint1[0].x,pPoint1[0].y)；
glVertex2d(pPoint1[1].x,pPoint1[1].y)；
glVertex2d(pPoint1[2].x,pPoint1[2].y)；
glVertex2d(pPoint1[3].x,pPoint1[3].y)；
glEnd；
其中，glBegin(GL_POLYGON)表示開始柵格化處理，glVertex2d(pPoint1[0].x,pPoint1[0].y)至glVertex2d(pPoint1[3].x,pPoint1[3].y)表示順次輸入多邊形所有順序排列的頂點坐標，可見該示例的多邊形是有四個頂點的四邊形，glEnd表示柵格化處理結束。
在OpenGL軟體開發環境下，通過上述處理程序示例即可完成對輸入的以頂點坐標表示的多邊形轉換為由GPU處理的以柵格表示的多邊形柵格圖像，這已經是柵格化的過程。此時，這個經過轉化後的四邊形柵格圖像裡面的每一個柵格此時對應的位置標示符都變為了1(傳入之前為0)。然後，在後續步驟中可以繼續通過glBegin(GL_POLYGON)和glEnd這樣的函數語句傳入下一個多邊形，如果存在相交，則相交部分的位置標示符的值會不斷的累加。
圖1中，在步驟S2實現對第一個多邊形的處理之後，進入步驟S3完成後續對其他多邊形的處理:按照與步驟S2相類似的方法依次對其餘n-1個多邊形柵格化，繼續生成第2～n個多邊形柵格圖像，n≥2，並修正每個多邊形柵格圖像對應各柵格的位置標示符的值；其中，在生成每一個當前多邊形柵格圖像時，若柵格區域內任一柵格位於當前多邊形柵格圖像的內部或邊線上，則將該柵格對應的位置標示符的值累加b，否則，若柵格區域內任一柵格位於當前多邊形柵格圖像的外部，則該柵格對應的位置標示符的值不變。
步驟S3是順次對輸入的每一個多邊形進行柵格化處理和位置標示符的賦值處理，在步驟S2已經對第一個多邊形進行了處理，步驟S3是對後續的多邊形進行處理，其目的是要計算n個多邊形相交的面積，因此步驟S3主要是針對後續n-1個多邊形，並且，對其中每一個多邊形都是獨立處理的。當正在處理其中某一個多邊形時，該多邊形對應生成的多邊形柵格圖像即為當前多邊形柵格圖像。
比如，在生成第2個多邊形柵格圖像時，如果某一柵格位於第2個多邊形柵格圖像的內部或邊線上將該柵格對應的位置標示符的值做一次累加運算，即累加b，b優選為1，否則，不做累加運算。至於之前該柵格是否在第1個多邊形柵格圖像內部(包括邊線)還是外部，並不影響對第2個多變形柵格圖像的處理。因此，上述步驟S2和步驟S3相結合對多個多邊形順次處理的方法保證了對每一個多邊形柵格圖像處理的獨立性，同時也能保證最終對這n個多邊形相交面積的計算。
由上述過程可知，在該柵格區域內，如果某一個柵格沒有與任何一個多邊形柵格圖像相交，則其對應的位置標示符的值仍為初始值0，如果某一個柵格只位於任意一個多邊形柵格圖像的內部或邊線上，則其對應的位置標示符的值為1，如果位於任意兩個多邊形柵格圖像的內部或邊線上，則其對應的位置標示符的值為2，如果位於任意三個多邊形柵格圖像的內部或邊線上，則其對應的位置標示符的值為3，……由此類推，如果某一個柵格位於n個多邊形柵格圖像的內部或邊線上，則其對應的位置標示符的值為n。需要說明的是，由於本發明的目的是要計算n個多邊形的相交面積，那麼只有位置標示符的值為n的柵格才是我們要統計計算的。
本步驟的多邊形柵格化仍由GPU通過OpenGL中語句glBegin(GL_POLYGON)和glEnd順序傳入對應的多邊形坐標頂點來實現，如果存在相交，則相交部分柵格的位置標示符的值會不斷的累加。
以圖2中兩個多邊形相交(即n為2)為例進行說明，如圖2所示，假定該圖中第一個輸入的是一個四邊形，第二個輸入的是五邊形，本實施例中所選的柵格區域為這兩個多邊形所確定的柵格圖幅。具體過程如下：
首先經過步驟S1對柵格區域Screen1進行初始化，各個柵格的位置標示符賦初始值0；
然後經過步驟S2，在該柵格區域Screen1內轉化生成的第一個多邊形柵格圖像T1，即在柵格區域Screen1內傳入四邊形，通過上述步驟S2中程序示例的方式對該四邊形柵格化處理，同時將該柵格圖像T1內部或邊線上的柵格進行一次累加操作，使其位置標示符的值從初始值0變為1，而四邊形柵格圖像T1區域外的柵格的位置標示符的值均為初始值0。
再經過步驟S3，在該柵格區域Screen1內轉化生成的第二個多邊形柵格圖像T2，即以同樣的方式在柵格區域Screen1內傳入五邊形，在傳入該五邊形的過程中，對相關柵格的位置標示符的值進行修正，對處於該五邊形柵格圖像T2的內部或邊線上的柵格進行一次累加操作，由圖2可知進行累加操作的柵格分為兩部分，一部分是兩個圖像的相交部分，這部分柵格的位置標示符的值經過了兩次累加變為2，另一部分是未與四邊形柵格圖像T1相交的部分，這部分柵格的位置標示符累加一次變為1，處於該五邊形柵格圖像T2區域外的柵格不做處理。可以看出，柵格M1對應的位置標示符的值為2，表明該柵格M1的位置標示符經歷了兩次累加操作，而該柵格M1正好也是第一個多邊形柵格圖像T1和第二個多邊形柵格圖像T2相交的柵格。因此，通過柵格的位置標示符的累加後的結果值可以判斷多邊形柵格圖像相交的情況，而且這種判斷方法實現簡單，也不受多邊形是凸多邊形或凹多邊形等形狀的限制，增強了該方法的應用的魯棒性。
通過以上三個步驟完成了對多邊形柵格圖像相交的柵格的確定，在此基礎上進一步確定相交的面積計算。
將所有多邊形柵格化處理以後，進入步驟S4：統計n個多邊形柵格圖像的相交柵格數count'，在柵格區域內隨機獨立選取m個柵格，m≤RES，RES為柵格區域的解析度，統計這m個柵格中位置標示符的值為a+nb的柵格的數目，該數目即為n個多邊形柵格圖像的相交柵格數count'。
通過步驟S2、S3對n個多邊形柵格化並對柵格區域內的所有柵格賦值、修正以後，計算n個多邊形的相交面積S就轉化為計算n個多邊形柵格圖像相交柵格的總面積。
在統計多邊形柵格圖像的相交柵格(像素)時，一般情況下是需要在柵格區域(整個柵格場或者柵格圖幅)範圍內遍歷所有柵格。例如對於兩個多邊形相交，柵格區域為整個柵格場，且柵格場的解析度RES為256×256＝65536的情況，那麼該方法就要遍歷65536個柵格，統計其中位置標示符的值等於2的柵格的數目，這樣的處理方式需要的時間會比較長。
為此，本發明實施例的改進之處在於不必遍歷整個柵格區域的所有柵格來統計多邊形柵格圖像的相交柵格數，而是利用概率統計的原理，僅從該柵格區域內隨機選取一定數量的柵格，通過統計這些隨機選取柵格中的位置標示符為a+nb的柵格的數目即可。這是一種概率統計方法，即利用少量隨機柵格子塊來模擬整個柵格場，以提高時間性能。這個方法速率上比採用遍歷柵格場或者柵格圖幅的方法有提高，但是精確度會有一定降低。
需要說明的是，這裡所利用的概率統計的原理是基於蒙特卡羅計算定積分的原理，結合圖3，對該原理進行簡要介紹。圖3中，對於陰影區P11的面積G，該區域是由函數y＝f(x)在x∈[a，b]區間所圍成的區域，由積分的面積含義有在平面區域Ω＝[a,b]×[0,T]上設置一個均勻隨機變量ξ，則該隨機變量落入陰影區P11的概率產生一個與該隨機變量ξ對應的隨機點(xi,yi)，檢驗隨機點(xi,yi)是否落入陰影區P11內，如果滿足條件yi≤f(xi)，則記錄點(xi,yi)落入陰影區P11內一次，對於N個獨立的均勻隨機數ξi，(i≤N)，記錄NS＝{ξ1,ξ2...,ξN}中落在陰影區P11中的個數。根據大數定理可得就是對積分的無偏估計，(b-a)T是矩形平面區域Ω的面積值。由此可見，對積分面積的計算可以通過概率統計而近似估計，特別是當隨機點數量增多時這種近似估計就越準確。
基於上述蒙特卡羅計算定積分的原理，我們在統計多邊形柵格圖像的相交柵格數時，不必遍歷柵格區域內的所有柵格獲得位置標示符為a+nb的柵格數目，而是只需要在該柵格區域內多次隨機選取柵格，從這些隨機選取的柵格中統計位置標示符為a+nb的柵格數目。這樣會帶來處理時間複雜度的降低，例如：若柵格區域的解析度RES為2048×2048，則全部柵格遍歷的時間複雜度為ο(2048×2048)；若從該柵格區域內隨機選取百分之一的柵格，即1％RES＝1％×2048×2048＝204×204(經過取整處理)，隨機選取柵格進行統計的時間複雜度為ο(204×204)，顯然帶來了處理速度的提升。
本實施例在圖形圖像開發軟體環境OpenGL中，GPU將所有多邊形都柵格化形成對應的柵格圖像以後，從這些柵格圖像佔據的柵格圖幅中隨機選取m個柵格，m小於或等於該柵格圖幅或整個柵格場的解析度，即m≤RES。然後，由GPU通過OpenGL中的glReadPixels函數將這些隨機選取的m個柵格及其對應的位置標示符的值傳送給CPU，再由CPU來統計這m個柵格中位置標示符的值為a+nb的柵格的數目count'。這裡的glReadPixels函數是由OpenGL提供的，該函數是用來讀取像素的，利用該函數可以「把已經被保存到GPU的像素讀取到CPU」。在應用該函數時，可以定義一個隨機數組result，從GPU中通過glReadPixels函數把result值讀出到CPU中，統計等於位置標示符的值為n的個數。
另外，由於在統計相交柵格的數目時需要從GPU中將數據讀回CPU，這是比較耗時的，會造成CPU和GPU之間的通信延遲。因此，統計柵格區域內位置標示符的值為n的柵格的數目也可以通過GPU利用遮擋查詢方法處理完成，GPU遮擋查詢方法是在OpenGL軟體開發環境下利用ARB_occlusion_query來實現的，其具體過程如下：
在OPENGL1.5及後續版本以及OpenGL ES 3.0中，ARB_occlusion_query擴展執行GPU遮擋查詢的命令，它的查詢過程就是由GPU來確定最終在屏幕上可見像素的數量。由於像素在流水線中需要經過各種檢驗，如alpha測試、模板測試和深度測試等(這些測試都是本領域的常規技術，這裡不再贅述)，遮擋查詢就是將最終通過上述測試的像素的數量進行計數，本實施例所要統計的為位置標示符的值為n的柵格(即像素)的數目，也就是說這裡的「通過上述測試的像素」即為「位置標示符的值為n的柵格」。本實施例中GPU直接通過ARB_occlusion_query調用glGetQueryObjectuiv函數統計位置標示符等於n的柵格數，解決了統計相交柵格數時從GPU讀數據到CPU需要延遲時間的問題。但該方法有應用局限性，就是必須在OPENGL1.5及後續版本以及OpenGL ES 3.0中，才能通過ARB_occlusion_query擴展執行GPU遮擋查詢的命令，只有在這些版本上才能調用glGetQueryObjectuiv函數，如果軟體版本達不到，該方法就不可用，此時可根據精度的容忍範圍選擇由CPU統計處理的方法。
在步驟S4的基礎上，以下步驟S5進一步完成相交面積的計算：計算n個多邊形柵格圖像的相交面積S，將相交柵格數count'除以隨機獨立選取的柵格數m，然後再乘以所選柵格區域的面積，即得到n個多邊形柵格圖像的相交面積S。
通過步驟S4得到隨機選取的m個柵格中n個多邊形柵格圖像相交柵格的數目count'以後，結合柵格區域的面積和隨機數m,就可以計算這n個多邊形柵格圖像相交柵格的總面積了。
這裡，所選的柵格區域分為兩種情況，一種是整個柵格場，另一種是柵格圖幅。當所選柵格區域為整個柵格場時，若柵格場的面積為SArea，隨機選取的某一柵格位於兩相交部分的概率為S/SArea，則n個多邊形柵格圖像相交面積S的計算公式如下：
同理，當所選柵格區域為待相交多邊形確定的柵格圖幅時，若該柵格圖幅的面積為STexArea，則相交面積S的計算公式如下：
公式(1)、(2)中的m一般是柵格場解析度RES分別乘以40％、50％或者60％的柵格數，count'是m個柵格中相交柵格的數目。
本發明基於概率統計的任意多邊形相交面積計算方法的基本思想來源於上述蒙特卡羅計算定積分原理，該方法是在GPU中實現的，原理更簡單，效率更高，而且不對多邊形的凹凸性做任何假設，對於凹多邊形也可以處理，適用於任意可光柵化的幾何圖元，該方法的效率較使用CPU的方法提高數百倍。
為了檢驗本發明方法所得結果是否有效，分別給出以下3個模型並對這些模型進行仿真比較。
實驗條件：使用C++與GLSL語言，在Microsoft Windows 7作業系統，OpenGL 4.4.0上實現本發明的計算方法，實驗用計算機的CPU採用 Core(TM)i5-3337U，4G內存，GPU為NVIDIA GeForce GT 620M。
模型1，本實驗隨機選取的兩個多邊形為P1和P2，這兩個多邊形的各個定點在平面直角坐標為：
P1＝{(4，4)，(1，13，)(，12，6)，(98)}
P2＝{(11，3)，(1，63，)(，18，8)，(1，41，2)(98)}。
該模型是通過兩個常規的多邊形來驗證本發明計算方法的正確性。
模型2，選取兩個有「洞」的複雜多邊形，這裡所說的有洞的多邊形是指類似於圖4(該圖為一個簡單的單洞多邊形示例)的多邊形，這樣的多邊形一般可以表示為一個外環和至少一個內環，該模型用於證明本發明的計算方法既可以針對凸多邊形，也能對凹多邊形進行處理。
模型3，選取了兩個頂點數較多的凸多邊形，一個多邊形有800個頂點，另一個多邊形有358個頂點。該模型用於證明本發明的計算方法對於具有頂點數較多(大數據量)的任意多邊形具有較好的處理效果。
表1，表2和表3分別給出了上述3個模型在本發明計算方法下計算相交面積的精度及時間。本實驗中的計算方法是分別選取不同隨機點數(柵格數)，重複相應程序10次所得到的誤差值。
表1模型1實驗結果
表2模型2實驗結果
表3模型3實驗結果
以下以模型1為例，進行誤差率分析和執行效率對比，具體分析如下：
誤差率分析：由表1可知，在解析度為256×256時，當隨機點個數m取依次取40％、50％、60％時，誤差率的值分別為2.84、2.1、1.89；解析度為512×512時，誤差率的值分別為0.19、0.09、0.08；解析度為1024×1024時，誤差率的值分別為0.078、0.075、0.067。由上述數據可知，一方面在隨機個數相同的情況下，隨著解析度的逐漸提高，該計算方法的誤差率會隨之越來越小；另一方面在解析度不變的情況下，隨著隨機點個數m的逐漸增多，誤差率也會越來越小。上述如此數量級別的捨入誤差在很多工程和一些大型軟體中都是可接受的。
執行效率對比：由表1可知，在解析度為256×256時，當隨機點個數m依次取40％、50％、60％時，執行時間分別為0.002s、0.002s、0.003s；解析度為512×512時，執行時間分別為0.007s、0.008s、0.011s；解析度為1024×1024時，執行時間分別為0.024s、0.026s、0.028s。由上述數據可知，雖然隨著解析度的逐漸提高和隨機點個數m的逐漸增多，執行時間會有增加，但是增加的幅度非常小。而現有採用CPU的計算方法在解析度增加一個數量級時，執行時間會成百上千倍地增加。因此，對比來看，本發明的計算方法比現有技術的計算方法效率提升了百倍，數據量越大，加速效果越明顯。
表2和表3分別是模型2、模型3採用本發明的方法計算相交面積的精度及時間對比，與模型1類似，這裡就不再進行詳細的數據對比說明。
另外，從表3可知，對於頂點數較多的多邊形，採用現有技術的計算方法即便是花費較長時間也可能計算不出結果。而對於本發明的計算方法，在256×256解析度下，m依次取40％、50％、60％時，執行時間分別為0.003s、0.003s、0.004s；在解析度增加到1024×1024時，相應的執行時間也僅為0.027s、0.03s、0.004s、0.032s，效率提升非常大。
本發明提出的任意多邊形相交面積計算方法，引入了蒙特卡羅方法,更方便高效，面積誤差在工程上是可以接受的，這是一種以精度的適當犧牲換取優異綜合性能的方法。實驗結果表明，本發明的計算方法適用於多邊形數量龐大且任意複雜的多邊形，很好的避免了傳統計算方法所遇到的奇異性問題(邊界問題)，比如重疊邊、邊與邊交於邊的頂點等情形，從而具有較好的魯棒性。
以上所述僅為本發明的實施例，並非因此限制本發明的專利範圍，凡是利用本發明說明書及附圖內容所作的等效結構變換，或直接或間接運用在其他相關的技術領域，均包括在本發明的專利保護範圍內。