Hemicycle chart (general)

algorithm.py

# calculates optimal numbers of representives for hemicycle chart
import math
import csv
import numpy as np
import timeit

start = timeit.default_timer()
#benchmark:
#n0 = 200 : 4:23s, 5:52s, 6:132s, 7:285s, 8:579s, 9:1167s , 10:2342s, 11: 4632s
#n0=751 : 7:217s, 8:570s, 9:1331, 10:2816s, 11: 5686s, 12: 10905s, 13:21918s,14:44362s


# number of representatives
n0=751


optim = {}

# loss function 1 (gaps between rows)
def loss1(g):
  return (g-1.2)*(g-1.2) #looks best

# loss function 2 (spaces in rows)
def loss2(w,s,n):
  n0 = sum(n)
  l2 = 0
  i = 0
  ln = len(n)
  for item in n:
    if s[i] > 0:
      #l2 = l2 + item*(s[i] - 0.1*w)*(s[i] - 0.1*w)/n0
      l2 = l2 + (s[i] - 0.1*w)*(s[i] - 0.1*w)/ln
    else:
      l2 = l2 + 10
    i = i + 1
  return l2

# loss function
def lossf(w,g,s,n):
  l1 = loss1(g)
  l2 = loss2(w,s,n)
  l = l1 + l2 + (l1 - l2)*(l1 - l2)
  return l

# spaces in rows
def ss(w,g,n):
  s = [0]*len(n)
  i = 0
  for item in n:
    s[i] = (math.pi/w + math.pi*i*g-n[i])/(n[i] - 1)
    i = i + 1 
  return s

# max n in row for grid search
def nmax(k,n):
  return math.floor(n-((k-1)*k/2))/k

# nrow for grid search
def nrow(n):
  return {'max':round(math.sqrt(n)*3/4),'min':round(max(math.sqrt(n)/4,1))}

# grid search
def grid(n):
  out = []
  for k in np.arange (0.01,1,0.01): #(0.01,1,0.005):
    for kk in np.arange (1.15,1.25,0.01): #(1,1.35,0.01)
      g = kk
      w = k
      s = ss(w,g,n)
      l1 = loss1(g)
      l2 = loss2(w,s,n)
      l = l1 + l2 + (l1-l2)*(l1-l2)
      try:
        if l < mmin:
          out = [w,g]
          mmin = l
      except:
        out = [w,g]
        mmin = l
  #print(out,mmin)
  return {'w':out[0],'g':out[1],'loss':mmin}     
    #outwriter.writerow(row)

# recursion
def go(level,n,nrows,n0):
#  print(n,level)
  global optim
#  print('optim:',optim)
  global ll
  while level < (nrows-1):
    #conservative (slow):
#    jmin = max(level+2,n[level-1]+1)
#    jmax = int(nmax(nrows-level,n0-sum(n[0:level]))+1)
    #faster (aritmetic series):
    if level > 0:
      if (nrows>1):
        q = 2*(n0-nrows*n[0])/(nrows-1)/nrows
        jmin = math.floor(n[0] + level*q - 0.5) #better with  -1, but slower
        jmax = math.ceil(n[0] + level*q + 0.5) #better with  +1, but slower
      else:
        jmin = max(level+2+round(sqrt(level)),n[level-1]+1)
        jmax = int(nmax(nrows-level,n0-sum(n[0:level]))+1)
    else:
      jmin = max(level+2,n[level-1]+1)
      jmax = int(nmax(nrows-level,n0-sum(n[0:level]))+1)
    for j in range(jmin,jmax):
      n[level] = j
      go(level+1,n,nrows,n0)
    return False
  n[level] = n0-sum(n)
#  print("calculating:",level,k,n)
  opt = grid(n)
#  print(opt,ll)
  try:
    if ll > opt['loss']:
      optim = opt.copy()
      optim['n'] = n.copy()
      ll = optim['loss']
  except:
    optim = opt.copy()
    optim['n'] = n.copy()
    ll = optim['loss']
#  print('optim2:',optim)
  n[level] = 0
  return True

# for each reasonable number of rows:
nr = nrow(n0)
for k in range(nr['min'],nr['max']+1):
  n = [0]*k
  optim = {}
  ll = 100000000
  go(0,n,k,n0)
  print("final optim:",optim)
  print("time:",timeit.default_timer() - start)


    
#example of results:
#n = 200:
#final optim: {'n': [44, 48, 52, 56], 'loss': 6.0494609377272378e-05, 'w': 0.069999999999999993, 'g': 1.2000000000000002}
#time: 23.457229251012905
#final optim: {'n': [34, 37, 40, 43, 46], 'loss': 0.003021820005212728, 'w': 0.089999999999999997, 'g': 1.1900000000000002}
#time: 51.52483937999932
#final optim: {'n': [24, 28, 31, 35, 39, 43], 'loss': 0.0009935459225664401, 'w': 0.13, 'g': 1.2300000000000002}
#time: 131.58585535301245
#final optim: {'n': [18, 21, 25, 29, 32, 36, 39], 'loss': 0.000796945129917957, 'w': 0.17000000000000001, 'g': 1.1900000000000002}
#time: 284.771323367022
#final optim: {'n': [12, 16, 19, 23, 27, 31, 34, 38], 'loss': 0.00031275649495655434, 'w': 0.25, 'g': 1.2000000000000002}
#time: 579.2367971060157
#final optim: {'n': [8, 11, 15, 19, 22, 26, 29, 33, 37], 'loss': 0.00043985954926300044, 'w': 0.39000000000000001, 'g': 1.2000000000000002}
#time: 1167.0518377900007
#final optim: {'n': [4, 8, 11, 15, 18, 22, 25, 29, 32, 36], 'loss': 0.00064177079858304589, 'w': 0.72999999999999998, 'g': 1.2000000000000002}
#time: 2341.9838014570123
#final optim: {'n': [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 35], 'loss': 0.0087001372112743003, 'w': 0.98999999999999999, 'g': 1.1400000000000001}
#time: 4631.68083341801


#n = 751 (Euro Parliament)
#final optim: {'n': [98, 101, 104, 107, 110, 113, 118], 'loss': 0.0062929076050250469, 'w': 0.029999999999999999, 'g': 1.1899999999999999}
#time: 217.3275479080039
#final optim: {'n': [85, 88, 90, 93, 95, 98, 100, 102], 'loss': 0.068194024500854655, 'w': 0.029999999999999999, 'g': 1.1599999999999999}
#time: 570.2674658489996
#final optim: {'n': [71, 74, 77, 80, 83, 87, 90, 93, 96], 'loss': 0.014035298736485213, 'w': 0.040000000000000001, 'g': 1.1799999999999999}
#time: 1331.067573258013
#final optim: {'n': [60, 63, 67, 70, 73, 77, 80, 83, 87, 91], 'loss': 0.0032756194901112823, 'w': 0.050000000000000003, 'g': 1.1899999999999999}
#time: 2816.806992516009
#final optim: {'n': [51, 54, 58, 61, 65, 68, 72, 75, 79, 82, 86], 'loss': 0.0013354982259395371, 'w': 0.060000000000000005, 'g': 1.1899999999999999}
#time: 5686.576568382996
#final optim: {'n': [44, 47, 51, 54, 57, 61, 64, 68, 71, 74, 78, 82], 'loss': 0.0016497989012379932, 'w': 0.069999999999999993, 'g': 1.1899999999999999}
#time: 10905.816249452997
#final optim: {'n': [34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 73, 77, 81], 'loss': 0.0025690587369525267, 'w': 0.089999999999999997, 'g': 1.25}
#time: 21918.771677729994
#final optim: {'n': [31, 34, 38, 41, 45, 48, 52, 55, 59, 62, 66, 69, 73, 78], 'loss': 0.00099189844185821208, 'w': 0.099999999999999992, 'g': 1.1899999999999999}
#time: 44362.27788667599
# ...

# n = 81 (CZ Senate)
#final optim: {'n': [39, 42], 'loss': 0.00015113520955957024, 'w': 0.080000000000000002, 'g': 1.2}
#time: 2.056351581995841
#final optim: {'n': [23, 27, 31], 'loss': 0.00074731223308436374, 'w': 0.13, 'g': 1.2}
#time: 3.672953786997823
#final optim: {'n': [15, 18, 22, 26], 'loss': 0.0017986444368775138, 'w': 0.20000000000000001, 'g': 1.1899999999999999}
#time: 5.949895355995977
#final optim: {'n': [9, 13, 16, 20, 23], 'loss': 0.0004283781313137963, 'w': 0.34000000000000002, 'g': 1.2}
#time: 10.962005101988325
#final optim: {'n': [5, 8, 12, 15, 19, 22], 'loss': 0.0011676166427925727, 'w': 0.62, 'g': 1.1899999999999999}
#time: 21.31037131600897
#final optim: {'n': [3, 6, 9, 12, 14, 17, 20], 'loss': 0.017012374030482232, 'w': 0.98999999999999999, 'g': 1.1499999999999999}
#time: 41.0609374709893

calculation.ods

cz-senate.png

cz-senate.svg

czechia.svg

ep.svg

europarliament.svg

hemicycle.png

hemicycle.svg

index.html

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <!--<script src="d3.v3.js"></script>-->
    <script src="http://d3js.org/d3.v3.min.js"></script>
    <link href="//netdna.bootstrapcdn.com/font-awesome/4.0.3/css/font-awesome.css" rel="stylesheet"> <!-- note: http://stackoverflow.com/questions/20032426/fontawesome-doesnt-display-in-firefox -->
    <link href="//maxcdn.bootstrapcdn.com/bootswatch/3.2.0/united/bootstrap.min.css" rel="stylesheet">
    <style>
    
    .axis path,
      .axis line {
          fill: none;
          stroke: #000;
          shape-rendering: crispEdges;
        }
          path, line {
        stroke:#bbb;
        stroke-width:1
      }
      /*http://www.d3noob.org/2013/01/adding-drop-shadow-to-allow-text-to.html*/
      text.shadow {
        stroke: gray;
        stroke-width: 1px;
        opacity: 0.9;
    }
    .half {
      fill: #888;
      opacity:0.5;
    }
        </style>
  </head>
  <body>
    <div class="navbar navbar-default">
      <div class="container">
        <div class="navbar-header">
          <span class="navbar-brand">Hemicycle - for parliaments/councils of any size, with draggable majority arc</span>
        </div>
      </div>
    </div>
    <div id="chart"></div>
    <div class="alert alert-info">
      The <strong>algorithm.py</strong> calculates optimal number of representatives in each row for several numbers of rows (+ size of icons and gap between the rows). These numbers are used as parameters for the chart.
      <br/><em>It may be slow for big parliaments, but it is needed just once for any number (e.g., 200 representatives took about 1 hour, due to the grid search - further optimization possible, my trial using steepest descent algorithm did not converge many times).</em>
    </div>
    <div class="col-lg-4">
      <div class="bs-component">
        <div class="list-group">
          <a href="#" class="list-group-item active">Legend</a>
          <a href="#" class="list-group-item">
            <div id="legend"></div>
          </a>
        </div>
      </div>
      <div class="alert alert-info">
      The legend is also created as a svg picture.
      </div>
    </div>
    <script>

    // 2:1!
var margin = {top: 0, right: 0, bottom: 0, left: 0},
    width = 600 - margin.left - margin.right,
    height = 300 - margin.top - margin.bottom;

var svg = d3.select("#chart").append("svg")
    .attr("width", width + margin.left + margin.right)
    .attr("height", height + margin.top + margin.bottom)
  .append("g")
    .attr("transform", "translate(" + margin.left + "," + margin.top + ")");

/*examples of parliaments*/
/*Plasy 2010*/
/*var groups = [
  {'name':'KSČM','n':2,'color':'red'},
  {'name':'ČSSD','n':4,'color':'orange'},
  {'name':'KDU-ČSL','n':2,'color':'yellow'},
  {'name':'TOP 09','n':2,'color':'violet'},
  {'name':'ODS','n':5,'color':'blue'}
];*/
/*Czech Republic 2013*/
var groups = [
  {'name':'KSČM','n':33,'color':'red'},
  {'name':'Úsvit','n':14,'color':'pink'},
  {'name':'ČSSD','n':50,'color':'orange'},
  {'name':'KDU-ČSL','n':14,'color':'yellow'},
  {'name':'ANO','n':47,'color':'aqua'},
  {'name':'TOP 09','n':26,'color':'purple'},
  {'name':'ODS','n':16,'color':'blue'}
];
/*Czech Republic Senate 2013*/
/*var groups = [
  {'name':'KSČM','n':2,'color':'red'}, 
  {'name':'ČSSD','n':46,'color':'orange'},
  {'name':'SPOZ','n':1,'color':'pink'},
  {'name':'Severočeši','n':2,'color':'darkred'},
  {'name':'Piráti','n':1,'color':'black'},
  {'name':'Zelení','n':1,'color':'green'},
  {'name':'KDU-ČSL','n':5,'color':'yellow'},
  {'name':'Nezávislí kand.','n':1,'color':'gray'},
  {'name':'Nestraníci','n':1,'color':'aqua'},
  {'name':'TOP 09 + STAN','n':4,'color':'purple'},
  {'name':'Ostravak','n':1,'color':'brown'},
  {'name':'ODS','n':15,'color':'blue'},
  {'name':'Neobsazeno','n':1,'color':'white'}
];*/

/*European Parliament 2014*/
/*var groups = [
  {'name':'GUE-NGL','n':52,'color':'darkred'},
  {'name':'Greens-EFA','n':50,'color':'green'},
  {'name':'S&D','n':191,'color':'red'},
  {'name':'ALDE','n':67,'color':'yellow'},
  {'name':'EPP','n':221,'color':'blue'},
  {'name':'ECR','n':70,'color':'darkblue'},
  {'name':'EFDD','n':48,'color':'aqua'},
  {'name':'Non-inscrits','n':52,'color':'gray'}
];*/

/*Plasy*/
/*var h = {
  'n': [6,9],
  'g': 1.19,
  'w': 0.52,
}*/

/*CZ*/
/*var h = {
  'n': [33,37,40,43,47],
  'g': 1.17,
  'w': 0.09,
}
var h = {
  'n': [24,28,31,35,39,43],
  'g': 1.23,
  'w': 0.13,
}
var h = {
  'n': [18,21,25,29,32,36,39],
  'g': 1.19,
  'w': 0.17,
}*/
var h = {
  'n': [8,11,15,19,22,26,29,33,37],
  'g': 1.20,
  'w': 0.39,
}
/*var h = {
  'n': [4,8,11,15,18,22,25,29,32,36],
  'g': 1.20,
  'w': 0.73,
}*/

/*CZ Senate*/
/*var h = {
  'n': [9,13,16,20,23],
  'g': 1.2,
  'w': 0.34,
}*/
/*EP*/
/*var h = {
  'n': [85,88,90,93,95,98,100,102],
  'g': 1.16,
  'w': 0.03,
}
var h = {
  'n': [31,34,38,41,45,48,52,55,59,62,66,69,73,78],
  'g': 1.19,
  'w': 0.1,
}*/

//max radius (for scales)
rmax = 1 + h['n'].length *h['g']*h['w'];

var 
	xScale = d3.scale.linear()
	  .domain([-1*rmax, rmax])
	  .range([0, width]),
    yScale = d3.scale.linear()
      .domain([0, rmax])
      .range([height,0])
    x0Scale = d3.scale.linear()
	  .domain([0, 2*rmax])
	  .range([0, width]);

//generate data: 1 representative ~ 1 datum
data = [];
s = [];
for (i in h['n']) {
  s.push((Math.PI/h['w'] + Math.PI*i*h['g']-h['n'][i])/(h['n'][i] - 1));
  ninrow = h['n'][i];
  radwidth = Math.PI/(h['n'][i]+(h['n'][i]-1)*s[i]);
  radspace = radwidth*s[i];
  r = 1 + i*h['g']*h['w'];
  for (j=0;j<ninrow;j++) {
    x = Math.cos(radwidth*(0.5+j)+j*radspace)*r;
    y = Math.sin(radwidth*(0.5+j)+j*radspace)*r;
    rot = -1*(radwidth*(0.5+j)+j*radspace)/Math.PI*180+90;
    data.push({'x':x,'y':y,'rot':rot});
  }
}

//sort data by rotation (representatives from 1 parl. groups together)
data.sort(function(x,y) {
  if (x['rot'] < y['rot']) return -1;
  if (x['rot'] > y['rot']) return 1;
  return 0
});

//add colors and names to data - may be used later
i = 0;
for (gkey in groups) {
  group = groups[gkey];
  for (j=0;j<group['n'];j++) {
    data[i]['color'] = group['color'];
    data[i]['name'] = group['name'];
    i++;
  }
}

/* MAJORITY ARC */
var angle = [{'startangle':0,'endangle':Math.PI/2}];

var arci = d3.svg.arc()
                .startAngle(function(d){return d.startangle})
                .endAngle(function(d){return d.endangle})
                .outerRadius(x0Scale(rmax))
                .innerRadius(0);

var position = [xScale(0),yScale(0)];
             
//http://stackoverflow.com/questions/8538651/d3-update-data-and-update-graph             
var arc = svg.selectAll('.half') 
    .data(angle)
    .enter()
    .append("path")
    .attr("d",arci)
    .attr("transform", "translate(" + position + ")")
    .attr("class","half");

//http://stackoverflow.com/questions/15303342/how-to-apply-drag-behavior-to-a-d3-svg-arc
var drag = d3.behavior.drag()
    .on("drag", function(d,i) {
        alpha1 = Math.atan((d3.event.x - xScale(0))/(-d3.event.y + yScale(0)));
        x2 = d3.event.dx + d3.event.x;
        y2 = d3.event.dy + d3.event.y;
        alpha2 = Math.atan((x2 - xScale(0))/(-y2 + yScale(0)));
        alpha = alpha2-alpha1;
        angle[0]['startangle'] += alpha;
        angle[0]['endangle'] += alpha;
        /*angle[0]['startangle'] = Math.min(0,angle[0]['startangle']);
        angle[0]['startangle'] = Math.max(Math.PI/2,angle[0]['startangle']);
        angle[0]['endangle'] = Math.min(Math.PI/2,angle[0]['endangle']);
        angle[0]['endangle'] = Math.max(Math.PI,angle[0]['endangle']);*/
        arc.attr("d",arci);   // redraw the arc
        /*position[0] += d3.event.dx;
        position[1] += d3.event.dy;
        d3.select(this)
        .attr("transform", function(d,i){
            return "translate(" + position + ")"
        })*/
    });
arc.call(drag);

// creating HEMICYCLE
var icons = svg.selectAll(".icon")
		.data(data)
      .enter().append("text")
        .attr('font-family', 'FontAwesome')
        .attr('font-size',x0Scale(h['w']*1.15)) //the icon is about 1.15times higher then wide
        .attr('fill', function(d) {return d.color;})
        .attr('text-anchor',"middle")
        .attr('class', 'shadow')
        .attr('x',function(d) {return xScale(d.x);})
        .attr('y',function(d) {return yScale(d.y);})
        .attr("transform",function(d) {return "rotate("+d.rot+","+xScale(d.x)+","+yScale(d.y)+")"})
        .text('\uf007');

//custom text
svg.append("text")
  .attr('font-family', 'sans-serif')
  .attr('font-size',x0Scale(h['w']*1))        //adjust as needed
  .attr('font-weight','bold')
  .attr('text-anchor',"middle")
  .attr('fill', '#444')
  .attr('x',xScale(0)) 
  .attr('y',yScale(0))
  .text("CZ 2013");

/* LEGEND */
heightleg = x0Scale(groups.length * h['w']*1.15*h['g']);
var svgleg = d3.select("#legend").append("svg")
    .attr("width", width + margin.left + margin.right)
    .attr("height", heightleg + margin.top + margin.bottom)
  .append("g")
    .attr("transform", "translate(" + margin.left + "," + margin.top + ")");
//sorting for legend
groups.sort(function(x,y) {
  if (x.n > y.n) return -1;
  if (x.n < y.n) return 1;
  return 0;
});
//creating legend
var iconsleg = svgleg.selectAll(".iconleg")
		.data(groups)
      .enter().append("text")
        .attr('font-family', 'FontAwesome')
        .attr('font-size',x0Scale(h['w']*1.15))
        .attr('fill', function(d) {return d.color;})
        .attr('text-anchor',"middle")
        .attr('class', 'shadow')
        .attr('x',x0Scale(h['w']*1.15))
        .attr('y',function(d,i) {return (i+1)*x0Scale(h['w']*1.15);})
        .text('\uf007');

var textleg = svgleg.selectAll(".textleg")
		.data(groups)
      .enter().append("text")
        .attr('font-family', 'sans-serif')
        .attr('font-size',x0Scale(h['w']*0.9))
        //.attr('fill', function(d) {return d.color;})
        //.attr('text-anchor',"middle")
        //.attr('class', 'shadow')
        .attr('x',x0Scale(2*h['w']*1.15))
        .attr('y',function(d,i) {return (i+1)*x0Scale(h['w']*1.15);})
        .text(function(d){return d.name + ' (' + d.n + ')'});
   </script>
  </body>
</html>

legend.svg

<?xml version="1.0" standalone="no"?><!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"><svg width="600" height="216.84957789716043" version="1.1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"><defs><style type="text/css"><![CDATA[
.axis path, .axis line { fill: none; stroke: rgb(0, 0, 0); shape-rendering: crispedges; }
path, line { stroke: rgb(187, 187, 187); stroke-width: 1px; }
text.shadow { stroke: rgb(128, 128, 128); stroke-width: 1px; opacity: 0.9; }
.half { fill: rgb(136, 136, 136); opacity: 0.5; }]]></style></defs><g transform="translate(0,0)"><text font-family="FontAwesome" font-size="25.81542594013814" fill="orange" text-anchor="middle" class="shadow" x="25.81542594013814" y="25.81542594013814"></text><text font-family="FontAwesome" font-size="25.81542594013814" fill="aqua" text-anchor="middle" class="shadow" x="25.81542594013814" y="51.63085188027628"></text><text font-family="FontAwesome" font-size="25.81542594013814" fill="red" text-anchor="middle" class="shadow" x="25.81542594013814" y="77.44627782041442"></text><text font-family="FontAwesome" font-size="25.81542594013814" fill="purple" text-anchor="middle" class="shadow" x="25.81542594013814" y="103.26170376055256"></text><text font-family="FontAwesome" font-size="25.81542594013814" fill="blue" text-anchor="middle" class="shadow" x="25.81542594013814" y="129.0771297006907"></text><text font-family="FontAwesome" font-size="25.81542594013814" fill="pink" text-anchor="middle" class="shadow" x="25.81542594013814" y="154.89255564082885"></text><text font-family="FontAwesome" font-size="25.81542594013814" fill="yellow" text-anchor="middle" class="shadow" x="25.81542594013814" y="180.707981580967"></text><text font-family="sans-serif" font-size="20.20337682271681" x="51.63085188027628" y="25.81542594013814">ČSSD (50)</text><text font-family="sans-serif" font-size="20.20337682271681" x="51.63085188027628" y="51.63085188027628">ANO (47)</text><text font-family="sans-serif" font-size="20.20337682271681" x="51.63085188027628" y="77.44627782041442">KSČM (33)</text><text font-family="sans-serif" font-size="20.20337682271681" x="51.63085188027628" y="103.26170376055256">TOP 09 (26)</text><text font-family="sans-serif" font-size="20.20337682271681" x="51.63085188027628" y="129.0771297006907">ODS (16)</text><text font-family="sans-serif" font-size="20.20337682271681" x="51.63085188027628" y="154.89255564082885">Úsvit (14)</text><text font-family="sans-serif" font-size="20.20337682271681" x="51.63085188027628" y="180.707981580967">KDU-ČSL (14)</text></g></svg>

mix.png

plasy.svg

thumbnail.png