耳切法

    1. 判斷三角形是否多邊形的耳朵
    2. 取出耳尖的點，剩下的多邊形重複上述步驟直到剩下一個三角形

判斷三角形是否多邊形的耳朵

1. 連續的三個點 
2. 找出凸頂點，可用兩鄰邊的最小夾角得到凸頂點
3. 鄰邊在多邊形內 / 鄰邊的兩個端點都在多邊形內
4. 多邊形沒有其他頂點在此三角形內

Snippets

求三點最小夾角

function TriangleAngle(A,B,C, notdeg)
    --dot: a.x * b.x + a.y * b.y
    local v1 = vector2(A.x - B.x, A.y - B.y)
    local v2 = vector2(C.x - B.x, C.y - B.y)

    return math.acos(dot(v1,v2) / (#v1 * #v2)) * (notdeg and 1.0 or 180.0 / math.pi)
end 
--test print(TriangleAngle(vector2(9.4,12.4),vector2(17.5,12),vector2(1.5,4.2))) : 28.8

一點是否在三角形內

function IsPointInTriangle(point,vertice1,vertice2,vertice3)
    if point == vertice1 or point == vertice2 or point == vertice3 then return true end
    local v1 = vector2(vertice1.x - vertice2.x, vertice1.y - vertice2.y)
    local v2 = vector2(vertice3.x - vertice2.x, vertice3.y - vertice2.y)
    local v3 = vector2(point.x - vertice2.x, point.y - vertice2.y)
    local dot00 = dot(v1, v1)
    local dot01 = dot(v1, v2)
    local dot02 = dot(v1, v3)
    local dot11 = dot(v2, v2)
    local dot12 = dot(v2, v3)

    local denom = (dot00 * dot11 - dot01 * dot01)
    local u = (dot11 * dot02 - dot01 * dot12) / denom
    local v = (dot00 * dot12 - dot01 * dot02) / denom

    return (u >= 0) and (v >= 0) and (u + v < 1)
end

思路：影片

1. 取出最右邊的點
2. 取出鄰邊的點
3. 判斷三點順時針逆時針，此為多邊形的順逆時針
4. 取得所有角度
5. 取得最小角度
6. 取得最小角度的點
7. 取得鄰邊的點
8. 構成的三角形加入返回列表
9. 取下一個三角形的三個點和刷新角度
10. 去除三角形頂點和其角度
11. 重複上述步驟直到剩下一個三角形

function triangulate(vertices)
    local n,pi = #vertices, math.pi  
    local rightmost_x = vertices[1].x 
    local rightmost_idx = 1
    
    for i=2,n do
        if vertices[i].x > rightmost_x then
            rightmost_x = vertices[i].x
            rightmost_idx = i
        end
    end
    
    local get_next_vertice_index = function(i)
        local j = i + 1
        if j > n then j = 1 end
        return j
    end

    local get_previous_vertice_index = function(i)
        local j = i - 1
        if j < 1 then j = n end
        return j
    end

    
    local A = vertices[get_previous_vertice_index(rightmost_idx)]
    local B = vertices[rightmost_idx]
    local C = vertices[get_next_vertice_index(rightmost_idx)]

    local polygon_clockwise = IsTriangleClockwise(A,B,C)
    
    local polygon_vertices_angles = {}

    for i=1,n do
        local A = vertices[i]
        local B = vertices[get_next_vertice_index(i)]
        local C = vertices[get_next_vertice_index(get_next_vertice_index(i))]
        
        local theta = TriangleAngle(A,B,C)
        
        local triangle_clockwise = IsTriangleClockwise(A,B,C)

        if triangle_clockwise ~= polygon_clockwise then
            theta = 2 * pi - theta
        end
      
        polygon_vertices_angles[i] = theta
    end

    local triangles = {}

    local maxvertices = n 
    
    for i=1,  maxvertices - 2 do
        local min_angle = polygon_vertices_angles[1]
        local min_angle_index = 1

        for i=1,#polygon_vertices_angles do
            if polygon_vertices_angles[i] < min_angle then
                min_angle = polygon_vertices_angles[i]
                min_angle_index = i
            end
        end
        
        local i1 = get_next_vertice_index(min_angle_index)
        local i2 = min_angle_index
        local i3 = get_previous_vertice_index(min_angle_index)
        local A = vertices[i1]
        local B = vertices[i2]
        local C = vertices[i3]

        triangles[#triangles + 1] = {A,B,C}

        local a = vertices[get_next_vertice_index(i1)]
        local b = vertices[i1]
        local c = vertices[i3]

        local theta = TriangleAngle(a,b,c)
        local triangle_clockwise = IsTriangleClockwise(a,b,c)

        if triangle_clockwise ~= polygon_clockwise then
            theta = 2 * pi - theta
        end

        polygon_vertices_angles[i1] = theta

        local a = vertices[i1]
        local b = vertices[i3]
        local c = vertices[get_next_vertice_index(i3)]

        local theta = TriangleAngle(a,b,c)
        local triangle_clockwise = IsTriangleClockwise(a,b,c)

        if triangle_clockwise ~= polygon_clockwise then
            theta = 2 * pi - theta
        end

        polygon_vertices_angles[i3] = theta
        
        table.remove(vertices, min_angle_index)
        table.remove(polygon_vertices_angles, min_angle_index)
        n  = n - 1
        print('wow',n)
    end

    return triangles

end