Circle packing 2x2

Following this circle packing tutorial trying to get to this rendering tutorial.

This adjacency placement algorithm has some problems. You need to pass in the parent with the biggest radius first. I think I'm missing some key piece of math that would make sure the proper angle is always used.

We need to use some trigonometry to find the center of the circle we want to place adjacent to its two parents.

SSS rule for finding angle with three known sides

Isosceles relationships for finding perpendicular segment for placing child circle.

Built with blockbuilder.org

forked from enjalot's block: Adjacent circles

<!DOCTYPE html>
<head> 
  <meta charset="utf-8">
  <script src="https://d3js.org/d3.v4.min.js"></script>
  <script src="https://d3js.org/d3-queue.v2.min.js"></script>
  <style>
    body { margin:0;position:fixed;top:0;right:0;bottom:0;left:0; }
    
    circle.main {
      fill: none;
      stroke: #111;
      stroke-width: 2;
    }
  </style>
</head>

<body>
  <script>
    var width = window.innerWidth || 960;
    var height = window.innerHeight || 500;
    
    var Ra = 20; // starting radius
    var Rb = 20;
    var maxRadius = Ra;
   
    //var ratio = 0.8; //how much to decay radius
    var ratio = [0.8, 1.4];
    //var ratio = [1, 1]
    var maxLevel = 20; 
    
    var adam = { x: width/2 - Ra, y: height/2, r: Ra, color: "#111", level: 0 };
    var eve = { x: width/2 + Rb, y: height/2, r: Rb, color: "#111", level: 0};
    var data = [adam, eve];
    
    var quadtree = d3.quadtree()
      .x(function(d) { return d.x })
      .y(function(d) { return d.y })
      .extent([[-1, -1], [width + 1, height + 1]]);
    
    quadtree.add(adam)
    quadtree.add(eve)
    
    var svg = d3.select("body").append("svg")
      .attr("width", width)
      .attr("height", height)
    
   
    function addCircle(a,b, ROTATE) {
      //console.log("a,b", a,b)
      // create a new circle given parents a & b
      
      var child = { r: a.r };
      var randomRatio = Math.random() * (ratio[1] - ratio[0]) + ratio[0]
      //var randomRatio = 0.9
      child.r = randomRatio * child.r;
      
      // we want to find our child's center by
      // finding the 3rd point in the triangle
      // with the base defined by the parents centers
      var AC = a.r + child.r;
      var AB = a.r + b.r;
      var BC = child.r + b.r;
      // SSS rule to find the angle between parents segment and a -> child segment
      var atheta = Math.acos((AC*AC + AB*AB - BC*BC)/(2*AC*AB));
      
      // base of the right triangle made by dropping perpendicular line from child
      // down to the segment between a and b
      var base = Math.cos(atheta) * AC;
      // length of the above mentioned line segment that is perpendicular
      var altitude = Math.sin(atheta) * AC;
      
      var dx = b.x - a.x;
      var dy = b.y - a.y;
      var magnitude = Math.sqrt(dx*dx + dy*dy);
      
      var normalized = {
        x: dx/magnitude,
        y: dy/magnitude
      }
      // the angle between the parent segment (connection between a and b)
      // and the x-axis (we essentially rotate our altitude)
      var ptheta = -Math.acos(dx/magnitude) * (dy<0 ? -1 : 1);
      var rotate = ptheta
      if(ptheta < -Math.PI/2) rotate += Math.PI;
      rotate += ROTATE
      
      // we find the point perpendicular 
      var perp = {
        x: a.x + normalized.x * base,
        y: a.y + normalized.y * base
      }
      /*
      svg.append("circle")
        .attr("cx", perp.x)
        .attr("cy", perp.y)
        .attr("r", 5)
        .style("fill", b.color)
      */
      
      child.x = perp.x - Math.sin(rotate)*altitude;
      child.y = perp.y - Math.cos(rotate)*altitude;
      
      return child;
    }
    
    
    function recurseCircle(a,b) {
      
      if(a.level > maxLevel) return;
      var c1 = addCircle(a,b, 0);
      c1.level = a.level + 1;
      if(c1.r > maxRadius) maxRadius = c1.r;
      // check if new circle collides
      var hits = [];
      quadtree.visit(nearest(c1, maxRadius, hits))
      if(!hits.length && c1.x > c1.r + 2 && c1.x < width - 2 - c1.r && c1.y > c1.r + 2 && c1.y < height - 2 - c1.r ) {
        data.push(c1)
        quadtree.add(c1)
        render();
        setTimeout(function() {
          recurseCircle(c1, a);
        }, 150)
        setTimeout(function() {
          recurseCircle(c1, b)
        }, 300)
      };
      
      
      
      var c2 = addCircle(a,b, Math.PI);
      c2.level = a.level + 1;
      if(c2.r > maxRadius) maxRadius = c2.r;
      // check if new circle collides
      var hits = [];
      quadtree.visit(nearest(c2, maxRadius, hits))
      if(!hits.length && c2.x > c2.r + 2 && c2.x < width - 2 - c2.r && c2.y > c2.r + 2 && c2.y < height - 2 - c2.r ) {
        data.push(c2)
        quadtree.add(c2)
        render();
        setTimeout(function() {
          recurseCircle(c2, a);
        }, 150)
        setTimeout(function() {
          recurseCircle(c2, b)
        }, 300)
      };
 
    }
    
    recurseCircle(adam, eve)

</script>
</body>

https://d3js.org/d3.v4.min.js

https://d3js.org/d3-queue.v2.min.js