Hello!
I want to triangulate a polygon and I found this code:
local function isInCircle(p, cx, cy, r)
return (cx - p.x) ^ 2 + (cy - p.y) ^ 2 <= r ^ 2
end
local function getCircumCenter(t)
local D = (t[1].x * (t[2].y - t[3].y) + t[2].x * (t[3].y - t[1].y) + t[3].x * (t[1].y - t[2].y)) * 2
local x = ((t[1].x * t[1].x + t[1].y * t[1].y) * (t[2].y - t[3].y) + (t[2].x * t[2].x + t[2].y * t[2].y) * (t[3].y - t[1].y) + (t[3].x * t[3].x + t[3].y * t[3].y) * (t[1].y - t[2].y))
local y = ((t[1].x * t[1].x + t[1].y * t[1].y) * (t[3].x - t[2].x) + (t[2].x * t[2].x + t[2].y * t[2].y) * (t[1].x - t[3].x) + (t[3].x * t[3].x + t[3].y * t[3].y) * (t[2].x - t[1].x))
return x / D, y / D
end
local function getCircumRadius(t)
local a, b, c = math.sqrt((t[1].x - t[2].x) ^ 2 + (t[1].y - t[2].y) ^ 2), math.sqrt((t[2].x - t[3].x) ^ 2 + (t[2].y - t[3].y) ^ 2), math.sqrt((t[3].x - t[1].x) ^ 2 + (t[3].y - t[1].y) ^ 2)
return a * b * c / math.sqrt((a + b + c) * (a + b - c) * (a - b + c) * (-a + b + c))
end
local function inCircumCircle(t, p)
local x, y = getCircumCenter(t)
local r = getCircumRadius(t)
return isInCircle(p, x, y, r)
end
local function triangulate(points: {Vector2}): {{Vector2}}
local vertices = {}
for i, p in points do
if i == #points and points[1] == p then
break
end
vertices[i] = {x=p.X,y=p.Y,i=i}
end
local nvertices = #vertices
if nvertices < 3 then
return {}
elseif nvertices == 3 then
return {vertices}
end
local trmax = nvertices * 4
local minX, minY = vertices[1].x, vertices[1].y
local maxX, maxY = minX, minY
for i = 1, #vertices do
local vertex = vertices[i]
if vertex.x < minX then minX = vertex.x end
if vertex.y < minY then minY = vertex.y end
if vertex.x > maxX then maxX = vertex.x end
if vertex.y > maxY then maxY = vertex.y end
end
local dx, dy = (maxX - minX) * 1e3, (maxY - minY) * 1e3
local deltaMax = math.max(dx, dy)
local midx, midy = (minX + maxX) * 0.5, (minY + maxY) * 0.5
local p1 = {x = midx - 2 * deltaMax, y = midy - deltaMax, i = nvertices + 1}
local p2 = {x = midx, y = midy + 2 * deltaMax, i = nvertices + 2}
local p3 = {x = midx + 2 * deltaMax, y = midy - deltaMax, i = nvertices + 3}
vertices[p1.i] = p1
vertices[p2.i] = p2
vertices[p3.i] = p3
local triangles = {}
table.insert(triangles, {
vertices[nvertices + 1],
vertices[nvertices + 2],
vertices[nvertices + 3]
})
for i = 1, nvertices do
local edges = {}
local ntriangles = #triangles
for j = #triangles, 1, -1 do
local curTriangle = triangles[j]
if inCircumCircle(curTriangle, vertices[i]) then
table.insert(edges, {curTriangle[1], curTriangle[2]})
table.insert(edges, {curTriangle[2], curTriangle[3]})
table.insert(edges, {curTriangle[3], curTriangle[1]})
table.remove(triangles, j)
end
end
for j = #edges - 1, 1, -1 do
for k = #edges, j + 1, -1 do
if edges[j] and edges[k] and edges[j][1] == edges[k][1] and edges[j][2] == edges[k][2] then
table.remove(edges, j)
table.remove(edges, k - 1)
end
end
end
for j = 1, #edges do
local n = #triangles
assert(n <= trmax, "Generated more than needed triangles")
triangles[n + 1] = {edges[j][1], edges[j][2], vertices[i]}
end
end
for i = #triangles, 1, -1 do
local triangle = triangles[i]
if triangle[1].i > nvertices or
triangle[2].i > nvertices or
triangle[3].i > nvertices then
table.remove(triangles, i)
end
end
for _ = 1,3 do
table.remove(vertices)
end
return triangles
end
But it generates quite strange results:
How do I get rid of these outside triangles?