在很多圖形相關的編輯器里都會有選區(qū)功能达布，有的只能按某種固定形狀選擇，比如：矩形逾冬，圓形……，有的可以按任意形狀選擇粉渠，有的甚至可以分析圖片自動選區(qū)（例如：Photoshop魔法棒工具），今天來說說任意形狀選區(qū)怎么實現(xiàn)霸株。

通過鼠標描點，再用線段連接集乔，組合成一個幾何選區(qū)去件，這看似沒有難度扰路，它實際上……的確沒有難度。如果要填充選區(qū)內(nèi)部汗唱，這就有一丟丟難度（至少很久前我被這個問題困住很久）。

計算機圖形接口

在計算機里授霸，圖片普遍都是矩形的际插，當渲染一張圖片到屏幕時，這張圖片會被拆成兩個三角形框弛，這兩個三角形將圖片斜角對折切開，然后提交到渲染管道斗搞，而這個渲染管道則由顯卡接管慷妙。

至于為什么會被拆成三角形，因為計算機3D渲染技術已經(jīng)非常成熟景殷，而3D渲染完全可以渲染2D圖像澡屡，因此顯卡只需要按3D渲染的架構設計就可以了驶鹉，但是铣墨，3D圖形比2D圖形復雜的多，因為2D形狀統(tǒng)統(tǒng)都可以在一個矩形的圖片上畫出來伊约，而3D要顯示一個形狀需要模型姚淆，而怎么構建這個模型就成了問題屡律。例如：立方體模型，六個面搏讶，那可以用六個正方形來構建霍殴。但是球形或更復雜的模型，純用正方形去拼湊完全不可能妒蔚，因此這可能需要各種各樣的形狀月弛，從而導致非常凌亂。如果有一種圖元可以拼湊出任意形狀的模型尊搬，那一切都完美，三角形正是這樣的圖元幌墓，它雖然不能完美拼湊任意形狀的模型冀泻，卻可以在硬件允許的情況下無限近似任意形狀的模型。當前流行的顯卡通常只支持三角形硬件加速胳施，聽說俄羅斯還有人搞圓形硬件加速的肢专？
上面大概已經(jīng)說明三角形和渲染管道的關系了焦辅，下面進入正題椿胯。

閉合路徑

要填充一個不規(guī)則的選區(qū)，要把它拆分成多個三角形前方，而怎么拆分成三角形就是問題所在廉油。

任意形狀選區(qū)

在拆分三角形之前，需要計算出選區(qū)內(nèi)包含的所有閉合路徑班巩，因為一個選區(qū)可能會有多個閉合路徑十兢，就像上圖顯示，選區(qū)包含了兩個閉合路徑，要填充這兩個閉合路徑．

選區(qū)的數(shù)據(jù)結構是一組頂點列表[p0, p1, p2...pN]
從 p2 開始遍歷：
pi -> p(i+1) 正好構成一條線段卫袒，將這條線段與前面的線段做相交檢測，一旦相交宝穗，則說明此時遇到了一個閉合路徑．
記錄交點CrossP码秉，
記錄交點線段的起點CrossA，
記錄交點線段的終點CrossB．
[CrossP, CrossB, ..., pi] 頂點列表則是該閉合路徑．
隨后將這個閉合路徑的頂點列表從原始頂點列表中剔除须鼎，并將CrossP插入到CrossB的位置．
直到把原始頂點列表遍歷完畢府蔗，則所有的閉合路徑都被計算出來了．

三角形切割

已經(jīng)得到了所有的閉合路徑，接下來就可以切割三角形了．這非常容易赡译，因為每一個閉合路徑都是一個多邊形不铆，只需要求得這個多邊形的中點裹唆，再從中點依次連接到各個頂點就可以了．

切割三角形

從圖中可以清楚的看到閉合路徑的中心只洒，以及從中心連接到各個頂點的線段，因為圖中的閉合路徑只有四個頂點舞吭，因此只需要切割四個三角形就足夠了．
計算多邊形中心的公式：

(p[i] + p[i+1] + p[N]) / N

如果一切都是這么容易析珊，那活著就舒坦了，幾何學告訴我們惧浴，上述算法并不是總是湊效．

凹多邊形切割

凹多邊形閉合路徑

從圖中可以看出奕剃，閉合路徑只有一個，但這個路徑是凹多邊形柿顶，按上述的方法求得中心很可能在多邊形外面操软，連接出來的三角形并不正確．需要先把凹多邊形切割成凸多邊形，這非常容易．

只需要在多邊形的凹點處家乘，延伸出一條線段藏澳，連接到最近的邊，這條線段作為交界翔悠，劃分出兩個多邊形，再分別將這兩個多邊形重復此步驟腻要，直到?jīng)]有凹點涝登，則這個多邊形是凸多邊形．

首先需要知道如何判斷一個多邊形是凹的還是凸的．
以左上角為原點的２D坐標系來說．

當一個順時針排列的多邊形，某一條邊往左拐趟济，這個多邊形是凹多邊形．
當一個逆時針排列的多邊形，某一條邊往右拐顷编，這個多邊形是凹多邊形．
計算邊的拐向很容易媳纬，只要判斷兩條邊的向量積符號是正是負就行了．
//    向量拐向公式
//    具體拐向跟坐標系有關，在本例中钮惠，順時針排列，向量積小于零是左拐．
Cross(p0p1, p1p2) < 0? "左拐?右拐?": "左拐?右拐?"

因為頂點順序是隨機的蔑赘，因此可能是順時針排列也可能是逆時針排列预明，所以要先計算出這個多邊形的排列順序，計算思路非常容易：
只需要遍歷多邊形頂點酥馍，對所有邊計算拐向阅酪，如果左拐向多余右拐向，則是逆時針排列，否則是順時針排列．

float Cutting::Polygon::CheckOrder(const math::Points & points)
{
    auto order0 = 0;    //  順時針
    auto order1 = 0;    //  逆時針
    for (auto i = 0; i != points.size(); ++i)
    {
        auto & a = points.at(INDEX(i    , points.size()));
        auto & b = points.at(INDEX(i + 1, points.size()));
        auto & c = points.at(INDEX(i + 2, points.size()));
        if (CheckOrder(a, b, c) < 0)
        {
            ++order1;
        }
        else
        {
            ++order0;
        }
    }
    return order0 > order1 ? 1.0f : -1.0f;
}

整個算法到這就結束了术吗，下圖是凹多邊形切割后的形狀帆精，很容易發(fā)現(xiàn)，多了幾根線段卓练，這些線段正是切分成凸多邊形的線段，而閉合路徑也由１個變成了３個嘱么，再用上述的方法計算三角形就容易多了．

切割凹多邊形

填充選區(qū)

效果展示

png

png