上回說(shuō)到我們已經(jīng)得到了以輪廓線頂點(diǎn)集表示d的可行走區(qū)域
但是對(duì)于不規(guī)則的輪廓線，我們并不能直接在上面尋路，我們希望得到的是一個(gè)一個(gè)的凸多邊形，因?yàn)橥苟噙呅蝺?nèi)部的任意兩點(diǎn)一定是直線可達(dá)的，但凹多邊形則不滿足這一點(diǎn)

需要凸多邊形保證任意兩點(diǎn)直線可達(dá)

現(xiàn)在我們要做的就是把由輪廓線表示的區(qū)域分割成多個(gè)相鄰的凸多變形集合（即最后的多邊形網(wǎng)格）

Step 6. Build polygons mesh from contours.

多邊形網(wǎng)格的生成大概分這樣幾個(gè)步驟：
a.將初始輪廓線圖形進(jìn)行三角化
b.將上一步得到的三角形進(jìn)行合并（合并成凸多邊形集合）
c.計(jì)算凸多邊形的鄰接關(guān)系

其實(shí)這一部分做的內(nèi)容基本上都是純計(jì)算幾何算法的應(yīng)用

首先是三角化，項(xiàng)目中用了耳裁剪(EarClipping)的算法
先說(shuō)下幾個(gè)定義：
多邊形的對(duì)角線：設(shè)多邊形連續(xù)的三個(gè)頂點(diǎn)為v1,v2,v3，則v1v3的連線為多邊形的對(duì)角線
多邊形的耳朵：可以理解為不包含其他頂點(diǎn)的一個(gè)外凸三角形，對(duì)應(yīng)的v2稱為耳尖

如圖下中
ABC是一個(gè)耳朵
FAB內(nèi)部包含點(diǎn)D，不是耳朵
CDE不是外凸三角形，不是耳朵

多邊形耳朵

三角化的具體算法流程是：
找到當(dāng)前多邊形的所有耳朵，選擇其中對(duì)角線最短的耳朵，將對(duì)應(yīng)的耳尖頂點(diǎn)刪除，這樣N邊形就變?yōu)榱薔-1邊形
重復(fù)這個(gè)過(guò)程N(yùn)-3次

具體的代碼在這個(gè)函數(shù)中實(shí)現(xiàn)：

static int triangulate(int n, const int* verts, int* indices, int* tris)

三角化之后，其實(shí)已經(jīng)得到了凸多邊形集合，但是這樣的三角形網(wǎng)格太細(xì)碎了，如果直接上a*搜索會(huì)導(dǎo)致搜索節(jié)點(diǎn)非常多，所以可以將三角形再合并成凸多邊形
項(xiàng)目中處理的方式是：
每次枚舉所有的多邊形對(duì)，判斷是否可以合成，取其中公共邊最長(zhǎng)的一對(duì)進(jìn)行合并
重復(fù)這個(gè)過(guò)程直到無(wú)法再合并得到新的凸多邊形

最后我們?cè)儆?jì)算出凸多邊形之間的鄰接關(guān)系
具體的做法是：
先得到所有多邊形的邊，用鏈?zhǔn)角跋蛐堑姆绞酱嫫饋?lái)（每個(gè)點(diǎn)記錄以它為起始點(diǎn)的邊）
然后遍歷所有邊，對(duì)每條邊設(shè)置以它為公共邊的多邊形的鄰接信息
鄰接信息是跟多邊形的頂點(diǎn)信息存在一起的，在rcPolyMesh這個(gè)結(jié)構(gòu)體里
每個(gè)區(qū)域輪廓對(duì)應(yīng)一個(gè)rcPolyMesh，內(nèi)部包含了這個(gè)輪廓內(nèi)的所有凸多邊形

struct rcPolyMesh
{
    unsigned short* verts;  ///所有多邊形的頂點(diǎn)，注意這里頂點(diǎn)的坐標(biāo)不是實(shí)際坐標(biāo)，而是網(wǎng)格坐標(biāo)
    unsigned short* polys;  ///所有凸多邊形的信息
    ///polys數(shù)組長(zhǎng)度為 多邊形數(shù)量maxpolys*多邊形最大頂點(diǎn)數(shù)nvp
    ///對(duì)于每個(gè)多邊形，前nvp個(gè)數(shù)存頂點(diǎn)id，后nvp個(gè)數(shù)存與它相鄰的多邊形id（n個(gè)頂點(diǎn)最多與n個(gè)多邊形相鄰）
};