From 9fda5ec667848f12d732a4ca1e89088ac30f2a69 Mon Sep 17 00:00:00 2001 From: Jukka Kurkela Date: Wed, 22 Jan 2020 01:31:17 +0200 Subject: [PATCH] Use binary search for interpolations (#6958) --- src/core/core.datasetController.js | 4 ++ src/core/core.interaction.js | 82 +++++++++++++++++------------- src/elements/element.point.js | 5 ++ src/elements/element.rectangle.js | 4 ++ src/helpers/helpers.collection.js | 49 ++++++++++++++++++ src/scales/scale.time.js | 43 ++-------------- 6 files changed, 112 insertions(+), 75 deletions(-) create mode 100644 src/helpers/helpers.collection.js diff --git a/src/core/core.datasetController.js b/src/core/core.datasetController.js index b0a63f02f..2e1b31fb4 100644 --- a/src/core/core.datasetController.js +++ b/src/core/core.datasetController.js @@ -980,6 +980,10 @@ helpers.extend(DatasetController.prototype, { * @private */ _getSharedOptions: function(mode, el, options) { + if (!mode) { + // store element option sharing status for usage in interactions + this._sharedOptions = options && options.$shared; + } if (mode !== 'reset' && options && options.$shared && el && el.options && el.options.$shared) { return {target: el.options, options}; } diff --git a/src/core/core.interaction.js b/src/core/core.interaction.js index 3e130e02f..77780e0d8 100644 --- a/src/core/core.interaction.js +++ b/src/core/core.interaction.js @@ -1,8 +1,8 @@ 'use strict'; import helpers from '../helpers/index'; -import {isNumber} from '../helpers/helpers.math'; import {_isPointInArea} from '../helpers/helpers.canvas'; +import {_lookup, _rlookup} from '../helpers/helpers.collection'; /** * Helper function to get relative position for an event @@ -42,38 +42,58 @@ function evaluateAllVisibleItems(chart, handler) { } /** - * Helper function to check the items at the hovered index on the index scale + * Helper function to do binary search when possible + * @param {object} metaset - the dataset meta + * @param {string} axis - the axis mide. x|y|xy + * @param {number} value - the value to find + * @param {boolean} intersect - should the element intersect + * @returns {lo, hi} indices to search data array between + */ +function binarySearch(metaset, axis, value, intersect) { + const {controller, data, _sorted} = metaset; + const iScale = controller._cachedMeta.iScale; + if (iScale && axis === iScale.axis && _sorted) { + const lookupMethod = iScale._reversePixels ? _rlookup : _lookup; + if (!intersect) { + return lookupMethod(data, axis, value); + } else if (controller._sharedOptions) { + // _sharedOptions indicates that each element has equal options -> equal proportions + // So we can do a ranged binary search based on the range of first element and + // be confident to get the full range of indices that can intersect with the value. + const el = data[0]; + const range = typeof el.getRange === 'function' && el.getRange(axis); + if (range) { + const start = lookupMethod(data, axis, value - range); + const end = lookupMethod(data, axis, value + range); + return {lo: start.lo, hi: end.hi}; + } + } + } + // Default to all elements, when binary search can not be used. + return {lo: 0, hi: data.length - 1}; +} + +/** + * Helper function to get items using binary search, when the data is sorted. * @param {Chart} chart - the chart * @param {string} axis - the axis mode. x|y|xy * @param {object} position - the point to be nearest to * @param {function} handler - the callback to execute for each visible item - * @return whether all scales were of a suitable type + * @param {boolean} intersect - consider intersecting items */ -function evaluateItemsAtIndex(chart, axis, position, handler) { +function optimizedEvaluateItems(chart, axis, position, handler, intersect) { const metasets = chart._getSortedVisibleDatasetMetas(); - const indices = []; - for (let i = 0, ilen = metasets.length; i < ilen; ++i) { - const metaset = metasets[i]; - const iScale = metaset.controller._cachedMeta.iScale; - if (!iScale || axis !== iScale.axis || !iScale.getIndexForPixel) { - return false; - } - const index = iScale.getIndexForPixel(position[axis]); - if (!isNumber(index)) { - return false; - } - indices.push(index); - } - // do this only after checking whether all scales are of a suitable type + const value = position[axis]; for (let i = 0, ilen = metasets.length; i < ilen; ++i) { - const metaset = metasets[i]; - const index = indices[i]; - const element = metaset.data[index]; - if (!element.skip) { - handler(element, metaset.index, index); + const {index, data} = metasets[i]; + let {lo, hi} = binarySearch(metasets[i], axis, value, intersect); + for (let j = lo; j <= hi; ++j) { + const element = data[j]; + if (!element.skip) { + handler(element, index, j); + } } } - return true; } /** @@ -112,12 +132,7 @@ function getIntersectItems(chart, position, axis) { } }; - const optimized = evaluateItemsAtIndex(chart, axis, position, evaluationFunc); - if (optimized) { - return items; - } - - evaluateAllVisibleItems(chart, evaluationFunc); + optimizedEvaluateItems(chart, axis, position, evaluationFunc, true); return items; } @@ -154,12 +169,7 @@ function getNearestItems(chart, position, axis, intersect) { } }; - const optimized = evaluateItemsAtIndex(chart, axis, position, evaluationFunc); - if (optimized) { - return items; - } - - evaluateAllVisibleItems(chart, evaluationFunc); + optimizedEvaluateItems(chart, axis, position, evaluationFunc); return items; } diff --git a/src/elements/element.point.js b/src/elements/element.point.js index 25b5e2d19..2e9275f41 100644 --- a/src/elements/element.point.js +++ b/src/elements/element.point.js @@ -77,6 +77,11 @@ class Point extends Element { helpers.canvas.drawPoint(ctx, options, me.x, me.y); } } + + getRange() { + const options = this.options || {}; + return options.radius + options.hitRadius; + } } Point.prototype._type = 'point'; diff --git a/src/elements/element.rectangle.js b/src/elements/element.rectangle.js index 85d957a52..239dd9ebb 100644 --- a/src/elements/element.rectangle.js +++ b/src/elements/element.rectangle.js @@ -181,6 +181,10 @@ class Rectangle extends Element { y: this.y }; } + + getRange(axis) { + return axis === 'x' ? this.width / 2 : this.height / 2; + } } Rectangle.prototype._type = 'rectangle'; diff --git a/src/helpers/helpers.collection.js b/src/helpers/helpers.collection.js new file mode 100644 index 000000000..15535c25c --- /dev/null +++ b/src/helpers/helpers.collection.js @@ -0,0 +1,49 @@ +'use strict'; + +/** + * Binary search + * @param {array} table - the table search. must be sorted! + * @param {string} key - property name for the value in each entry + * @param {number} value - value to find + * @private + */ +export function _lookup(table, key, value) { + let hi = table.length - 1; + let lo = 0; + let mid; + + while (hi - lo > 1) { + mid = (lo + hi) >> 1; + if (table[mid][key] < value) { + lo = mid; + } else { + hi = mid; + } + } + + return {lo, hi}; +} + +/** + * Reverse binary search + * @param {array} table - the table search. must be sorted! + * @param {string} key - property name for the value in each entry + * @param {number} value - value to find + * @private + */ +export function _rlookup(table, key, value) { + let hi = table.length - 1; + let lo = 0; + let mid; + + while (hi - lo > 1) { + mid = (lo + hi) >> 1; + if (table[mid][key] < value) { + hi = mid; + } else { + lo = mid; + } + } + + return {lo, hi}; +} diff --git a/src/scales/scale.time.js b/src/scales/scale.time.js index 6d28e496e..2bd00c6a1 100644 --- a/src/scales/scale.time.js +++ b/src/scales/scale.time.js @@ -5,6 +5,7 @@ import defaults from '../core/core.defaults'; import helpers from '../helpers/index'; import {toRadians} from '../helpers/helpers.math'; import Scale from '../core/core.scale'; +import {_lookup} from '../helpers/helpers.collection'; const resolve = helpers.options.resolve; const valueOrDefault = helpers.valueOrDefault; @@ -130,33 +131,6 @@ function buildLookupTable(timestamps, min, max, distribution) { return table; } -// @see adapted from https://www.anujgakhar.com/2014/03/01/binary-search-in-javascript/ -function lookup(table, key, value) { - let lo = 0; - let hi = table.length - 1; - let mid, i0, i1; - - while (lo >= 0 && lo <= hi) { - mid = (lo + hi) >> 1; - i0 = mid > 0 && table[mid - 1] || null; - i1 = table[mid]; - - if (!i0) { - // given value is outside table (before first item) - return {lo: null, hi: i1}; - } else if (i1[key] < value) { - lo = mid + 1; - } else if (i0[key] > value) { - hi = mid - 1; - } else { - return {lo: i0, hi: i1}; - } - } - - // given value is outside table (after last item) - return {lo: i1, hi: null}; -} - /** * Linearly interpolates the given source `value` using the table items `skey` values and * returns the associated `tkey` value. For example, interpolate(table, 'time', 42, 'pos') @@ -164,11 +138,11 @@ function lookup(table, key, value) { * index [0, 1] or [n - 1, n] are used for the interpolation. */ function interpolate(table, skey, sval, tkey) { - const range = lookup(table, skey, sval); + const {lo, hi} = _lookup(table, skey, sval); // Note: the lookup table ALWAYS contains at least 2 items (min and max) - const prev = !range.lo ? table[0] : !range.hi ? table[table.length - 2] : range.lo; - const next = !range.lo ? table[1] : !range.hi ? table[table.length - 1] : range.hi; + const prev = table[lo]; + const next = table[hi]; const span = next[skey] - prev[skey]; const ratio = span ? (sval - prev[skey]) / span : 0; @@ -716,15 +690,6 @@ class TimeScale extends Scale { return interpolate(me._table, 'pos', pos, 'time'); } - getIndexForPixel(pixel) { - const me = this; - if (me.options.distribution !== 'series') { - return null; // not implemented - } - const index = Math.round(me._numIndices * me.getDecimalForPixel(pixel)); - return index < 0 || index >= me.numIndices ? null : index; - } - /** * @private */ -- 2.47.2