Hi!
Recently I was searching for a polygon triangulation algorithm. I choosed the method of kong. It was working fine until I tried to triangulate bezier curves.
Here is the code:
local function ccw(p: Vector2, q: Vector2, r: Vector2): boolean
return (q - p):Cross(r - p) >= 0
end
function pointInTriangle(q: Vector2, p1: Vector2, p2: Vector2, p3: Vector2)
local v1, v2 = p2 - p1, p3 - p1
local qp = q - p1
local dv = v1:Cross(v2)
local l = qp:Cross(v2) / dv
if l <= 0 then
return false
end
local m = v1:Cross(qp) / dv
if m <= 0 then
return false
end
return l + m < 1
end
local function isEar(concave: { Vector2 }, p1: Vector2, p2: Vector2, p3: Vector2)
if not ccw(p1, p2, p3) then
return false
end
for q, _ in concave do
if pointInTriangle(q, p1, p2, p3) then
return false
end
end
return true
end
local function triangulate(points: { Vector2 }): { { Vector2 } }
local vertices = table.clone(points)
if vertices[1] == vertices[#vertices] then
vertices[#vertices] = nil
end
if #vertices < 3 then
return {}
elseif #vertices == 3 then
return {vertices}
end
local triangles = {}
local concave = {}
local adj = {}
for i, p in vertices do
local l = if i == 1 then vertices[#vertices] else vertices[i - 1]
local r = if i == #vertices then vertices[1] else vertices[i + 1]
adj[p] = {p = p, l = l, r = r}
if not ccw(l, p, r) then
concave[p] = true
end
end
local nPoints, skipped = #vertices, 0
local p = adj[vertices[2]]
while nPoints > 3 do
if not concave[p.p] and isEar(concave, p.l, p.p, p.r) then
table.insert(triangles, { p.l, p.p, p.r })
if concave[p.l] and ccw(adj[p.l].l, p.l, p.r) then
concave[p.l] = nil
end
if concave[p.r] and ccw(p.l, p.r, adj[p.r].r) then
concave[p.r] = nil
end
adj[p.p] = nil
adj[p.l].r = p.r
adj[p.r].l = p.l
nPoints = nPoints - 1
skipped = 0
p = adj[p.l]
else
p = adj[p.r]
skipped = skipped + 1
assert(skipped <= nPoints, "Cannot triangulate polygon (is the polygon intersecting itself?)")
end
end
table.insert(triangles, { p.l, p.p, p.r })
return triangles
end
It can’t handle this table of points (I got these by simplifying this shape): {{460, 110}, {450.52001953125, 107.1199951171875}, {441.2799987792969, 105.68000030517578}, {432.2799987792969, 105.68000030517578}, {423.52001953125, 107.1199951171875}, {415, 110}, {460, 110}}. But it works fine if I reverse the table.
Why? How can I upgrade it and fix this error?
Thank you for your help.