d3-delaunay

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

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

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

Установка

Если вы используете npm, npm install d3-delaunay. Вы также можете загрузить последнюю версию на GitHub. Для обычного HTML в современных браузерах импортируйте d3-delaunay из Skypack:

<script type="module">

import {Delaunay} from "https://cdn.skypack.dev/d3-delaunay@6";

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

</script>

Для устаревших сред вы можете загрузить UMD-пакет d3-delaunay с CDN на основе npm, например, jsDelivr; экспортируется глобальная переменная d3:

<script src="https://cdn.jsdelivr.net/npm/d3-delaunay@6"></script>
<script>

const delaunay = d3.Delaunay.from(points);

</script>

Справочник 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 path вместо этого.

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

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

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

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

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

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

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⟩. (Этот метод не зависит от области просмотра диаграммы Вороного bounds.)

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 из API CanvasPathMethods. Если context не указан, возвращается строка SVG-пути.

voronoi.cellPolygons() Source

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

voronoi.cellPolygon(i) Source

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

voronoi.update() Source

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