Ok, the triangulation part is done ... but ...
I'm again in a need of something to fill a polygon with rectangles.
This time I would like to fill a polygon with secure buttons - which surly can't be done with triangles.
Any thoughts?
[e]
As building this was no fun: if someone ever has to triangulate a polygon in lua, here's the code (it's a simple ear clipping approach).
Triangulate() expects a table containing a sorted list of verticles data (n tables with x and y values) and returns a table containing n tables with triangle data (point 1, 2, 3 each containing a index number from the verticle table that was passed to the function).
Verticle list can be clockWise or anti-clockwise. Works with convex and concave polygons. Does not work with self intersecting polygons or polygons with holes.
No optimization right now. Could surly be faster.
Lua Code:
function IntersectionPoint(x1, y1, x2, y2, x3, y3, x4, y4)
if x1 and y1 and x2 and y2 and x3 and y3 and x4 and y4 then
local d = ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1))
local Ua
local Ub
if d ~= 0 then
Ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / d
Ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / d
end
if Ua and Ub then
if Ua >= -0.0 and Ua <= 1.0 and Ub >= -0.0 and Ub <= 1.0 then
x = x1 + Ua * (x2 - x1)
y = y1 + Ua * (y2 - y1)
return math.floor(x), math.floor(y), Ua
end
end
end
end
function LineCenter(sx, sy, ex, ey)
return (sx + ex) * 0.5, (sy + ey ) * 0.5
end
function InPolygon(pMeshVerticles, a, b)
local count = 0
for x = 1, table.getn(pMeshVerticles) do
local s, e = x, x + 1
if s < 1 then s = table.getn(pMeshVerticles) end
if e > table.getn(pMeshVerticles) then e = 1 end
if ((a.x ~= pMeshVerticles[s].x and a.y ~= pMeshVerticles[s].y) and (b.x ~= pMeshVerticles[e].x and b.y ~= pMeshVerticles[e].y)) and ((b.x ~= pMeshVerticles[s].x and b.y ~= pMeshVerticles[s].y) and (a.x ~= pMeshVerticles[e].x and a.y ~= pMeshVerticles[e].y)) then
if IntersectionPoint(a.x, a.y, b.x, b.y, pMeshVerticles[s].x, pMeshVerticles[s].y, pMeshVerticles[e].x, pMeshVerticles[e].y) then
count = count + 1
end
end
end
if count > 0 then
return false
else
count = 0
local ax, ay = LineCenter(a.x, a.y, b.x, b.y)
if not ax and ay then print("!!! FAIL") return false end
for x = 1, getn(pMeshVerticles) do
local s, e = x, x + 1
if s < 1 then s = getn(pMeshVerticles) end
if e > getn(pMeshVerticles) then e = 1 end
if IntersectionPoint(ax, ay, 5000, 5000, pMeshVerticles[s].x, pMeshVerticles[s].y, pMeshVerticles[e].x, pMeshVerticles[e].y) then
count = count + 1
end
end
local _, b = math.modf(count / 2)
if b > 0 then
return true
else
return false
end
end
return false
end
function Triangulate(pMeshVerticles)
local tTriangles = {}
local currentVerticle
local tMaxY = -10000
for x = 1, table.getn(pMeshVerticles) do
if pMeshVerticles[x].y > tMaxY then
currentVerticle = x
tMaxY = pMeshVerticles[x].y
end
if x == 1 then
pMeshVerticles[x].prev = table.getn(pMeshVerticles)
pMeshVerticles[x].next = x + 1
elseif x == table.getn(pMeshVerticles) then
pMeshVerticles[x].prev = x - 1
pMeshVerticles[x].next = 1
else
pMeshVerticles[x].prev = x - 1
pMeshVerticles[x].next = x + 1
end
pMeshVerticles[x].out = false
end
if not currentVerticle then print("!!! FAIL") return end
local tFailCounter = 0
local tTriCounter = 0
local numberPointsLeft = table.getn(pMeshVerticles)
while numberPointsLeft >= 3 do
if InPolygon(pMeshVerticles, pMeshVerticles[pMeshVerticles[currentVerticle].prev], pMeshVerticles[pMeshVerticles[currentVerticle].next]) == true then
insert(tTriangles, {
[1] = pMeshVerticles[currentVerticle].prev,
[2] = currentVerticle,
[3] = pMeshVerticles[currentVerticle].next
})
tTriCounter = tTriCounter + 1
pMeshVerticles[pMeshVerticles[currentVerticle].prev].next = pMeshVerticles[currentVerticle].next
pMeshVerticles[pMeshVerticles[currentVerticle].next].prev = pMeshVerticles[currentVerticle].prev
pMeshVerticles[currentVerticle].out = true
currentVerticle = pMeshVerticles[currentVerticle].next
numberPointsLeft = numberPointsLeft -1
else
currentVerticle = pMeshVerticles[currentVerticle].next
end
tFailCounter = tFailCounter + 1
if tFailCounter > table.getn(pMeshVerticles) * 3 then
print("FAIL: ", tFailCounter)
print("currentVerticle:", currentVerticle, "prev:", pMeshVerticles[currentVerticle].prev, "next: ", pMeshVerticles[currentVerticle].next)
return
end
end
return tTriangles
end