Wiki
Clone wikiCore / triangulate
Back to Beyond the Codea in-app reference
triangulate() function
Introduction
The 'Shaders & Mesh' chapter of Codea's in-app reference documents most of the triangulate(points)
function. The function takes an array of vec2
values representing the vertices of a polygon (points
) and returns a table (an array) of vec2
values representing the vertices of triangles which together comprise the polygon.
Order of the vertices
From Codea version 1.5, the array of vec2
values representing the vertices of the polygon can be in a clockwise or anti-clockwise order. Before version 1.5, the order of the vertices was important. For example:
-- A helper function to reverse the order of an array
local function reverse(a)
local ra = {}
local n = #a
for i = 1, n do
ra[i] = a[n - i + 1]
end
return ra
end
function setup()
local pCW = { -- A 100 x 100 'C', in clockwise order:
vec2(0, 0), -- 2--------------3
vec2(0, 100), -- | |
vec2(100, 100), -- | 5-----------4
vec2(100,75), -- | |
vec2(25,75), -- | |
vec2(25,25), -- | |
vec2(100,25), -- | 6-----------7
vec2(100, 0) -- | |
} -- 1--------------8
local pCCW = reverse(pCW) -- Counter-clockwise
print("-- Clockwise --")
local tCW = triangulate(pCW)
for i = 1, #tCW, 3 do
local p = {tCW[i], tCW[i+1], tCW[i+2]}
print(unpack(p)) -- Outputs: six triangles
end
print("-- Counter-clockwise --")
local tCCW = triangulate(pCCW)
for i = 1, #tCCW, 3 do
local p = {tCCW[i], tCCW[i+1], tCCW[i+2]}
print(unpack(p)) -- Outputs: same six triangles
end
end
Any triangles returned by the triangulate()
function are themselves in a counter-clockwise order.
Detecting the order of polygon vertices
A polygon with vertices in a counter-clockwise order has a positive 'signed' area and a polygon with vertices in a clockwise order has a negative 'signed' area. The code below returns the 'signed' area of a polygon:
-- A helper function to calculate 'signed' area of a polygon
local function area(p)
local a = 0 -- will hold 'signed' area
for i = 1, #p do -- iterate through vertices
local p1 = p[i]
local p2 = p[i % #p + 1] -- if i < #p then i % #p + 1 is i + 1
-- if i = #p then i % #p + 1 is 1
a = a + p1:cross(p2) -- p1:cross(p2) is x1y2 - x2y1
end
return a/2
end
Updated