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

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

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

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

Самый простой случай [ править ]

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

Формальное определение [ править ]

Позвольте быть метрическое пространство с функцией расстояния . Позвольте быть набором индексов и пусть будет кортежем (упорядоченным набором) непустых подмножеств (узлов) в пространстве . Ячейка Вороного или область Вороного , связанная с сайтом, представляет собой набор всех точек , расстояние до которых не превышает их расстояние до других сайтов , где - любой индекс, отличный от . Другими словами, если обозначает расстояние между точкой и подмножеством , то ${\ 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}}$

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

В обычном евклидовом пространстве мы можем переписать формальное определение в обычных терминах. Каждый многоугольник Вороного связан с образующей точкой . Позвольте быть набор всех точек в евклидовом пространстве. Позвольте быть точкой, которая генерирует свою область Вороного , которая генерирует , и которая генерирует , и так далее. Затем, как выражаются Tran и др , ^[7] «все места в многоугольнике Вороного ближе к точке генератора этого многоугольника , чем любая другая точка генератора в диаграмме Вороного в евклидовой плоскости». ${\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 точек при двух разных метриках

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

Свойства [ править ]

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

История и исследования [ править ]

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

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

Примеры [ править ]

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

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

Двумерная решетка дает нерегулярную мозаику сот с равными шестиугольниками с точечной симметрией; в случае правильной треугольной решетки - правильная; в случае прямоугольной решетки шестиугольники сводятся к прямоугольникам в строках и столбцах; квадратная решетка дает регулярную тесселяцию квадратов; обратите внимание, что прямоугольники и квадраты также могут быть созданы другими решетками (например, решетка, определенная векторами (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 . ^[11]^[12]

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

Обобщения и вариации [ править ]

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

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

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

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

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

Приложения [ править ]

Гуманитарные науки [ править ]

В классической археологии соответственно историях искусства симметрия статуй головок анализируются , чтобы определить тип статуи отрезанной головка может принадлежать как в случае известной головы Sabouroff с использованием высокого разрешения полигональной сеткой . ^[18]^[19]

Естественные науки [ править ]

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

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

Здоровье [ править ]

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

Инженерное дело [ править ]

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

Геометрия [ править ]

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

Информатика [ править ]

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

Гражданское право и планирование [ править ]

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

Пекарня [ править ]

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

Алгоритмы [ править ]

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

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

См. Также [ править ]

Метод природных элементов
Интерполяция естественного соседа
Интерполяция ближайшего соседа
Вороной полюс
Схема питания
Сегментация карты

Примечания [ править ]

^ Берроу, Питер А .; Макдоннелл, Рэйчел; McDonnell, Rachael A .; Ллойд, Кристофер Д. (2015). «8.11 Ближайшие соседи: полигоны Тиссена (Дирихле / Ворони)» . Принципы географических информационных систем . Издательство Оксфордского университета. С. 160–. ISBN 978-0-19-874284-5.
^ Лонгли, Пол А .; Гудчайлд, Майкл Ф .; Магуайр, Дэвид Дж .; Райнд, Дэвид В. (2005). «14.4.4.1 Полигоны Тиссена» . Географические информационные системы и наука . Вайли. стр. 333–. ISBN 978-0-470-87001-3.
^ Сен, Зекай (2016). «2.8.1 Полигоны Делани, Варони и Тиссена» . Принципы пространственного моделирования в науках о Земле . Springer. С. 57–. ISBN 978-3-319-41758-5.
^ Aurenhammer, Franz (1991). «Диаграммы Вороного - обзор фундаментальной геометрической структуры данных». ACM Computing Surveys . 23 (3): 345–405. DOI : 10.1145 / 116873.116880 . S2CID 4613674 .
^ Окабе, Atsuyuki; Сапоги, Барри; Сугихара, Кокичи; Чиу, Сунг Нок (2000). Пространственная мозаика - концепции и приложения диаграмм Вороного (2-е изд.). Джон Вили. ISBN 978-0-471-98635-5.
^ Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Упражнение 2.9: Издательство Кембриджского университета. п. 60.CS1 maint: location (link)
^ Тран, QT; Тайнар, Д .; Сафар, М. (2009). Транзакции в крупномасштабных системах, ориентированных на данные и знания . п. 357. ISBN. 9783642037214.
^ Reem 2009 .
^ Reem 2011 .
^ Вороной 1908a и Вороной 1908b .
^ а б де Берг, Марк ; ван Кревельд, Марк ; Овермарс, Марк ; Шварцкопф, Отфрид (2008). Вычислительная геометрия (Третье изд.). Springer-Verlag . ISBN 978-3-540-77974-2.7.4. Диаграммы Вороного для дальней точки. Включает описание алгоритма.
^ Skyum, Свен (18 февраля 1991). «Простой алгоритм вычисления наименьшего окружающего круга». Письма об обработке информации . 37 (3): 121–125. DOI : 10.1016 / 0020-0190 (91) 90030-L ., содержит простой алгоритм вычисления диаграммы Вороного самой дальней точки.
^ Бидль, Тереза ; Гримм, Карстен; Палиос, Леонид; Шевчук, Джонатан ; Вердоншот, Сандер (2016). «Реализация диаграмм Вороного по наиболее удаленным точкам». Труды 28-й Канадской конференции по вычислительной геометрии (CCCG 2016) .
^ Edelsbrunner, Герберт (2012) [1987]. «13.6 Диаграммы мощности». Алгоритмы комбинаторной геометрии . Монографии EATCS по теоретической информатике. 10 . Springer-Verlag. С. 327–328. ISBN 9783642615689..
^ Сунил Арья, Сунил; Маламатос, Теохарис; Маунт, Дэвид М. (2002). «Экономичные приближенные диаграммы Вороного». Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений . С. 721–730. DOI : 10.1145 / 509907.510011 . ISBN 1581134959. S2CID 1727373 .
^ Geraerts, Roland (2010), Планирование Короткие пути с использованием Зазор Явные Коридоры (PDF) , Международная конференция по робототехнике и автоматизации, IEEE, стр. 1997-2004 .
^ van Toll, Wouter G .; Повар IV, Атлас F .; ван Кревельд, Марк Дж .; Гераертс, Роланд (2018), Медиальная ось многослойной среды и ее применение в качестве навигационной сетки (PDF) , Транзакции ACM по пространственным алгоритмам и системам, стр. 2: 1–2: 34 .
^ Хельшер, Тонио; Кремкер, Сюзанна; Мара, Хуберт (2020), «Der Kopf Sabouroff в Берлине: Zwischen archäologischer Beobachtung und geometrischer Vermessung», Gedenkschrift für Georgios Despinis (на немецком языке), Афины, Греция: Музей Бенаки
^ Ячейки Вороного и геодезические расстояния - глава Sabouroff на YouTube . Анализ с использованием GigaMesh Software Framework, как описано Hölscher et al. ср. DOI: 10.11588 / heidok.00027985 .
^ Бок, Мартин; Тьяги, Амит Кумар; Крефт, Ян-Ульрих; Альт, Вольфганг (2009). "Обобщенная мозаика Вороного как модель двумерной динамики клеточной ткани". Вестник математической биологии . 72 (7): 1696–1731. arXiv : 0901.4469v1 . Bibcode : 2009arXiv0901.4469B . DOI : 10.1007 / s11538-009-9498-3 . PMID 20082148 . S2CID 16074264 .
^ Хуэй Ли (2012). Баскурт, Атилла М; Ситник, Роберт (ред.). «Пространственное моделирование микроархитектуры кости». Обработка трехмерных изображений (3Dip) и приложения II . 8290 : 82900С. Bibcode : 2012SPIE.8290E..0PL . DOI : 10.1117 / 12.907371 . S2CID 1505014 .
^ a b Санчес-Гутьеррес, Д .; Тозлуоглу, М .; Барри, JD; Pascual, A .; Mao, Y .; Эскудеро, Л. М. (4 января 2016 г.). «Фундаментальные физические ограничения клетки приводят к самоорганизации тканей» . Журнал EMBO . 35 (1): 77–88. DOI : 10.15252 / embj.201592374 . PMC 4718000 . PMID 26598531 .
^ Springel, Volker (2010). "E pur si muove: Космологические гидродинамические симуляции, инвариантные к Галилею, на движущейся сетке". МНРАС . 401 (2): 791–851. arXiv : 0901.4107 . Bibcode : 2010MNRAS.401..791S . DOI : 10.1111 / j.1365-2966.2009.15715.x . S2CID 119241866 .
^ Касим Мухаммад Firmansyah (2017-01-01). «Количественная теневая и протонная радиография для модуляции большой интенсивности». Physical Review E . 95 (2): 023306. arXiv : 1607.04179 . Bibcode : 2017PhRvE..95b3306K . DOI : 10.1103 / PhysRevE.95.023306 . PMID 28297858 . S2CID 13326345 .
↑ Стивен Джонсон (19 октября 2006 г.). Карта-призрак: история самой ужасающей эпидемии Лондона и того, как она изменила науку, города и современный мир . Издательская группа "Пингвин". п. 187. ISBN. 978-1-101-15853-1. Проверено 16 октября 2017 года .
^ Малхеран, Пенсильвания; Блэкман, Дж. А. (1996). «Зоны захвата и масштабирование при однородном росте тонких пленок». Physical Review B . 53 (15): 10261–7. Bibcode : 1996PhRvB..5310261M . DOI : 10.1103 / PhysRevB.53.10261 . PMID 9982595 .
^ Пимпинелли, Альберто; Тумбек, Левент; Винклер, Адольф (2014). "Масштабирование и экспоненциальные равенства в островной нуклеации: новые результаты и применение к органическим пленкам" . Журнал писем по физической химии . 5 (6): 995–8. DOI : 10.1021 / jz500282t . PMC 3962253 . PMID 24660052 .
^ Fanfoni, M .; Placidi, E .; Arciprete, F .; Orsini, E .; Patella, F .; Бальзаротти, А. (2007). «Внезапное зарождение против масштабной инвариантности квантовых точек InAs на GaAs». Physical Review B . 75 (24): 245312. Bibcode : 2007PhRvB..75x5312F . DOI : 10.1103 / PhysRevB.75.245312 . ISSN 1098-0121 .
^ Миямото, Сатору; Мутанаббир, Усама; Haller, Eugene E .; Ито, Кохей М. (2009). «Пространственная корреляция самоорганизованных изотопически чистых наноостровков Ge / Si (001)» . Physical Review B . 79 (165415): 165415. Bibcode : 2009PhRvB..79p5415M . DOI : 10.1103 / PhysRevB.79.165415 . ISSN 1098-0121 . S2CID 13719907 .
^ "ЗОЛОТОЕ ПОБЕРЕЖЬЕ КУЛЬТУРНЫЙ ПРИМЕР" . ARM архитектура.
^ Лопес, C .; Zhao, C.-L .; Магниол, S; Chiabaut, N; Леклерк, Л. (28 февраля 2019 г.). «Микроскопическое моделирование движения для стоянки грузовиков как средство управления зоной погрузки груза» . Устойчивость . 11 (5), 1276.
^ Singh, K .; Садеги, Ф .; Correns, M .; Бласс, Т. (декабрь 2019 г.). «Основанный на микроструктуре подход к моделированию влияния шероховатости поверхности на усталость при растяжении» . Международный журнал усталости . 129 : 105229. DOI : 10.1016 / j.ijfatigue.2019.105229 .
^ Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. стр. 987 . ISBN 978-1-57955-008-0.
^ Митчелл, Том М. (1997). Машинное обучение (международное издание). Макгроу-Хилл. п. 233 . ISBN 978-0-07-042807-2.
^ «Алгоритмы пользовательского интерфейса» .
^ "Школьные зоны" . Департамент образования и профессиональной подготовки правительства штата Виктория . Проверено 24 августа 2020 .

Ссылки [ править ]

Ауренхаммер, Франц ; Кляйн, Рольф; Ли, Дер-Цай (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". Журнал 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) . Журнал 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) . Журнал 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 .

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме диаграмм Вороного .

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

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

Программное обеспечение [ править ]

Диаграммы Вороного требуют вычислительного шага, прежде чем показывать результаты. Таким образом, эффективный инструмент будет обрабатывать вычисления в режиме реального времени, чтобы показать прямой результат пользователю. Существует множество коммерческих и бесплатных приложений. Особенно практичным типом инструментов являются веб-инструменты. Доступ к веб-инструментам и к ним проще. Кроме того, SVG, являющийся форматом, изначально поддерживаемым Интернетом, позволяет одновременно осуществлять эффективный (с ускорением графического процессора) рендеринг и является стандартным форматом, поддерживаемым несколькими инструментами CAD (например, 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.

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

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

[1] Берроу, Питер А .; Макдоннелл, Рэйчел; McDonnell, Rachael A .; Ллойд, Кристофер Д. (2015). «8.11 Ближайшие соседи: полигоны Тиссена (Дирихле / Ворони)» . Принципы географических информационных систем . Издательство Оксфордского университета. С. 160–. ISBN 978-0-19-874284-5.

[2] Лонгли, Пол А .; Гудчайлд, Майкл Ф .; Магуайр, Дэвид Дж .; Райнд, Дэвид В. (2005). «14.4.4.1 Полигоны Тиссена» . Географические информационные системы и наука . Вайли. стр. 333–. ISBN 978-0-470-87001-3.

[3] Сен, Зекай (2016). «2.8.1 Полигоны Делани, Варони и Тиссена» . Принципы пространственного моделирования в науках о Земле . Springer. С. 57–. ISBN 978-3-319-41758-5.

[4] Aurenhammer, Franz (1991). «Диаграммы Вороного - обзор фундаментальной геометрической структуры данных». ACM Computing Surveys . 23 (3): 345–405. DOI : 10.1145 / 116873.116880 . S2CID 4613674 .

[5] Окабе, Atsuyuki; Сапоги, Барри; Сугихара, Кокичи; Чиу, Сунг Нок (2000). Пространственная мозаика - концепции и приложения диаграмм Вороного (2-е изд.). Джон Вили. ISBN 978-0-471-98635-5.

[6] Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Упражнение 2.9: Издательство Кембриджского университета. п. 60.CS1 maint: location (link)

[Tran09-7] Тран, QT; Тайнар, Д .; Сафар, М. (2009). Транзакции в крупномасштабных системах, ориентированных на данные и знания . п. 357. ISBN. 9783642037214.

[Reem_alg-8] Reem 2009 .

[Reem_geo_stable-9] Reem 2011 .

[10] Вороной 1908a и Вороной 1908b .

[berg2008-11] а б де Берг, Марк ; ван Кревельд, Марк ; Овермарс, Марк ; Шварцкопф, Отфрид (2008). Вычислительная геометрия (Третье изд.). Springer-Verlag . ISBN 978-3-540-77974-2.7.4. Диаграммы Вороного для дальней точки. Включает описание алгоритма.

[12] Skyum, Свен (18 февраля 1991). «Простой алгоритм вычисления наименьшего окружающего круга». Письма об обработке информации . 37 (3): 121–125. DOI : 10.1016 / 0020-0190 (91) 90030-L ., содержит простой алгоритм вычисления диаграммы Вороного самой дальней точки.

[13] Бидль, Тереза ; Гримм, Карстен; Палиос, Леонид; Шевчук, Джонатан ; Вердоншот, Сандер (2016). «Реализация диаграмм Вороного по наиболее удаленным точкам». Труды 28-й Канадской конференции по вычислительной геометрии (CCCG 2016) .

[14] Edelsbrunner, Герберт (2012) [1987]. «13.6 Диаграммы мощности». Алгоритмы комбинаторной геометрии . Монографии EATCS по теоретической информатике. 10 . Springer-Verlag. С. 327–328. ISBN 9783642615689..

[15] Сунил Арья, Сунил; Маламатос, Теохарис; Маунт, Дэвид М. (2002). «Экономичные приближенные диаграммы Вороного». Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений . С. 721–730. DOI : 10.1145 / 509907.510011 . ISBN 1581134959. S2CID 1727373 .

[16] Geraerts, Roland (2010), Планирование Короткие пути с использованием Зазор Явные Коридоры (PDF) , Международная конференция по робототехнике и автоматизации, IEEE, стр. 1997-2004 .

[17] van Toll, Wouter G .; Повар IV, Атлас F .; ван Кревельд, Марк Дж .; Гераертс, Роланд (2018), Медиальная ось многослойной среды и ее применение в качестве навигационной сетки (PDF) , Транзакции ACM по пространственным алгоритмам и системам, стр. 2: 1–2: 34 .

[Hoelscher20a-18] Хельшер, Тонио; Кремкер, Сюзанна; Мара, Хуберт (2020), «Der Kopf Sabouroff в Берлине: Zwischen archäologischer Beobachtung und geometrischer Vermessung», Gedenkschrift für Georgios Despinis (на немецком языке), Афины, Греция: Музей Бенаки

[Hoelscher20b-19] Ячейки Вороного и геодезические расстояния - глава Sabouroff на YouTube . Анализ с использованием GigaMesh Software Framework, как описано Hölscher et al. ср. DOI: 10.11588 / heidok.00027985 .

[20] Бок, Мартин; Тьяги, Амит Кумар; Крефт, Ян-Ульрих; Альт, Вольфганг (2009). "Обобщенная мозаика Вороного как модель двумерной динамики клеточной ткани". Вестник математической биологии . 72 (7): 1696–1731. arXiv : 0901.4469v1 . Bibcode : 2009arXiv0901.4469B . DOI : 10.1007 / s11538-009-9498-3 . PMID 20082148 . S2CID 16074264 .

[21] Хуэй Ли (2012). Баскурт, Атилла М; Ситник, Роберт (ред.). «Пространственное моделирование микроархитектуры кости». Обработка трехмерных изображений (3Dip) и приложения II . 8290 : 82900С. Bibcode : 2012SPIE.8290E..0PL . DOI : 10.1117 / 12.907371 . S2CID 1505014 .

[Sanchez-Gutierrez_77–88-22] Санчес-Гутьеррес, Д .; Тозлуоглу, М .; Барри, JD; Pascual, A .; Mao, Y .; Эскудеро, Л. М. (4 января 2016 г.). «Фундаментальные физические ограничения клетки приводят к самоорганизации тканей» . Журнал EMBO . 35 (1): 77–88. DOI : 10.15252 / embj.201592374 . PMC 4718000 . PMID 26598531 .

[23] Springel, Volker (2010). "E pur si muove: Космологические гидродинамические симуляции, инвариантные к Галилею, на движущейся сетке". МНРАС . 401 (2): 791–851. arXiv : 0901.4107 . Bibcode : 2010MNRAS.401..791S . DOI : 10.1111 / j.1365-2966.2009.15715.x . S2CID 119241866 .

[24] Касим Мухаммад Firmansyah (2017-01-01). «Количественная теневая и протонная радиография для модуляции большой интенсивности». Physical Review E . 95 (2): 023306. arXiv : 1607.04179 . Bibcode : 2017PhRvE..95b3306K . DOI : 10.1103 / PhysRevE.95.023306 . PMID 28297858 . S2CID 13326345 .

[Johnson2006-25] Стивен Джонсон (19 октября 2006 г.). Карта-призрак: история самой ужасающей эпидемии Лондона и того, как она изменила науку, города и современный мир . Издательская группа "Пингвин". п. 187. ISBN. 978-1-101-15853-1. Проверено 16 октября 2017 года .

[MulheranBlackman1996-26] Малхеран, Пенсильвания; Блэкман, Дж. А. (1996). «Зоны захвата и масштабирование при однородном росте тонких пленок». Physical Review B . 53 (15): 10261–7. Bibcode : 1996PhRvB..5310261M . DOI : 10.1103 / PhysRevB.53.10261 . PMID 9982595 .

[PimpinelliTumbek2014-27] Пимпинелли, Альберто; Тумбек, Левент; Винклер, Адольф (2014). "Масштабирование и экспоненциальные равенства в островной нуклеации: новые результаты и применение к органическим пленкам" . Журнал писем по физической химии . 5 (6): 995–8. DOI : 10.1021 / jz500282t . PMC 3962253 . PMID 24660052 .

[FanfoniPlacidi2007-28] Fanfoni, M .; Placidi, E .; Arciprete, F .; Orsini, E .; Patella, F .; Бальзаротти, А. (2007). «Внезапное зарождение против масштабной инвариантности квантовых точек InAs на GaAs». Physical Review B . 75 (24): 245312. Bibcode : 2007PhRvB..75x5312F . DOI : 10.1103 / PhysRevB.75.245312 . ISSN 1098-0121 .

[MiyamotoMoutanabbir2009-29] Миямото, Сатору; Мутанаббир, Усама; Haller, Eugene E .; Ито, Кохей М. (2009). «Пространственная корреляция самоорганизованных изотопически чистых наноостровков Ge / Si (001)» . Physical Review B . 79 (165415): 165415. Bibcode : 2009PhRvB..79p5415M . DOI : 10.1103 / PhysRevB.79.165415 . ISSN 1098-0121 . S2CID 13719907 .

[30] "ЗОЛОТОЕ ПОБЕРЕЖЬЕ КУЛЬТУРНЫЙ ПРИМЕР" . ARM архитектура.

[31] Лопес, C .; Zhao, C.-L .; Магниол, S; Chiabaut, N; Леклерк, Л. (28 февраля 2019 г.). «Микроскопическое моделирование движения для стоянки грузовиков как средство управления зоной погрузки груза» . Устойчивость . 11 (5), 1276.

[32] Singh, K .; Садеги, Ф .; Correns, M .; Бласс, Т. (декабрь 2019 г.). «Основанный на микроструктуре подход к моделированию влияния шероховатости поверхности на усталость при растяжении» . Международный журнал усталости . 129 : 105229. DOI : 10.1016 / j.ijfatigue.2019.105229 .

[33] Вольфрам, Стивен (2002). Новый вид науки . Wolfram Media, Inc. стр. 987 . ISBN 978-1-57955-008-0.

[34] Митчелл, Том М. (1997). Машинное обучение (международное издание). Макгроу-Хилл. п. 233 . ISBN 978-0-07-042807-2.

[35] «Алгоритмы пользовательского интерфейса» .

[36] "Школьные зоны" . Департамент образования и профессиональной подготовки правительства штата Виктория . Проверено 24 августа 2020 .

[1]