31:T4fc,hexGrid = { const gridExtent = projectionHex.invert([width, height]); let g = []; let hexGridMap = new Map(); for (let x = 0; x < gridExtent[0]; x++) { for (let y = 0; y < gridExtent[1]; y++) { let pos = projectionHex([x, y]); let geo = projectionUTM.invert(pos); let kom = kommuner.some((k) => locWithinKommune(k, geo)); let komc = kommuner.filter((d) => d.hex[0] === x && d.hex[1] === y); if (!kom) continue; let o = { axial: [x, y], pos, geo, kn: kom, komc, knc: komc.length }; g.push(o); hexGridMap.set(key([x, y]), o); } } // Do a second run-through to indentify hexagons that are not selected, but is surrounded by all marks. for (let x = 0; x < gridExtent[0]; x++) { for (let y = 0; y < gridExtent[1]; y++) { if (hexGridMap.has(key([x, y]))) continue; if (surroundingKeys([x, y]).some((dkey) => !hexGridMap.has(dkey))) continue; let pos = projectionHex([x, y]); let geo = projectionUTM.invert(pos); let o = { axial: [x, y], pos, geo, kn: false, komc: 0, knc: 0 }; g.push(o); console.log("Found hole", x, y); } } return g; }32:T4b4,{ return Plot.plot({ //marginLeft: 100, // 1) Define a color scale: color: { // type of scale, e.g. quantize splits into discrete color bins type: "quantize", // domain automatically determined from the min/max of d.km domain: [0, d3.max(hexGrid, (d) => d.knc)], // pick a nice color scheme from d3, e.g. "YlOrRd", "Blues", etc. scheme: "YlOrRd", // label for the legendn label: "Distance (km)" }, x: { type: "identity", axis: null }, y: { type: "identity", axis: null }, height, width, marks: [ Plot.hexagon(hexGrid, { r: radius, // Hexagon radius stroke: "#433", //fill: "#88ccaa", fill: (d) => d.knc, x: (d) => projectionHex(d.axial)[0], // Horizontal position y: (d) => projectionHex(d.axial)[1] // Vertical position }), Plot.text(hexGrid, { r: radius, // Hexagon radius //stroke: "#337744", //fill: "#88ccaa", fill: (d) => "black", x: (d) => projectionHex(d.axial)[0], // Horizontal position y: (d) => projectionHex(d.axial)[1], // Vertical position text: (d) => d.knc }) ] }); }33:T623,{ return Plot.plot({ //marginLeft: 100, // 1) Define a color scale: color: { // type of scale, e.g. quantize splits into discrete color bins type: "quantize", // domain automatically determined from the min/max of d.km domain: [0, d3.max(optimizedGrid, (d) => d.cost)], // pick a nice color scheme from d3, e.g. "YlOrRd", "Blues", etc. scheme: "YlOrRd", // label for the legendn label: "Distance (km)" }, x: { type: "identity", axis: null }, y: { type: "identity", axis: null }, height, width, marks: [ Plot.hexagon(optimizedGrid, { r: radius, // Hexagon radius stroke: "#433", //fill: "#88ccaa", fill: (d) => d.cost, x: (d) => projectionHex(d.marker.axial)[0], // Horizontal position y: (d) => projectionHex(d.marker.axial)[1] // Vertical position }), Plot.text(optimizedGrid, { r: radius, // Hexagon radius //stroke: "#337744", //fill: "#88ccaa", fill: (d) => "black", x: (d) => projectionHex(d.marker.axial)[0], // Horizontal position y: (d) => projectionHex(d.marker.axial)[1], // Vertical position text: (d) => d.kommune.name.substring(0, 3), fontSize: 8 }), Plot.tip( optimizedGrid, Plot.pointer({ x: (d) => projectionHex(d.marker.axial)[0], // Horizontal position y: (d) => projectionHex(d.marker.axial)[1], // Vertical position title: (d) => d.kommune.name }) ) ] }); }34:T43b,compressed = { let grid = _.cloneDeep(optimizedGrid); let xrange = d3.extent(grid, (d) => d.marker.axial[0]); let yrange = d3.extent(grid, (d) => d.marker.axial[1]); for (let x = xrange[0]; x < xrange[1] - 1; x++) { let r1 = grid .filter((d) => d.marker.axial[0] === x) .map((d) => d.marker.axial[1]); let r2 = grid .filter((d) => d.marker.axial[0] === x + 1) .map((d) => d.marker.axial[1]); if (_.intersection(r1, r2).length === 0) { grid .filter((d) => d.marker.axial[0] > x) .forEach((d) => { d.marker.axial[0]--; }); } } /* for (let y = yrange[0]; y < yrange[1] - 1; y++) { let c1 = grid .filter((d) => d.marker.axial[1] === y) .map((d) => d.marker.axial[0]); let c2 = grid .filter((d) => d.marker.axial[1] === y + 1) .map((d) => d.marker.axial[0]); if (_.intersection(c1, c2).length === 0) { grid .filter((d) => d.marker.axial[1] > y) .forEach((d) => { d.marker.axial[1]--; }); } } */ return grid; }35:T61b,{ return Plot.plot({ //marginLeft: 100, // 1) Define a color scale: color: { // type of scale, e.g. quantize splits into discrete color bins type: "quantize", // domain automatically determined from the min/max of d.km domain: [0, d3.max(optimizedGrid, (d) => d.cost)], // pick a nice color scheme from d3, e.g. "YlOrRd", "Blues", etc. scheme: "YlOrRd", // label for the legendn label: "Distance (km)" }, x: { type: "identity", axis: null }, y: { type: "identity", axis: null }, height, width, marks: [ Plot.hexagon(compressed, { r: radius, // Hexagon radius stroke: "#433", //fill: "#88ccaa", fill: (d) => d.cost, x: (d) => projectionHex(d.marker.axial)[0], // Horizontal position y: (d) => projectionHex(d.marker.axial)[1] // Vertical position }), Plot.text(compressed, { r: radius, // Hexagon radius //stroke: "#337744", //fill: "#88ccaa", fill: (d) => "black", x: (d) => projectionHex(d.marker.axial)[0], // Horizontal position y: (d) => projectionHex(d.marker.axial)[1], // Vertical position text: (d) => d.kommune.name.substring(0, 3), fontSize: 8 }), Plot.tip( compressed, Plot.pointerX({ x: (d) => projectionHex(d.marker.axial)[0], // Horizontal position y: (d) => projectionHex(d.marker.axial)[1], // Vertical position title: (d) => d.kommune.name }) ) ] }); }36:T620,{ return Plot.plot({ //marginLeft: 100, // 1) Define a color scale: color: { // type of scale, e.g. quantize splits into discrete color bins type: "quantize", // domain automatically determined from the min/max of d.km domain: [0, d3.max(optimizedGrid, (d) => d.cost)], // pick a nice color scheme from d3, e.g. "YlOrRd", "Blues", etc. scheme: "YlOrRd", // label for the legendn label: "Distance (km)" }, x: { type: "identity", axis: null }, y: { type: "identity", axis: null }, height, width, marks: [ Plot.hexagon(compressed, { r: radius, // Hexagon radius stroke: "#343434", fill: "#FFE66D", //fill: (d) => d.cost, x: (d) => projectionHex(d.marker.axial)[0], // Horizontal position y: (d) => projectionHex(d.marker.axial)[1] // Vertical position }), Plot.text(compressed, { r: radius, // Hexagon radius //stroke: "#337744", //fill: "#88ccaa", fill: (d) => "#2F3061", x: (d) => projectionHex(d.marker.axial)[0], // Horizontal position y: (d) => projectionHex(d.marker.axial)[1], // Vertical position text: (d) => d.kommune.name.substring(0, 3), fontSize: 8 }), Plot.tip( compressed, Plot.pointerX({ x: (d) => projectionHex(d.marker.axial)[0], // Horizontal position y: (d) => projectionHex(d.marker.axial)[1], // Vertical position title: (d) => d.kommune.name }) ) ] }); }37:T54f6,munkres = { /** * Source: https://github.com/addaleax/munkres-js (Apache License, Version 2.0) * Introduction * ============ * * The Munkres module provides an implementation of the Munkres algorithm * (also called the Hungarian algorithm or the Kuhn-Munkres algorithm), * useful for solving the Assignment Problem. * * Assignment Problem * ================== * * Let C be an n×n-matrix representing the costs of each of n workers * to perform any of n jobs. The assignment problem is to assign jobs to * workers in a way that minimizes the total cost. Since each worker can perform * only one job and each job can be assigned to only one worker the assignments * represent an independent set of the matrix C. * * One way to generate the optimal set is to create all permutations of * the indices necessary to traverse the matrix so that no row and column * are used more than once. For instance, given this matrix (expressed in * Python) * * matrix = [[5, 9, 1], * [10, 3, 2], * [8, 7, 4]] * * You could use this code to generate the traversal indices:: * * def permute(a, results): * if len(a) == 1: * results.insert(len(results), a) * * else: * for i in range(0, len(a)): * element = a[i] * a_copy = [a[j] for j in range(0, len(a)) if j != i] * subresults = [] * permute(a_copy, subresults) * for subresult in subresults: * result = [element] + subresult * results.insert(len(results), result) * * results = [] * permute(range(len(matrix)), results) # [0, 1, 2] for a 3x3 matrix * * After the call to permute(), the results matrix would look like this:: * * [[0, 1, 2], * [0, 2, 1], * [1, 0, 2], * [1, 2, 0], * [2, 0, 1], * [2, 1, 0]] * * You could then use that index matrix to loop over the original cost matrix * and calculate the smallest cost of the combinations * * n = len(matrix) * minval = sys.maxsize * for row in range(n): * cost = 0 * for col in range(n): * cost += matrix[row][col] * minval = min(cost, minval) * * print minval * * While this approach works fine for small matrices, it does not scale. It * executes in O(n!) time: Calculating the permutations for an n×x-matrix * requires n! operations. For a 12×12 matrix, that’s 479,001,600 * traversals. Even if you could manage to perform each traversal in just one * millisecond, it would still take more than 133 hours to perform the entire * traversal. A 20×20 matrix would take 2,432,902,008,176,640,000 operations. At * an optimistic millisecond per operation, that’s more than 77 million years. * * The Munkres algorithm runs in O(n³) time, rather than O(n!). This * package provides an implementation of that algorithm. * * This version is based on * http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html * * This version was originally written for Python by Brian Clapper from the * algorithm at the above web site (The ``Algorithm::Munkres`` Perl version, * in CPAN, was clearly adapted from the same web site.) and ported to * JavaScript by Anna Henningsen (addaleax). * * Usage * ===== * * Construct a Munkres object * * var m = new Munkres(); * * Then use it to compute the lowest cost assignment from a cost matrix. Here’s * a sample program * * var matrix = [[5, 9, 1], * [10, 3, 2], * [8, 7, 4]]; * var m = new Munkres(); * var indices = m.compute(matrix); * console.log(format_matrix(matrix), 'Lowest cost through this matrix:'); * var total = 0; * for (var i = 0; i < indices.length; ++i) { * var row = indices[l][0], col = indices[l][1]; * var value = matrix[row][col]; * total += value; * * console.log('(' + rol + ', ' + col + ') -> ' + value); * } * * console.log('total cost:', total); * * Running that program produces:: * * Lowest cost through this matrix: * [5, 9, 1] * [10, 3, 2] * [8, 7, 4] * (0, 0) -> 5 * (1, 1) -> 3 * (2, 2) -> 4 * total cost: 12 * * The instantiated Munkres object can be used multiple times on different * matrices. * * Non-square Cost Matrices * ======================== * * The Munkres algorithm assumes that the cost matrix is square. However, it's * possible to use a rectangular matrix if you first pad it with 0 values to make * it square. This module automatically pads rectangular cost matrices to make * them square. * * Notes: * * - The module operates on a *copy* of the caller's matrix, so any padding will * not be seen by the caller. * - The cost matrix must be rectangular or square. An irregular matrix will * *not* work. * * Calculating Profit, Rather than Cost * ==================================== * * The cost matrix is just that: A cost matrix. The Munkres algorithm finds * the combination of elements (one from each row and column) that results in * the smallest cost. It’s also possible to use the algorithm to maximize * profit. To do that, however, you have to convert your profit matrix to a * cost matrix. The simplest way to do that is to subtract all elements from a * large value. * * The ``munkres`` module provides a convenience method for creating a cost * matrix from a profit matrix, i.e. make_cost_matrix. * * References * ========== * * 1. http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html * * 2. Harold W. Kuhn. The Hungarian Method for the assignment problem. * *Naval Research Logistics Quarterly*, 2:83-97, 1955. * * 3. Harold W. Kuhn. Variants of the Hungarian method for assignment * problems. *Naval Research Logistics Quarterly*, 3: 253-258, 1956. * * 4. Munkres, J. Algorithms for the Assignment and Transportation Problems. * *Journal of the Society of Industrial and Applied Mathematics*, * 5(1):32-38, March, 1957. * * 5. https://en.wikipedia.org/wiki/Hungarian_algorithm * * Copyright and License * ===================== * * Copyright 2008-2016 Brian M. Clapper * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ /** * A very large numerical value which can be used like an integer * (i. e., adding integers of similar size does not result in overflow). */ var MAX_SIZE = parseInt(Number.MAX_SAFE_INTEGER / 2) || (1 << 26) * (1 << 26); /** * A default value to pad the cost matrix with if it is not quadratic. */ var DEFAULT_PAD_VALUE = 0; // --------------------------------------------------------------------------- // Classes // --------------------------------------------------------------------------- /** * Calculate the Munkres solution to the classical assignment problem. * See the module documentation for usage. * @constructor */ function Munkres() { this.C = null; this.row_covered = []; this.col_covered = []; this.n = 0; this.Z0_r = 0; this.Z0_c = 0; this.marked = null; this.path = null; } /** * Pad a possibly non-square matrix to make it square. * * @param {Array} matrix An array of arrays containing the matrix cells * @param {Number} [pad_value] The value used to pad a rectangular matrix * * @return {Array} An array of arrays representing the padded matrix */ Munkres.prototype.pad_matrix = function (matrix, pad_value) { pad_value = pad_value || DEFAULT_PAD_VALUE; var max_columns = 0; var total_rows = matrix.length; var i; for (i = 0; i < total_rows; ++i) if (matrix[i].length > max_columns) max_columns = matrix[i].length; total_rows = max_columns > total_rows ? max_columns : total_rows; var new_matrix = []; for (i = 0; i < total_rows; ++i) { var row = matrix[i] || []; var new_row = row.slice(); // If this row is too short, pad it while (total_rows > new_row.length) new_row.push(pad_value); new_matrix.push(new_row); } return new_matrix; }; /** * Compute the indices for the lowest-cost pairings between rows and columns * in the database. Returns a list of (row, column) tuples that can be used * to traverse the matrix. * * **WARNING**: This code handles square and rectangular matrices. * It does *not* handle irregular matrices. * * @param {Array} cost_matrix The cost matrix. If this cost matrix is not square, * it will be padded with DEFAULT_PAD_VALUE. Optionally, * the pad value can be specified via options.padValue. * This method does *not* modify the caller's matrix. * It operates on a copy of the matrix. * @param {Object} [options] Additional options to pass in * @param {Number} [options.padValue] The value to use to pad a rectangular cost_matrix * * @return {Array} An array of ``(row, column)`` arrays that describe the lowest * cost path through the matrix */ Munkres.prototype.compute = function (cost_matrix, options) { options = options || {}; options.padValue = options.padValue || DEFAULT_PAD_VALUE; this.C = this.pad_matrix(cost_matrix, options.padValue); this.n = this.C.length; this.original_length = cost_matrix.length; this.original_width = cost_matrix[0].length; var nfalseArray = []; /* array of n false values */ while (nfalseArray.length < this.n) nfalseArray.push(false); this.row_covered = nfalseArray.slice(); this.col_covered = nfalseArray.slice(); this.Z0_r = 0; this.Z0_c = 0; this.path = this.__make_matrix(this.n * 2, 0); this.marked = this.__make_matrix(this.n, 0); var step = 1; var steps = { 1: this.__step1, 2: this.__step2, 3: this.__step3, 4: this.__step4, 5: this.__step5, 6: this.__step6 }; while (true) { var func = steps[step]; if (!func) // done break; step = func.apply(this); } var results = []; for (var i = 0; i < this.original_length; ++i) for (var j = 0; j < this.original_width; ++j) if (this.marked[i][j] == 1) results.push([i, j]); return results; }; /** * Create an n×n matrix, populating it with the specific value. * * @param {Number} n Matrix dimensions * @param {Number} val Value to populate the matrix with * * @return {Array} An array of arrays representing the newly created matrix */ Munkres.prototype.__make_matrix = function (n, val) { var matrix = []; for (var i = 0; i < n; ++i) { matrix[i] = []; for (var j = 0; j < n; ++j) matrix[i][j] = val; } return matrix; }; /** * For each row of the matrix, find the smallest element and * subtract it from every element in its row. Go to Step 2. */ Munkres.prototype.__step1 = function () { for (var i = 0; i < this.n; ++i) { // Find the minimum value for this row and subtract that minimum // from every element in the row. var minval = Math.min.apply(Math, this.C[i]); for (var j = 0; j < this.n; ++j) this.C[i][j] -= minval; } return 2; }; /** * Find a zero (Z) in the resulting matrix. If there is no starred * zero in its row or column, star Z. Repeat for each element in the * matrix. Go to Step 3. */ Munkres.prototype.__step2 = function () { for (var i = 0; i < this.n; ++i) { for (var j = 0; j < this.n; ++j) { if ( this.C[i][j] === 0 && !this.col_covered[j] && !this.row_covered[i] ) { this.marked[i][j] = 1; this.col_covered[j] = true; this.row_covered[i] = true; break; } } } this.__clear_covers(); return 3; }; /** * Cover each column containing a starred zero. If K columns are * covered, the starred zeros describe a complete set of unique * assignments. In this case, Go to DONE, otherwise, Go to Step 4. */ Munkres.prototype.__step3 = function () { var count = 0; for (var i = 0; i < this.n; ++i) { for (var j = 0; j < this.n; ++j) { if (this.marked[i][j] == 1 && this.col_covered[j] == false) { this.col_covered[j] = true; ++count; } } } return count >= this.n ? 7 : 4; }; /** * Find a noncovered zero and prime it. If there is no starred zero * in the row containing this primed zero, Go to Step 5. Otherwise, * cover this row and uncover the column containing the starred * zero. Continue in this manner until there are no uncovered zeros * left. Save the smallest uncovered value and Go to Step 6. */ Munkres.prototype.__step4 = function () { var done = false; var row = -1, col = -1, star_col = -1; while (!done) { var z = this.__find_a_zero(); row = z[0]; col = z[1]; if (row < 0) return 6; this.marked[row][col] = 2; star_col = this.__find_star_in_row(row); if (star_col >= 0) { col = star_col; this.row_covered[row] = true; this.col_covered[col] = false; } else { this.Z0_r = row; this.Z0_c = col; return 5; } } }; /** * Construct a series of alternating primed and starred zeros as * follows. Let Z0 represent the uncovered primed zero found in Step 4. * Let Z1 denote the starred zero in the column of Z0 (if any). * Let Z2 denote the primed zero in the row of Z1 (there will always * be one). Continue until the series terminates at a primed zero * that has no starred zero in its column. Unstar each starred zero * of the series, star each primed zero of the series, erase all * primes and uncover every line in the matrix. Return to Step 3 */ Munkres.prototype.__step5 = function () { var count = 0; this.path[count][0] = this.Z0_r; this.path[count][1] = this.Z0_c; var done = false; while (!done) { var row = this.__find_star_in_col(this.path[count][1]); if (row >= 0) { count++; this.path[count][0] = row; this.path[count][1] = this.path[count - 1][1]; } else { done = true; } if (!done) { var col = this.__find_prime_in_row(this.path[count][0]); count++; this.path[count][0] = this.path[count - 1][0]; this.path[count][1] = col; } } this.__convert_path(this.path, count); this.__clear_covers(); this.__erase_primes(); return 3; }; /** * Add the value found in Step 4 to every element of each covered * row, and subtract it from every element of each uncovered column. * Return to Step 4 without altering any stars, primes, or covered * lines. */ Munkres.prototype.__step6 = function () { var minval = this.__find_smallest(); for (var i = 0; i < this.n; ++i) { for (var j = 0; j < this.n; ++j) { if (this.row_covered[i]) this.C[i][j] += minval; if (!this.col_covered[j]) this.C[i][j] -= minval; } } return 4; }; /** * Find the smallest uncovered value in the matrix. * * @return {Number} The smallest uncovered value, or MAX_SIZE if no value was found */ Munkres.prototype.__find_smallest = function () { var minval = MAX_SIZE; for (var i = 0; i < this.n; ++i) for (var j = 0; j < this.n; ++j) if (!this.row_covered[i] && !this.col_covered[j]) if (minval > this.C[i][j]) minval = this.C[i][j]; return minval; }; /** * Find the first uncovered element with value 0. * * @return {Array} The indices of the found element or [-1, -1] if not found */ Munkres.prototype.__find_a_zero = function () { for (var i = 0; i < this.n; ++i) for (var j = 0; j < this.n; ++j) if (this.C[i][j] === 0 && !this.row_covered[i] && !this.col_covered[j]) return [i, j]; return [-1, -1]; }; /** * Find the first starred element in the specified row. Returns * the column index, or -1 if no starred element was found. * * @param {Number} row The index of the row to search * @return {Number} */ Munkres.prototype.__find_star_in_row = function (row) { for (var j = 0; j < this.n; ++j) if (this.marked[row][j] == 1) return j; return -1; }; /** * Find the first starred element in the specified column. * * @return {Number} The row index, or -1 if no starred element was found */ Munkres.prototype.__find_star_in_col = function (col) { for (var i = 0; i < this.n; ++i) if (this.marked[i][col] == 1) return i; return -1; }; /** * Find the first prime element in the specified row. * * @return {Number} The column index, or -1 if no prime element was found */ Munkres.prototype.__find_prime_in_row = function (row) { for (var j = 0; j < this.n; ++j) if (this.marked[row][j] == 2) return j; return -1; }; Munkres.prototype.__convert_path = function (path, count) { for (var i = 0; i <= count; ++i) this.marked[path[i][0]][path[i][1]] = this.marked[path[i][0]][path[i][1]] == 1 ? 0 : 1; }; /** Clear all covered matrix cells */ Munkres.prototype.__clear_covers = function () { for (var i = 0; i < this.n; ++i) { this.row_covered[i] = false; this.col_covered[i] = false; } }; /** Erase all prime markings */ Munkres.prototype.__erase_primes = function () { for (var i = 0; i < this.n; ++i) for (var j = 0; j < this.n; ++j) if (this.marked[i][j] == 2) this.marked[i][j] = 0; }; // --------------------------------------------------------------------------- // Functions // --------------------------------------------------------------------------- /** * Create a cost matrix from a profit matrix by calling * 'inversion_function' to invert each value. The inversion * function must take one numeric argument (of any type) and return * another numeric argument which is presumed to be the cost inverse * of the original profit. * * This is a static method. Call it like this: * * cost_matrix = make_cost_matrix(matrix[, inversion_func]); * * For example: * * cost_matrix = make_cost_matrix(matrix, function(x) { return MAXIMUM - x; }); * * @param {Array} profit_matrix An array of arrays representing the matrix * to convert from a profit to a cost matrix * @param {Function} [inversion_function] The function to use to invert each * entry in the profit matrix * * @return {Array} The converted matrix */ function make_cost_matrix(profit_matrix, inversion_function) { var i, j; if (!inversion_function) { var maximum = -1.0 / 0.0; for (i = 0; i < profit_matrix.length; ++i) for (j = 0; j < profit_matrix[i].length; ++j) if (profit_matrix[i][j] > maximum) maximum = profit_matrix[i][j]; inversion_function = function (x) { return maximum - x; }; } var cost_matrix = []; for (i = 0; i < profit_matrix.length; ++i) { var row = profit_matrix[i]; cost_matrix[i] = []; for (j = 0; j < row.length; ++j) cost_matrix[i][j] = inversion_function(profit_matrix[i][j]); } return cost_matrix; } /** * Convenience function: Converts the contents of a matrix of integers * to a printable string. * * @param {Array} matrix The matrix to print * * @return {String} The formatted matrix */ function format_matrix(matrix) { var columnWidths = []; var i, j; for (i = 0; i < matrix.length; ++i) { for (j = 0; j < matrix[i].length; ++j) { var entryWidth = String(matrix[i][j]).length; if (!columnWidths[j] || entryWidth >= columnWidths[j]) columnWidths[j] = entryWidth; } } var formatted = ""; for (i = 0; i < matrix.length; ++i) { for (j = 0; j < matrix[i].length; ++j) { var s = String(matrix[i][j]); // pad at front with spaces while (s.length < columnWidths[j]) s = " " + s; formatted += s; // separate columns if (j != matrix[i].length - 1) formatted += " "; } if (i != matrix[i].length - 1) formatted += "\n"; } return formatted; } // --------------------------------------------------------------------------- // Exports // --------------------------------------------------------------------------- function computeMunkres(cost_matrix, options) { var m = new Munkres(); return m.compute(cost_matrix, options); } computeMunkres.version = "1.2.2"; computeMunkres.format_matrix = format_matrix; computeMunkres.make_cost_matrix = make_cost_matrix; computeMunkres.Munkres = Munkres; // backwards compatibility return computeMunkres; }38:T6d9,genderData = { let dataset = befolkningsdata.Dataset(0); const regionDim = dataset.Dimension("Region"); const codeDim = dataset.Dimension("ContentsCode"); const tidDim = dataset.Dimension("Tid"); const kjonnDim = dataset.Dimension("Kjonn"); // There's only one ContentsCode and one Tid const singleCodeKey = codeDim.id[0]; const singleTidKey = tidDim.id[0]; const output = {}; regionDim.id.forEach((regionKey) => { // Remove the first two chars and parse as int const regionIdAsInt = regionKey.slice(2); // Create an object for this region output[regionIdAsInt] = { label: regionDim.Category(regionKey).label, data: {} }; // 1) Gather all kjonn values so we can compute the total const valuesByKjonn = {}; kjonnDim.id.forEach((kjonnKey) => { const val = dataset.Data({ Region: regionKey, ContentsCode: singleCodeKey, Tid: singleTidKey, Kjonn: kjonnKey }).value; valuesByKjonn[kjonnKey] = val; }); // 2) Compute the total across all Kjonn const total = Object.values(valuesByKjonn).reduce((sum, v) => sum + v, 0); // 3) For each Kjonn, store its value and portion kjonnDim.id.forEach((kjonnKey) => { const val = valuesByKjonn[kjonnKey]; const ratio = total !== 0 ? val / total : 0; const kjonnLabel = kjonnDim.Category(kjonnKey).label; // Store numeric value under the Kjonn label output[regionIdAsInt].data[kjonnLabel] = val; // And the fraction under a "_part" property keyed by the Kjonn label output[regionIdAsInt].data[`_part${kjonnLabel}`] = ratio; }); // Also store the total output[regionIdAsInt].data["_total"] = total; }); return output; }39:T65d,{ return Plot.plot({ //marginLeft: 100, // 1) Define a color scale: color: { // type of scale, e.g. quantize splits into discrete color bins type: "linear", // domain automatically determined from the min/max of d.km domain: [0.44, 0.56], // pick a nice color scheme from d3, e.g. "YlOrRd", "Blues", etc. range: ["#ca0020", "white", "#0571b0"], // label for the legendn label: "Share of men", legend: true // turn on the legend }, x: { type: "identity", axis: null }, y: { type: "identity", axis: null }, height, width, marks: [ Plot.hexagon(genderMarkers, { r: radius, // Hexagon radius stroke: "none", //fill: "#88ccaa", fill: (d) => d.data.data["_partMenn"] || null, x: (d) => projectionHex([d.i, d.j])[0], // Horizontal position y: (d) => projectionHex([d.i, d.j])[1] // Vertical position }), Plot.text(genderMarkers, { r: radius, // Hexagon radius //stroke: "#337744", //fill: "#88ccaa", stroke: "none", fill: (d) => "black", x: (d) => projectionHex([d.i, d.j])[0], // Horizontal position y: (d) => projectionHex([d.i, d.j])[1], // Vertical position text: (d) => d.name.substring(0, 3), fontSize: 8 }), Plot.tip( genderMarkers, Plot.pointerX({ x: (d) => projectionHex([d.i, d.j])[0], // Horizontal position y: (d) => projectionHex([d.i, d.j])[1], // Vertical position title: (d) => d.name + ` (${d.id})` }) ) ] }); }3a:[{"id":"70f8306718ba06e0adfe85f91f6be61cea0e02418fec6a57c57919ee48474ea85575d1c6002a426809061f978933eeb750b4be6fbe46125c83e903d6cb1a1679","href":"https://static.observableusercontent.com/files/70f8306718ba06e0adfe85f91f6be61cea0e02418fec6a57c57919ee48474ea85575d1c6002a426809061f978933eeb750b4be6fbe46125c83e903d6cb1a1679","name":"07459_20241226-131427.json","type":"application/json","lastModified":1735215283879.799,"size":24082},{"id":"2d571296d7fd05dbdbc3712e95933a1674978226cd532ef33dd6283cfec5511ba4fb1ed8d6517b92cb655ab6bf82142f89749071fa0be0feec9bf651c674ae81","href":"https://static.observableusercontent.com/files/2d571296d7fd05dbdbc3712e95933a1674978226cd532ef33dd6283cfec5511ba4fb1ed8d6517b92cb655ab6bf82142f89749071fa0be0feec9bf651c674ae81","name":"Norge-S.geojson","type":"application/geo+json","lastModified":1734811453918.021,"size":530122},{"id":"9040a3133fdc317eb5edfbcdb541dd723da57f21a69ebdf4246697f5be6b80728b9b011daca724a0fb7c60eff7ae864349f0f817526d11c79a1a83486dec857d","href":"https://static.observableusercontent.com/files/9040a3133fdc317eb5edfbcdb541dd723da57f21a69ebdf4246697f5be6b80728b9b011daca724a0fb7c60eff7ae864349f0f817526d11c79a1a83486dec857d","name":"Kommuner-S.topojson","type":"application/octet-stream","lastModified":1734813248384.08,"size":1015090}] 2f:{"title":"Hexmap of Norwegian Municipalities","cells":[{"id":0,"value":"# Hexmap of Norwegian Municipalities\n\nIn this notebook the goal is to create a hexmap of Norway representing 357 municipalities, while maintaining a shape similar to Norway, and still keep each hexagon located relatively near the original position of the municipality.\n\n**CC BY 4.0** – [On the bottom a data set is available for you](#cell-1160) to easy adopt the hexmap to create your own visualizations with municipalities of Norway.\n\n**Notice** that this notebook contains heavy calculations that will run in your browser each time you load the notebook. If you run on an old computer or adjust the parameters you may end up with a browser hanging – append `/safe` to the end of the url in order to load the notebook content without executing the code.\n\n","pinned":false,"hidden":false,"mode":"md"},{"id":1354,"value":"![](http://public-andreassolberg.s3.eu-north-1.amazonaws.com/hexagon-small-norway.png)\n\n*Here is a preview of the hexagon map explain in more detail in this notebook.*","pinned":false,"hidden":false,"mode":"md"},{"id":74,"value":"## Configuration options","pinned":false,"hidden":false,"mode":"md"},{"id":1126,"value":"Height and width of the vizualization","pinned":false,"hidden":false,"mode":"md"},{"id":9,"value":"height = 1000","pinned":false,"hidden":false,"mode":"ojs"},{"id":567,"value":"width = 800","pinned":false,"hidden":false,"mode":"ojs"},{"id":1128,"value":"Radius represents the size of the hexagon markers. ","pinned":false,"hidden":false,"mode":"md"},{"id":546,"value":"radius = 10","pinned":false,"hidden":false,"mode":"ojs"},{"id":1131,"value":"The *matching* parameter represents a percentage of margin around the muncipality shape in order to include a hexagon marker at that position.","pinned":false,"hidden":false,"mode":"md"},{"id":622,"value":"matching = 0.8","pinned":false,"hidden":false,"mode":"ojs"},{"id":510,"value":"## UTM 33N Projection of Norway\n\nUTM Zone 33N is well-suited for Norway because it aligns closely with the country’s central meridians, minimizing distortion across its north–south extent. This projection provides accurate distance, area, and direction measurements over large regions, ensuring reliable mapping.","pinned":false,"hidden":false,"mode":"md"},{"id":501,"value":"projectionUTM = d3\n .geoTransverseMercator()\n .scale(4100) // Adjust the scale to fit your area of interest\n .translate([width / 2, height / 2]) // Center on the canvas\n .rotate([-15.4, -65, 0]) // Rotation for UTM Zone 33N (centered at 15°E)","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"map1 = {\n const svg = d3.create(\"svg\").attr(\"width\", width).attr(\"height\", height);\n\n /*\n const projection = d3\n .geoSatellite()\n .translate([width / 2, height / 2])\n .scale(2800)\n .center([0, 0])\n .rotate([-12.1, -66.02, -0])\n // .tilt(-10)\n .distance(9.5)\n //.clipAngle((Math.acos(1 / 1.1) * 180) / Math.PI)\n .precision(1);\n*/\n\n const pathUTM = d3.geoPath().projection(projectionUTM);\n //const path = d3.geoPath(projection);\n\n const colors = {\n sea: \"#369\",\n land: \"#fff\",\n citymarker: \"#E63946\",\n citymarker2: \"#CD7A13\",\n marker: \"#494\"\n };\n\n svg.style(\"font-family\", \"sans-serif\");\n svg.style(\"font-size\", \"8\");\n\n svg\n .append(\"rect\")\n .attr(\"width\", width)\n .attr(\"height\", height)\n .style(\"fill\", colors.sea);\n\n svg\n .append(\"path\")\n .datum(norgeReverse)\n .attr(\"d\", pathUTM)\n .attr(\"fill\", colors.land);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":536,"value":"## Creating a UTM33 Hex grid that covers Norway","pinned":false,"hidden":false,"mode":"md"},{"id":544,"value":"projectionHex = {\n let convert = ([x, y]) => [\n radius * (2 * (1 + x) + (y % 2)),\n radius * Math.sqrt(3) * (1 + y)\n ];\n\n convert.invert = ([px, py]) => {\n // Solve for Y first (using pixelY = radius * sqrt(3) * (1 + Y))\n const floatY = py / (radius * Math.sqrt(3)) - 1;\n // Round to the nearest integer (assuming hex grid is integer-based)\n const Y = Math.round(floatY);\n\n // Solve for X (using pixelX = radius * (2*(1 + X) + (Y % 2)))\n // => (px / radius) = 2 * (1 + X) + (Y % 2)\n // => 2*(1 + X) = (px / radius) - (Y % 2)\n // => X = ((px / radius) - (Y % 2)) / 2 - 1\n const floatX = (px / radius - (Y % 2)) / 2 - 1;\n const X = Math.round(floatX);\n\n return [X, Y];\n };\n return convert;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":553,"value":"projectionHex([20, 13])","pinned":true,"hidden":false,"mode":"ojs"},{"id":555,"value":"projectionHex.invert([430, 242.4871130596428])","pinned":true,"hidden":false,"mode":"ojs"},{"id":538,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":585,"value":"## Visualizing the hex map\n\nThis map shows all hexagon markers from the defined grid, that intersects with the municipality polygons.\n\nThen for all ${kommuner.length} municipalities, the nearest hexagon marker is calculated and increase a counter. The result is that each marker shows a number (and color) indicating how many municipalities that share this hexagon marker location as the nearest marker for the centroid of the municipality. It illustrates the sparsely distributed municipalities in the north, and the denser distribution in around Oslo and the wester coast.\n","pinned":false,"hidden":false,"mode":"md"},{"id":587,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":900,"value":"## Optimal Distributed Placement\n\nMake a optiomal distribution of the muncipalities with minimum travel distance, using the Hungarian Algorithm.","pinned":false,"hidden":false,"mode":"md"},{"id":966,"value":"### Calculate distances\n\nCalculate distances from all muncipalities to all hexagon markers.","pinned":false,"hidden":false,"mode":"md"},{"id":968,"value":"distanceMatrix = {\n let dist = new Map();\n let costMatrix = [];\n let i = 0;\n for (let k of kommuner) {\n let costRow = [];\n for (let marker of hexGrid) {\n //if (i++ > 1000000) break;\n //console.log(k, marker);\n let dist = calculateDistance(k.centroid, marker.geo);\n costRow.push(dist);\n //dist.set(k.id + \"-\" + key(marker.axial), dist);\n }\n costMatrix.push(costRow);\n }\n\n return costMatrix;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":976,"value":"calculateDistance = (a, b) => {\n // console.log(\"calculate\", a, b);\n return Math.pow(b[1] - a[1], 2) + Math.pow(b[0] - a[0], 2);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1011,"value":"## Optimization using Munkres","pinned":false,"hidden":false,"mode":"md"},{"id":1013,"value":"optimizedSolution = munkres(distanceMatrix)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1033,"value":"optimizedGrid = {\n let g = [];\n for (let o of optimizedSolution) {\n g.push({\n kommune: kommuner[o[0]],\n marker: hexGrid[o[1]],\n cost: distanceMatrix[o[0]][o[1]]\n });\n }\n return g;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1336,"value":"**The visualization below shows optimal placement of hexagon markers for all ${optimizedGrid.length} municipalities of Norway.**\n\n[The Munkres algorithm, also known as the Hungarian algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm), is utilized to optimally position municipalities on a hexagonal map by ensuring each municipality is assigned to a new location with the shortest possible distance from its original placement. By constructing a cost matrix where each entry represents the distance between a municipality’s current position and potential hex tiles, the algorithm systematically evaluates and pairs municipalities with the most proximate available locations. This approach guarantees that the total relocation distance is minimized, resulting in an efficient and balanced distribution across the map.\n\nThe hexagon markers are displayed with a color representing the misplacement according to the original centroid of the municipality.","pinned":false,"hidden":false,"mode":"md"},{"id":1036,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":1062,"value":"### Compression\n\nSkip vertical and horizontal lines when possible.\n\nThis section explores the removal of empty horizontal and vertical lines. However I am not happy about the results, and it needs to be refined further in order to use this data. ","pinned":false,"hidden":false,"mode":"md"},{"id":1066,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":1085,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":1358,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":72,"value":"## Data processing","pinned":false,"hidden":false,"mode":"md"},{"id":105,"value":"kommuner = kommunerGeo.features.map(processKommuneGeometry)","pinned":true,"hidden":false,"mode":"ojs"},{"id":315,"value":"stats = {\n let xrange = [\n d3.min(kommuner.map((d) => d.xrange).map((d) => d[0])),\n d3.max(kommuner.map((d) => d.xrange).map((d) => d[1]))\n ];\n let yrange = [\n d3.min(kommuner.map((d) => d.yrange).map((d) => d[0])),\n d3.max(kommuner.map((d) => d.yrange).map((d) => d[1]))\n ];\n return {\n xrange,\n yrange,\n xwidth: xrange[1] - xrange[0],\n ywidth: yrange[1] - yrange[0],\n centroid: [d3.mean([xrange[1], xrange[0]]), d3.mean([yrange[1], yrange[0]])]\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":65,"value":"## Utilities","pinned":false,"hidden":false,"mode":"md"},{"id":941,"value":"key = ([x, y]) => {\n return x + \",\" + y;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":949,"value":"surroundingKeys([5, 5])","pinned":true,"hidden":false,"mode":"ojs"},{"id":946,"value":"surroundingKeys = ([x, y]) => {\n let kl = [\n [-1, 0],\n [1, 0],\n [0, -1],\n [0, 1]\n ];\n return kl\n .filter((d) => d[0] !== 0 || d[1] !== 0)\n .map((d) => [x + d[0], y + d[1]])\n .map(key);\n /*\n return d3\n .cross([-1, 0, 1], [-1, 0, 1])\n .filter((d) => d[0] !== 0 || d[1] !== 0)\n .map((d) => [x + d[0], y + d[1]])\n .map(key);\n\n */\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":384,"value":"locWithinKommune = (kommune, geo) => {\n //console.log(\"Check kommune\", kommune, i, j);\n\n let margin = 1; //radius * matching;\n\n if (kommune.xrange[0] - margin > geo[0]) return false;\n if (kommune.xrange[1] + margin < geo[0]) return false;\n if (kommune.yrange[0] - margin > geo[1]) return false;\n if (kommune.yrange[1] + margin < geo[1]) return false;\n //console.log(\"About to check point\", geo, \"with polygons\", kommune.c);\n const polygon = turf.polygon(kommune.c);\n const point = turf.point(geo);\n if (turf.booleanPointInPolygon(point, polygon)) return true;\n\n const circle = turf.circle(geo, radius * matching);\n\n return turf.booleanIntersects(circle, polygon);\n\n if (turf.booleanWithin(circle, polygon)) return true;\n if (turf.booleanIntersects(circle, polygon)) return true;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":91,"value":"processKommuneGeometry = (input) => {\n let c =\n input.geometry.type === \"Polygon\"\n ? input.geometry.coordinates\n : input.geometry.coordinates.map((d) => d[0]);\n //c = cmapList(c);\n let id = input.properties.id;\n let name = input.properties.name;\n let flat = _.flatten(c);\n let xrange = d3.extent(flat.map((d) => d[0]));\n let yrange = d3.extent(flat.map((d) => d[1]));\n let centroidOld = [\n d3.mean([xrange[1], xrange[0]]),\n d3.mean([yrange[1], yrange[0]])\n ];\n let centroid = turf.centroid(turf.polygon(c)).geometry.coordinates;\n\n let xy = projectionUTM(centroid);\n let hex = projectionHex.invert(xy);\n\n return {\n id,\n name,\n c,\n type: input.geometry.type,\n xrange,\n yrange,\n centroid,\n centroidOld,\n hex\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"## Data import","pinned":false,"hidden":false,"mode":"md"},{"id":43,"value":"kommunerTopo = FileAttachment(\"Kommuner-S.topojson\").json()","pinned":true,"hidden":false,"mode":"ojs"},{"id":101,"value":"kommunerGeo = topojson.feature(kommunerTopo, kommunerTopo.objects.Kommuner)","pinned":true,"hidden":false,"mode":"ojs"},{"id":5,"value":"norgeS = FileAttachment(\"Norge-S.geojson\").json()","pinned":true,"hidden":false,"mode":"ojs"},{"id":23,"value":"norgeReverse = turf.rewind(norgeS, { reverse: true })","pinned":true,"hidden":false,"mode":"ojs"},{"id":61,"value":"## Import libraries","pinned":false,"hidden":false,"mode":"md"},{"id":989,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":82,"value":"proj4 = require(\"proj4\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"turf = require(\"@turf/turf@6\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":84,"value":"topojson = require(\"topojson\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"d3 = require(\"d3\", \"d3-geo@3\", \"d3-geo-projection@4\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1166,"value":"import { button } from \"@jeremiak/download-data-button\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1195,"value":"import { JSONstat } from \"@jsonstat/toolkit\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":1190,"value":"## Example of usage: visaluzation of gender balance in Norwegian municipalities","pinned":false,"hidden":false,"mode":"md"},{"id":1192,"value":"befolkningsdataRaw = FileAttachment(\"07459_20241226-131427.json\").json()","pinned":true,"hidden":false,"mode":"ojs"},{"id":1204,"value":"befolkningsdata = JSONstat(befolkningsdataRaw)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1221,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":1242,"value":"genderMarkers = {\n let m = [];\n for (let element of dataset) {\n let o = _.cloneDeep(element);\n if (genderData.hasOwnProperty(element.id)) {\n o.data = genderData[element.id];\n } else {\n o.data = { data: {} };\n }\n m.push(o);\n }\n return m;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1286,"value":"d3.extent(genderMarkers, (d) => d.data.data[\"_partMenn\"])","pinned":true,"hidden":false,"mode":"ojs"},{"id":1248,"value":"$39","pinned":false,"hidden":false,"mode":"ojs"},{"id":1160,"value":"# Use dataset for your own visualizations\n\nClick the button below to download the dataset.\n","pinned":false,"hidden":false,"mode":"md"},{"id":1169,"value":"button(dataset, \"norway-municipalities-hexagon-markers.json\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1309,"value":"The data set contains objects such as this:\n\n```js\n{\n id: \"4014\"\n name: \"Kragerø\"\n i: 7\n j: 51\n x: 170\n y: 900.6664199358161\n}\n```\n\nwhere id means *kommunenr*, and *name* is the name of the municipality.\n\nThe **i** and **j** coordinates, are integer axial coordinates to represent the hexagon marker in a grid. To calculate the position of the hexagon markers, use this formula:\n\n* ${tex`x = \\mathrm{radius} \\cdot \\left(2x + \\left(y \\bmod 2\\right)\\right)`}\n* ${tex`y = \\text{radius} \\cdot \\sqrt{3} \\cdot y`}\n\nThe radius variable in the formula needs to be selected to scale the hexagon markers properly to your viewport.\n\nThe **x** and **y** coordinates are precalculated positions of the *(i, j)* coordinate, in a viewport with width ${width} and height ${height}.","pinned":false,"hidden":false,"mode":"md"},{"id":1163,"value":"dataset = optimizedGrid.map((d) => ({\n id: d.kommune.id,\n name: d.kommune.name,\n i: d.marker.axial[0],\n j: d.marker.axial[1],\n x: d.marker.pos[0],\n y: d.marker.pos[1]\n}))","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W3a","stdlib":"1","titling":"auto"}