В математике , A - схема Вороного является разбиение из плоскости в области , близкой к каждой из заданного множества объектов. В простейшем случае эти объекты представляют собой просто конечное число точек на плоскости (называемых семенами, узлами или генераторами). Для каждого семени есть соответствующая область , называемая ячейками Вороного , состоящая из всех точек плоскости, более близких к этому семени, чем к любой другой. Диаграмма Вороного множества точек двойственна своей триангуляции Делоне .
Диаграмма Вороной названа в честь Георгия Вороного , а также называет Вороной тесселяцией , разложение Вороного , разбиение Вороного , или тесселяцию Дирихля (после того, как Петр Густав Лежен Дирихлем ). Ячейки Вороного также известны как многоугольники Тиссена . [1] [2] [3] Диаграммы Вороного находят практическое и теоретическое применение во многих областях, в основном в науке и технике , а также в изобразительном искусстве . [4] [5]
Самый простой случай
В простейшем случае, показанном на первом рисунке, нам дан конечный набор точек { p 1 , ..., p n } на евклидовой плоскости . В этом случае каждый узел p k является просто точкой, а соответствующая ему ячейка Вороного R k состоит из каждой точки на евклидовой плоскости, расстояние до которой до p k меньше или равно ее расстоянию до любого другого p k . Каждая такая клетка получается из пересечения полупространств и, следовательно, является (выпуклым) многогранником . [6] В отрезках диаграммы Вороной все точек в плоскости, равноудаленные к двум ближайшим узлам. Вершины ( узлы ) Вороного - это точки, равноотстоящие от трех (или более) узлов.
Формальное определение
Позволять быть метрическое пространство с функцией расстояния. Позволять - набор индексов и пусть быть кортеж (упорядоченный набор) непустых подмножеств (Сайты) в пространстве. Ячейка Вороного, или Вороной район,, связанный с сайтом это множество всех точек в чье расстояние до не больше, чем их расстояние до других сайтов , где любой индекс отличается от . Другими словами, если обозначает расстояние между точкой и подмножество , тогда
Диаграмма Вороного - это просто набор ячеек. В принципе, некоторые из сайтов могут пересекаться и даже совпадать (приложение описано ниже для сайтов, представляющих магазины), но обычно предполагается, что они не пересекаются. Кроме того, в определении разрешено бесконечно много узлов (этот параметр имеет приложения в геометрии чисел и кристаллографии ), но, опять же, во многих случаях рассматривается только конечное число узлов.
В частном случае, когда пространство является конечномерным евклидовым пространством , каждый узел является точкой, имеется конечное количество точек, и все они разные, тогда ячейки Вороного являются выпуклыми многогранниками, и их можно представить комбинаторным способом, используя их вершины, стороны, двумерные грани и т. д. Иногда индуцированную комбинаторную структуру называют диаграммой Вороного. Однако в общем случае клетки Вороного не могут быть выпуклыми или даже связными.
В обычном евклидовом пространстве мы можем переписать формальное определение в обычных терминах. Каждый многоугольник Вороного связана с образующей точкой . Позволять- множество всех точек в евклидовом пространстве. Позволять быть точкой, которая порождает свою область Вороного , что порождает , а также что порождает , и так далее. Затем, как выражаются Tran и др , [7] «все места в многоугольнике Вороного ближе к точке генератора этого многоугольника , чем любая другая точка генератора в диаграмме Вороного в евклидовой плоскости».
Иллюстрация
В качестве простой иллюстрации рассмотрим группу магазинов в городе. Предположим, мы хотим оценить количество покупателей данного магазина. При прочих равных условиях (цена, продукты, качество обслуживания и т. Д.) Разумно предположить, что покупатели выбирают предпочитаемый магазин просто из соображений расстояния: они пойдут в ближайший к ним магазин. В этом случае ячейка Вороного данного магазина можно использовать для приблизительной оценки количества потенциальных клиентов, посещающих этот магазин (смоделированный по точке в нашем городе).
Для большинства городов расстояние между точками можно измерить, используя известное евклидово расстояние :
или расстояние Манхэттена :
- .
Соответствующие диаграммы Вороного выглядят по-разному для разных метрик расстояния.
Характеристики
- Двойственный граф для диаграммы Вороного (в случае евклидова пространства с точечными сайтов) соответствует триангуляции Делоне для того же набора точек.
- Ближе весь пар точек соответствует два соседним ячейкам в диаграмме Вороного.
- Предположим, что задана евклидова плоскость и задана группа различных точек. Тогда две точки на выпуклой оболочке смежны тогда и только тогда, когда их клетки Вороного имеют бесконечно длинную сторону.
- Если пространство является нормированным пространством и расстояние до каждого узла достигнуто (например, когда узел представляет собой компактное множество или замкнутый шар), то каждая ячейка Вороного может быть представлена как объединение линейных сегментов, исходящих из узлов. [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 1 , x 2 , ..., x n −1 }, на диаграмма , Вороного генерируется на множестве S - X .
Диаграмма Вороного самой дальней точки
Для набора из n точек диаграмма Вороного ( n - 1) -го порядка называется диаграммой Вороного самой дальней точки.
Для данного набора точек S = { p 1 , p 2 , ..., p n } диаграмма Вороного с самой дальней точкой делит плоскость на ячейки, в которых одна и та же точка P является самой дальней точкой. Точка Р имеет ячейку в самой дальней точке диаграммы Вороной тогда и только тогда , когда она является вершиной выпуклой оболочки из P . Пусть H = { h 1 , h 2 , ..., 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]
Диаграммы Вороного также связаны с другими геометрическими структурами, такими как медиальная ось (которая нашла применение в сегментации изображений, оптическом распознавании символов и других вычислительных приложениях), прямой скелет и диаграммы зон . Помимо точек, на таких диаграммах в качестве семян используются линии и многоугольники. Дополняя диаграмму линейными сегментами, которые соединяются с ближайшими точками на семенах, получается планарное подразделение окружающей среды. [16] Эта структура может использоваться в качестве навигационной сетки для поиска пути через большие пространства. Сетка навигации была обобщена для поддержки трехмерных многоуровневых сред, таких как аэропорт или многоэтажное здание. [17]
Приложения
Гуманитарные науки
- В классической археологии , особенно в истории искусства , анализируется симметрия голов статуй, чтобы определить тип статуи, которой могла принадлежать отрубленная голова. Примером этого, в котором использовались ячейки Ворного, была идентификация головы Сабурова , в которой использовалась полигональная сетка высокого разрешения . [18] [19]
Природные науки
- В биологии диаграммы Вороного используются для моделирования ряда различных биологических структур, включая клетки [20] и микроархитектуру костей. [21] Действительно, мозаика Вороного работает как геометрический инструмент для понимания физических ограничений, которые управляют организацией биологических тканей. [22]
- В гидрологии диаграммы Вороного используются для расчета количества осадков в районе на основе серии точечных измерений. В этом контексте они обычно называются многоугольниками Тиссена.
- В экологии диаграммы Вороного используются для изучения моделей роста лесов и лесных пологов, а также могут быть полезны при разработке моделей прогнозирования лесных пожаров.
- В вычислительной химии сайты связывания лигандов преобразуются в диаграммы Вороного для приложений машинного обучения (например, для классификации карманов связывания в белках). [23] В других приложениях клетки Вороного, определяемые положением ядер в молекуле, используются для вычисления атомных зарядов . Это делается с помощью метода плотности деформации Вороного .
- В астрофизике диаграммы Вороного используются для создания зон адаптивного сглаживания на изображениях, добавляя потоки сигналов к каждой из них. Основная цель этих процедур - поддерживать относительно постоянное отношение сигнал / шум на всех изображениях.
- В вычислительной гидродинамике мозаика Вороного набора точек может использоваться для определения вычислительных областей, используемых в методах конечных объемов , например, как в коде космологии подвижной сетки AREPO. [24]
- В вычислительной физике диаграммы Вороного используются для расчета профилей объекта с помощью Shadowgraph и протонной радиографии в физике высоких плотностей энергии . [25]
Здоровье
- В медицинской диагностике модели мышечной ткани, основанные на диаграммах Вороного, могут использоваться для выявления нервно-мышечных заболеваний. [22]
- В эпидемиологии диаграммы Вороного могут использоваться для корреляции источников инфекций в эпидемиях. Одно из первых применений диаграмм Вороного было применено Джоном Сноу для изучения вспышки холеры на Брод-стрит в 1854 году в Сохо, Англия. Он показал корреляцию между жилыми районами на карте центрального Лондона, жители которых использовали конкретный водяной насос, и районами с наибольшим количеством смертей из-за вспышки. [26]
Инженерное дело
- В физике полимеров диаграммы Вороного могут использоваться для представления свободных объемов полимеров.
- В материаловедении поликристаллические микроструктуры в металлических сплавах обычно представляются с помощью мозаики Вороного. При росте острова диаграмма Вороного используется для оценки скорости роста отдельных островов. [27] [28] [29] [30] В физике твердого тела , то ячейка Вигнера-Зейтец является Вороной тесселяцией твердого тела, а зона Бриллюэа является Вороной тесселяцией взаимной ( волновом ) пространство кристаллов , которые имеют симметрия пространственной группы.
- В авиации диаграммы Вороного накладываются на океанические картографические карты, чтобы определить ближайший аэродром для отклонения в полете (см. ETOPS ) по мере того, как самолет продвигается по плану полета.
- В архитектуре узоры Вороного были основой для победившей заявки на реконструкцию Центра искусств Голд-Кост . [31]
- В городском планировании диаграммы Вороного могут использоваться для оценки системы грузовых зон погрузки. [32]
- В горной промышленности полигоны Вороного используются для оценки запасов ценных материалов, полезных ископаемых или других ресурсов. В качестве точек в полигонах Вороного используются разведочные скважины.
- В метрологии поверхности мозаику Вороного можно использовать для моделирования шероховатости поверхности . [33]
- В робототехнике некоторые стратегии управления системами с несколькими роботами основаны на разбиении среды Вороного. [34] [35]
Геометрия
- Точка расположения структура данных может быть построена на вершине диаграммы Вороного, чтобы ответить на ближайших соседей запросов, где один хочет , чтобы найти объект , который находится ближе всего к данной точке запроса. Запросы ближайшего соседа имеют множество применений. Например, кто-то может захотеть найти ближайшую больницу или наиболее похожий объект в базе данных . Большое приложение - векторное квантование , обычно используемое при сжатии данных .
- В геометрии диаграммы Вороного могут использоваться, чтобы найти самый большой пустой круг среди набора точек и в окружающем многоугольнике; например, построить новый супермаркет как можно дальше от всех существующих, лежащих в определенном городе.
- Диаграммы Вороного вместе с диаграммами Вороного самых дальних точек используются для эффективных алгоритмов вычисления округлости набора точек. [11] Подход Вороного также используется для оценки округлости / округлости при оценке набора данных с координатно-измерительной машины .
Информатика
- В сети диаграммы Вороного могут использоваться для определения пропускной способности беспроводной сети .
- В компьютерной графике диаграммы Вороного используются для расчета трехмерных геометрических моделей разрушения / разрушения. Он также используется для процедурной генерации органических текстур или текстур, похожих на лаву.
- В автономной навигации роботов диаграммы Вороного используются для поиска четких маршрутов. Если точки являются препятствиями, то ребрами графа будут маршруты, наиболее удаленные от препятствий (и теоретически любых столкновений).
- В машинном обучении диаграммы Вороного используются для классификации 1-NN . [36]
- При разработке пользовательского интерфейса шаблоны Вороного можно использовать для вычисления наилучшего состояния наведения для данной точки. [37]
Гражданское воспитание и планирование
- В Мельбурне учащиеся государственных школ всегда имеют право посещать ближайшую к месту их проживания начальную или среднюю школу, если измерять расстояние по прямой. Таким образом, карта школьных зон представляет собой диаграмму Вороного. [38]
Пекарня
- Украинский кондитер Динара Касько использует математические принципы диаграммы Вороного для создания силиконовых форм, сделанных на 3D-принтере, для придания формы своим оригинальным тортам.
Алгоритмы
Известно несколько эффективных алгоритмов построения диаграмм Вороного либо напрямую (как сама диаграмма), либо косвенно, начиная с триангуляции Делоне и затем получая ее двойственную. Прямые алгоритмы включают в себя алгоритм фортуны , в O ( н лог ( п )) алгоритм для генерации диаграммы Вороного из множества точек на плоскости. Алгоритм Бойера – Ватсона, алгоритм от O ( n log ( n )) до O ( n 2 ) для генерации триангуляции Делоне в любом количестве измерений, может использоваться в косвенном алгоритме для диаграммы Вороного. Алгоритм Jump Flooding может генерировать приблизительные диаграммы Вороного за постоянное время и подходит для использования на стандартном графическом оборудовании. [39] [40]
В алгоритме Ллойда и его обобщении с помощью алгоритма Линде – Бузо – Грея (также известного как кластеризация 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.
- ^ Ауренхаммер, Франц (1991). «Диаграммы Вороного - обзор фундаментальной геометрической структуры данных». ACM Computing Surveys . 23 (3): 345–405. DOI : 10.1145 / 116873.116880 . S2CID 4613674 .
- ^ Окабе, Ацуюки; Сапоги, Барри; Сугихара, Кокичи; Чиу, Сунг Нок (2000). Пространственная мозаика - концепции и приложения диаграмм Вороного (2-е изд.). Джон Вили. ISBN 978-0-471-98635-5.
- ^ Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация . Упражнение 2.9: Издательство Кембриджского университета. п. 60.CS1 maint: location ( ссылка )
- ^ Тран, QT; Тайнар, Д .; Сафар, М. (2009). Транзакции в крупномасштабных системах, ориентированных на данные и знания . п. 357. ISBN. 9783642037214.
- ^ Reem 2009 .
- ^ Reem 2011 .
- ^ Вороной 1908a и Вороной 1908b .
- ^ а б де Берг, Марк ; ван Кревельд, Марк ; Овермарс, Марк ; Шварцкопф, Отфрид (2008). Вычислительная геометрия (Третье изд.). Springer-Verlag . ISBN 978-3-540-77974-2.7.4. Диаграммы Вороного для дальней точки. Включает описание алгоритма.
- ^ Скайум, Свен (18 февраля 1991 г.). «Простой алгоритм вычисления наименьшего окружающего круга». Письма об обработке информации . 37 (3): 121–125. DOI : 10.1016 / 0020-0190 (91) 90030-L ., содержит простой алгоритм вычисления диаграммы Вороного самой дальней точки.
- ^ Бидль, Тереза ; Гримм, Карстен; Палиос, Леонид; Шевчук, Джонатан ; Вердоншот, Сандер (2016). «Реализация диаграмм Вороного по наиболее удаленным точкам». Труды 28-й Канадской конференции по вычислительной геометрии (CCCG 2016) .
- ^ Эдельсбруннер, Герберт (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 .
- ^ Гераертс, Роланд (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 .
- ^ а б Sanchez-Gutierrez, D .; Тозлуоглу, М .; Барри, JD; Pascual, A .; Mao, Y .; Эскудеро, Л. М. (4 января 2016 г.). «Фундаментальные физические ограничения клетки приводят к самоорганизации тканей» . Журнал EMBO . 35 (1): 77–88. DOI : 10.15252 / embj.201592374 . PMC 4718000 . PMID 26598531 .
- ^ Файнштейн, Джозеф; Ши, Вентао; Ramanujam, J .; Брылински, Михал (2021), Балланте, Флавио (ред.), «Bionoi: представление лиганд-связывающих сайтов в белках на основе диаграммы Вороного для приложений машинного обучения» , Взаимодействие белок-лиганд и дизайн лекарств , Методы в молекулярной биологии, Нью - Йорк, Нью - Йорк: Springer США, 2266 . С. 299-312, DOI : 10.1007 / 978-1-0716-1209-5_17 , ISBN 978-1-0716-1209-5, PMID 33759134 , получено 2021-04-23
- ^ Спрингель, Волкер (2010). "E pur si muove: Космологические гидродинамические симуляции, инвариантные к Галилею, на движущейся сетке". MNRAS . 401 (2): 791–851. arXiv : 0901.4107 . Bibcode : 2010MNRAS.401..791S . DOI : 10.1111 / j.1365-2966.2009.15715.x . S2CID 119241866 .
- ^ Касим, Мухаммад Фирмансьях (01.01.2017). «Количественная теневая и протонная радиография для модуляции большой интенсивности». 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 .; Орсини, Э .; 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 Архитектура.
- ^ Lopez, 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 .
- ^ Cortes, J .; Мартинес, С .; Каратас, Т .; Булло, Ф. (апрель 2004 г.). «Контроль покрытия для мобильных сетей зондирования» . IEEE Transactions по робототехнике и автоматизации . 20 (2): 243–255. DOI : 10,1109 / TRA.2004.824698 . ISSN 2374-958X .
- ^ Теруэль, Энрике; Арагуес, Росарио; Лопес-Николас, Гонсало (апрель 2021 г.). «Практический метод равномерного покрытия динамической области роем» . Письма IEEE по робототехнике и автоматизации . 6 (2): 1359–1366. DOI : 10,1109 / LRA.2021.3057568 . ISSN 2377-3766 .
- ^ Митчелл, Том М. (1997). Машинное обучение (международное издание). Макгроу-Хилл. п. 233 . ISBN 978-0-07-042807-2.
- ^ «Алгоритмы пользовательского интерфейса» .
- ^ «Школьные зоны» . Департамент образования и обучения правительства Виктории . Проверено 24 августа 2020 .
- ^ https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf
- ^ https://www.shadertoy.com/view/4syGWK
Рекомендации
- Ауренхаммер, Франц ; Кляйн, Рольф; Ли, Дер-Цай (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). «Новые приложения непрерывных параметров теории квадратичных форм. Премьер воспоминания. С учетом собственных свойств квадратичных положительных форм» (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 voronoi, а вторая - это библиотека 3d voronoi.
- Трехмерные диаграммы Вороного и медиальная ось
- Воронцовское ++ C ++ библиотека для расчета 3d Вороного