Last active
November 22, 2020 12:52
-
-
Save michalskop/7e55931562cb3e5a9344 to your computer and use it in GitHub Desktop.
Hemicycle chart (general)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # 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 | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!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> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment