All examples By author By category About

kevinlin1

Full window Github gist

k-d Tree Visualization

k-d trees are space-partitioning data structures for organizing points in k-dimensional space. They are a useful data structure for finding, for example, the n nearest neighbors of a point in k-dimensional space.

This block provides a visualization of k-d tree creation which connects the intuition of binary trees with the concept of space partitioning.

Operation

Click on the left square to add points in a 2D projection of RGB space.

Additional Reading

Robert Sedgewick and Kevin Wayne
- Geometric Applications of BSTs
- 2D Tree Demo
Shewchuk's notes on Faster Nearest Neighbors
Wikipedia: k-d tree
Data Structures and Algorithm Analysis in Java, Third Edition: Spatial Data Structures

Acknowledgements

Forked from ludwigschubert's block: kD-tree explorations in D3.js

<html>
  <head>
    <link rel="stylesheet" href="style.css" />
  </head>
  <body>
    <div id="kdtree"></div>
    <div id="binarytree"></div>
    <script src="https://code.jquery.com/jquery-3.3.1.min.js"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.17/d3.min.js"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/tinycolor/1.4.1/tinycolor.min.js"></script>
    <script src="kdTree.js"></script>
    <script>
      var data;
      var colorSubset = [];
      var tree = new kdTree(colorSubset, colorDistance, ["red", "green"]);
      var bTree;

// Pretty good color distance from
      // https://www.compuphase.com/cmetric.htm
      function colorDistance(a, b) {
        var dr = a.red - b.red;
        var dg = a.green - b.green;
        var db = a.blue - b.blue;
        var redMean = (a.red + b.red)/2;
        return (2 + redMean / 256) * dr * dr + 4 * dg * dg + (2 + (255 - redMean) / 256) * db * db;
      }

$(function(){ // on document load

function update(color) {

$("#picked").css('background', color.toHex());
          var rgb = color.toRgb();
          var search = {red: rgb.r, green: rgb.g, blue: rgb.b};
          var nearest = tree.nearest(search, 4);
          nearest.sort(function(a,b){return a[1] - b[1]});

var $list = $("#results ul");
          $list.html("");
          for(var i=0; i<nearest.length; i++) {
            var c = nearest[i][0];

var $box = $("<div>")
              .css('background', c.hex)
              .css('display', 'inline-block')
              .css('margin-right', '10px')
              .height('30px')
              .width('30px');
            var $line = $("<li>").append($box).append(c.title);
            $list.append($line);
          }

updateSearchResults(nearest);
        }

function setRGBfromHex (hex_color) {
          var color = new tinycolor(hex_color.hex).toRgb();
          hex_color.red = color.r;
          hex_color.green = color.g;
          hex_color.blue = color.b;
        }

// D3 kdtree

var margin = {top: 0, right: 0, bottom: 0, left: 0},
            width  = 470 - margin.left - margin.right,
            height = width - margin.top - margin.bottom,
            pointRadius = 6;

var x = d3.scale.linear()
                .range([0, width])
                .domain([0, 255]);

var y = d3.scale.linear()
                .range([height, 0])
                .domain([0, 255]);

var svg = d3.select("#kdtree").append("svg")
                  .attr("class", "kdtree")
                  .attr("width", width + margin.left + margin.right)
                  .attr("height", height + margin.top + margin.bottom)

var graph = svg.append("g")
                    .attr("transform", "translate(" + margin.left + "," + margin.top + ")")
                    .attr("width", width)
                    .attr("height", height);

var linesG = graph.append("g")
                    .attr("class", "lines");

var pointsG = graph.append("g")
                     .attr("class", "points");

// D3 binarytree

bTree = d3.layout.tree()
                .size([height, width]);

var diagonal = d3.svg.diagonal()
                        .projection(function(d) { return [d.y, d.x]; });

var bSvg = d3.select("#binarytree").append("svg")
                  .attr("class", "binarytree")
                  .attr("width", width + margin.left + margin.right)
                  .attr("height", height + margin.top + margin.bottom);

var bLinesG = bSvg.append("g")
                    .attr("class", "lines");

var bPointsG = bSvg.append("g")
                     .attr("class", "points");

svg.on('click', function() {
          coordinates = d3.mouse(this);
          var red   = x.invert( coordinates[0] );
          var green = y.invert( coordinates[1] );
          var color = d3.rgb(red, green, 128);
          var object = { title: "user defined", hex: color.toString() };
          setRGBfromHex(object);

// check for very similar colors; don't insert to keep layouter sane
          var potentialDuplicates = tree.nearest(object, 1);
          if (potentialDuplicates.length > 0) {
            // var potentialDuplicate = potentialDuplicates[0][0];
            var distance = potentialDuplicates[0][1];
            if (distance < 10) return;
          }

colorSubset.push(object);
          tree.insert(object);
          data = tree.pointsBFS();
          drawDataSubset(data);
        });

data = tree.pointsBFS();
        drawDataSubset(data);

function drawDataSubset(dataSubset) {

// points

var pointsSelection = pointsG.selectAll(".point")
            .data(dataSubset, function(d){return d.hex + "point";});

pointsSelection.enter()
          .append("circle")
            .attr("class", function(d) { d.fresh = true; return "point" })
            .attr("class", "point")
            .attr("dimension", function(d) { return d.dimension;  })
            .attr("r", pointRadius)
            .attr("cx",      function(d) { return x(d.red);  })
            .attr("cy",      function(d) { return y(d.green); })
            .style("fill",   function(d) { return d3.rgb(d.hex); })
            .style("stroke", function(d) { return d3.rgb(d.hex); })
            .on("mouseover", function(d) {
              if (d.fresh) return;
              var parent = d.node;
              while(parent) {
                parent.onAccessPath = true;
                parent = parent.parent;
              }
              drawDataSubset(data);
            })
            .on("mouseout", function(d) {
              if (d.fresh) {
                d.fresh = false;
                return;
              }
              var parent = d.node;
              while(parent) {
                parent.onAccessPath = false;
                parent = parent.parent;
              }
              drawDataSubset(data);
            })

pointsSelection
            .style("stroke-width", function(d) { return d.node.onAccessPath || d.node.isSearchResult ? 2 : 0; });

// lines

var selection = linesG.selectAll(".point-line")
            .data(dataSubset, function(d){return d.hex + "line";});

selection // update
            .style("stroke-width",  function(d) { return d.node.onAccessPath ? 2*height/400 : height/400; })
            .transition()
              .attr("x1", function(d) { return x(d.x1); })
              .attr("y1", function(d) { return y(d.y1); })
              .attr("x2", function(d) { return x(d.x2); })
              .attr("y2", function(d) { return y(d.y2); })
              .attr("stroke",function(d) {
                switch(d.dimension) {
                  case 0: return d3.rgb(d.red, 0, 0);
                  case 1: return d3.rgb(0, d.green, 0);
                  // case 2: return "green";
                }
              })

selection.enter()
            .append("line")
            .attr("class", "point-line")
            .attr("stroke-width", height/400)
            .attr("x1", function(d) { return x(d.red); })
            .attr("y1", function(d) { return y(d.green); })
            .attr("x2", function(d) { return x(d.red); })
            .attr("y2", function(d) { return y(d.green); })
            .attr("stroke",function(d) {
                switch(d.dimension) {
                  case 0: return d3.rgb(d.red, 0, 0);
                  case 1: return d3.rgb(0, d.green, 0);
                  // case 2: return "green";
                }
              })
            .transition()
              .attr("x1", function(d) { return x(d.x1); })
              .attr("y1", function(d) { return y(d.y1); })
              .attr("x2", function(d) { return x(d.x2); })
              .attr("y2", function(d) { return y(d.y2); })

selection.exit()
            .remove();

// binary tree

// nodes

var depth = d3.max(dataSubset, function(d){return d.depth;})

var binaryTreePoints = bPointsG.selectAll(".binarytreepoint")
            .data(dataSubset, function(d){return d.hex + "binarytreepoint";});

binaryTreePoints.enter()
          .append("circle")
            .attr("class", "binarytreepoint")
            .attr("dimension", function(d) { return d.dimension;  })
            .attr("r", pointRadius)
            .style("fill",   function(d) { return d3.rgb(d.hex); })
            .style("stroke", function(d) { return d3.rgb(d.hex); });

binaryTreePoints // enter + update
            .style("stroke-width",  function(d) { return d.node.onAccessPath ? 2 : 0; })
            .transition()
            .attr("cx", function(d) {
              if (!d.node.parent) {
                d.node.bx = width / 2;
              } else {
                var inc = (width - 4*pointRadius) / Math.pow(2, d.depth + 1 );
                if (d.node == d.node.parent.left) { // left child
                  d.node.bx = d.node.parent.bx - inc;
                } else { // right child
                  d.node.bx = d.node.parent.bx + inc;
                }
              }
              return d.node.bx;
            })
            .attr("cy",      function(d) {
              d.node.by = (d.depth * ((height - 4*pointRadius) / depth)) + (2 * pointRadius);
              return d.node.by;
            })
            .style("fill",   function(d) { return d3.rgb(d.hex); })

binaryTreePoints.exit()
            .remove();

// edges

var selection = bLinesG.selectAll(".binarytreepoint-edge")
            .data(dataSubset, function(d){return d.hex + "binarytreepoint-edge";});

selection // update
            .style("stroke-width",  function(d) { return d.node.onAccessPath ? 2*height/400 : height/400; })
            .transition()
              .attr("x1", function(d) { return d.node.parent ? d.node.parent.bx : d.node.bx; })
              .attr("y1", function(d) { return d.node.parent ? d.node.parent.by : d.node.by; })
              .attr("x2", function(d) { return d.node.bx;                            })
              .attr("y2", function(d) { return d.node.by;                            })
              .attr("stroke",function(d) {
                switch(d.dimension) {
                  case 0: return d3.rgb(d.red, 0, 0);
                  case 1: return d3.rgb(0, d.green, 0);
                }
              })

selection.enter()
            .append("line")
            .attr("class", "binarytreepoint-edge")
            // .attr("stroke-width", function(d) { return w(d.depth); })
            .attr("stroke-dasharray", "1,3")
            .attr("stroke-width", height/400)
            .style("opacity", 0.8)
            // start all animation from point
            .attr("x1", function(d) { return d.node.parent ? d.node.parent.bx : d.node.bx; })
            .attr("y1", function(d) { return d.node.parent ? d.node.parent.by : d.node.by; })
            .attr("x2", function(d) { return d.node.parent ? d.node.parent.bx : d.node.bx; })
            .attr("y2", function(d) { return d.node.parent ? d.node.parent.by : d.node.by; })
            .attr("stroke",function(d) {
                switch(d.dimension) {
                  case 0: return d3.rgb(d.red, 0, 0);
                  case 1: return d3.rgb(0, d.green, 0);
                }
              })
            .transition()
              .attr("x1", function(d) { return d.node.parent ? d.node.parent.bx : d.node.bx; })
              .attr("y1", function(d) { return d.node.parent ? d.node.parent.by : d.node.by; })
              .attr("x2", function(d) { return d.node.bx; })
              .attr("y2", function(d) { return d.node.by; })

selection.exit()
            .remove();

}
      });
    </script>
  </body>
</html>

https://code.jquery.com/jquery-3.3.1.min.js

https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.17/d3.min.js

https://cdnjs.cloudflare.com/ajax/libs/tinycolor/1.4.1/tinycolor.min.js