Диаграммы Вороного: немного теории

Это информационно-просветительский пост
к творчески-оригинальному посту о Сумке Вороного

Рассматривая в интернете очередные красивые математические картинки, наткнулась в их описании на странное слово Voronoi - странное для англоязычного автора и очень странное для русскоязычной меня: вроде слово совсем русское, почему не знаю? Набрала voronoi в поисковике и попала в дивный новый мир!

иллюстрация пользователя eskimoblood  с flickr

Voronoi diagram - диаграммы Вороного - названы так по имени украинско-русского математика Г.Ф. Вороного (1868-1908). Статья о диаграммах в русской Википедии состоит из невразумительных формул, никаких популярных объяснений, никаких иллюстраций, ничего. Нет пророка в своем отечестве. При таком отношении неудивительно, что я, выпускница мехмата, ничего не слышала о работах моего соотечественника и коллеги.

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

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

Теперь - немножко картинок для полета творческой мысли.

Самые "засвеченные" природные объекты, являющиеся, по сути, диаграммами Вороного - крыло стрекозы, пятна жирафа, растрескавшаяся почва:

Лично мой любимый объект - головки чеснока в разрезе:

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

Во-первых, они просто красивые!

картинка с форума Grasshopper3D

 

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

картинка с Flickr

или вышить:

картинка с flickr

(или сшить квилт! Но это еще впереди. Не нашла ни одного квилта с диаграммами Вороного. непорядок)

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

... а также модифицировать фото разными интересными способами:

картинка с EvilMadScientist

А если у вас еще и 3D-принтер есть, тогда самые смелые фантазии на тему диаграмм Вороного можно тут же напечатать и любоваться:

картинка с Flickr

... или использовать:

... или даже носить:

Все картинки в посте взяты с Пинтереста из моего альбома о диаграммах Вороного, если интересно - заглядывайте.