class Rubyvis::Layout::Pack

Implements a hierarchical layout using circle-packing. The meaning of
the exported mark prototypes changes slightly in the space-filling
implementation:<ul>

<li><tt>node</tt> - for rendering nodes; typically a Rubyvis::Dot.

<p><li><tt>link</tt> - unsupported; undefined. Links are encoded implicitly
in the arrangement of the space-filling nodes.

<p><li><tt>label</tt> - for rendering node labels; typically a
Rubyvis::Label.

</ul>The pack layout support dynamic sizing for leaf nodes, if a
{@link #size} psuedo-property is specified. The default size function returns
1, causing all leaf nodes to be sized equally, and all internal nodes to be
sized by the number of leaf nodes they have as descendants.

<p>The size function can be used in conjunction with the order property,
which allows the nodes to the sorted by the computed size. Note: for sorting
based on other data attributes, simply use the default <tt>null</tt> for the
order property, and sort the nodes beforehand using the {@link pv.Dom}
operator.

<p>For more details on how to use this layout, see
Rubyvis::Layout::Hierarchy.

@extends pv.Layout.Hierarchy
@see <a href="http://portal.acm.org/citation.cfm?id=1124772.1124851"
>"Visualization of large hierarchical data by circle packing"</a> by W. Wang,
H. Wang, G. Dai, and H. Wang, ACM CHI 2006.

/

Attributes

order[RW]

The sibling node order. The default order is null, which means to use the sibling order specified by the nodes property as-is. A value of “ascending” will sort siblings in ascending order of size, while “descending” will do the reverse. For sorting based on data attributes other than size, use the default null for the order property, and sort the nodes beforehand using the {@link pv.Dom} operator.

@see pv.Dom.Node#sort

spacing[RW]

The spacing parameter; defaults to 1, which provides a little bit of padding between sibling nodes and the enclosing circle. Larger values increase the spacing, by making the sibling nodes smaller; a value of zero makes the leaf nodes as large as possible, with no padding on enclosing circles.

@type number

Public Class Methods

defaults() click to toggle source

Default properties for circle-packing layouts. The default spacing parameter is 1 and the default order is “ascending”.

# File lib/rubyvis/layout/pack.rb, line 84
def self.defaults
  Rubyvis::Layout::Pack.new.mark_extend(Rubyvis::Layout::Hierarchy.defaults).
  spacing(1).
  order("ascending")
end
new() click to toggle source
# File lib/rubyvis/layout/pack.rb, line 41
def initialize
  super
  @node.
  shape_radius(lambda {|n| n.radius }).
  stroke_style("rgb(31, 119, 180)").
  fill_style("rgba(31, 119, 180, 0.25)")


  @node_label.text_align("center")

  @link=nil

  @radius = lambda { 1 }
end

Public Instance Methods

bound(n) click to toggle source
# File lib/rubyvis/layout/pack.rb, line 154
def bound(n)
  @x_min = [n.x - n.radius, @x_min].min
  @x_max = [n.x + n.radius, @x_max].max
  @y_min = [n.y - n.radius, @y_min].min
  @y_max = [n.y + n.radius, @y_max].max
end
build_implied(s) click to toggle source
# File lib/rubyvis/layout/pack.rb, line 313
def build_implied(s)
  return nil if hierarchy_build_implied(s)
  @s=s
  nodes = s.nodes
  root = nodes[0]
  radii(nodes)

  # Recursively compute the layout. #/
  root.x = 0
  root.y = 0
  root.radius = pack_tree(root)

  w = self.width
  h = self.height
  k = 1.0 / [2.0 * root.radius / w, 2.0 * root.radius / h].max
  transform(root, w / 2.0, h / 2.0, k)
end
insert(a,b) click to toggle source
# File lib/rubyvis/layout/pack.rb, line 160
def insert(a,b)
  c = a.n
  a.n = b
  b._p = a
  b.n = c
  c._p = b
end
intersects(a, b) click to toggle source
# File lib/rubyvis/layout/pack.rb, line 171
def intersects(a, b)
  dx = b.x - a.x
  dy = b.y - a.y
  dr = a.radius + b.radius
  (dr * dr - dx * dx - dy * dy) > 0.001 # within epsilon
end
pack_circle(nodes) click to toggle source
# File lib/rubyvis/layout/pack.rb, line 211
def pack_circle(nodes)
  @x_min = Infinity
  @x_max = -Infinity
  @y_min = Infinity
  @y_max = -Infinity
  a=b=c=j=k=nil


  # Create first node.
  a = nodes[0];
  a.x = -a.radius
  a.y = 0
  bound(a)

  # Create second node. #/
  if (nodes.size > 1)
    b = nodes[1]
    b.x = b.radius
    b.y = 0
    bound(b)

    # Create third node and build chain.
    if (nodes.size > 2)
      c = nodes[2]
      place(a, b, c)
      bound(c)
      insert(a, c)
      a._p = c
      insert(c, b)
      b = a.n

      # Now iterate through the rest.
      i=3
      while(i < nodes.size) do
        c=nodes[i]
        place(a, b, c)

        # Search for the closest intersection. #/
        isect = 0
        s1 = 1
        s2 = 1

        j=b.n
        while(j!=b) do
          if (intersects(j, c))
            isect=1
            break
          end
          j=j.n
          s1+=1
        end

        if isect==1
          k=a._p
          while(k!=j._p) do
            if(intersects(k,c))
              if(s2 < s1)
                isect=-1
                j=k
              end
              break
            end
            k=k._p
            s2+=1
          end
        end


        # Update node chain. #/
        if (isect == 0)
          insert(a, c)
          b = c
          bound(c)
        elsif (isect > 0)
          splice(a, j)
          b = j
          i-=1
        elsif (isect < 0)
          splice(j, b)
          a = j
          i-=1
        end
        i+=1
      end


    end
  end

  # Re-center the circles and return the encompassing radius. #/
  cx = (@x_min + @x_max) / 2.0
  cy = (@y_min + @y_max) / 2.0
  cr = 0
  nodes.each do |n|
    n.x -= cx
    n.y -= cy
    cr = [cr, n.radius + Math.sqrt(n.x * n.x + n.y * n.y)].max
  end
  cr + @s.spacing
end
pack_tree(n) click to toggle source
# File lib/rubyvis/layout/pack.rb, line 132
def pack_tree(n)
  nodes = []
  c=n.first_child
  while(c)
    c.radius=pack_tree(c) if c.first_child
    c.n=c._p=c
    nodes.push(c)
    c=c.next_sibling
  end

  # Sort.
  case @s.order
  when "ascending"
    nodes.sort {|a,b| a.radius<=>b.radius}
  when 'descending'
    nodes.sort {|a,b| b.radius<=>a.radius}
  when 'reverse'
    nodes.reverse
  end

  return pack_circle(nodes)
end
place(a, b, c) click to toggle source

@private #/

# File lib/rubyvis/layout/pack.rb, line 179
def place(a, b, c)
  da = b.radius + c.radius
  db = a.radius + c.radius
  dx = b.x - a.x
  dy = b.y - a.y
  dc = Math.sqrt(dx * dx + dy * dy)
  cos = (db * db + dc * dc - da * da) / (2.0 * db * dc)
  theta = Math.acos(cos)
  x = cos * db
  h = Math.sin(theta) * db
  dx = dx/dc
  dy = dy/dc
  c.x = a.x + x * dx + h * dy
  c.y = a.y + x * dy - h * dx
end
radii(nodes) click to toggle source

@private Compute the radii of the leaf nodes. #/

# File lib/rubyvis/layout/pack.rb, line 121
def radii(nodes)
  stack=Mark.stack
  stack.unshift(nil)
  nodes.each {|c|
    if !c.first_child
      stack[0]=c
      c.radius = @radius.js_apply(self, stack)
    end
  }
  stack.shift
end
size(f) click to toggle source

Specifies the sizing function. By default, a sizing function is disabled and all nodes are given constant size. The sizing function is invoked for each leaf node in the tree (passed to the constructor).

<p>For example, if the tree data structure represents a file system, with files as leaf nodes, and each file has a bytes attribute, you can specify a size function as:

<pre> .size(function(d) d.bytes)</pre>

As with other properties, a size function may specify additional arguments to access the data associated with the layout and any enclosing panels.

@param {function} f the new sizing function. @returns {pv.Layout.Pack} this.

# File lib/rubyvis/layout/pack.rb, line 110
def size(f)
  if f.is_a? Proc
    @radius=lambda {|*args| Math.sqrt(f.js_apply(self,args))}
  else
    f=Math.sqrt(f)
    @radius=lambda {f}
  end
  self
end
splice(a, b) click to toggle source
# File lib/rubyvis/layout/pack.rb, line 167
def splice(a, b)
  a.n = b
  b._p = a
end
transform(n, x, y, k) click to toggle source

@private #/

# File lib/rubyvis/layout/pack.rb, line 196
def transform(n, x, y, k)
  c=n.first_child
  while(c) do
    c.x += n.x
    c.y += n.y
    transform(c, x, y, k)
    c=c.next_sibling
  end
  n.x = x + k * n.x
  n.y = y + k * n.y
  n.radius *= k
  n.mid_angle=0 # Undefined on protovis
end