31:T71e,function triangulate(poly, context) { const pl = poly.length; const triangles = []; const polyC = poly.slice(); if (pl <= 3) return poly; const [left, index] = polyC.reduce( (acc, cur, i) => { const [old, ind] = acc; if (old.length === 0) return [cur, i]; if (cur[0] < old[0]) return [cur, i]; if (cur[0] === old[0]) { if (cur[1] < old[1]) return [cur, i]; } return acc; }, [[], -1] ); let trian = [ polyC[index > 0 ? index - 1 : pl - 1], polyC[index], polyC[(index + 1) % pl] ]; const ccw = orientation(trian); while (polyC.length >= 3) { let reflex = []; let eartip = -1; for (let i = 0; i < polyC.length; ++i) { if (eartip >= 0) break; const p = i > 0 ? i - 1 : polyC.length - 1; const n = (i + 1) % polyC.length; const tri = [polyC[p], polyC[i], polyC[n]]; if (orientation(tri) !== ccw) { // triangle(tri, context, { color: "rgba(255,0,0,0.1)" }); reflex.push(i); } let isEar = true; for (let j = 0; j < reflex.length; ++j) { if (reflex[j] === p || reflex[j] === n) continue; if (inTriangle(tri, polyC[reflex[j]])) { isEar = false; break; } } if (isEar) { for (let j = i + 1; j < polyC.length; ++j) { if (j === p || j === n) continue; if (inTriangle(tri, polyC[j])) { isEar = false; break; } } } if (isEar) eartip = i; } if (eartip < 0) break; const earp = eartip > 0 ? eartip - 1 : polyC.length - 1; const earn = (eartip + 1) % polyC.length; const parts = [polyC[earp], polyC[eartip], polyC[earn]]; triangles.push(parts); polyC.splice(eartip, 1); } return triangles; }32:[] 2f:{"title":"Polygon triangulation","cells":[{"id":0,"value":"md`# Polygon triangulation\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"{\n const context = DOM.context2d(width, width);\n\n const c = [width / 2, width / 2, 100];\n const poly = randPolygon(c, n, context);\n\n const triangles = triangulate(poly, context);\n triangles.forEach(tr => triangle(tr, context, { color: \"rgba(0,0,0,0.1)\" }));\n\n return context.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":700,"value":"n = 450","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"function randPolygon(c, n, context) {\n const cr = c[2];\n const pts = [];\n while (pts.length < n) {\n const rp = randomPoint(c, [cr + 10, 200], pts.length * (360 / n));\n if (dist2D(c, rp) > cr) {\n pts.push(rp);\n }\n }\n\n const con = convexHull2D(pts, context);\n return con;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"function randomPoint(c, [min,max], deg) {\n const rlen = min + Math.floor(Math.random() * max);\n return coordsFromDeg(deg, rlen, c);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":95,"value":"function orientation([[x1, y1], [x2, y2], [x3, y3]]) {\n return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) >= 0;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":99,"value":"function inTriangle([[x1, y1], [x2, y2], [x3, y3]], [px, py]) {\n let denom = (y2 - y3) * (x1 - x3) + (x3 - x2) * (y1 - y3);\n if (denom === 0) return true;\n denom = 1 / denom;\n\n const alpha = denom * ((y2 - y3) * (px - x3) + (x3 - x2) * (py - y3));\n if (alpha < 0) return false;\n\n const beta = denom * ((y3 - y1) * (px - x3) + (x1 - x3) * (py - y3));\n if (beta < 0) return false;\n\n return alpha + beta >= 1;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":110,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":4,"value":"import {\n dist2D,\n line,\n circle,\n coordsFromDeg,\n triangle,\n incircleTriangle,\n} from '@timhau/geometry'","pinned":false,"hidden":false,"mode":"ojs"},{"id":118,"value":"import { sortByX, convexHull2D } from '@timhau/convex-hull'","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}