legend.js

  1. 'use strict';
  2. const TOO_MANY_LAYERS = 15;
  4. // This file relates to legends on an exported map, not legends in the layer selector
  6. /**
  7.  * Generate all permutations of length M, with exactly N `true` values.
  8.  *
  9.  * @function
  10.  * @param {int} M the size of the array (must be greater than 0)
  11.  * @param {int} N the number of entries which should be true (must not be greater than M)
  12.  * @return an array containing all possible size M arrays of boolean values with N true entries
  13.  */
  14. function allComb(M, N) {
  15.     const maxTrue = N;
  16.     const maxFalse = M - N;
  17.     const C = [[[[]]]]; // C[m][n] is the solution to all_comb(m,n), C[0][0] starts with an empty array
  18.     for (let m = 1; m <= M; ++m) {
  19.         C[m] = [];
  20.         for (let n = 0; n <= m; ++n) {
  21.             // if this would place more than the max number of true or false values we don't need this part of the array
  22.             if (n > maxTrue || (m - n) > maxFalse) { continue; }
  24.             const a = n > 0 ? C[m - 1][n - 1].map(x => x.concat(true)) : [];
  25.             const b = m > n ? C[m - 1][n].map(x => x.concat(false)) : [];
  27.             C[m][n] = a.concat(b);
  28.         }
  29.     }
  30.     return C[M][N];
  31. }
  33. /**
  34.  * Convenience function for assigning the `splitBefore` property on layers at specified points.
  35.  * NOTE: this function modifies data in place
  36.  * @function
  37.  * @private
  38.  * @param {Array} layers a list of layers to be updated (modified in place)
  39.  * @param {Array} splitPoints an array of boolean values indicating if the layer list should be split at that point (must be layers.length-1 in size)
  40.  * @return layers the same array as passed in
  41.  */
  42. function assignLayerSplits(layers, splitPoints) {
  43.     layers[0].splitBefore = false;
  44.     splitPoints.forEach((split, i) => layers[i + 1].splitBefore = split);
  45.     return layers;
  46. }
  48. /**
  49.  * Groups multiple layers into each section while attempting to minimize the legend height.
  50.  * Allocates to the exact number specified in the `sections` argument.
  51.  * NOTE: don't call this with too many layers as it tests all possible groupings and can be
  52.  * computationally expensive (< 15 layers should be fine)
  53.  * @function
  54.  * @private
  55.  * @param {Array} layers a list of layers to be fitted
  56.  * @param {int} sections the number of sections to use
  57.  * @return {Object} an object in the form { layers, sectionsUsed, bestPerm, bestHeight }
  58.  */
  59. function packLayersIntoExactSections(layers, sections) {
  60.     const potentialSplits = layers.length - 1;
  61.     const requiredSplits = sections - 1;
  63.     const permutations = allComb(potentialSplits, requiredSplits);
  64.     let bestHeight = Number.MAX_VALUE;
  65.     let bestPerm = null;
  66.     const heights = Array(sections);
  68.     permutations.forEach(perm => {
  69.         heights.fill(0);
  70.         let curSec = 0;
  71.         layers.forEach((l, i) => {
  72.             heights[curSec] += l.height;
  73.             if (perm[i]) {
  74.                 ++curSec;
  75.             }
  76.         });
  77.         const h = Math.max(...heights);
  78.         if (h <= bestHeight) {
  79.             bestHeight = h;
  80.             bestPerm = perm;
  81.         }
  82.     });
  83.     return { layers, sectionsUsed: sections, bestPerm, bestHeight };
  84. }
  86. /**
  87.  * Groups multiple layers into each section while attempting to minimize the legend height.
  88.  * Repeats as necessary to use the least number of sections while still keeping the resulting
  89.  * legend height within 20% of optimal.
  90.  * NOTE: don't call this with too many layers as it tests all possible groupings and can be
  91.  * computationally expensive (< 15 layers should be fine)
  92.  * @function
  93.  * @private
  94.  * @param {Array} layers a list of layers to be updated (modified in place)
  95.  * @param {int} sections the number of sections to use
  96.  * @return {Object} an object in the form { layers, sectionsUsed }
  97.  */
  98. function packLayersIntoOptimalSections(layers, sections) {
  99.     let bestHeight = Number.MAX_VALUE;
  100.     let bestPerm = null;
  101.     let sectionsUsed = -1;
  102.     for (let n = sections; n > 1; --n) {
  103.         const { bestPerm: perm, bestHeight: height } = packLayersIntoExactSections(layers, n);
  104.         if (height * 0.8 > bestHeight) {
  105.             break;
  106.         } else if (height <= bestHeight) {
  107.             [bestHeight, bestPerm, sectionsUsed] = [height, perm, n];
  108.         }
  109.     }
  110.     assignLayerSplits(layers, bestPerm);
  111.     return { layers, sectionsUsed };
  112. }
  114. /**
  115.  * Split a layer into `splitCount` parts of roughly equal size.
  116.  * @function
  117.  * @private
  118.  * @param {Object} layer a layer object to be split into `splitCount` parts
  119.  * @param {int} chunkSize the maximum height in pixels of the legend sections
  120.  * @param {int} splitCount the number of pieces which the layer should be broken into
  121.  * @return an object with properties whiteSpace: <int>, splits: [ <layerItems> ]
  122.  */
  123. function splitLayer(layer, chunkSize, splitCount) {
  124.     let itemYOffset = layer.y;
  125.     let itemYMax = 0;
  126.     const splits = [];
  127.     const splitSizes = Array(splitCount).fill(0);
  129.     function traverse(items) {
  130.         items.forEach(item => {
  132.             if (splitCount === 1) {
  133.                 return;
  134.             }
  136.             splitSizes[splitCount - 1] = itemYMax - itemYOffset; // bottom of current item - offset at current section start
  138.             // this is the y coordinate of the item's bottom boundary
  139.             itemYMax = item.y + (item.type === 'group' ? item.headerHeight : item.height);
  141.             if (itemYMax - itemYOffset >= chunkSize) {
  142.                 splitCount--;
  144.                 // whitespace is created when an item sitting on the boundary pulled into the next chunk, the space
  145.                 // it would have occupied is wasted; the waste doubles as the entire item is moved to the next legend chunk
  146.                 itemYOffset = item.y;
  147.                 splits.push(item);
  148.             }
  150.             if (item.type === 'group') {
  151.                 traverse(item.items);
  152.             }
  153.         });
  154.     }
  156.     traverse(layer.items);
  157.     splitSizes[splitCount - 1] = layer.height - (itemYOffset - layer.y); // bottom of layer - start of last section; start of last section = total offset of last section - offset at start of layer
  159.     // with whiteSpace we want to find the difference between the chunkSize and used space
  160.     // for each section used (whiteSpace may be negative indicating that a section is
  161.     // spilling past the target size); the total amount of whiteSpace is a measure of how
  162.     // bad the layer allocation was
  163.     return { whiteSpace: splitSizes.reduce((a, b) => a + Math.abs(chunkSize - b), 0), splits };
  164. }
  166. /**
  167.  * Find the optimal split points for the given layer.
  168.  * @function
  169.  * @private
  170.  * @param {Object} layer a layer object to be split into `splitCount` parts
  171.  * @param {int} splitCount the number of pieces which the layer should be broken into
  172.  * @return a reference to the layer passed in
  173.  */
  174. function findOptimalSplit(layer, splitCount) {
  175.     if (splitCount === 1) {
  176.         return layer;
  177.     }
  179.     let chunkSize = layer.height / splitCount; // get initial chunk size for starters
  181.     // get initial splits and whitespace with initial chunk size; this will serve to determine the steps at which the chunk size will be increased
  182.     let { splits: minSplits, whiteSpace: minWhiteSpace } = splitLayer(layer, chunkSize, splitCount);
  184.     const stepCount = 8; // number of attempts
  185.     const step = minWhiteSpace / stepCount;
  187.     // calculate splits while increasing the chunk size
  188.     for (let i = 1; i <= stepCount; i++) {
  189.         chunkSize += step;
  191.         let { splits, whiteSpace } = splitLayer(layer, chunkSize, splitCount);
  193.         // store splits corresponding to the minimum whitespace
  194.         if (whiteSpace < minWhiteSpace) {
  195.             minWhiteSpace = whiteSpace;
  196.             minSplits = splits;
  197.         }
  198.     }
  200.     // apply split to the splits that result in the minimum of whitespace
  201.     minSplits.forEach(split => split.splitBefore = true);
  202.     return layer;
  203. }
  205. /**
  206.  * @function
  207.  * @private
  208.  * @param {Array} layers a list of layers to be updated (modified in place)
  209.  * @param {int} sectionsAvailable the maximum number of sections to use
  210.  * @param {int} mapHeight the rendered height of the map image
  211.  * @return the same layers array as passed in
  212.  */
  213. function allocateLayersToSections(layers, sectionsAvailable, mapHeight) {
  214.     assignLayerSplits(layers, Array(layers.length - 1).fill(true));
  215.     const bestSectionUsage = {}; // maps number of sections used to best height achieved
  216.     bestSectionUsage[layers.length] = {
  217.         height: Math.max(...layers.map(l => l.height)),
  218.         segments: Array(layers.length)
  219.     };
  220.     bestSectionUsage[layers.length].segments.fill(1);
  222.     let curSectionsUsed = layers.length;
  223.     while (curSectionsUsed < sectionsAvailable && bestSectionUsage[curSectionsUsed].height > mapHeight * 2) {
  224.         const oldSegments = bestSectionUsage[curSectionsUsed].segments;
  225.         const normalizedLayers = oldSegments.map((seg, i) => layers[i].height / seg);
  226.         const worstLayerIndex = normalizedLayers.indexOf(Math.max(...normalizedLayers));
  227.         const newSegments = oldSegments.map((seg, i) => i === worstLayerIndex ? seg + 1 : seg);
  228.         ++curSectionsUsed;
  229.         bestSectionUsage[curSectionsUsed] = {
  230.             height: Math.max(...newSegments.map((seg, i) => layers[i].height / seg)),
  231.             segments: newSegments
  232.         };
  233.     }
  234.     while (curSectionsUsed > layers.length) {
  235.         if (bestSectionUsage[curSectionsUsed].height < 0.9 * bestSectionUsage[curSectionsUsed - 1].height) {
  236.             break;
  237.         }
  238.         --curSectionsUsed;
  239.     }
  240.     layers.forEach((l, i) => findOptimalSplit(l, bestSectionUsage[curSectionsUsed].segments[i]));
  241.     return { layers, sectionsUsed: curSectionsUsed };
  242. }
  244. /**
  245.  * Generate the structure for a legend given a set of layers.
  246.  * @function
  247.  * @param {Array} layerList a list of layers to be updated (modified in place)
  248.  * @param {int} sectionsAvailable the maximum number of sections to use
  249.  * @param {int} mapHeight the rendered height of the map image
  250.  * @return an object with properties layers, sectionsUsed. (layerList is modified in place)
  251.  */
  252. function makeLegend(layerList, sectionsAvailable, mapHeight) {
  253.     if (layerList.length > TOO_MANY_LAYERS) {
  254.         const layersPerSection = Math.ceil(layerList.length / sectionsAvailable);
  255.         const splitPoints = Array(layerList.length - 1).fill(0).map((v, i) => (i + 1) % layersPerSection === 0); // I don't know why the useless fill is necessary
  256.         assignLayerSplits(layerList, splitPoints);
  257.         return { layers: layerList, sectionsUsed: sectionsAvailable };
  258.     }
  259.     if (layerList.length <= sectionsAvailable) {
  260.         return allocateLayersToSections(layerList, sectionsAvailable, mapHeight);
  261.     } else {
  262.         return packLayersIntoOptimalSections(layerList, sectionsAvailable);
  263.     }
  264. }
  266. module.exports = () => ({ makeLegend, allComb, splitLayer, findOptimalSplit });