2d:null 2e:["$","title",null,{"children":"Circle Packing | John C | Observable"}] 33:T68c,p5(s => { let started = false, finished = false, init = false, time = 0; let min = 5, max = 40; let circles = []; s.setup = function(){ s.createCanvas(600,600); } s.draw = function () { if (!started) { s.textAlign(s.CENTER, s.CENTER); s.textSize(20); s.text("click to start", s.width/2, s.height/2); s.noLoop(); } else { if (!init) { init = true; doInit(); } else { let x = Math.random() * s.width; let y = Math.random() * s.height; let r = min; let tries = 0 while(!validateCircle(x, y, r) ) { tries ++; x = Math.random() * s.width; y = Math.random() * s.height; if (tries > 10000) { time++; return; } } while(validateCircle(x, y, r)) { r ++; } s.circle(x, y, r*2); circles.push([x, y, r]); if (circles.length > 500 || time > 300) { s.noLoop(); } } } } const doInit = () =>{ s.background(255); circles = []; time = 0; } const validateCircle = (x, y, r) => { if (r > max) return false; for (let i = 0; i < circles.length; ++i) { let c = circles[i]; let cx = c[0]; let cy = c[1]; let cr = c[2]; if (s.dist(cx,cy,x,y) < cr + r) { return false; } } return true; } s.mouseClicked = function () { if (s.mouseX > s.width || s.mouseX < 0 || s.mouseY > s.height || s.mouseY < 0) return; if (!started) { started = true; s.loop(); } if (started) { doInit(); s.loop(); } } })34:Tc63,p5(s =>{ class circle{ constructor(x, y, r){ this.loc = s.createVector(x,y); this.v = p5c.Vector.random2D(); this.a = s.createVector(0,0); this.r = r; } applyForce(force){ this.a.add(force); } update(){ this.v.add(this.a); if (this.v.magSq() > 1) this.v = this.v.normalize(); this.a.mult(0); this.loc.add(this.v); } display(){ s.circle(this.loc.x, this.loc.y, this.r * 2); } } let circles = [], forces = [], neighbourCount = []; let maxR = maxSize; let minR = 5; let isDone = false, started = false; s.setup = function(){ s.createCanvas(600,600); s.background(0); s.stroke(255); s.noFill(); reset(); //s.frameRate(1); } let reset = function(){ circles = []; let circleNo = 100; for(let i = 0 ; i < circleNo; i ++){ circles.push(new circle(s.width/2, s.height/2, minR + Math.random() * (maxR - minR))); } } let checkOthers = () => { forces = []; neighbourCount = Array(circles.length).fill(0); for (let i = 0; i < circles.length; i ++) { let ci = circles[i]; if (forces[i] === undefined) forces[i] = s.createVector(0,0); for (let j = i + 1; j < circles.length; j++){ let cj = circles[j]; if (forces[j] === undefined) forces[j] = s.createVector(0,0); let d = p5c.Vector.dist(ci.loc, cj.loc); if (d < ci.r + cj.r) { if (d > 0){ let f = p5c.Vector.sub(ci.loc, cj.loc); f = f.normalize(); f = f.div(d); forces[i] = forces[i].add(f); forces[j] = forces[j].sub(f); } neighbourCount[i] ++; neighbourCount[j] ++; } } } } let updateAndDisplay = () => { circles.forEach((c,i) => { if (neighbourCount[i] === 0) { c.v.x = 0; c.v.y = 0; } else if (isDone) { isDone = false; } let f = forces[i]; f.div(neighbourCount[i] > 0 ? neighbourCount[i] : 1); if (f.magSq() > 0) { f = f.normalize(); f = f.sub(c.v); f = f.limit(1); } c.applyForce(f); if ((c.loc.x - c.r <= 0 && c.v.x <= 0) || (c.loc.x + c.r >= s.width && c.v.x >=0)){ c.v.x *= -1; } if ((c.loc.y - c.r <= 0 && c.v.y <= 0) || (c.loc.y + c.r >= s.height && c.v.y >=0)){ c.v.y *= -1; } c.update(); c.display(); }) } s.draw = function () { if (!started){ s.push(); s.fill(255); s.textAlign(s.CENTER,s.CENTER); s.textSize(20); s.text("Click to start", s.width/2, s.height/2); s.pop(); s.noLoop(); } else { s.background(0); isDone = true; checkOthers(); updateAndDisplay(); if (isDone) { isDone = false; s.noLoop(); } } } s.mouseClicked = function(){ if (s.mouseX > 0 && s.mouseY > 0 && s.mouseX < s.width && s.mouseY < s.height){ if (!started){ started = true; s.loop(); } else { reset(); s.loop(); } } } })35:Tc71,p5(s =>{ class circle{ constructor(x, y, r){ this.loc = s.createVector(x,y); this.v = p5c.Vector.random2D(); this.a = s.createVector(0,0); this.r = r; } applyForce(force){ this.a.add(force); } update(){ this.v.add(this.a); if (this.v.magSq() > 1) this.v = this.v.normalize(); this.a.mult(0); this.loc.add(this.v); this.r = s.noise(this.loc.x * 0.01, this.loc.y*0.01) * 20; } display(){ s.circle(this.loc.x, this.loc.y, this.r * 2); } } let circles = [], forces = [], neighbourCount = []; let maxR = 0; let minR = 5; let isDone = false; s.setup = function(){ s.createCanvas(600,600); s.background(0); s.stroke(255); s.noFill(); reset(); //s.frameRate(1); } let reset = function(){ circles = []; let circleNo = 400; for(let i = 0 ; i < circleNo; i ++){ circles.push(new circle(s.width/2, s.height/2, 10)); } } let checkOthers = () => { forces = []; neighbourCount = Array(circles.length).fill(0); for (let i = 0; i < circles.length; i ++) { let ci = circles[i]; if (forces[i] === undefined) forces[i] = s.createVector(0,0); for (let j = i + 1; j < circles.length; j++){ let cj = circles[j]; if (forces[j] === undefined) forces[j] = s.createVector(0,0); let d = p5c.Vector.dist(ci.loc, cj.loc); if (d < ci.r + cj.r) { if (d > 0){ let f = p5c.Vector.sub(ci.loc, cj.loc); f = f.normalize(); f = f.div(d); forces[i] = forces[i].add(f); forces[j] = forces[j].sub(f); } neighbourCount[i] ++; neighbourCount[j] ++; } } } } let updateAndDisplay = () => { circles.forEach((c,i) => { if (neighbourCount[i] === 0) { c.v.x = 0; c.v.y = 0; } else if (isDone) { isDone = false; } let f = forces[i]; f.div(neighbourCount[i] > 0 ? neighbourCount[i] : 1); if (f.magSq() > 0) { f = f.normalize(); f = f.sub(c.v); f = f.limit(1); } c.applyForce(f); if ((c.loc.x - c.r <= 0 && c.v.x <= 0) || (c.loc.x + c.r >= s.width && c.v.x >=0)){ c.v.x *= -1; } if ((c.loc.y - c.r <= 0 && c.v.y <= 0) || (c.loc.y + c.r >= s.height && c.v.y >=0)){ c.v.y *= -1; } c.update(); c.display(); }) } let started = false; s.draw = function () { if (!started) { s.push(); s.fill(255); s.textAlign(s.CENTER,s.CENTER); s.textSize(20); s.text("Click to start", s.width/2, s.height/2); s.pop(); s.noLoop(); } else { s.background(0); isDone = true; checkOthers(); updateAndDisplay(); if (isDone) { isDone = false; s.noLoop(); } } } s.mouseClicked = function(){ if (s.mouseX > 0 && s.mouseY > 0 && s.mouseX < s.width && s.mouseY < s.height){ if (!started) { started = true; s.loop(); } else { reset(); s.loop(); } } } })36:Tdc2,p5(s =>{ class circle{ constructor(x, y, r){ this.loc = s.createVector(x,y); this.v = p5c.Vector.random2D(); this.a = s.createVector(0,0); this.r = r; } applyForce(force){ this.a.add(force); } update(){ this.v.add(this.a); if (this.v.magSq() > 1) this.v = this.v.normalize(); this.a.mult(0); this.loc.add(this.v); } display(){ s.circle(this.loc.x, this.loc.y, this.r * 2); } updateSize(noN){ if (noN > 5) this.r *= 0.99; if (noN < 5) this.r *= 1.01 if (this.r < minR) this.r = minR; if (this.r > maxR) this.r = maxR; } } let circles = [], forces = [], neighbourCount = [], closerCount = []; let maxR = maxSize; let minR = 5; let isDone = false; s.setup = function(){ s.createCanvas(600,600); s.background(0); s.stroke(255); s.noFill(); reset(); //s.frameRate(1); } let reset = function(){ circles = []; let circleNo = 200; for(let i = 0 ; i < circleNo; i ++){ circles.push(new circle(s.width/2, s.height/2, 30)); } } let checkOthers = () => { forces = []; neighbourCount = Array(circles.length).fill(0); closerCount = Array(circles.length).fill(0); for (let i = 0; i < circles.length; i ++) { let ci = circles[i]; if (forces[i] === undefined) forces[i] = s.createVector(0,0); for (let j = i + 1; j < circles.length; j++){ let cj = circles[j]; if (forces[j] === undefined) forces[j] = s.createVector(0,0); let d = p5c.Vector.dist(ci.loc, cj.loc); if (d < ci.r + cj.r) { if (d > 0){ let f = p5c.Vector.sub(ci.loc, cj.loc); f = f.normalize(); f = f.div(d); forces[i] = forces[i].add(f); forces[j] = forces[j].sub(f); } neighbourCount[i] ++; neighbourCount[j] ++; } if (d < (ci.r + cj.r) * 1.5) { closerCount[i] ++; closerCount[j] ++; } } } } let updateAndDisplay = () => { circles.forEach((c,i) => { if (neighbourCount[i] === 0) { c.v.x = 0; c.v.y = 0; } else if (isDone) { isDone = false; } c.updateSize(closerCount[i]); let f = forces[i]; f.div(neighbourCount[i] > 0 ? neighbourCount[i] : 1); if (f.magSq() > 0) { f = f.normalize(); f = f.sub(c.v); f = f.limit(1); } c.applyForce(f); if ((c.loc.x - c.r <= 0 && c.v.x <= 0) || (c.loc.x + c.r >= s.width && c.v.x >=0)){ c.v.x *= -1; } if ((c.loc.y - c.r <= 0 && c.v.y <= 0) || (c.loc.y + c.r >= s.height && c.v.y >=0)){ c.v.y *= -1; } c.update(); c.display(); }) } let started = false; s.draw = function () { if (!started) { s.push(); s.fill(255); s.textAlign(s.CENTER,s.CENTER); s.textSize(20); s.text("Click to start", s.width/2, s.height/2); s.pop(); s.noLoop(); } else { s.background(0); isDone = true; checkOthers(); updateAndDisplay(); if (isDone) { isDone = false; s.noLoop(); } } } s.mouseClicked = function(){ if (s.mouseX > 0 && s.mouseY > 0 && s.mouseX < s.width && s.mouseY < s.height){ if (!started) { started = true; s.loop(); } else { reset(); s.loop(); } } } })37:T2033,p5(s => { class Circle{ constructor(x, y, r, d){ this.x = x; this.y = y; this.r = r; this.distance = d; } } const distanceSqCircles = function(circle1, circle2){ return (circle1.x - circle2.x)*(circle1.x - circle2.x) + (circle1.y - circle2.y)*(circle1.y - circle2.y); } const distanceCircles = function(c1, c2){ return Math.sqrt(distanceSqCircles(c1,c2)); } const distanceSqFromOrigin = function(circle) { return circle.x * circle.x + circle.y * circle.y; } const distanceFromOrigin = function(circle){ return Math.sqrt(distanceSqFromOrigin(circle)); } const newCircle = function(cm, cn, r){ let angle1 = Math.atan2(cn.y - cm.y, cn.x - cm.x); let angle2 = Math.acos((distanceSqCircles(cm,cn) + (cm.r + r) * (cm.r + r) - (cn.r + r) * (cn.r + r)) / (2*(cm.r + r)*distanceCircles(cm,cn))); let sol1 = new Circle(cm.x+(cm.r+r)*Math.cos(angle1+angle2),cm.y+(cm.r+r)*Math.sin(angle1+angle2),r,undefined); let sol2 = new Circle(cm.x+(cm.r+r)*Math.cos(angle1-angle2),cm.y+(cm.r+r)*Math.sin(angle1-angle2),r,undefined); sol1.distance = distanceFromOrigin(sol1); sol2.distance = distanceFromOrigin(sol2); return [sol1, sol2]; } const init = function(r0, r1, r2){ let circles = [new Circle(0,0,r0,undefined), new Circle(r0+r1,0,r1,undefined)]; let arr = newCircle(circles[0], circles[1], r2); if (arr[0].y < 0){ circles.push(arr[0]); } else { circles.push(arr[1]); } let a = r0+r1, b = r0 + r2, c = r1+r2; let s = (a+b+c)/2; let delta = Math.sqrt(s*(s-a)*(s-b)*(s-c)); let l1 = a + delta/(s-a), l2 = b + delta/(s-b), l3 = c + delta/(s-c); let lsum = l1 + l2 + l3; l1 = l1/lsum; l2 = l2/lsum; l3 = l3/lsum; let xEDP = l1*circles[2].x + l2*circles[1].x + l3*circles[0].x; let yEDP = l1*circles[2].y + l2*circles[1].y + l3*circles[0].y; for (let ind = 0; ind < circles.length; ind++){ let circle = circles[ind]; circle.x = circle.x - xEDP; circle.y = circle.y - yEDP; circle.distance = distanceFromOrigin(circle); } let frontChain = new DoubleLinkedList(...circles); let cm; let minD = Number.POSITIVE_INFINITY; for (let node of frontChain.iterNodes()){ if (node.value.distance < minD){ cm = node; minD = node.value.distance; } } return { circles:circles, cm:cm, frontChain:frontChain }; } const candidateCircle = function(cm, r, frontChain){ let cn = cm.next; if (cn === null) cn = frontChain.first; let arr = newCircle(cm.value, cn.value, r); let d = (arr[0].x-cm.value.x)*(cn.value.y-cm.value.y)-(arr[0].y-cm.value.y)*(cn.value.x-cm.value.x); if (d < 0) return arr[0]; return arr[1]; } const checkIntersect = function(candidate, cm, frontChain){ let cn = cm.next; if (cn === null) cn = frontChain.first; let intersectingNode = null; let direction = 0; let intersectingNodes = []; let totalDistance = 0; for (const node of frontChain.iterNodes()){ if (distanceCircles(candidate, node.value) - (node.value.r + candidate.r) < -0.00000001){ intersectingNodes.push(node); } totalDistance += 2 * node.value.r; } if (intersectingNodes.length === 0) return {intersectingNode:intersectingNode, direction:direction}; let distances = intersectingNodes.map(node => distanceToNode(node, cm, cn, frontChain,totalDistance)); let minIndex, minDistance = Number.POSITIVE_INFINITY; distances.forEach((d,i) => { s.rect(intersectingNodes[i].value.x - 5, intersectingNodes[i].value.y - 5, 10, 10); let localMin = Math.min(d[0],d[1]); if (localMin < minDistance) { minDistance = d; minIndex = i; } }) intersectingNode = intersectingNodes[minIndex]; if (minDistance[0] < minDistance[1]) { direction = -1; } else { direction = 1; } return {intersectingNode:intersectingNode, direction:direction, mul: distances.length > 1}; } const distanceToNode = function(toNode, cm, cn, frontChain,totalDistance){ let cmBacwardDistance = 0; let currentNode = cm; while(true) { cmBacwardDistance += 2 * currentNode.value.r; if (currentNode == frontChain.first){ currentNode = frontChain.last; } else { currentNode = currentNode.prev; } if (currentNode === toNode) break; } let cnForwardDistance = totalDistance - cmBacwardDistance - 2*toNode.value.r; return [cmBacwardDistance, cnForwardDistance]; } const removeNodesAhead = function(toNode, cm, frontChain){ while(cm.next !== toNode){ if (cm === frontChain.last){ if (frontChain.first === toNode) break; frontChain.popLeft(); continue; } frontChain.remove(cm.next); } } const remodeNodesBehind = function(toNode, cn, frontChain){ while(cn.prev !== toNode) { if (cn === frontChain.first){ if (frontChain.last === toNode) break; frontChain.pop(); continue; } frontChain.remove(cn.prev); } } const modifyFrontChain = function(intersectingNode,cm,frontChain,direction){ if (direction === 0) return {cm:cm, modified:false}; if (direction === -1) { let cn = cm.next; //console.log("cm", cm.owner) if (cn === null) cn = frontChain.first; remodeNodesBehind(intersectingNode,cn,frontChain); cm = intersectingNode; } else { removeNodesAhead(intersectingNode, cm, frontChain); } return {cm:cm, modified:true}; } const resolveIntersection = function(cm, r, frontChain){ let intersections = true; let res; let tries = 1; while(intersections && tries < 100) { let candidate = candidateCircle(cm, r, frontChain); let obj = checkIntersect(candidate,cm,frontChain); let intersectingNode = obj.intersectingNode; let direction = obj.direction; let mul = obj.mul; intersections = intersectingNode !== null; if (intersections){ if (mul) { cm = cm.prev ? cm.prev : frontChain.last; } else { let obj2 = modifyFrontChain(intersectingNode, cm, frontChain, direction); cm = obj2.cm; } } tries ++; res = candidate; } return {cm:cm, candidate:res, success: tries < 100}; } let started = false; let frontChain; let cm; let history = []; let minR = 5, maxR = 30; s.setup = function(){ s.createCanvas(600,600); s.background(255); } s.draw = function () { if (!started) { s.textAlign(s.CENTER, s.CENTER); s.textSize(20); s.text("click to start", s.width/2, s.height/2); s.noLoop(); } else { s.background(255); s.translate(s.width/2,s.height/2); s.stroke(0); let r = s.random(minR,maxR); let obj = resolveIntersection(cm, r, frontChain); let newNode = obj.candidate; cm = obj.cm; let success = obj.success; if (success) { frontChain.insertAfter(newNode,cm); history.forEach(c => { s.circle(c.x,c.y,c.r*2); }) // frontChain.toArray().forEach(c => { // s.circle(c.x,c.y,c.r*2); // }) s.stroke(0,255,0); s.circle(cm.value.x,cm.value.y,cm.value.r*2); s.stroke(255,0,0); s.circle(newNode.x,newNode.y,newNode.r*2); history.push(newNode); } else { s.noLoop(); } //s.noLoop(); if (history.length > 200) { s.background(255); history.forEach(c => { s.circle(c.x,c.y,c.r*2); }) s.noLoop(); } } } s.mouseClicked = function () { if (s.mouseX > s.width || s.mouseX < 0 || s.mouseY > s.height || s.mouseY < 0) return; if (!started) { started = true; s.background(255); s.frameRate(5); s.noFill(); s.stroke(0); let obj = init(s.random(minR,maxR), s.random(minR,maxR), s.random(minR,maxR)); cm = obj.cm; frontChain = obj.frontChain; s.translate(s.width/2,s.height/2); obj.circles.forEach(c => { history.push(c); }) s.loop(); } } })38:T1fef,p5(s => { class Circle{ constructor(x, y, r, d){ this.x = x; this.y = y; this.r = r; this.distance = d; this.currentR = 5; this.ongoing = true; } display(){ s.circle(this.x, this.y, this.currentR * 2); } update(){ this.currentR += 0.5; if (this.currentR >= this.r) { this.currentR = this.r; this.ongoing = false; } } } const distanceSqCircles = function(circle1, circle2){ return (circle1.x - circle2.x)*(circle1.x - circle2.x) + (circle1.y - circle2.y)*(circle1.y - circle2.y); } const distanceCircles = function(c1, c2){ return Math.sqrt(distanceSqCircles(c1,c2)); } const distanceSqFromOrigin = function(circle) { return circle.x * circle.x + circle.y * circle.y; } const distanceFromOrigin = function(circle){ return Math.sqrt(distanceSqFromOrigin(circle)); } const newCircle = function(cm, cn, r){ let angle1 = Math.atan2(cn.y - cm.y, cn.x - cm.x); let angle2 = Math.acos((distanceSqCircles(cm,cn) + (cm.r + r) * (cm.r + r) - (cn.r + r) * (cn.r + r)) / (2*(cm.r + r)*distanceCircles(cm,cn))); let sol1 = new Circle(cm.x+(cm.r+r)*Math.cos(angle1+angle2),cm.y+(cm.r+r)*Math.sin(angle1+angle2),r,undefined); let sol2 = new Circle(cm.x+(cm.r+r)*Math.cos(angle1-angle2),cm.y+(cm.r+r)*Math.sin(angle1-angle2),r,undefined); sol1.distance = distanceFromOrigin(sol1); sol2.distance = distanceFromOrigin(sol2); return [sol1, sol2]; } const init = function(r0, r1, r2){ let circles = [new Circle(0,0,r0,undefined), new Circle(r0+r1,0,r1,undefined)]; let arr = newCircle(circles[0], circles[1], r2); if (arr[0].y < 0){ circles.push(arr[0]); } else { circles.push(arr[1]); } let a = r0+r1, b = r0 + r2, c = r1+r2; let s = (a+b+c)/2; let delta = Math.sqrt(s*(s-a)*(s-b)*(s-c)); let l1 = a + delta/(s-a), l2 = b + delta/(s-b), l3 = c + delta/(s-c); let lsum = l1 + l2 + l3; l1 = l1/lsum; l2 = l2/lsum; l3 = l3/lsum; let xEDP = l1*circles[2].x + l2*circles[1].x + l3*circles[0].x; let yEDP = l1*circles[2].y + l2*circles[1].y + l3*circles[0].y; for (let ind = 0; ind < circles.length; ind++){ let circle = circles[ind]; circle.x = circle.x - xEDP; circle.y = circle.y - yEDP; circle.distance = distanceFromOrigin(circle); } let frontChain = new DoubleLinkedList(...circles); let cm; let minD = Number.POSITIVE_INFINITY; for (let node of frontChain.iterNodes()){ if (node.value.distance < minD){ cm = node; minD = node.value.distance; } } return { circles:circles, cm:cm, frontChain:frontChain }; } const candidateCircle = function(cm, r, frontChain){ let cn = cm.next; if (cn === null) cn = frontChain.first; let arr = newCircle(cm.value, cn.value, r); let d = (arr[0].x-cm.value.x)*(cn.value.y-cm.value.y)-(arr[0].y-cm.value.y)*(cn.value.x-cm.value.x); if (d < 0) return arr[0]; return arr[1]; } const checkIntersect = function(candidate, cm, frontChain){ let cn = cm.next; if (cn === null) cn = frontChain.first; let intersectingNode = null; let direction = 0; let intersectingNodes = []; let totalDistance = 0; for (const node of frontChain.iterNodes()){ if (distanceCircles(candidate, node.value) - (node.value.r + candidate.r) < -0.00000001){ intersectingNodes.push(node); } totalDistance += 2 * node.value.r; } if (intersectingNodes.length === 0) return {intersectingNode:intersectingNode, direction:direction}; let distances = intersectingNodes.map(node => distanceToNode(node, cm, cn, frontChain,totalDistance)); let minIndex, minDistance = Number.POSITIVE_INFINITY; distances.forEach((d,i) => { let localMin = Math.min(d[0],d[1]); if (localMin < minDistance) { minDistance = d; minIndex = i; } }) intersectingNode = intersectingNodes[minIndex]; if (minDistance[0] < minDistance[1]) { direction = -1; } else { direction = 1; } return {intersectingNode:intersectingNode, direction:direction, mul: distances.length > 1}; } const distanceToNode = function(toNode, cm, cn, frontChain,totalDistance){ let cmBacwardDistance = 0; let currentNode = cm; while(true) { cmBacwardDistance += 2 * currentNode.value.r; if (currentNode == frontChain.first){ currentNode = frontChain.last; } else { currentNode = currentNode.prev; } if (currentNode === toNode) break; } let cnForwardDistance = totalDistance - cmBacwardDistance - 2*toNode.value.r; return [cmBacwardDistance, cnForwardDistance]; } const removeNodesAhead = function(toNode, cm, frontChain){ while(cm.next !== toNode){ if (cm === frontChain.last){ if (frontChain.first === toNode) break; frontChain.popLeft(); continue; } frontChain.remove(cm.next); } } const remodeNodesBehind = function(toNode, cn, frontChain){ while(cn.prev !== toNode) { if (cn === frontChain.first){ if (frontChain.last === toNode) break; frontChain.pop(); continue; } frontChain.remove(cn.prev); } } const modifyFrontChain = function(intersectingNode,cm,frontChain,direction){ if (direction === 0) return {cm:cm, modified:false}; if (direction === -1) { let cn = cm.next; if (cn === null) cn = frontChain.first; remodeNodesBehind(intersectingNode,cn,frontChain); cm = intersectingNode; } else { removeNodesAhead(intersectingNode, cm, frontChain); } return {cm:cm, modified:true}; } const resolveIntersection = function(cm, r, frontChain){ let intersections = true; let res; let tries = 1; while(intersections && tries < 100) { let candidate = candidateCircle(cm, r, frontChain); let obj = checkIntersect(candidate,cm,frontChain); let intersectingNode = obj.intersectingNode; let direction = obj.direction; let mul = obj.mul; intersections = intersectingNode !== null; if (intersections){ if (mul) { cm = cm.prev ? cm.prev : frontChain.last; } else { let obj2 = modifyFrontChain(intersectingNode, cm, frontChain, direction); cm = obj2.cm; } } tries ++; res = candidate; } return {cm:cm, candidate:res, success: tries < 100}; } let started = false; let frontChain; let cm; let history = []; let minR = 5, maxR = 30; s.setup = function(){ s.createCanvas(600,600); s.background(255); } s.draw = function () { if (!started) { s.background(10); s.fill(255); s.textAlign(s.CENTER, s.CENTER); s.textSize(20); s.text("click to start", s.width/2, s.height/2); s.noLoop(); } else { s.background(10); s.translate(s.width/2,s.height/2); s.stroke(240); if (history.length < 200){ let r = s.random(minR,maxR); let obj = resolveIntersection(cm, r, frontChain); let newNode = obj.candidate; cm = obj.cm; let success = obj.success; if (success) { history.push(newNode); frontChain.insertAfter(newNode,cm); } } let done = true; history.forEach(c => { c.display(); if (c.ongoing) { c.update(); done = false; } }) //s.noLoop(); if (done) { s.noLoop(); } } } s.mouseClicked = function () { if (s.mouseX > s.width || s.mouseX < 0 || s.mouseY > s.height || s.mouseY < 0) return; if (!started) { started = true; s.background(255); s.frameRate(30); s.noFill(); s.stroke(0); let obj = init(s.random(minR,maxR), s.random(minR,maxR), s.random(minR,maxR)); cm = obj.cm; frontChain = obj.frontChain; s.translate(s.width/2,s.height/2); obj.circles.forEach(c => { history.push(c); }) s.loop(); } } })39:T2109,p5(s => { class Circle{ constructor(x, y, r, d){ this.x = x; this.y = y; this.r = r; this.distance = d; this.currentR = 5; this.ongoing = true; } display(){ s.circle(this.x, this.y, this.currentR * 2); } update(){ this.currentR += 0.5; if (this.currentR >= this.r) { this.currentR = this.r; this.ongoing = false; } } } const distanceSqCircles = function(circle1, circle2){ return (circle1.x - circle2.x)*(circle1.x - circle2.x) + (circle1.y - circle2.y)*(circle1.y - circle2.y); } const distanceCircles = function(c1, c2){ return Math.sqrt(distanceSqCircles(c1,c2)); } const distanceSqFromOrigin = function(circle) { return circle.x * circle.x + circle.y * circle.y; } const distanceFromOrigin = function(circle){ return Math.sqrt(distanceSqFromOrigin(circle)); } const newCircle = function(cm, cn, r){ let angle1 = Math.atan2(cn.y - cm.y, cn.x - cm.x); let angle2 = Math.acos((distanceSqCircles(cm,cn) + (cm.r + r) * (cm.r + r) - (cn.r + r) * (cn.r + r)) / (2*(cm.r + r)*distanceCircles(cm,cn))); let sol1 = new Circle(cm.x+(cm.r+r)*Math.cos(angle1+angle2),cm.y+(cm.r+r)*Math.sin(angle1+angle2),r,undefined); let sol2 = new Circle(cm.x+(cm.r+r)*Math.cos(angle1-angle2),cm.y+(cm.r+r)*Math.sin(angle1-angle2),r,undefined); sol1.distance = distanceFromOrigin(sol1); sol2.distance = distanceFromOrigin(sol2); return [sol1, sol2]; } const init = function(r0, r1, r2){ let circles = [new Circle(0,0,r0,undefined), new Circle(r0+r1,0,r1,undefined)]; let arr = newCircle(circles[0], circles[1], r2); if (arr[0].y < 0){ circles.push(arr[0]); } else { circles.push(arr[1]); } let a = r0+r1, b = r0 + r2, c = r1+r2; let s = (a+b+c)/2; let delta = Math.sqrt(s*(s-a)*(s-b)*(s-c)); let l1 = a + delta/(s-a), l2 = b + delta/(s-b), l3 = c + delta/(s-c); let lsum = l1 + l2 + l3; l1 = l1/lsum; l2 = l2/lsum; l3 = l3/lsum; let xEDP = l1*circles[2].x + l2*circles[1].x + l3*circles[0].x; let yEDP = l1*circles[2].y + l2*circles[1].y + l3*circles[0].y; for (let ind = 0; ind < circles.length; ind++){ let circle = circles[ind]; circle.x = circle.x - xEDP; circle.y = circle.y - yEDP; circle.distance = distanceFromOrigin(circle); } let frontChain = new DoubleLinkedList(...circles); let cm; let minD = Number.POSITIVE_INFINITY; for (let node of frontChain.iterNodes()){ if (node.value.distance < minD){ cm = node; minD = node.value.distance; } } return { circles:circles, cm:cm, frontChain:frontChain }; } const candidateCircle = function(cm, r, frontChain){ let cn = cm.next; if (cn === null) cn = frontChain.first; let arr = newCircle(cm.value, cn.value, r); let d = (arr[0].x-cm.value.x)*(cn.value.y-cm.value.y)-(arr[0].y-cm.value.y)*(cn.value.x-cm.value.x); if (d < 0) return arr[0]; return arr[1]; } const checkIntersect = function(candidate, cm, frontChain){ let cn = cm.next; if (cn === null) cn = frontChain.first; let intersectingNode = null; let direction = 0; let intersectingNodes = []; let totalDistance = 0; for (const node of frontChain.iterNodes()){ if (distanceCircles(candidate, node.value) - (node.value.r + candidate.r) < -0.00000001){ intersectingNodes.push(node); } totalDistance += 2 * node.value.r; } if (intersectingNodes.length === 0) return {intersectingNode:intersectingNode, direction:direction}; let distances = intersectingNodes.map(node => distanceToNode(node, cm, cn, frontChain,totalDistance)); let minIndex, minDistance = Number.POSITIVE_INFINITY; distances.forEach((d,i) => { let localMin = Math.min(d[0],d[1]); if (localMin < minDistance) { minDistance = d; minIndex = i; } }) intersectingNode = intersectingNodes[minIndex]; if (minDistance[0] < minDistance[1]) { direction = -1; } else { direction = 1; } return {intersectingNode:intersectingNode, direction:direction, mul: distances.length > 1}; } const distanceToNode = function(toNode, cm, cn, frontChain,totalDistance){ let cmBacwardDistance = 0; let currentNode = cm; while(true) { cmBacwardDistance += 2 * currentNode.value.r; if (currentNode == frontChain.first){ currentNode = frontChain.last; } else { currentNode = currentNode.prev; } if (currentNode === toNode) break; } let cnForwardDistance = totalDistance - cmBacwardDistance - 2*toNode.value.r; return [cmBacwardDistance, cnForwardDistance]; } const removeNodesAhead = function(toNode, cm, frontChain){ while(cm.next !== toNode){ if (cm === frontChain.last){ if (frontChain.first === toNode) break; frontChain.popLeft(); continue; } frontChain.remove(cm.next); } } const remodeNodesBehind = function(toNode, cn, frontChain){ while(cn.prev !== toNode) { if (cn === frontChain.first){ if (frontChain.last === toNode) break; frontChain.pop(); continue; } frontChain.remove(cn.prev); } } const modifyFrontChain = function(intersectingNode,cm,frontChain,direction){ if (direction === 0) return {cm:cm, modified:false}; if (direction === -1) { let cn = cm.next; if (cn === null) cn = frontChain.first; remodeNodesBehind(intersectingNode,cn,frontChain); cm = intersectingNode; } else { removeNodesAhead(intersectingNode, cm, frontChain); } return {cm:cm, modified:true}; } const resolveIntersection = function(cm, r, frontChain){ let intersections = true; let res; let tries = 1; while(intersections && tries < 100) { let candidate = candidateCircle(cm, r, frontChain); let obj = checkIntersect(candidate,cm,frontChain); let intersectingNode = obj.intersectingNode; let direction = obj.direction; let mul = obj.mul; intersections = intersectingNode !== null; if (intersections){ if (mul) { cm = cm.prev ? cm.prev : frontChain.last; } else { let obj2 = modifyFrontChain(intersectingNode, cm, frontChain, direction); cm = obj2.cm; } } tries ++; res = candidate; } return {cm:cm, candidate:res, success: tries < 100}; } let started = false; let frontChain; let cm; let history = []; let minR = 5, maxR = 30, noiseP = Math.random()*14400, noiseStep = 0.4; s.setup = function(){ s.createCanvas(600,600); s.background(255); } s.draw = function () { if (!started) { s.background(10); s.fill(255); s.textAlign(s.CENTER, s.CENTER); s.textSize(20); s.text("click to start", s.width/2, s.height/2); s.noLoop(); } else { s.background(10); s.translate(s.width/2,s.height/2); s.stroke(240); if (history.length < 200){ let r = s.noise(noiseP)*(maxR - minR) + minR; noiseP += noiseStep; let obj = resolveIntersection(cm, r, frontChain); let newNode = obj.candidate; cm = obj.cm; let success = obj.success; if (success) { history.push(newNode); frontChain.insertAfter(newNode,cm); } } let done = true; history.forEach(c => { c.display(); if (c.ongoing) { c.update(); done = false; } }) //s.noLoop(); if (done) { s.noLoop(); } } } s.mouseClicked = function () { if (s.mouseX > s.width || s.mouseX < 0 || s.mouseY > s.height || s.mouseY < 0) return; if (!started) { started = true; s.background(255); s.frameRate(30); s.noFill(); s.stroke(0); let r1 = s.noise(noiseP)*(maxR - minR) + minR; noiseP += noiseStep; let r2 = s.noise(noiseP)*(maxR - minR) + minR; noiseP += noiseStep; let r3 = s.noise(noiseP)*(maxR - minR) + minR; noiseP += noiseStep; let obj = init(r1, r2, r3); cm = obj.cm; frontChain = obj.frontChain; s.translate(s.width/2,s.height/2); obj.circles.forEach(c => { history.push(c); }) s.loop(); } } })3a:T5f9,p5(s => { class Circle{ constructor(minR, maxR){ this.x = 0; this.y = 0; this.noiseP = Math.random() * 100; this.r = minR + s.noise(this.noiseP) * (maxR - minR); this.maxR = maxR; this.minR = minR } display(){ s.circle(this.x, this.y, this.r * 2); } update(){ this.noiseP += 0.01; this.r = this.minR + s.noise(this.noiseP)* (this.maxR - this.minR); } } let started = false, paused = false; let circles = []; let outer; s.setup = function(){ s.createCanvas(600,600); let circleNo = Math.floor(Math.random() * 50 + 100); for (let i = 0; i < circleNo; ++i) { circles.push(new Circle(0, 40)); } //console.log(circles); d3.packSiblings(circles); outer = d3.packEnclose(circles); s.frameRate(1) } s.draw = function () { if (!started) { s.textAlign(s.CENTER, s.CENTER); s.textSize(20); s.text("click to start", s.width/2, s.height/2); s.noLoop(); s.noFill(); s.stroke(0); } else { s.background(255) s.translate(s.width/2, s.height/2); s.circle(outer.x, outer.y, outer.r * 2); circles.forEach(c => { c.display(), c.update()}); d3.packSiblings(circles); outer = d3.packEnclose(circles); //s.noLoop(); } } s.mouseClicked = function () { if (s.mouseX > s.width || s.mouseX < 0 || s.mouseY > s.height || s.mouseY < 0) return; if (!started) { started = true; s.loop(); } } })3b:Ta12,p5(s => { class Circle{ constructor(x, y, i, n, inner) { this.x = x; this.y = y; this.index = i; this.neighbours=n; this.isInner = inner; if (inner) { this.r = 20; } else { this.r = s.width/2; } } display(){ if (this.isInner) s.circle(this.x, this.y, this.r*2) } } let circles = []; let delaunay; let outerPointNo = 3; s.setup = () => { s.createCanvas(600,600); s.background(0); s.stroke(255); s.noFill(); let pds = new PoissonDiscSampling({ shape:[s.width, s.height], minDistance: 30, maxDistance:70, tries:20 }); let ps = pds.fill(); let outer = []; for (let i = 0; i < outerPointNo; i ++) { let ang = i * (2*Math.PI / outerPointNo); outer.push([s.width/2 + Math.cos(ang) * s.width, s.height/2 + Math.sin(ang) * s.width]); } ps.push(...outer); let tem = ps.flat(); delaunay = new Delaunay(tem); delaunay.display = () => { const {points, halfedges, triangles, hull} = delaunay; for(let i = 1; i < hull.length; i++) { let idx1 = hull[i-1], idx2 = hull[i]; s.line(points[2 * idx1], points[2 * idx1 + 1], points[2*idx2], points[2*idx2 + 1]); } for (let i = 0, n = halfedges.length; i < n; ++i) { const j = halfedges[i]; if (j < i) continue; const ti = triangles[i]; const tj = triangles[j]; s.line(points[ti * 2], points[ti * 2 + 1], points[tj * 2], points[tj * 2 + 1]); } }; //delaunay.display(); ps.forEach((p,i) => { let nei = [...delaunay.neighbors(i)]; let inner = i < ps.length - outerPointNo; circles.push(new Circle(p[0], p[1],i, nei, inner)); }) } let displayDelaunay = true; let started = false; let allowThreshold = 0.1; s.draw = function(){ if (!started) { s.push(); s.fill(255); s.textAlign(s.CENTER,s.CENTER); s.textSize(20); s.text("Click to start", s.width/2, s.height/2); s.pop(); s.noLoop(); } else { s.background(0); if (displayDelaunay) delaunay.display(); } } const placeCircle = function(target, theta, ref){ target.x = (ref.r + target.r) * Math.cos(theta) + ref.x; target.y = (ref.r + target.r) * Math.sin(theta) + ref.y; } s.mouseClicked = () => { if (s.mouseX > s.width || s.mouseX < 0 || s.mouseY > s.height || s.mouseY < 0) return; if (!started) { started = true; s.loop(); } else { s.loop(); } } })3c:[] 31:{"id":"b505f87d3671fb99","slug":"circle-packing","title":"Circle Packing","thumbnail":"ceb7004d3c1844b9c6cee2734c85780ae57c1ad294928bf8360c498556347088","access_level":"public","create_time":"$D2023-11-10T11:24:58.709Z","update_time":"$D2023-11-29T11:50:59.106Z","view_time":null,"first_public_time":"$D2023-11-10T11:24:58.709Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":"starter_2024"},"version":399,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null}],"members":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"aac27ce630a2ebd4","slug":"posts","title":"Posts","owner":{"id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C"}},"type":"notebook","body":{"title":"Circle Packing","cells":[{"id":0,"value":"# Circle Packing\n\nA few ways to create Circle Packing patterns for generative art\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":170,"value":"## Random Circles\n\nFirstly we have this very straights forward algorithm:\n* We start with a maximum and minimum size\n* pick a random point and draw a circle at minimum size, increase its size until it touch other circles\n* repeat","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":172,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":168,"value":"## Circle spreading\n\nThis is taken from a [blog of Alberto Giachino](http://codeplastic.com/2017/09/09/controlled-circle-packing-with-processing). The idea of this algorithm is simple, we first create a bunch of circles of random size, then:\n* if two circles overlap, move them apart\n* if a circle is not overlapping with any circle, fix its location","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":74,"value":"viewof maxSize = Inputs.range([10,50], {value:20,label:\"max size\", step:5})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"One thing I notice with this algorithm is that when we have circles with significantly different sizes, we see lots of gap in between them. One way to fix that is making the size of the circles dynamic. We can play with the size of the circles to form different patterns. One idea provided in Alberto's blog is to match it to a noise map.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":80,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":118,"value":"We can also change how we calculate the dynamic size to create different effects","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":102,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":250,"value":"## Node based\n\nbased on Wang, W., Wang, H., Dai, G., & Wang, H. (2006). Visualization of large hierarchical data by circle packing. Proceedings of the SIGCHI Conference on Human Factors in Computing Systems.\n\nThe idea of this algorithm is also simple, it started with 3 circles, then add new circles with known radius based on the last two circle added using law of cosine. Base on that I added a backtrack function to ensure that new circles will not intersect with old ones.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":254,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":359,"value":"There are quite a few things you can play around with this algorithm, for example, playing with the radius sequence for the new circles, and adding some growing effect animation.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":361,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":366,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":385,"value":"The same node based algorithm is implemented in [D3 Hierarchy](https://d3js.org/d3-hierarchy/pack) too. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":388,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":122,"value":"## Using Delaunay triangulation\n\nThis is inspired by the works from [Dr Lam Miu Ling](http://miulinglam.com). With this method we can effectively eliminate the gaps, we started with some random points. We will use [Poisson Disc Sampling](https://en.wikipedia.org/wiki/Poisson_sampling) for a more even distribution. We first form the triangle mesh for them. Then grow circles from the vertexes. Finally finished by adjustment using virtual force, just like what we did above.\n\n//#Under Construction#//","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":134,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"

","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":11,"value":"import {p5c, p5} from \"@real-john-cheung/p5js\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":" Delaunay = d3.Delaunay;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":149,"value":"PoissonDiscSampling = require ('https://cdn.jsdelivr.net/gh/kchapelier/poisson-disk-sampling@2.3.1/build/poisson-disk-sampling.min.js')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":263,"value":"import {DoubleLinkedList} from \"@real-john-cheung/dllist\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3c","stdlib":"1","titling":"auto"}} 32:"$31:body"