Диаграмма Вороного высшего порядка на различных сетках, на плоскости и в пространстве

Актуальность

Диаграмма Вороного имеет множество применений, одно из них – построение расчётных сеток для численного решения задач. Сетки на основе диаграммы Вороного имеют некоторые преимущества: их ячейки представляют собой выпуклые многоугольники, а использование узлов – генераторов диаграммы Вороного в качестве расчётных узлов делает такую сетку в точности ортогональной. Одно из первых применений диаграммы Вороного было сделано доктором Джоном Сноу – известным лондонским врачом. Холера, получившая широкое распространение в XIX веке, унесла жизни десятков миллионов человек. До того, как бактерия холеры была изолирована, подозревались перенаселённость, плохое питание, плохие санитарные условия и ядовитые миазмы, исходящие от гниющего органического вещества. Сноу считал, что причиной холеры является заражённая питьевая вода.

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

Цель

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

Оснащение и оборудование, использованное при создании работы

• Персональный компьютер
• Язык программирования Python

Описание

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

После чего была написана программа с помощью языка программирования Python, в которую вводились параметры диаграммы.

Результаты работы/выводы

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

Перспективы использования результатов работы

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