понедельник, 4 мая 2015 г.

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

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

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

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

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

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

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

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

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


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


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

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

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


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

картинка с Flickr

или вышить:

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

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



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

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

картинка с Flickr

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


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

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

16 комментариев:

  1. Как красиво...всегда любовалась подобными вещами, но и не догадывалась, что есть закономерность. Или все таки без закономерности? например трещины на земле.
    Лера не смейся на мои вопросы-рассуждения, я далеко от математики)))
    Чесночинки самые красивые, согласна с тобой!

    ОтветитьУдалить
    Ответы
    1. Аня, мое математическое прошлое мне, увы, совсем не помогло - кроме самых-самых начальных основ (про аптеку, к примеру) ничего не понимаю. Но восхищаюсь!

      Удалить
  2. Как всегда, спасибо за перевод с математического на человеческий! Вы не устаёте расширять наш кругозор. Спасибо, что делитесь с нами такими интересными открытиями!

    ОтветитьУдалить
  3. Лера, опять удивила! Интересно очень.

    ОтветитьУдалить
    Ответы
    1. Таня, а уж я как удивилась! Но теперь стала просто-таки фанатом этих диаграмм. Жаль, сама строить не умею - для этого, похоже, придется этот самый Grasshopper осваивать.

      Удалить
  4. Лерусик, а детские конфетки какие Фкусные! Леденцы на палочке, помнишь?

    ОтветитьУдалить
  5. Спасибо! Заразили. Вот бы еще их самой научиться строить!

    ОтветитьУдалить
    Ответы
    1. теоретически это несложно, а практически я пробовала - нет, нужна программа. И она есть, и не одна, но освоить их непросто. Вот простенький диалоговый примерчик: http://alexbeutel.com/webgl/voronoi.html просто тыкать мышкой в прямоугольник на экране

      Удалить
  6. О сколько нам открытий чудных!...
    Лера, очень интересный рассказ, спасибо!

    ОтветитьУдалить
  7. Лера, спасибо за утренний подарок. Эти диаграммы Вороного и в моем мозгу загогулинами живут как творческое томление! В 5.30 утра про твой чеснок размышляла, в 7 рассылку нашла про все это. Спасибочки, теперь томление ручкам покою не даст, пошла тряпочки выстраивать... покажу потом

    ОтветитьУдалить
    Ответы
    1. Наташа, 1) а что за рассылка? тоже хочу и 2) обязательно покажите результат, я уже говорила, я в эти диаграммы просто влюбилась!

      Удалить
    2. Лера, я на твой блог подписана, вот в курсе твоих новостей....

      Удалить
  8. Лерусь, спасибо! С большим интересом прочитала, поняла ли? Да, ничего, даже на примере аптек, но фотографии нравятся все и очень нравится название!))))

    ОтветитьУдалить
  9. Лера, теперь всплыло , что нам давали что-то подобное в теории множеств. Не даром после пояснений к сумке в голове что-то промелькнуло. Но фамилия вряд ли звучала, я бы ее запомнила. Конечно таких дивных картинок тоже не видела. Спасибо, очень интересно.

    ОтветитьУдалить
    Ответы
    1. а нам точно-точно не давали. Ни задачу о нахождении ближайшего соседа (а здесь я о ней уж не стала говорить, потому что ее использование грандиозно), ни наибольший пустой круг, ничего, никаких упоминаний.

      Удалить
  10. Ой, как же интересно! Получается, выражение: "Своя рубашка ближе к телу" тоже неким образом иллюстрирует диаграммы Воронова? То есть все "ниточки" своей рубашки-вакуоли ближе к "телу"-генератору. Я правильно поняла систему своим литературным умом? ;))))

    ОтветитьУдалить