Диаграмма Вороного - Voronoi diagram

20 точек и их ячейки Вороного (увеличенная версия ниже )

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

Диаграмма Вороной названа в честь Георгия Вороного , а также называет Вороной тесселяцией , разложение Вороного , разбиение Вороного , или тесселяцию Дирихля (после того, как Петр Густав Лежен Дирихлем ). Ячейки Вороного также известны как многоугольники Тиссена . Диаграммы Вороного находят практическое и теоретическое применение во многих областях, в основном в науке и технике , но также и в изобразительном искусстве .

Самый простой случай

В простейшем случае, показанном на первом рисунке, нам дан конечный набор точек { p ₁ , ..., p _n } на евклидовой плоскости . В этом случае каждый узел p _k является просто точкой, а соответствующая ему ячейка Вороного R _k состоит из каждой точки на евклидовой плоскости, расстояние до которой до p _k меньше или равно ее расстоянию до любого другого p _k . Каждая такая клетка получается из пересечения полупространств и, следовательно, является (выпуклым) многогранником . В отрезки диаграммы Вороного все точки в плоскости, равноудаленные к двум ближайшим узлам. Вершины ( узлы ) Вороного - это точки, равноотстоящие от трех (или более) узлов.

Формальное определение

Позвольте быть метрическим пространством с функцией расстояния . Позвольте быть набором индексов и пусть быть кортежем (упорядоченным набором) непустых подмножеств (узлов) в пространстве . Ячейка Вороного или область Вороного , связанная с сайтом, представляет собой набор всех точек , расстояние до которых не превышает их расстояние до других сайтов , где - любой индекс, отличный от . Другими словами, если обозначает расстояние между точкой и подмножеством , то ${\textstyle X}$ ${\textstyle d}$ ${\textstyle K}$ ${\textstyle (P_{k})_{k\in K}}$ ${\textstyle X}$ ${\textstyle R_{k}}$ ${\textstyle P_{k}}$ ${\textstyle X}$ ${\textstyle P_{k}}$ ${\textstyle P_{j}}$ ${\textstyle j}$ ${\textstyle k}$ ${\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}$ ${\textstyle x}$ ${\textstyle A}$

R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}

Диаграмма Вороного - это просто набор ячеек . В принципе, некоторые из сайтов могут пересекаться и даже совпадать (приложение описано ниже для сайтов, представляющих магазины), но обычно предполагается, что они не пересекаются. Кроме того, в определении разрешено бесконечно много узлов (этот параметр имеет приложения в геометрии чисел и кристаллографии ), но, опять же, во многих случаях рассматривается только конечное число узлов. ${\textstyle (R_{k})_{k\in K}}$

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

В обычном евклидовом пространстве мы можем переписать формальное определение в обычных терминах. Каждый многоугольник Вороного связан с образующей точкой . Позвольте быть набор всех точек в евклидовом пространстве. Позвольте быть точкой, которая генерирует свою область Вороного , которая генерирует , и которая генерирует , и так далее. Затем, как выразился Тран и др. , «Все местоположения в многоугольнике Вороного находятся ближе к образующей точке этого многоугольника, чем к любой другой образующей точке на диаграмме Вороного в евклидовой плоскости». ${\textstyle R_{k}}$ ${\textstyle P_{k}}$ ${\textstyle X}$ ${\textstyle P_{1}}$ ${\textstyle R_{1}}$ ${\textstyle P_{2}}$ ${\textstyle R_{2}}$ ${\textstyle P_{3}}$ ${\textstyle R_{3}}$

Иллюстрация

В качестве простой иллюстрации рассмотрим группу магазинов в городе. Предположим, мы хотим оценить количество покупателей данного магазина. При прочих равных условиях (цена, продукты, качество обслуживания и т. Д.) Разумно предположить, что покупатели выбирают предпочитаемый магазин просто из соображений расстояния: они пойдут в ближайший к ним магазин. В этом случае ячейку Вороного данного магазина можно использовать для грубой оценки количества потенциальных клиентов, идущих в этот магазин (который моделируется точкой в нашем городе). $R_{k}$ $P_{k}$

Для большинства городов расстояние между точками можно измерить, используя известное евклидово расстояние :

\ell _{2}=d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]={\sqrt {\left(a_{1}-b_{1}\right)^{2}+\left(a_{2}-b_{2}\right)^{2}}}

или расстояние Манхэттена :

d\left[\left(a_{1},a_{2}\right),\left(b_{1},b_{2}\right)\right]=\left|a_{1}-b_{1}\right|+\left|a_{2}-b_{2}\right|

.

Соответствующие диаграммы Вороного выглядят по-разному для разных метрик расстояния.

Диаграммы Вороного из 20 точек при двух разных метриках

Евклидово расстояние

Манхэттенское расстояние

Характеристики

Двойственный граф для диаграммы Вороного (в случае евклидова пространства с точечными сайтов) соответствует триангуляции Делоне для того же набора точек.
Ближе весь пар точек соответствует два соседним ячейкам в диаграмме Вороного.
Предположим, что задана евклидова плоскость и задана группа различных точек. Тогда две точки на выпуклой оболочке смежны тогда и только тогда, когда их клетки Вороного имеют бесконечно длинную сторону.
Если пространство является нормированным пространством и расстояние до каждого узла достигнуто (например, когда узел является компактным множеством или замкнутым шаром), то каждая ячейка Вороного может быть представлена как объединение линейных сегментов, исходящих из узлов. Как показано там, это свойство не обязательно сохраняется, когда расстояние не достигается.
При относительно общих условиях (пространство является, возможно, бесконечномерным равномерно выпуклым пространством , может быть бесконечно много узлов общего вида и т. Д.) Ячейки Вороного обладают определенным свойством устойчивости: небольшое изменение формы узлов, например , изменение, вызванное некоторым перемещением или искажением, приводит к небольшому изменению формы ячеек Вороного. Это геометрическая устойчивость диаграмм Вороного. Как показано там, это свойство не выполняется в общем случае, даже если пространство двумерное (но неравномерно выпуклое и, в частности, неевклидово), а узлы являются точками.

История и исследования

Неформальное использование диаграмм Вороного восходит к Декарту в 1644 году. Питер Густав Лежен Дирихле использовал двумерные и трехмерные диаграммы Вороного в своем исследовании квадратичных форм в 1850 году. Британский врач Джон Сноу использовал диаграмму, подобную диаграмме Вороного в 1854 году, чтобы проиллюстрируйте, как большинство людей, умерших во время вспышки холеры на Брод-стрит, жили ближе к инфицированному насосу на Брод-стрит, чем к любому другому водяному насосу.

Диаграммы Вороного названы в честь Георгия Феодосиевича Вороного, который определил и изучил общий n- мерный случай в 1908 году. Диаграммы Вороного, которые используются в геофизике и метеорологии для анализа пространственно распределенных данных (таких как измерения осадков), называются многоугольниками Тиссена в честь американского метеоролога Альфреда Х. Тиссен . Другие эквивалентные названия этой концепции (или ее особо важных случаев): многогранники Вороного, многоугольники Вороного, область (и) влияния, разложение Вороного, мозаика (я) Вороного, мозаика (я) Дирихле.

Примеры

Это фрагмент диаграммы Вороного случайного набора точек в трехмерном блоке. В общем, поперечное сечение трехмерной мозаики Вороного не является самим двухмерным мозаичным построением Вороного. (Все клетки представляют собой выпуклые многогранники .)

Тесселяции Вороного регулярных решеток точек в двух или трех измерениях дают начало многим знакомым мозаикам.

Двумерная решетка дает нерегулярную мозаику сот с равными шестиугольниками с точечной симметрией; в случае правильной треугольной решетки - правильная; в случае прямоугольной решетки шестиугольники сводятся к прямоугольникам в строках и столбцах; квадратная решетка дает регулярную тесселяцию квадратов; обратите внимание, что прямоугольники и квадраты также могут быть созданы другими решетками (например, решетка, определенная векторами (1,0) и (1 / 2,1 / 2), дает квадраты).
Простая кубическая решетка дает кубические соты .
Гексагональная плотноупакованная решетка дает тесселяцию пространства с trapezo-ромбические додекаэдрами .
Гранецентрированной кубической решетки дает тесселяции пространства с ромбической додекаэдры .
Кубическая объемно-центрированная решетка дает тесселяцию пространства с усеченными октаэдрами .
Параллельные плоскости с правильными треугольными решетками, выровненными по центрам друг друга, образуют гексагональные призматические соты .
Некоторые объемно-центрированные тетрагональные решетки образуют мозаику пространства с ромбо-гексагональными додекаэдрами .

Для набора точек ( x , y ) с x в дискретном наборе X и y в дискретном наборе Y мы получаем прямоугольные плитки с точками, не обязательно в их центрах.

Диаграммы Вороного высших порядков

Хотя нормальная ячейка Вороного определяется как набор точек, ближайших к одной точке в S , ячейка Вороного n- го порядка определяется как набор точек, имеющих конкретный набор из n точек в S в качестве своих n ближайших соседей. Диаграммы Вороного более высокого порядка также разделяют пространство.

Диаграммы Вороного более высокого порядка могут быть сгенерированы рекурсивно. Чтобы сгенерировать диаграмму Вороного n- ^го порядка из множества S , начните с диаграммы ( n - 1) ^-го порядка и замените каждую ячейку, сгенерированную X = { x ₁ , x ₂ , ..., x _{n −1} }, на диаграмма , Вороного генерируется на множестве S - X .

Диаграмма Вороного самой дальней точки

Для набора из n точек диаграмма Вороного ( n - 1) ^-го порядка называется диаграммой Вороного самой дальней точки.

Для данного набора точек S = { p ₁ , p ₂ , ..., p _n } диаграмма Вороного с самой дальней точкой делит плоскость на ячейки, в которых _{одна и} та же точка P является самой дальней точкой. Точка Р имеет ячейку в самой дальней точке диаграммы Вороной тогда и только тогда , когда она является вершиной выпуклой оболочки из P . Пусть H = { h ₁ , h ₂ , ..., h _k } - выпуклая оболочка P ; тогда диаграмма Вороного с самой дальней точкой представляет собой подразделение плоскости на k ячеек, по одной для каждой точки в H , с тем свойством, что точка q лежит в ячейке, соответствующей узлу h _i тогда и только тогда, когда d ( q , h _i )> d ( q , p _j ) для каждого p _j ∈ S с h _i ≠ p _j , где d ( p , q ) - евклидово расстояние между двумя точками p и q .

Границы ячеек на диаграмме Вороного с самой дальней точкой имеют структуру топологического дерева с бесконечными лучами в качестве его листьев. Любое конечное дерево изоморфно дереву, образованному таким образом из диаграммы Вороного с самой дальней точкой.

Обобщения и вариации

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

Приближенная диаграмма Вороного множества точек. Обратите внимание на смешанные цвета на нечеткой границе ячеек Вороного.

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

Диаграмма Вороного точек в -мерном пространстве может иметь вершины, что требует такой же оценки количества памяти, необходимой для хранения ее явного описания. Поэтому диаграммы Вороного часто невозможны для средних или больших размеров. Более компактная альтернатива - использование приближенных диаграмм Вороного . $n$ $d$ ${\textstyle O(n^{\lceil d/2\rceil })}$

Диаграммы Вороного также связаны с другими геометрическими структурами, такими как медиальная ось (которая нашла применение в сегментации изображений, оптическом распознавании символов и других вычислительных приложениях), прямой скелет и диаграммы зон . Помимо точек, на таких диаграммах в качестве семян используются линии и многоугольники. Дополняя диаграмму линейными сегментами, которые соединяются с ближайшими точками на семенах, получается планарное подразделение окружающей среды. Эту структуру можно использовать в качестве навигационной сетки для поиска пути через большие пространства. Сетка навигации была обобщена для поддержки трехмерных многоуровневых сред, таких как аэропорт или многоэтажное здание.

Приложения

Метеорология / гидрология

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

записывать данные об осадках. Серединные перпендикулярные линии проводятся к линии, соединяющей любые две станции. Это приводит к образованию полигонов вокруг станций. Зона касания точки станции известна как зона влияния станции. Среднее количество осадков рассчитывается по формуле $(A_{i})$ ${\bar {P}}={\frac {\sum A_{i}P_{i}}{\sum A_{i}}}$

Гуманитарные науки

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

Природные науки

Месселяция Вороного возникает в результате радиального роста семян наружу.

В биологии диаграммы Вороного используются для моделирования ряда различных биологических структур, включая клетки и микроархитектуру костей. Действительно, мозаики Вороного работают как геометрический инструмент для понимания физических ограничений, которые определяют организацию биологических тканей.
В гидрологии диаграммы Вороного используются для расчета количества осадков в районе на основе серии точечных измерений. В этом контексте они обычно называются многоугольниками Тиссена.
В экологии диаграммы Вороного используются для изучения моделей роста лесов и лесных пологов, а также могут быть полезны при разработке моделей прогнозирования лесных пожаров.
В вычислительной химии сайты связывания лигандов преобразуются в диаграммы Вороного для приложений машинного обучения (например, для классификации карманов связывания в белках). В других приложениях ячейки Вороного, определяемые положением ядер в молекуле, используются для вычисления атомных зарядов . Это делается с помощью метода плотности деформации Вороного .
В астрофизике диаграммы Вороного используются для создания зон адаптивного сглаживания на изображениях, добавляя потоки сигналов к каждой из них. Основная цель этих процедур - поддерживать относительно постоянное отношение сигнал / шум на всех изображениях.
В вычислительной гидродинамике мозаика Вороного набора точек может использоваться для определения вычислительных областей, используемых в методах конечных объемов , например, как в коде космологии подвижной сетки AREPO.
В вычислительной физике диаграммы Вороного используются для расчета профилей объекта с помощью Shadowgraph и протонной радиографии в физике высоких плотностей энергии .

Здоровье

В медицинской диагностике модели мышечной ткани, основанные на диаграммах Вороного, могут использоваться для выявления нервно-мышечных заболеваний.
В эпидемиологии диаграммы Вороного могут использоваться для корреляции источников инфекций в эпидемиях. Одно из первых применений диаграмм Вороного было применено Джоном Сноу для изучения вспышки холеры на Брод-стрит в 1854 году в Сохо, Англия. Он показал корреляцию между жилыми районами на карте центрального Лондона, жители которых использовали конкретный водяной насос, и районами с наибольшим количеством смертей из-за вспышки.

Инженерное дело

В физике полимеров диаграммы Вороного могут использоваться для представления свободных объемов полимеров.
В материаловедении поликристаллические микроструктуры в металлических сплавах обычно представляются с помощью мозаики Вороного. При росте острова диаграмма Вороного используется для оценки скорости роста отдельных островов. В физике твердого тела , то ячейка Вигнера-Зейтец является Вороной тесселяцией твердого тела, а зона Бриллюэа является Вороной тесселяцией взаимного ( волнового чисел ) пространства кристаллов , которые имеют симметрию пространственной группы.
В авиации диаграммы Вороного накладываются на океанические картографические карты, чтобы определить ближайший аэродром для отклонения в полете (см. ETOPS ) по мере того, как самолет продвигается по плану полета.
В архитектуре узоры Вороного были основой для победившей заявки на реконструкцию Центра искусств Голд-Кост .
В городском планировании диаграммы Вороного могут использоваться для оценки системы грузовых зон погрузки.
В горной промышленности полигоны Вороного используются для оценки запасов ценных материалов, полезных ископаемых или других ресурсов. В качестве точек в полигонах Вороного используются разведочные скважины.
В метрологии поверхности мозаику Вороного можно использовать для моделирования шероховатости поверхности .
В робототехнике некоторые стратегии управления и алгоритмы планирования пути для систем с несколькими роботами основаны на разбиении среды Вороного.

Геометрия

Точка расположения структура данных может быть построена на вершине диаграммы Вороного, чтобы ответить на ближайших соседей запросов, где один хочет , чтобы найти объект , который находится ближе всего к данной точке запроса. Запросы ближайшего соседа имеют множество применений. Например, кто-то может захотеть найти ближайшую больницу или наиболее похожий объект в базе данных . Большое приложение - векторное квантование , обычно используемое при сжатии данных .
В геометрии диаграммы Вороного можно использовать, чтобы найти самый большой пустой круг среди набора точек и в окружающем многоугольнике; например, построить новый супермаркет как можно дальше от всех существующих, лежащих в определенном городе.
Диаграммы Вороного вместе с диаграммами Вороного самых дальних точек используются для эффективных алгоритмов вычисления округлости набора точек. Подход Вороного также используется для оценки округлости / округлости при оценке набора данных с координатно-измерительной машины .

Информатика

В сети диаграммы Вороного могут использоваться для определения пропускной способности беспроводной сети .
В компьютерной графике диаграммы Вороного используются для расчета трехмерных геометрических моделей разрушения / разрушения. Он также используется для процедурной генерации органических текстур или текстур, похожих на лаву.
В автономной навигации роботов диаграммы Вороного используются для поиска четких маршрутов. Если точки являются препятствиями, то ребрами графа будут маршруты, наиболее удаленные от препятствий (и теоретически любых столкновений).
В машинном обучении диаграммы Вороного используются для классификации 1-NN .
При разработке пользовательского интерфейса шаблоны Вороного можно использовать для вычисления наилучшего состояния наведения для данной точки.

Гражданское право и планирование

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

Пекарня

Украинский кондитер Динара Касько использует математические принципы диаграммы Вороного для создания силиконовых форм, сделанных на 3D-принтере, для придания формы своим оригинальным тортам.

Алгоритмы

Известно несколько эффективных алгоритмов построения диаграмм Вороного либо напрямую (как сама диаграмма), либо косвенно, начиная с триангуляции Делоне и затем получая ее двойственную. Прямые алгоритмы включают в себя алгоритм фортуны , в O ( н лог ( п )) алгоритм для генерации диаграммы Вороного из множества точек на плоскости. Алгоритм Бойера – Ватсона, алгоритм от O ( n log ( n )) до O ( n ² ) для генерации триангуляции Делоне в любом количестве измерений, может использоваться в косвенном алгоритме для диаграммы Вороного. Алгоритм Jump Flooding может генерировать приблизительные диаграммы Вороного за постоянное время и подходит для использования на стандартном графическом оборудовании.

В алгоритме Ллойда и его обобщении с помощью алгоритма Линде – Бузо – Грея (также известного как кластеризация k-средних ) построение диаграмм Вороного используется в качестве подпрограммы. Эти методы чередуют шаги, на которых строят диаграмму Вороного для набора начальных точек, и шаги, на которых начальные точки перемещаются в новые местоположения, которые являются более центральными в их ячейках. Эти методы можно использовать в пространствах произвольной размерности, чтобы итеративно сходиться к специальной форме диаграммы Вороного, называемой центроидной тесселяцией Вороного , где сайты были перемещены в точки, которые также являются геометрическими центрами их ячеек.

Смотрите также

Примечания

использованная литература

Ауренхаммер, Франц ; Кляйн, Рольф; Ли, Дер-Цай (2013). Диаграммы Вороного и триангуляции Делоне . World Scientific. ISBN 978-9814447638.
Бойер, Адриан (1981). «Вычисление мозаики Дирихле» . Comput. J. 24 (2): 162–166. DOI : 10.1093 / comjnl / 24.2.162 .
де Берг, Марк; ван Кревельд, Марк; Овермарс, Марк ; Шварцкопф, Отфрид (2000). «7. Диаграммы Вороного» . Вычислительная геометрия (2-е изд., Перераб.). Springer. С. 47–163. ISBN 978-3-540-65620-3. Включает описание алгоритма Фортуны.
Кляйн, Рольф (1989). «Абстрактные диаграммы Вороного и их приложения». Вычислительная геометрия и ее приложения . Конспект лекций по информатике . 333 . Springer. С. 148–157. DOI : 10.1007 / 3-540-50335-8_31 . ISBN 978-3-540-52055-9.
Лежен Дирихле, Г. (1850). "Uber die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen". Journal für die Reine und Angewandte Mathematik . 1850 (40): 209–227. DOI : 10,1515 / crll.1850.40.209 .
Окабе, Ацуюки; Сапоги, Барри; Сугихара, Кокичи ; Чиу, Сунг Нок (2000). Пространственная мозаика - концепции и приложения диаграмм Вороного (2-е изд.). Вайли. ISBN 0-471-98635-6.
Рим, Дэниел (2009). «Алгоритм вычисления диаграмм Вороного общих образующих в общих нормированных пространствах». Труды Шестого Международного симпозиума по диаграммам Вороного в науке и технике (ISVD 2009) . С. 144–152. DOI : 10.1109 / ISVD.2009.23 .
Рим, Дэниел (2011). «Геометрическая устойчивость диаграмм Вороного относительно небольших изменений узлов». Труды 27-го ежегодного симпозиума ACM по вычислительной геометрии (SoCG) : 254–263. arXiv : 1103.4125 . Bibcode : 2011arXiv1103.4125R . DOI : 10.1145 / 1998196.1998234 . ISBN 9781450306829. S2CID 14639512 .
Вороной, Жорж (1908a). «Новые приложения непрерывных параметров в теории квадратичных форм. Премьер-воспоминания. Sur quelques propriétés des form quadratiques positives parfaites» (PDF) . Journal für die Reine und Angewandte Mathematik . 1908 (133): 97–178. DOI : 10,1515 / crll.1908.133.97 . S2CID 116775758 .
Вороной, Жорж (1908b). «Новые приложения непрерывных параметров в теории квадратичных форм. Deuxième mémoire. Recherches sur les parallélloèdres primitifs» (PDF) . Journal für die Reine und Angewandte Mathematik . 1908 (134): 198–287. DOI : 10,1515 / crll.1908.134.198 . S2CID 118441072 .
Уотсон, Дэвид Ф. (1981). «Вычисление n- мерной мозаики Делоне с применением к многогранникам Вороного» . Comput. J. 24 (2): 167–172. DOI : 10.1093 / comjnl / 24.2.167 .

внешние ссылки

Интерактивные диаграммы Вороного и Делоне с исходным кодом в реальном времени
Демо для различных показателей
Mathworld на диаграммах Вороного
Диаграммы Вороного: приложения от археологии к зоологии
Диаграммы Вороного в CGAL , библиотеке алгоритмов вычислительной геометрии
Другие обсуждения и галерея изображений по центроидальной мозаике Вороного
Вороного от Ed Пегг, младший , Джефф Брайант, и Теодор Грей , Wolfram Demonstrations проекта .
Диаграмма Вороного на сфере, в 3D и др.
Постройте диаграмму Вороного с помощью Mathematica
Тесселяция Вороного - Интерактивная тесселяция Вороного с D3.js
Интерактивная диаграмма Вороного и визуализация интерполяции естественных соседей (WebGL)

Программное обеспечение

Диаграммы Вороного требуют вычислительного шага перед отображением результатов. Таким образом, эффективный инструмент будет обрабатывать вычисления в реальном времени, чтобы показать пользователю прямой результат. Существует множество коммерческих и бесплатных приложений. Особенно практичным типом инструментов являются веб-инструменты. Доступ к веб-инструментам и к ним проще. Кроме того, SVG является форматом, изначально поддерживаемым Интернетом, позволяет одновременно осуществлять эффективный (с ускорением графического процессора) рендеринг и является стандартным форматом, поддерживаемым несколькими инструментами САПР (например, Autodesk Fusion360).

Voronator - это бесплатный инструмент (основанный на рекламе ), действующий на сетки трехмерных объектов для нанесения Вороного на их поверхность. Хотя инструмент воздействует на 3D, обработка вороного основана на его 2d поверхности.
rhill voronoi - это библиотека JavaScript с открытым исходным кодом для генерации 2d voronoi.
stg voronoi - это проект на github с простым веб-приложением, предлагающий интерактивный просмотр ячеек voronoi при перемещении мыши. Он также обеспечивает экспорт в SVG.
websvg voronoi - это адаптивное веб- приложение для редактирования и экспорта voronoi в SVG. Он также позволяет экспортировать и импортировать координаты семян. Он основан на 2d и отличается от ранее упомянутых инструментов тем, что обеспечивает операцию втягивания ячеек, которая основана не на масштабе, а на перемещении краев. Ребро можно удалить, если оно поглощено соседними ребрами.
A.Beutel voronoi использует WebGL и предоставляет в дополнение к статическому просмотру анимированное движение ячеек вороного.

Хотя voronoi - очень старая концепция, в доступных в настоящее время инструментах не хватает множества математических функций, которые могли бы добавлять значения в эти программы. Примерами могут быть использование другого стоимостного расстояния, чем евклидово, и, в основном, алгоритмов 3D-Вороного. Хотя это и не являются сами программные инструменты, первая ссылка объясняет концепцию 3D-вороного, а вторая - это библиотека 3D-вороного.

Трехмерные диаграммы Вороного и медиальная ось
Воронцовское ++ C ++ библиотека для расчета 3d Вороного

Languages

In other projects