D3: Что такое биссектриса?

Я изучаю диаграммы с D3 и наткнулся на d3.bisector. Однако я не понимаю, что это такое или делает из документации.

Почти все примеры, которые я нашел в Интернете, используют массив Date, похожий на пример в официальной документации:

var data = [
  {date: new Date(2011,  1, 1), value: 0.5},
  {date: new Date(2011,  2, 1), value: 0.6},
  {date: new Date(2011,  3, 1), value: 0.7},
  {date: new Date(2011,  4, 1), value: 0.8}
];

var bisect = d3.bisector(function(d) { return d.date; }).right;

Итак, что делает биссектриса, помимо выбора объекта даты из элементов массива? Что возвращает *.right?

И это полезно, если у меня есть простой одномерный массив, например var data = [3, 6, 2, 7, 5, 4, 8]?

Спасибо, что просвещал меня.

Ответ 1

Основная идея bisect заключается в следующем:

Рассмотрим массив, который вы упомянули - var data = [3, 6, 2, 7, 5, 4, 8]

Вы хотите вставить новое значение let say 3.5 в массив data и хотите знать, как бы это "переделать" его. Другими словами, вы хотите знать, что будет индексом 3.5, если он был вставлен при сортировке массива data.

   var data = [3, 6, 2, 7, 5, 4, 8]

   //Sorted data

  [2, 3, 4, 5, 6, 7, 8]

  //You want to insert 3.5


  The sorted array after insertion of 3.5 should look something like:

  [2, 3, 3.5, 4, 5, 6, 7, 8]


  So the index of 3.5 in sorted data array is "2".

Есть ситуации, когда вам нужно знать, как вставка этого элемента "делит" или "делит" массив. В этом случае вам нужно сначала отсортировать этот массив и сделать то, что мы называем Binary Search, чтобы узнать правильную позицию для вставки этого элемента.

bisectLeft и bisectRight позаботиться о том, чтобы выяснить аномалию в ситуации, когда вы хотите ввести элемент, который уже существует в массиве. Скажем, вы хотите ввести еще один 3 в массив. Есть две ситуации:

   3* -> The new element to be entered


   [2, 3*, 3, 4, 5, 6, 7, 8] -> entered at "1" (array is still sorted)


   [2, 3, 3*, 4, 5, 6, 7, 8] -> entered at "2" (array is still sorted)

Итак, в зависимости от того, как мы заботимся об этой двусмысленности, мы можем ввести этот элемент в "левое" или "право" уже существующего элемента. Из docs (Отметьте выделение):

Возвращенная точка вставки я разбивает массив на две половины так, чтобы все v < x для v в array.slice(lo, i) для левой стороны и все v > = x для v в array.slice(i, hi) для правой стороны.

В bisectLeft мы получим 1 в качестве подходящего индекса, все дубликаты записей будут находиться справа от этого индекса, и ситуация в обратном порядке в bisecRight.

Теперь, когда вы знаете, как работают bisectLeft и bisectRight, bisector просто позволяет нам определить пользовательскую функцию comparator или accessor для определения значений или смысла < и на объектах.

Итак, этот фрагмент кода:

  var bisect = d3.bisector(function(d) { return d.date; }).right;

  var bisect = d3.bisector(function(a, b) { return a.date - b.date; }).right;

Просто указывает, использовать параметр bisectRight и возвращать подходящий индекс для вставки элемента, предполагающего сортировку массива (в порядке возрастания).

Итак, если бы я собрался на вашем примере и предположил bisector с именем bisect. И вы сделали:

 bisect(data, 3); //it would return 2.

Я надеюсь, что это прояснит ситуацию и начнет вас в правильном направлении.

Ответ 2

Из документации (с которой вы связались):

Найдите точку вставки для x в массиве, чтобы сохранить отсортированный порядок.

Что он делает. Он сообщает вам, где новый элемент должен быть вставлен, чтобы после этого отсортировать массив. Массив может быть любой структурой, поэтому есть функция доступа, которая позволяет "разложить" эту структуру для целей поиска.

Разница между левым и правым биссектрисами заключается в том, где находится точка вставки (слева или справа от ближайшего элемента) - отсортирован ли массив по возрастанию или по убыванию.

Одним из вариантов использования биссектрисов является то, где вы хотите выделить ближайшую точку данных при перемещении мыши над графиком, см., например, этот пример.