Gosper Islands (No scale/rotation/translation)

README.md

This example introduces the concept of hexagon orientation. When a hexagonal grid is built, different orientation can be choosen. The layout can be represented using hexagons oriented with the flat side up or the pointy side up. The first orientation is called horizontal or pointy-side-up while the second vertical or flat-side-up ([1], [2], [3]).

Differently from the previous experiment, the hexagons are keept pointy-side-up and no rotation is applied to them. Moreover, the scale of the haxagons is not depending on the order but it is just fixed.

(Refresh for getting a new order, zoom in/out for navigating the map)

hept_tree_utils.coffee

window.hept_tree_utils = {
  ### Returns an array with 7 object nodes
  ###
  get_children: () ->
    return [{name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}, {name: '', type: '', children: []}]
      
  ### Given a base10 number, returns the base7 conversion
  ###
  base10_to_base7: (n) ->
    base7 = []
    
    while n > 0
      base7.unshift(n%7)
      n = Math.floor(n/7)
    
    return base7

  _align_arrays: (a, n) ->
    for i in [0...Math.abs(n)]
      a = [0].concat(a)
    return a

  align_arrays: (a, b) ->
    n = a.length - b.length

    if n > 0
      b = hept_tree_utils._align_arrays b, n
    else if n < 0
      a = hept_tree_utils._align_arrays a, n

    return [a, b]

  ### Given a base7 number, returns the corresponding HEPT TREE structure
  ###
  make_tree: (node, n1, n2, name1, name2, index) ->
    node.children = hept_tree_utils.get_children()

    for child,i in node.children
      # The digit of the base7 number matches the loop index: possible partially full node
      if i == n1[index]
        child.name = name1

        # Avoid to expand the tree for the last digit in the base7 number
        if index < n1.length-1
          child.type = 'partially full'
          if n1[index] == n2[index]
            hept_tree_utils.make_tree child, n1, n2, name1, name2, index+1
          else
            hept_tree_utils.make_tree child, n1, [], name1, name2, index+1
        else
          if name2 != 'empty'
            child.type = 'full'
          child.name = name2
      # The digit of the base7 number matches the loop index: possible partially full node
      else if i == n2[index]
        child.name = name2
        
        # Avoid to expand the tree for the last digit in the base7 number
        if index < n2.length-1
          child.type = 'partially full'
          hept_tree_utils.make_tree child, n2, [], name2, 'empty', index+1
        else
          child.type = 'full'
      else if i <= n1[index]
        child.name = name1
        child.type = 'full'
      else if i <= n2[index] or (n2.length == 0 and name2 != 'empty')
        child.name = name2
        child.type = 'full'
      else
        child.name = 'empty'

    return node

  ### 
  ###
  base7_to_hex: (n1, n2, index, data) ->
    
    for d,i in data
      if i < n1[index]
        d.class = 'n1'
      else if i < n2[index]
        d.class = 'n2'
      else
        d.class = 'empty'
    
    return data
  
  rotate_point: (point, theta) ->
    theta = theta*Math.PI/180
    new_point = {
      x: point.x * Math.cos(theta) - point.y * Math.sin(theta)
      y: point.x * Math.sin(theta) + point.y * Math.cos(theta)
    }
  
  rotate_point_around_pivot: (point, pivot, theta) ->
    point.x -= pivot.x
    point.y -= pivot.y
    
    point = hept_tree_utils.rotate_point point, theta
    
    point.x += pivot.x
    point.y += pivot.y
    
    point
  
  ### HEXAGONS
  ###
  hex_generate_svg_path: (a, theta) ->
    r = a / Math.sin(Math.PI/3)

    ###points = [
      hept_tree_utils.rotate_point {x: a, y: r/2}, theta
      hept_tree_utils.rotate_point {x: 0, y: r}, theta
      hept_tree_utils.rotate_point {x: -a, y: r/2}, theta
      hept_tree_utils.rotate_point {x: -a, y: -r/2}, theta
      hept_tree_utils.rotate_point {x: 0, y: -r}, theta
      hept_tree_utils.rotate_point {x: a, y: -r/2}, theta
    ]###
  
    # Vertices right and left
    #"M#{a} 0 L#{a/2} #{r} L#{-a/2} #{r} L#{-a} 0 L#{-a/2} #{-r} L#{a/2} #{-r} Z"
    # Vertices up and down
    "M#{a} #{r/2} L0 #{r} L#{-a} #{r/2} L#{-a} #{-r/2} L0 #{-r} L#{a} #{-r/2} Z"
    #"M#{points[0].x} #{points[0].y} L#{points[1].x} #{points[1].y} L#{points[2].x} #{points[2].y} L#{points[3].x} #{points[3].y} L#{points[4].x} #{points[4].y} L#{points[5].x} #{points[5].y} Z"
}

hept_tree_utils.js

// Generated by CoffeeScript 1.10.0
(function() {
  window.hept_tree_utils = {

    /* Returns an array with 7 object nodes
     */
    get_children: function() {
      return [
        {
          name: '',
          type: '',
          children: []
        }, {
          name: '',
          type: '',
          children: []
        }, {
          name: '',
          type: '',
          children: []
        }, {
          name: '',
          type: '',
          children: []
        }, {
          name: '',
          type: '',
          children: []
        }, {
          name: '',
          type: '',
          children: []
        }, {
          name: '',
          type: '',
          children: []
        }
      ];
    },

    /* Given a base10 number, returns the base7 conversion
     */
    base10_to_base7: function(n) {
      var base7;
      base7 = [];
      while (n > 0) {
        base7.unshift(n % 7);
        n = Math.floor(n / 7);
      }
      return base7;
    },
    _align_arrays: function(a, n) {
      var i, j, ref;
      for (i = j = 0, ref = Math.abs(n); 0 <= ref ? j < ref : j > ref; i = 0 <= ref ? ++j : --j) {
        a = [0].concat(a);
      }
      return a;
    },
    align_arrays: function(a, b) {
      var n;
      n = a.length - b.length;
      if (n > 0) {
        b = hept_tree_utils._align_arrays(b, n);
      } else if (n < 0) {
        a = hept_tree_utils._align_arrays(a, n);
      }
      return [a, b];
    },

    /* Given a base7 number, returns the corresponding HEPT TREE structure
     */
    make_tree: function(node, n1, n2, name1, name2, index) {
      var child, i, j, len, ref;
      node.children = hept_tree_utils.get_children();
      ref = node.children;
      for (i = j = 0, len = ref.length; j < len; i = ++j) {
        child = ref[i];
        if (i === n1[index]) {
          child.name = name1;
          if (index < n1.length - 1) {
            child.type = 'partially full';
            if (n1[index] === n2[index]) {
              hept_tree_utils.make_tree(child, n1, n2, name1, name2, index + 1);
            } else {
              hept_tree_utils.make_tree(child, n1, [], name1, name2, index + 1);
            }
          } else {
            if (name2 !== 'empty') {
              child.type = 'full';
            }
            child.name = name2;
          }
        } else if (i === n2[index]) {
          child.name = name2;
          if (index < n2.length - 1) {
            child.type = 'partially full';
            hept_tree_utils.make_tree(child, n2, [], name2, 'empty', index + 1);
          } else {
            child.type = 'full';
          }
        } else if (i <= n1[index]) {
          child.name = name1;
          child.type = 'full';
        } else if (i <= n2[index] || (n2.length === 0 && name2 !== 'empty')) {
          child.name = name2;
          child.type = 'full';
        } else {
          child.name = 'empty';
        }
      }
      return node;
    },

    /*
     */
    base7_to_hex: function(n1, n2, index, data) {
      var d, i, j, len;
      for (i = j = 0, len = data.length; j < len; i = ++j) {
        d = data[i];
        if (i < n1[index]) {
          d["class"] = 'n1';
        } else if (i < n2[index]) {
          d["class"] = 'n2';
        } else {
          d["class"] = 'empty';
        }
      }
      return data;
    },
    rotate_point: function(point, theta) {
      var new_point;
      theta = theta * Math.PI / 180;
      return new_point = {
        x: point.x * Math.cos(theta) - point.y * Math.sin(theta),
        y: point.x * Math.sin(theta) + point.y * Math.cos(theta)
      };
    },
    rotate_point_around_pivot: function(point, pivot, theta) {
      point.x -= pivot.x;
      point.y -= pivot.y;
      point = hept_tree_utils.rotate_point(point, theta);
      point.x += pivot.x;
      point.y += pivot.y;
      return point;
    },

    /* HEXAGONS
     */
    hex_generate_svg_path: function(a, theta) {
      var r;
      r = a / Math.sin(Math.PI / 3);

      /*points = [
        hept_tree_utils.rotate_point {x: a, y: r/2}, theta
        hept_tree_utils.rotate_point {x: 0, y: r}, theta
        hept_tree_utils.rotate_point {x: -a, y: r/2}, theta
        hept_tree_utils.rotate_point {x: -a, y: -r/2}, theta
        hept_tree_utils.rotate_point {x: 0, y: -r}, theta
        hept_tree_utils.rotate_point {x: a, y: -r/2}, theta
      ]
       */
      return "M" + a + " " + (r / 2) + " L0 " + r + " L" + (-a) + " " + (r / 2) + " L" + (-a) + " " + (-r / 2) + " L0 " + (-r) + " L" + a + " " + (-r / 2) + " Z";
    }
  };

}).call(this);

index.coffee

width = 960
height = 500
data = []

INITIAL_SCALE = height/25
GOSPER_ANGLE = Math.acos(5 * Math.sqrt(7) / 14) / Math.PI * 180
ROTATION_INDEXES = [0, 120, 0, -120, 0, 0, -120]
F_ROTATION_INDEXES = [-120, 0, 0, -120, 0, 120, 0]

order = Math.floor Math.random()*6
#order = Math.ceil(Math.log(n1+n2)/Math.log(7))

color = d3.scale.ordinal()
  .domain ["class1", "class2", "class3", "class4", "class5", "class6", "class7", ""]
  .range ["#fb8072","#80b1d3","#fdb462","#b3de69","#8dd3c7","#ffffb3","#bebada","#f2f2f2"]

# SVG setup
svg = d3.select 'svg'
  .attr
    width: width
    height: height
    viewBox: "#{-width/2} #{-height/2} #{width} #{height}"
  
zoomable_layer = svg.append('g')

# Zoom
zoom = d3.behavior.zoom()
  .scaleExtent([0,2])
  .on 'zoom', () ->
    zoomable_layer
      .attr
        transform: "translate(#{zoom.translate()})scale(#{zoom.scale()})"
    zoomable_layer.selectAll('.semantic_zoom')
      .attr
        transform: "scale(#{1/zoom.scale()})"
        
svg.call(zoom)

# Returns the coordinates of a hexagon 
get_hept_coords = (scale, indexes, index_i) ->
  # Hexagon apothem is calculated as
  a = scale / Math.sqrt(7)
  # Hexagon radius
  r = a / Math.sin(Math.PI/3)

  # Coordinates calculation
  coords = [
    {x: -a, y: r+r/2},
    {x: a, y: r+r/2},
    {x: 0, y: 0},
    {x: -2*a, y: 0},
    {x: -a, y: -r-r/2},
    {x: a, y: -r-r/2},
    {x: 2*a, y: 0}
  ]

  ###coords = [
    {x: 0, y: 0},
    {x: 2*a, y: 0},
    {x: a, y: -(r+r/2)},
    {x: -a, y: -(r+r/2)},
    {x: 0, y: -3*r},
    {x: 2*a, y: -3*r},
    {x: 3*a, y: -(r+r/2)}
  ]###
  
  flip = false
  if index_i > 0
    
    for i in indexes.slice(0,index_i)
      if not(flip) and i in [1,2,6]
        flip = not flip
      else if flip and i in [0,4,5]
        flip = not flip
  
  if flip
    coords.reverse()
  
  # Returns the coordinates of the ith hexagon
  {coords: coords[indexes[index_i]], flip: flip}
  
### Returns the rotation and translation of a certain hexagon described as a base 7 number
###
get_hex_data = (indexes) ->
  # For each iteration hexagons rotate by GOSPER_ANGLE
  # (minus order is used for having hexagons with the vertice on top)
  rotation = GOSPER_ANGLE * (indexes.length - order)
  # 
  f_rotation = 0
  # Hexagon coordinates start from the origin
  translation = {x: 0, y: 0}
  
  # For each index, denoting an iteration of the Gosper Curve, the translation coordinates are updated
  for index, i in indexes
    # The scale of a hexagon at a certain iteration i
    scale_i = 1 / Math.pow Math.sqrt(7), i-order
    
    # Get the hept coordinates
    result = get_hept_coords scale_i, indexes, i
    hept_coords = result.coords
    
    # Rotate the hept coordinates by the GOSPER ANGLE multiplied by the iteration
    # (minus order is used for having hexagons with the vertice on top)
    hept_coords = hept_tree_utils.rotate_point(hept_coords, GOSPER_ANGLE*(i+1-order))
    
    hept_coords = hept_tree_utils.rotate_point(hept_coords, f_rotation)
    
    #
    f_rotation += if result.flip then F_ROTATION_INDEXES[index] else ROTATION_INDEXES[index]
    
    # Coordinates update
    translation.x += hept_coords.x
    translation.y += hept_coords.y
  

  {rotation: rotation, frotation: f_rotation, translation: translation}
  
compare_base7_numbers = (a,b) ->
  return parseInt(a.join('')) < parseInt(b.join(''))

get_class = (index) ->

  for n,i in base7_numbers

    if compare_base7_numbers index, n
      return "class#{i+1}"

  return ""

# Recursive Procedure
rec = (order, index) ->
  if order == 0
    data.push({index: index, data: get_hex_data(index), class: get_class(index)})
    return
  
  for i in [0..6]
    rec order-1, index.concat([i])

### Initialization
###
max_hex = Math.pow 7, order
class_number = Math.floor Math.random()*7
numbers = []
base7_numbers = []

for i in [0...class_number]
  numbers.push Math.floor Math.random()*(max_hex-d3.sum(numbers))
  base7_numbers.push hept_tree_utils.base10_to_base7 d3.sum(numbers)

rec order, []
      
# Drawing
initial_translation = data[0].data.translation # FIXME data must be corrected not when visualized

svg.append 'g'
  .attr
    transform: "translate(#{-width/2+20}, #{-height/2+40})"
    #transform: "translate(#{20}, #{40})"
  .append 'text'
    .text "Order #{order}"

hexes = zoomable_layer.selectAll 'path'
  .data data
  
hexes.enter().append 'path'
  .attr
    class: 'hex'
    d: (d) ->
      hept_tree_utils.hex_generate_svg_path INITIAL_SCALE, 0
    transform: (d) -> "translate(#{(d.data.translation.x-initial_translation.x)*INITIAL_SCALE}, #{(d.data.translation.y-initial_translation.y)*INITIAL_SCALE}) rotate(#{d.data.rotation})"
    fill: (d) -> color d.class
    stroke: '#FFF'
    'stroke-width': () -> if order < 5 then 2 else 1

index.css

html, body {
  margin: 0;
  padding: 0;
}

.hex {
  fill-opacity: 0.6;
}

text {
  font-family: sans-serif;
  font-size: 20px;
  fill: steelblue;
}

.curve {
  stroke-width: 1.5px;
  opacity: 0.6
}

index.html

<!doctype html>
<html lang="en">
<head>
  <meta charset="utf-8">
  <title>Gosper Islands (No scale/rotation)</title>
  <meta name="description" content="Gosper Islands (No scale/rotation)">
  <script src="http://d3js.org/d3.v3.min.js"></script>
  <script src="hept_tree_utils.js"></script>
  <link rel="stylesheet" href="index.css">
</head>
<body>
  <svg></svg>
  <script src="index.js"></script>
</body>
</html>

index.js

// Generated by CoffeeScript 1.10.0
(function() {
  var F_ROTATION_INDEXES, GOSPER_ANGLE, INITIAL_SCALE, ROTATION_INDEXES, base7_numbers, class_number, color, compare_base7_numbers, data, get_class, get_hept_coords, get_hex_data, height, hexes, i, initial_translation, j, max_hex, numbers, order, rec, ref, svg, width, zoom, zoomable_layer;

  width = 960;

  height = 500;

  data = [];

  INITIAL_SCALE = height / 25;

  GOSPER_ANGLE = Math.acos(5 * Math.sqrt(7) / 14) / Math.PI * 180;

  ROTATION_INDEXES = [0, 120, 0, -120, 0, 0, -120];

  F_ROTATION_INDEXES = [-120, 0, 0, -120, 0, 120, 0];

  order = Math.floor(Math.random() * 6);

  color = d3.scale.ordinal().domain(["class1", "class2", "class3", "class4", "class5", "class6", "class7", ""]).range(["#fb8072", "#80b1d3", "#fdb462", "#b3de69", "#8dd3c7", "#ffffb3", "#bebada", "#f2f2f2"]);

  svg = d3.select('svg').attr({
    width: width,
    height: height,
    viewBox: (-width / 2) + " " + (-height / 2) + " " + width + " " + height
  });

  zoomable_layer = svg.append('g');

  zoom = d3.behavior.zoom().scaleExtent([0, 2]).on('zoom', function() {
    zoomable_layer.attr({
      transform: "translate(" + (zoom.translate()) + ")scale(" + (zoom.scale()) + ")"
    });
    return zoomable_layer.selectAll('.semantic_zoom').attr({
      transform: "scale(" + (1 / zoom.scale()) + ")"
    });
  });

  svg.call(zoom);

  get_hept_coords = function(scale, indexes, index_i) {
    var a, coords, flip, i, j, len, r, ref;
    a = scale / Math.sqrt(7);
    r = a / Math.sin(Math.PI / 3);
    coords = [
      {
        x: -a,
        y: r + r / 2
      }, {
        x: a,
        y: r + r / 2
      }, {
        x: 0,
        y: 0
      }, {
        x: -2 * a,
        y: 0
      }, {
        x: -a,
        y: -r - r / 2
      }, {
        x: a,
        y: -r - r / 2
      }, {
        x: 2 * a,
        y: 0
      }
    ];

    /*coords = [
      {x: 0, y: 0},
      {x: 2*a, y: 0},
      {x: a, y: -(r+r/2)},
      {x: -a, y: -(r+r/2)},
      {x: 0, y: -3*r},
      {x: 2*a, y: -3*r},
      {x: 3*a, y: -(r+r/2)}
    ]
     */
    flip = false;
    if (index_i > 0) {
      ref = indexes.slice(0, index_i);
      for (j = 0, len = ref.length; j < len; j++) {
        i = ref[j];
        if (!flip && (i === 1 || i === 2 || i === 6)) {
          flip = !flip;
        } else if (flip && (i === 0 || i === 4 || i === 5)) {
          flip = !flip;
        }
      }
    }
    if (flip) {
      coords.reverse();
    }
    return {
      coords: coords[indexes[index_i]],
      flip: flip
    };
  };


  /* Returns the rotation and translation of a certain hexagon described as a base 7 number
   */

  get_hex_data = function(indexes) {
    var f_rotation, hept_coords, i, index, j, len, result, rotation, scale_i, translation;
    rotation = GOSPER_ANGLE * (indexes.length - order);
    f_rotation = 0;
    translation = {
      x: 0,
      y: 0
    };
    for (i = j = 0, len = indexes.length; j < len; i = ++j) {
      index = indexes[i];
      scale_i = 1 / Math.pow(Math.sqrt(7), i - order);
      result = get_hept_coords(scale_i, indexes, i);
      hept_coords = result.coords;
      hept_coords = hept_tree_utils.rotate_point(hept_coords, GOSPER_ANGLE * (i + 1 - order));
      hept_coords = hept_tree_utils.rotate_point(hept_coords, f_rotation);
      f_rotation += result.flip ? F_ROTATION_INDEXES[index] : ROTATION_INDEXES[index];
      translation.x += hept_coords.x;
      translation.y += hept_coords.y;
    }
    return {
      rotation: rotation,
      frotation: f_rotation,
      translation: translation
    };
  };

  compare_base7_numbers = function(a, b) {
    return parseInt(a.join('')) < parseInt(b.join(''));
  };

  get_class = function(index) {
    var i, j, len, n;
    for (i = j = 0, len = base7_numbers.length; j < len; i = ++j) {
      n = base7_numbers[i];
      if (compare_base7_numbers(index, n)) {
        return "class" + (i + 1);
      }
    }
    return "";
  };

  rec = function(order, index) {
    var i, j, results;
    if (order === 0) {
      data.push({
        index: index,
        data: get_hex_data(index),
        "class": get_class(index)
      });
      return;
    }
    results = [];
    for (i = j = 0; j <= 6; i = ++j) {
      results.push(rec(order - 1, index.concat([i])));
    }
    return results;
  };


  /* Initialization
   */

  max_hex = Math.pow(7, order);

  class_number = Math.floor(Math.random() * 7);

  numbers = [];

  base7_numbers = [];

  for (i = j = 0, ref = class_number; 0 <= ref ? j < ref : j > ref; i = 0 <= ref ? ++j : --j) {
    numbers.push(Math.floor(Math.random() * (max_hex - d3.sum(numbers))));
    base7_numbers.push(hept_tree_utils.base10_to_base7(d3.sum(numbers)));
  }

  rec(order, []);

  initial_translation = data[0].data.translation;

  svg.append('g').attr({
    transform: "translate(" + (-width / 2 + 20) + ", " + (-height / 2 + 40) + ")"
  }).append('text').text("Order " + order);

  hexes = zoomable_layer.selectAll('path').data(data);

  hexes.enter().append('path').attr({
    "class": 'hex',
    d: function(d) {
      return hept_tree_utils.hex_generate_svg_path(INITIAL_SCALE, 0);
    },
    transform: function(d) {
      return "translate(" + ((d.data.translation.x - initial_translation.x) * INITIAL_SCALE) + ", " + ((d.data.translation.y - initial_translation.y) * INITIAL_SCALE) + ") rotate(" + d.data.rotation + ")";
    },
    fill: function(d) {
      return color(d["class"]);
    },
    stroke: '#FFF',
    'stroke-width': function() {
      if (order < 5) {
        return 2;
      } else {
        return 1;
      }
    }
  });

}).call(this);

thumbnail.png