2b:null 2c:["$","title",null,{"children":"Weighted Voronoi playground | Geckoslair | Observable"}] 31:T3f6a,// ConvexHull.js function epsilonesque(n) { return n === 0; return n >= -epsilon && n <= epsilon; } // IN: vectors or vertices // OUT: dot product var dot = function(v1, v2) { return (v1.x * v2.x) + (v1.y * v2.y) + (v1.z * v2.z); } // IN: Face face var Plane3D = function(face) { var p1 = face.verts[0]; var p2 = face.verts[1]; var p3 = face.verts[2]; this.a = p1.y * (p2.z-p3.z) + p2.y * (p3.z-p1.z) + p3.y * (p1.z-p2.z); this.b = p1.z * (p2.x-p3.x) + p2.z * (p3.x-p1.x) + p3.z * (p1.x-p2.x); this.c = p1.x * (p2.y-p3.y) + p2.x * (p3.y-p1.y) + p3.x * (p1.y-p2.y); this.d = -1 * (p1.x * (p2.y*p3.z - p3.y*p2.z) + p2.x * (p3.y*p1.z - p1.y*p3.z) + p3.x * (p1.y*p2.z - p2.y*p1.z)); } // OUT: int2D Plane3D.prototype.getDualPointMappedToPlane = function() { var nplane = this.getNormZPlane(); var dualPoint = new Point2D(nplane[0]/2, nplane[1]/2); return dualPoint; } Plane3D.prototype.getNormZPlane = function() { return [ -1 * (this.a / this.c), -1 * (this.b / this.c), -1 * (this.d / this.c) ]; } // IN: doubles x and y var Point2D = function(x, y) { this.x = x; this.y = y; } var ConflictListNode = function(face, vert) { this.face = face; this.vert = vert; this.nextf = null; this.prevf = null; this.nextv = null; this.prevv = null; } // IN: boolean forFace var ConflictList = function(forFace) { this.forFace = forFace; this.head = null; } // IN: ConflictListNode cln ConflictList.prototype.add = function(cln) { if (this.head === null) { this.head = cln; } else { if (this.forFace) { // Is FaceList this.head.prevv = cln; cln.nextv = this.head; this.head = cln; } else { // Is VertexList this.head.prevf = cln; cln.nextf = this.head; this.head = cln; } } } ConflictList.prototype.isEmpty = function() { return this.head === null; } // Array of faces visible ConflictList.prototype.fill = function(visible) { if (this.forFace) { return; } var curr = this.head; do { visible.push(curr.face); curr.face.marked = true; curr = curr.nextf; } while (curr !== null); } ConflictList.prototype.removeAll = function() { if (this.forFace) { // Remove all vertices from Face var curr = this.head; do { if (curr.prevf === null) { // Node is head if (curr.nextf === null) { curr.vert.conflicts.head = null; } else { curr.nextf.prevf = null; curr.vert.conflicts.head = curr.nextf; } } else { // Node is not head if (curr.nextf != null) { curr.nextf.prevf = curr.prevf; } curr.prevf.nextf = curr.nextf; } curr = curr.nextv; if (curr != null) { curr.prevv = null; } } while (curr != null); } else { // Remove all JFaces from vertex var curr = this.head; do { if (curr.prevv == null) { // Node is head if (curr.nextv == null) { curr.face.conflicts.head = null; } else { curr.nextv.prevv = null; curr.face.conflicts.head = curr.nextv; } } else { // Node is not head if (curr.nextv != null) { curr.nextv.prevv = curr.prevv; } curr.prevv.nextv = curr.nextv; } curr = curr.nextf; if (curr != null) curr.prevf = null; } while (curr != null); } } // IN: list of vertices ConflictList.prototype.getVertices = function() { var list = [], curr = this.head; while (curr !== null) { list.push(curr.vert); curr = curr.nextv; } return list; } // IN: coordinates x, y, z var Vertex = function(x, y, z, weight, orig, isDummy) { this.x = x; this.y = y; this.weight = epsilon; this.index = 0; this.conflicts = new ConflictList(false); this.neighbours = null; // Potential trouble this.nonClippedPolygon = null; this.polygon = null; this.originalObject = null; this.isDummy = false; if (orig !== undefined) { this.originalObject = orig; } if (isDummy != undefined) { this.isDummy = isDummy; } if (weight != null) { this.weight = weight; } if (z != null) { this.z = z; } else { this.z = this.projectZ(this.x, this.y, this.weight); } } Vertex.prototype.setWeight = function(weight) { this.weight = weight; this.z = this.projectZ(this.x, this.y, this.weight); } Vertex.prototype.projectZ = function(x, y, weight) { return ((x*x) + (y*y) - weight); } Vertex.prototype.subtract = function(v) { return new Vertex(v.x - this.x, v.y - this.y, v.z - this.z); } Vertex.prototype.crossproduct = function(v) { return new Vertex((this.y * v.z) - (this.z * v.y), (this.z * v.x) - (this.x * v.z), (this.x * v.y) - (this.y * v.x)); } Vertex.prototype.equals = function(v) { return (this.x === v.x && this.y === v.y && this.z === v.z); } // IN: coordinates x, y, z var Vector = function(x, y, z) { this.x = x; this.y = y; this.z = z; } Vector.prototype.negate = function() { this.x *= -1; this.y *= -1; this.z *= -1; } // Normalizes X Y and Z in-place Vector.prototype.normalize = function() { var len = Math.sqrt((this.x * this.x) + (this.y * this.y) + (this.z * this.z)); if (len > 0) { this.x /= len; this.y /= len; this.z /= len; } } // IN: Vertices a, b, c var Face = function(a, b, c, orient) { this.conflicts = new ConflictList(true); this.verts = [a, b, c]; this.marked = false; var t = (a.subtract(b)).crossproduct(b.subtract(c)); this.normal = new Vector(-t.x, -t.y, -t.z); this.normal.normalize(); this.createEdges(); this.dualPoint = null; if (orient != undefined) { this.orient(orient); } } // OUT: Point2D Face.prototype.getDualPoint = function() { if (this.dualPoint == null) { var plane3d = new Plane3D(this); this.dualPoint = plane3d.getDualPointMappedToPlane(); } return this.dualPoint; } Face.prototype.isVisibleFromBelow = function() { return (this.normal.z < -1.4259414393190911E-9); } Face.prototype.createEdges = function() { this.edges = []; this.edges[0] = new HEdge(this.verts[0], this.verts[1], this); this.edges[1] = new HEdge(this.verts[1], this.verts[2], this); this.edges[2] = new HEdge(this.verts[2], this.verts[0], this); this.edges[0].next = this.edges[1]; this.edges[0].prev = this.edges[2]; this.edges[1].next = this.edges[2]; this.edges[1].prev = this.edges[0]; this.edges[2].next = this.edges[0]; this.edges[2].prev = this.edges[1]; } // IN: vertex orient Face.prototype.orient = function(orient) { if (!(dot(this.normal,orient) < dot(this.normal, this.verts[0]))){ var temp = this.verts[1]; this.verts[1] = this.verts[2]; this.verts[2] = temp; this.normal.negate(); this.createEdges(); } } // IN: two vertices v0 and v1 Face.prototype.getEdge = function(v0, v1) { for (var i = 0; i < 3; i++) { if (this.edges[i].isEqual(v0, v1)) { return this.edges[i]; } } return null; } // IN: Face face, vertices v0 and v1 Face.prototype.link = function(face, v0, v1) { if (face instanceof Face) { var twin = face.getEdge(v0, v1); var edge = this.getEdge(v0, v1); if (twin === null || edge === null) { if (twin === null) { console.log("ERROR: can't find relevant edge on face"); } if (edge === null) { console.log("ERROR: can't find relevant edge on face"); } } twin.twin = edge; edge.twin = twin; } else { var e = face; var edge = this.getEdge(e.orig, e.dest); e.twin = edge; edge.twin = e; } } // IN: vertex v Face.prototype.conflict = function(v) { return (dot(this.normal, v) > dot(this.normal, this.verts[0]) + epsilon); } Face.prototype.getHorizon = function() { for (var i = 0; i < 3; i++) { if (this.edges[i].twin !== null && this.edges[i].twin.isHorizon()) { return this.edges[i]; } } return null; } Face.prototype.removeConflict = function() { this.conflicts.removeAll(); } // IN: vertex orig, vertex dest, Face face var HEdge = function(orig, dest, face) { this.next = null; this.prev = null; this.twin = null; this.orig = orig; this.dest = dest; this.iFace = face; } HEdge.prototype.isHorizon = function() { return this.twin !== null && this.twin.iFace.marked && !this.iFace.marked; } // IN: array horizon HEdge.prototype.findHorizon = function(horizon) { if (this.isHorizon()) { if (horizon.length > 0 && this === horizon[0]) { return; } else { horizon.push(this); this.next.findHorizon(horizon); } } else { if (this.twin !== null) { this.twin.next.findHorizon(horizon); } } } // IN: vertices origin and dest HEdge.prototype.isEqual = function(origin, dest) { return ((this.orig.equals(origin) && this.dest.equals(dest)) || (this.orig.equals(dest) && this.dest.equals(origin))); } var ConvexHull = { points: [], facets: [], created: [], horizon: [], visible: [], current: 0, // IN: sites (x,y,z) init: function(boundingSites, sites) { this.points = []; for (var i = 0; i < sites.length; i++) { this.points[i] = new Vertex(sites[i].x, sites[i].y, sites[i].z, null, sites[i], false); } this.points = this.points.concat(boundingSites); }, permutate: function() { var pointSize = this.points.length; for (var i = pointSize -1; i > 0; i--) { var ra = Math.floor(Math.random() * i); var temp = this.points[ra]; temp.index = i; var currentItem = this.points[i]; currentItem.index = ra; this.points.splice(ra, 1, currentItem); this.points.splice(i, 1, temp); } }, prep: function() { if (this.points.length <= 3) { console.log("ERROR: Less than 4 points"); } for (var i = 0; i < this.points.length; i++) { this.points[i].index = i; } var v0, v1, v2, v3; var f1, f2, f3, f0; v0 = this.points[0]; v1 = this.points[1]; v2 = v3 = null; for (var i = 2; i < this.points.length; i++) { if (!(this.linearDependent(v0, this.points[i]) && this.linearDependent(v1, this.points[i]))) { v2 = this.points[i]; v2.index = 2; this.points[2].index = i; this.points.splice(i, 1, this.points[2]); this.points.splice(2, 1, v2); break; } } if (v2 === null) { console.log("ERROR: v2 is null"); } f0 = new Face(v0, v1, v2); for (var i = 3; i < this.points.length; i++) { if (dot(f0.normal, f0.verts[0]) !== dot(f0.normal, this.points[i])) { v3 = this.points[i]; v3.index = 3; this.points[3].index = i; this.points.splice(i, 1, this.points[3]); this.points.splice(3, 1, v3); break; } } if (v3 === null) { console.log("ERROR: v3 is null"); } f0.orient(v3); f1 = new Face(v0, v2, v3, v1); f2 = new Face(v0, v1, v3, v2); f3 = new Face(v1, v2, v3, v0); this.addFacet(f0); this.addFacet(f1); this.addFacet(f2); this.addFacet(f3); // Connect facets f0.link(f1, v0, v2); f0.link(f2, v0, v1); f0.link(f3, v1, v2); f1.link(f2, v0, v3); f1.link(f3, v2, v3); f2.link(f3, v3, v1); this.current = 4; var v; for (var i = this.current; i < this.points.length; i++) { v = this.points[i]; if (f0.conflict(v)) { this.addConflict(f0, v); } if (f1.conflict(v)) { this.addConflict(f1, v); } if (f2.conflict(v)) { this.addConflict(f2, v); } if (f3.conflict(v)) { this.addConflict(f3,v); } } }, // IN: Faces old1 old2 and fn addConflicts: function(old1, old2, fn) { var l1 = old1.conflicts.getVertices(); var l2 = old2.conflicts.getVertices(); var nCL = []; var v1, v2; var i, l; i = l = 0; // Fill the possible new Conflict List while (i < l1.length || l < l2.length) { if (i < l1.length && l < l2.length) { v1 = l1[i]; v2 = l2[l]; // If the index is the same, it's the same vertex and only 1 has to be added if (v1.index === v2.index) { nCL.push(v1); i++; l++; } else if (v1.index > v2.index) { nCL.push(v1); i++; } else { nCL.push(v2); l++; } } else if ( i < l1.length) { nCL.push(l1[i++]); } else { nCL.push(l2[l++]); } } // Check if the possible conflicts are real conflicts for (var i = nCL.length - 1; i >= 0; i--) { v1 = nCL[i]; if (fn.conflict(v1)) this.addConflict(fn, v1); } }, // IN: Face face, Vertex v addConflict: function(face, vert) { var e = new ConflictListNode(face, vert); face.conflicts.add(e); vert.conflicts.add(e); }, // IN: Face f removeConflict: function(f) { f.removeConflict(); var index = f.index; f.index = -1; if (index === this.facets.length - 1) { this.facets.splice(this.facets.length - 1, 1); return; } if (index >= this.facets.length || index < 0) return; var last = this.facets.splice(this.facets.length - 1, 1); last[0].index = index; this.facets.splice(index, 1, last[0]); }, // IN: Face face addFacet: function(face) { face.index = this.facets.length; this.facets.push(face); }, compute: function() { this.prep(); while (this.current < this.points.length) { var next = this.points[this.current]; if (next.conflicts.isEmpty()) { // No conflict, point in hull this.current++; continue; } this.created = []; // TODO: make sure this is okay and doesn't dangle references this.horizon = []; this.visible = []; // The visible faces are also marked next.conflicts.fill(this.visible); // Horizon edges are orderly added to the horizon list var e; for (var jF = 0; jF < this.visible.length; jF++) { e = this.visible[jF].getHorizon(); if (e !== null) { e.findHorizon(this.horizon); break; } } var last = null, first = null; // Iterate over horizon edges and create new faces oriented with the marked face 3rd unused point for (var hEi = 0; hEi < this.horizon.length; hEi++) { var hE = this.horizon[hEi]; var fn = new Face(next, hE.orig, hE.dest, hE.twin.next.dest); fn.conflicts = new ConflictList(true); // Add to facet list this.addFacet(fn); this.created.push(fn); // Add new conflicts this.addConflicts(hE.iFace, hE.twin.iFace, fn); // Link the new face with the horizon edge fn.link(hE); if (last !== null) fn.link(last, next, hE.orig); last = fn; if (first === null) first = fn; } // Links the first and the last created JFace if (first !== null && last !== null) { last.link(first, next, this.horizon[0].orig); } if (this.created.length != 0) { // update conflict graph for (var f = 0; f < this.visible.length; f++) { this.removeConflict(this.visible[f]); } this.current++; this.created = []; } } return this.facets; }, // IN: two vertex objects, p1 and p2 // OUT: true if they are linearly dependent, false otherwise linearDependent: function(p1, p2) { if (p1.x == 0 && p2.x == 0) { if (p1.y == 0 && p2.y == 0) { if (p1.z == 0 && p2.z == 0) { return true; } if (p1.z == 0 || p2.z == 0) { return false; } return true; } if (p1.y == 0 || p2.y == 0) { return false; } if (epsilonesque(p1.z/p1.y - p2.z/p2.y)) { return true; } else { return false; } } if (p1.x == 0 || p2.x == 0) { return false; } if (epsilonesque(p1.y/p1.x - p2.y/p2.x) && epsilonesque(p1.z/p1.x - p2.z/p2.x)) { return true; } else { return false; } }, clear: function() { this.points = []; this.facets = []; this.created = []; this.horizon = []; this.visible = []; this.current = 0; } }32:[] 2f:{"id":"5f1021b85379522c","slug":null,"title":"Weighted Voronoi playground","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2022-12-02T16:27:08.640Z","update_time":"$D2022-12-02T18:07:50.444Z","view_time":null,"first_public_time":"$D2022-12-02T16:27:08.640Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"f730d71ac8df9684","login":"geckoslair","name":"Geckoslair","avatar_url":"https://avatars-next.observableusercontent.com/a9334481e702729724aa56c5742554242146346735589ee8f5f74d83d0247378","tier":"starter_2024"},"version":93,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"c1dd07c2ebd4e9be","login":"geckoslair","name":"Geckoslair","avatar_url":"https://avatars-next.observableusercontent.com/a9334481e702729724aa56c5742554242146346735589ee8f5f74d83d0247378","tier":null}],"members":[{"type":"individual","id":"c1dd07c2ebd4e9be","login":"geckoslair","name":"Geckoslair","avatar_url":"https://avatars-next.observableusercontent.com/a9334481e702729724aa56c5742554242146346735589ee8f5f74d83d0247378","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Weighted Voronoi playground","cells":[{"id":0,"value":"# Weighted Voronoi playground","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":12,"value":"svg = {\n const height = 500;\n const width = 960;\n const svg = d3\n .create(\"svg\")\n .attr(\"width\", width)\n .attr(\"height\", height);\n\n svg\n .append(\"defs\")\n .append(\"clipPath\")\n .attr(\"id\", \"clipper\")\n .append(\"rect\")\n .attr(\"x\", 0)\n .attr(\"y\", 0)\n .attr(\"width\", 960)\n .attr(\"height\", 500);\n\n const group = svg\n .append(\"g\")\n .attr(\"id\", \"drawing-area\")\n\n group\n .append(\"g\")\n .attr(\"id\", \"cell-container\")\n\n group\n .append(\"g\")\n .attr(\"id\", \"site-container\")\n\n \n \n\n const clippingPolygon = [[0,0], [0,height], [width,height], [width,0]];\n const cellLiner = d3.line()\n .x(function(d){ return d[0]; })\n .y(function(d){ return d[1]; });\n\n const clipper = d3.select(\"#clipper>rect\"),\n drawingArea = d3.select(\"#drawing-area\"),\n cellContainer = d3.select(\"#cell-container\"),\n siteContainer = d3.select(\"#site-container\");\n \n return svg.node();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"viewof voronoiSize = slider({\n min: 10,\n max: 100,\n step: 1,\n value: 10,\n title: 'Dimensione voronoi'\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"# Mutable","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":69,"value":"mutable cells = [[],[]]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"mutable points = [\n {index: 0, group: \"blue\", x: 100, y: 100, weight: 0},\n {index: 1, group: \"red\", x: 200, y: 200, weight:0},\n {index: 2, group: \"green\", x: 300, y: 400, weight:0},\n {index: 3, group: \"black\", x: 400, y: 600, weight:0}\n ]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"# Funzioni","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":32,"value":"function uc(w) { return (w<=0)? 0 : Math.sqrt(w); }","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"function weightUpdated() {\n var newWeights = [],\n index;\n newWeights[0] = +d3.select(\"#control-0 input\").node().value;\n newWeights[1] = +d3.select(\"#control-1 input\").node().value;\n if (newWeights[0] !== points[0].weight) {\n index = 0;\n } else {\n index = 1;\n }\n\n points[index].weight = newWeights[index];\n computeAllCells();\n\n redrawAllCells(WITHOUT_TRANSITION);\n redrawUnitCircle(index, WITHOUT_TRANSITION);\n redrawWeights(index);\n }","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"function computeAllCells() {\n //begin: map sites to the expected format of PowerDiagram\n var formatedSites = points.map(function(s) {\n return new Vertex(s.x, s.y, null, s.weight, s, false);\n })\n var boundingSites = getBoundingSites();\n //end: map sites to the expected format of PowerDiagram\n\n mutable cells = computePowerDiagramIntegrated(formatedSites, boundingSites, clippingPolygon);\n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"var epsilon = 1E-10\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"# Librerie","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":8,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"d3 = require(\"d3@5\", \"d3-weighted-voronoi\", \"d3-voronoi-map\", \"d3-voronoi-treemap\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W32","stdlib":"1"}} 30:"$2f:body"