29:null 2a:["$","title",null,{"children":"Polygon triangulation | tau | Observable"}] 2f: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; }30:[] 2d:{"id":"3665b85fd71662c4","slug":"broken-polygon-triangulation","title":"Polygon triangulation","thumbnail":"eb241e466c46b1da458818b8b88431d73d5ec9993104c80ffc293d0a9285b67c","access_level":"public","create_time":"$D2018-10-11T08:25:55.854Z","update_time":"$D2019-09-14T10:58:07.806Z","view_time":null,"first_public_time":"$D2018-10-12T19:12:56.990Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"8e8363b14a130065","login":"timhau","name":"tau","avatar_url":"https://avatars-next.observableusercontent.com/a3c8cec3733471c90bab096a990da9cfb3c5a02d8abcaaf3335550b6ff9e4234","tier":"starter_2024"},"version":730,"publish_version":730,"role":null,"authored":false,"authors":[{"type":"individual","id":"98fc0e4faeb2889d","login":"timhau","name":"tau","avatar_url":"https://avatars-next.observableusercontent.com/a3c8cec3733471c90bab096a990da9cfb3c5a02d8abcaaf3335550b6ff9e4234","tier":null}],"members":[{"type":"individual","id":"98fc0e4faeb2889d","login":"timhau","name":"tau","avatar_url":"https://avatars-next.observableusercontent.com/a3c8cec3733471c90bab096a990da9cfb3c5a02d8abcaaf3335550b6ff9e4234","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"ffea95499049c8c3","slug":"learning-geometry","title":"learning Geometry","owner":{"id":"8e8363b14a130065","login":"timhau","name":"tau"}},"type":"notebook","body":{"title":"Polygon triangulation","cells":[{"id":0,"value":"md`# Polygon triangulation\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":700,"value":"n = 450","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"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","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"import { sortByX, convexHull2D } from '@timhau/convex-hull'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W30","stdlib":"1","titling":"auto"}} 2e:"$2d:body"