d3-delaunay

Георгий “Воронатор” Вороной

Это быстрая библиотека без зависимостей для вычисления диаграммы Вороного для набора двумерных точек. Она основана на Delaunator, быстрой библиотеке для вычисления треугольной сетки Делоне с использованием алгоритмов обхода. Диаграмма Вороного строится путём соединения окружностей, прилегающих к соседним треугольникам в треугольной сетке Делоне.

Для интерактивного объяснения работы этой библиотеки, см. The Delaunay’s Dual.

Установка

Для установки, npm install d3-delaunay или yarn add d3-delaunay. Также можно загрузить последнюю версию или загрузить напрямую с unpkg. Поддерживаются среды AMD, CommonJS, ES5 и ES6+. В обычном JavaScript, экспортируется глобальная переменная d3.

import {Delaunay} from "d3-delaunay";

const points = [[0, 0], [0, 1], [1, 0], [1, 1]];
const delaunay = Delaunay.from(points);
const voronoi = delaunay.voronoi([0, 0, 960, 500]);

Справочник API

Delaunay

new Delaunay(points) Источник

Возвращает треугольную сетку Делоне для данного плоского массива [x0, y0, x1, y1, …] точек.

const delaunay = new Delaunay(Float64Array.of(0, 0, 0, 1, 1, 0, 1, 1));

Delaunay.from(points[, fx[, fy[, that]]]) Источник

Возвращает треугольную сетку Делоне для данного массива или итерируемого объекта точек. Если fx и fy не указаны, то points предполагается массивом двумерных массивов чисел: [[x0, y0], [x1, y1], …]. В противном случае, fx и fy — функции, которые вызываются для каждого элемента в массиве points, и должны возвращать соответствующую x и y координаты для каждой точки. Если that указан, функции fx и fy вызываются с that в качестве this. (См. Array.from для справки.)

const delaunay = Delaunay.from([[0, 0], [0, 1], [1, 0], [1, 1]]);

delaunay.points

Координаты точек в виде массива [x0, y0, x1, y1, …]. Как правило, это Float64Array, но вы можете использовать любой массив-подобный тип в конструкторе.

delaunay.halfedges

Индексы ребер как Int32Array [j0, j1, …]. Для каждого индекса 0 ≤ i < halfedges.length, существует ребро от вершины треугольника j = halfedges[i] к вершине треугольника i. Эквивалентно, это означает, что треугольник ⌊i / 3⌋ прилегает к треугольнику ⌊j / 3⌋. Если j отрицательно, то треугольник ⌊i / 3⌋ является внешним треугольником на выпуклой оболочке. Например, чтобы отрисовать внутренние рёбра треугольной сетки Делоне:

const {points, halfedges, triangles} = delaunay;
for (let i = 0, n = halfedges.length; i < n; ++i) {
  const j = halfedges[i];
  if (j < i) continue;
  const ti = triangles[i];
  const tj = triangles[j];
  context.moveTo(points[ti * 2], points[ti * 2 + 1]);
  context.lineTo(points[tj * 2], points[tj * 2 + 1]);
}

См. также delaunay.render.

delaunay.hull

Любая узел на выпуклой оболочке. Выпуклая оболочка представлена как связанный список узлов, каждый узел является объектом со следующими свойствами:

узел.i - индекс соответствующей точки
узел.x - координата x соответствующей точки
узел.y - координата y соответствующей точки
узел.t - индекс (входящего или исходящего?) соответствующего ребра
узел.next - следующий узел на оболочке
узел.prev - предыдущий узел на оболочке

См. также delaunay.renderHull.

delaunay.triangles

Индексы вершин треугольников как Uint32Array [i0, j0, k0, i1, j1, k1, …]. Каждый непрерывный тройка индексов i, j, k образует треугольник против часовой стрелки. Координаты точек треугольника можно найти, пройдясь по delaunay.points. Например, чтобы отрисовать треугольник i:

const {points, triangles} = delaunay;
const t0 = triangles[i * 3 + 0];
const t1 = triangles[i * 3 + 1];
const t2 = triangles[i * 3 + 2];
context.moveTo(points[t0 * 2], points[t0 * 2 + 1]);
context.lineTo(points[t1 * 2], points[t1 * 2 + 1]);
context.lineTo(points[t2 * 2], points[t2 * 2 + 1]);
context.closePath();

См. также delaunay.renderTriangle.

delaunay.inedges

Индексы входящих ребер как Int32Array [e0, e1, e2, …]. Для каждой точки i, inedges[i] — это индекс ребра e входящего ребра. Для совпадающих точек индекс ребра — -1; для точек на выпуклой оболочке, входящее ребро находится на выпуклой оболочке; для других точек выбор входящего ребра произвольный. Таблица inedges может использоваться для обхода треугольной сетки Делоне; см. также delaunay.neighbors.

delaunay.outedges

Индексы исходящих ребер как Int32Array [e0, e1, e2, …]. Для каждой точки i на выпуклой оболочке, outedges[i] — это индекс ребра e соответствующего исходящего ребра; для других точек индекс ребра — -1. Таблица outedges может использоваться для обхода треугольной сетки Делоне; см. также delaunay.neighbors.

delaunay.find(x, y[, i]) Источник

Возвращает индекс входной точки, ближайшей к заданной точке ⟨x, y⟩. Поиск начинается в заданной точке i. Если i не указан, он по умолчанию равен нулю.

delaunay.neighbors(i) Источник

Возвращает итерируемый объект над индексами соседних точек заданной точки i. Итерируемый объект пуст, если i является совпадающей точкой.

delaunay.render([context]) Источник

delaunay.render

Отрисовывает рёбра треугольной сетки Делоне в заданный контекст. Заданный контекст должен реализовывать методы context.moveTo и context.lineTo из CanvasPathMethods API. Если контекст не указан, возвращается строка пути SVG.

delaunay.renderHull([context]) Источник

delaunay.renderHull

Отрисовывает выпуклую оболочку треугольной сетки Делоне в заданный контекст. Заданный контекст должен реализовывать методы context.moveTo и context.lineTo из CanvasPathMethods API. Если контекст не указан, возвращается строка пути SVG.

delaunay.renderTriangle(i[, context]) Источник

delaunay.renderTriangle

Отрисовывает треугольник i треугольной сетки Делоне в заданный контекст. Заданный контекст должен реализовывать методы context.moveTo, context.lineTo и context.closePath из CanvasPathMethods API. Если контекст не указан, возвращается строка пути SVG.

delaunay.renderPoints([context][, radius]) Источник

Отрисовывает входные точки треугольной сетки Делоне в заданный контекст как окружности заданного радиуса. Если радиус не указан, по умолчанию равен 2. Заданный контекст должен реализовывать методы context.moveTo и context.arc из CanvasPathMethods API. Если контекст не указан, возвращается строка пути SVG.

delaunay.hullPolygon() Источник

Возвращает замкнутый многоугольник [[x0, y0], [x1, y1], …, [x0, y0]] представляющий выпуклую оболочку.

delaunay.trianglePolygons() Источник

Возвращает итерируемый объект над многоугольниками для каждого треугольника, в порядке.

delaunay.trianglePolygon(i) Источник

Возвращает замкнутый многоугольник [[x0, y0], [x1, y1], [x2, y2], [x0, y0]] представляющий треугольник i.

delaunay.voronoi([bounds]) Источник

Возвращает диаграмму Вороного для связанных точек. При отрисовке диаграмма будет обрезана до заданной границы = [xmin, ymin, xmax, ymax]. Если границы не указаны, по умолчанию равны [0, 0, 960, 500]. См. To Infinity and Back Again для интерактивного объяснения обрезки ячеек Вороного.

Диаграмма Вороного

voronoi.delaunay

Связанная с диаграммой Вороного треугольная сетка Делоне.

voronoi.circumcenters

Центры описанных окружностей треугольников Делоне в виде Float64Array [cx0, cy0, cx1, cy1, …]. Каждая пара последовательных координат cx, cy представляет центр описанной окружности соответствующего треугольника. Эти центры описанных окружностей формируют координаты многоугольников ячеек Вороного.

voronoi.vectors

An Uint64Array [vx0, vy0, wx0, wy0, …], где каждая неповторяющаяся четвёрка описывает открытую (бесконечную) ячейку на внешней оболочке, задавая направления двух открытых полупрямых.

voronoi.xmin
voronoi.ymin
voronoi.xmax
voronoi.ymax

Границы области просмотра [xmin, ymin, xmax, ymax] для визуализации диаграммы Вороного. Эти значения влияют только на методы визуализации (voronoi.render, voronoi.renderBounds, cell.render).

voronoi.contains(i, x, y) Источник

Возвращает true, если ячейка с указанным индексом i содержит заданную точку ⟨x, y⟩. (Этот метод не зависит от области просмотра ассоциированной диаграммы Вороного границы).

voronoi.render([context]) Источник

voronoi.render

Визуализирует сетку ячеек Вороного в указанном context. Указанный context должен реализовывать методы context.moveTo и context.lineTo из API CanvasPathMethods. Если context не указан, возвращается строка SVG пути.

voronoi.renderBounds([context]) Источник

voronoi.renderBounds

Визуализирует область просмотра в указанном context. Указанный context должен реализовывать метод context.rect из API CanvasPathMethods. Эквивалентно context.rect(voronoi.xmin, voronoi.ymin, voronoi.xmax - voronoi.xmin, voronoi.ymax - voronoi.ymin). Если context не указан, возвращается строка SVG пути.

voronoi.renderCell(i[, context]) Источник

cell.render

Визуализирует ячейку с указанным индексом i в указанном context. Указанный context должен реализовывать методы context.moveTo, context.lineTo и context.closePath из API CanvasPathMethods. Если context не указан, возвращается строка SVG пути.

voronoi.cellPolygons() Источник

Возвращает итерируемый объект по многоугольникам каждой ячейки в порядке следования.

voronoi.cellPolygon(i) Источник

Возвращает выпуклый, замкнутый многоугольник [[x0, y0], [x1, y1], …, [x0, y0]] представляющий ячейку для указанной точки i.