不规则多边形转化三角形（支持凹凸多边形）

作用：

（1）用于UnityMesh绘制

（2）可以用于判断一个点是否在多边形内部

 

多边形转三角形注意事项：

（1）凹凸边问题（Vector3.Cross 判断凹凸方向）

（2）共线问题（Vector3.Cross == 0代表一条直线）

（3）三角形内部问题（检测点在三条边同一个方向即在三角形内部）

（4）传入的顶点数据有效性（顶点数据需顺时针、简单多边形结构顶点）

 

-- 多边形三角化 支持凹凸多边形 只能传入简单多边形顶点 每个顶点不被大于两条边共享即简单多边形 
-- vertices顶点列表需要按照顺时针传入 return三角形顶点列表、三角形绘制顺序列表（用于mesh绘制）
function PolygonToTriangle(vertices)
    assert(#vertices >= 3, "多边形三角化顶点数量小于3个")
    local newVertices = {}
    local triangleOrders = {}
    local curVertices = {}
    local curVerticesCount = #vertices
    local index = 1

    --重包装 保存原有的顶点顺序
    for k, v in ipairs(vertices) do
        table.insert(curVertices, 
        {
            index = k,
            value = v
        })
    end
    while curVerticesCount > 3 do
        local aIndex = index % curVerticesCount
        local bIndex = (index + 1) % curVerticesCount
        local cIndex = (index + 2) % curVerticesCount
        aIndex = aIndex == 0 and curVerticesCount or aIndex
        bIndex = bIndex == 0 and curVerticesCount or bIndex
        cIndex = cIndex == 0 and curVerticesCount or cIndex
        local aPoint = curVertices[aIndex].value
        local bPoint = curVertices[bIndex].value
        local cPoint = curVertices[cIndex].value
        local aDir = (aPoint - bPoint).normalized
        local cDir = (cPoint - bPoint).normalized
        --检测凹凸角 < 0 是凸，> 0 是凹，= 0 是共线 直接排除
        local crossValue = Vector3.Cross(aDir, cDir).y
        if crossValue < 0 then
            --检测是否有顶点包含在该三角形内 有的话index + 1
            local isSucceed = true
            for _, checkPoint in ipairs(curVertices) do
                if InTriangle(checkPoint.value, aPoint, bPoint, cPoint) then
                    isSucceed = false
                    break
                end
            end
            if isSucceed then
                table.insert(newVertices, aPoint)
                table.insert(newVertices, bPoint)
                table.insert(newVertices, cPoint)
                table.insert(triangleOrders, curVertices[aIndex].index)
                table.insert(triangleOrders, curVertices[bIndex].index)
                table.insert(triangleOrders, curVertices[cIndex].index)
                table.remove(curVertices, bIndex)
            else
                index = index + 1
            end
        elseif crossValue == 0 then
            table.remove(curVertices, bIndex)
        else
            index = index + 1
        end
        curVerticesCount = #curVertices
    end

    --最后三个顶点组成最后一个三角形
    for i = 1, 3 do
        table.insert(newVertices, curVertices[i].value)
        table.insert(triangleOrders, curVertices[i].index)
    end
    -- print("生成顶点数量", #newVertices, "三角面数量", #triangleOrders)
    return newVertices, triangleOrders
end

--判断一个点是否在三角形内（在边上不算）
function InTriangle(checkPoint, angleA, angleB, angleC)
    local aC = Vector3.Cross((angleA - angleB).normalized, (angleA - checkPoint).normalized)
    local bC = Vector3.Cross((angleB - angleC).normalized, (angleB - checkPoint).normalized)
    local cC = Vector3.Cross((angleC - angleA).normalized, (angleC - checkPoint).normalized)
    return aC.y > 0 and bC.y > 0 and cC.y > 0 or aC.y < 0 and bC.y < 0 and cC.y < 0
end