d3-delaunay

Георгий «Воронатор» Вороной

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

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

Установка

Для установки, npm install d3-delaunay или yarn add d3-delaunay. Вы также можете скачать последнюю версию или загрузить напрямую с unpkg. Поддерживаются среды AMD, CommonJS и 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

Int32Array индексов точек, образующих выпуклую оболочку в против часовой стрелки. Если точки коллинеарны, возвращает их упорядоченные.

См. также 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.find(x, y[, i]) Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обновляет триангуляцию после изменения точек на месте.

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

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

Диаграмма Вороного возвращается даже в вырожденных случаях, когда нет триангуляции — а именно 0, 1 или 2 точки, и коллинеарные точки.

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

voronoi.delaunay

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

voronoi.circumcenters

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

voronoi.vectors

Float64Array [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) Source

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

voronoi.neighbors(i) Source

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

voronoi.render([context]) Source

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

voronoi.renderBounds([context]) Source

Отображает границы области просмотра в указанном 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]) Source

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

voronoi.cellPolygons() Source

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

voronoi.cellPolygon(i) Source

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

voronoi.update() Source

Обновляет диаграмму Вороного и базовую триангуляцию после изменения точек «in-place» — полезно для релаксации Ллойда.