Scientist, Designer, and Teacher. Assoc Prof of CompSci in visualization at Mississippi State University. Believes information wants to be seen. Loves Python. @dr_tj
function earcut(vertices)
{
// Cut until a triangle, box, or concave polygon left
let pixels = []
let concave = vertices.filter((x,i) => is_concave(vertices[mod(i-1, vertices.length)],
x,
vertices[(i+1)%vertices.length]));
let idx = 0;
while(concave.length > 0 && vertices.length > 3)
{
// Skip if this is concave
if(!concave.some((x) => equal(x, vertices[idx])))
{
if(is_ear(vertices[idx? idx-1: vertices.length-1],
vertices[idx],
vertices[(idx+1)%vertices.length],
concave))
{
// Draw pixels, remove ear vertex, update concave
pixels = [...pixels, ...fill_triangle(vertices[mod(idx-1, vertices.length)],
vertices[idx],
vertices[(idx+1)%vertices.length])];
concave = concave.filter((x) => !equal(x, vertices[mod(idx-1, vertices.length)])
|| is_concave(vertices[mod(idx-2, vertices.length)],
x,
vertices[(idx+1)%vertices.length]));
concave = concave.filter((x) => !equal(x, vertices[(idx+1)%vertices.length])
|| is_concave(vertices[mod(idx-1, vertices.length)],
x,
vertices[(idx+2)%vertices.length]));
vertices = [...vertices.slice(0,idx), ...vertices.slice(idx+1)];
idx -= 1; // Don't move forward
}
}
idx = (idx+1) % vertices.length;
}
// Handle box or triangle
if(vertices.length == 3)
return [...pixels, ...fill_triangle(...vertices)];
else
// A convex polygon we fan
return [...pixels,
...d3.range(2,vertices.length)
.map((i) => fill_triangle(vertices[0], vertices[i-1], vertices[i])).flat()];
}
function is_concave(v1, v2, v3)
{
// Assume counter-clockwise order, or the test will be reversed
// Numerical tolerance check as opposed to zero
return mutable ccw? cross(sub(v3, v2), sub(v1, v2))[2] < -zed : cross(sub(v1, v2), sub(v3, v2))[2] < -zed;
}
function is_ear(v1, v2, v3, concave)
{
// Filter out our end vertices then check if remaining concave verts are in triangle.
// Return true only if none inside
return concave.filter((x) => !equal(x, v1) && !equal(x, v3))
.every((x) => !in_triangle(x, v1, v2, v3));
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
