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

Диаграммы Вороного: разбиение пространства на основе близости

Представьте себе город, в котором есть несколько пожарных частей. Перед каждым жителем встает вопрос: «Если случится пожар, в какую пожарную часть обратиться?» Самый простой ответ: «В ту, что находится ближе всего к вам».

Таким образом, весь город можно разделить на отдельные зоны: для жителей одной зоны ближе всего находится пожарная часть А, для жителей другой — часть Б, а для жителей третьей — часть С. В конечном счете, каждая точка пространства оказывается «привязанной» к ближайшей к ней пожарной части.

Если нанести эти зоны на карту, получится характерный геометрический узор, который называется диаграммой Вороного.

Все начинается с нескольких точек

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

Допустим, у нас есть три точки: А, В и С. Для каждой точки на плоскости мы определяем, какая из этих трех точек находится к ней ближе всего. Например, все точки, расположенные в определенной области вокруг точки А, находятся ближе к А, чем к любой другой точке. Аналогичным образом, свои зоны имеют точки В и С. В результате вся плоскость оказывается разделенной на три части: зону точки А, зону точки В и зону точки С. Каждая из таких зон называется ячейкой Вороного или областью Вороного. Каждой порождающей точке соответствует одна область Вороного: 10 точек обычно образуют 10 областей, а 100 точек — 100 областей.

Итак, где же проходят границы?

Это важнейший аспект диаграммы Вороного.

Представьте, что у вас есть всего две точки — A и B. Возникает вопрос: в каком случае точка находится на одинаковом расстоянии от обеих этих точек? Ответ: когда она расположена ровно посередине между ними. Следовательно, прямая линия, проходящая точно между точками A и B, служит границей. Каждая точка на этой линии равноудалена от A и B, а пространство по обе стороны от линии относится либо к A, либо к B. С математической точки зрения, множество всех точек, равноудаленных от двух заданных точек, образует серединный перпендикуляр. Таким образом, границы на диаграмме Вороного проводятся не произвольно; они определяются очень простым математическим правилом: найти все точки, равноудаленные от двух заданных исходных точек.

А что происходит, если точек три? Если мы добавим третью точку, C, то A, B и C начнут «соперничать» за свои области. Для любой точки на плоскости возникает вопрос: «К какой из исходных точек я ближе всего?» В итоге вся плоскость разделяется на три отдельные области, а границы между ними представляют собой линии, состоящие из точек, равноудаленных от соответствующих исходных точек.

По мере увеличения количества точек узор, образуемый этими границами, становится всё более сложным. Независимо от того, начинаете ли вы с 3 точек или доводите их число до 10, 50 или даже 100, вы увидите, как вся плоскость быстро превращается в замысловатую сеть многоугольников. И всё же, при более внимательном рассмотрении становится ясно, что каждая область по-прежнему сосредоточена вокруг одной исходной точки — базовое правило остается неизменным.

Почему это так похоже на клетки?

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

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

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

Почему границы всегда выглядят так аккуратно? В этом и заключается прелесть диаграммы Вороного. Возьмем две точки, A и B; граница между ними проходит через все точки, равноудаленные от A и B, — по определению, такая граница является серединным перпендикуляром к отрезку AB. При добавлении новых точек эти серединные перпендикуляры пересекаются, образуя сеть многоугольников, ограниченных прямыми линиями. Таким образом, хотя диаграмма Вороного может казаться хаотичной, на самом деле она подчиняется строгой геометрической структуре.

Это не только пожарные части

Вернемся к нашему первому примеру — пожарным частям. Допустим, в городе есть несколько пожарных частей: A, B, C, D и так далее. Если мы обозначим каждую из них точкой и построим диаграмму Вороного, то каждая полученная область будет соответствовать зоне, за которую «отвечает» конкретная пожарная часть. Если житель находится в области, относящейся к части A, значит, именно она расположена к нему ближе всего; если в области части B — то ближе всего часть B. Таким образом, то, что выглядит как изящная геометрическая схема, на самом деле является прямым отражением вполне реальной жизненной задачи.

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

В основе диаграммы Вороного лежит одна ключевая концепция: близость (или «наименьшее расстояние»). Для любой точки на плоскости можно задаться вопросом: «Какая из заданных точек находится ко мне ближе всего?» Ответ на этот вопрос определяет, к какой области относится данное место. Если найти ответы для каждой возможной точки на плоскости, получится диаграмма Вороного.

Диаграмму Вороного можно представить как своего рода математический механизм. На вход подается набор точек, а для каждой позиции на экране система «спрашивает»: «К какой из этих точек ты ближе всего?» Если ответ — A, то эта позиция закрепляется за A; если B — за B; если C — за C, и так далее. В конечном итоге всё пространство оказывается автоматически разделенным на области.

Порядок может возникнуть из случайных точек

Если мы случайным образом распределим некоторое количество точек — расположив их совершенно произвольно, — а затем применим простое правило: «каждая область принадлежит ближайшей к ней точке», то возникнет высокоорганизованная геометрическая структура. Иными словами, случайные исходные данные могут привести к упорядоченному разбиению пространства.

Это не то же самое, что фрактал; диаграмма Вороного не является фракталом. В ней нет бесконечной рекурсии, бесконечного самоподобия или структур, которые повторяются при увеличении масштаба. Её главная суть — разбиение пространства.

Каждая точка выступает в роли «центра»

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

Что еще интереснее, изменение правил преображает сам мир. В стандартной диаграмме Вороного используется евклидово расстояние — привычное нам расстояние по прямой линии. Например, если одна точка находится от вас на расстоянии 3 метров, а другая — на расстоянии 5 метров, то первая точка, очевидно, ближе.

Однако в реальном мире всё зачастую сложнее. Возьмем, к примеру, город: больница, которая находится ближе всего по прямой линии, может оказаться не той, до которой быстрее всего добраться на автомобиле — ведь на путь влияют дороги, реки, горы, дорожное движение и многое другое. Таким образом, понятие «расстояния» не ограничивается евклидовым определением. Если изменить определение «расстояния», то изменится и соответствующая ему диаграмма Вороного. В этом и заключается прелесть математики: изменение всего одного правила может полностью преобразить целый мир.

Простой вопрос, создающий целую карту

Глядя на красивую диаграмму Вороного, не стоит видеть в ней лишь набор случайно сгенерированных разноцветных многоугольников. На самом деле перед вами — ответ на вопрос «Какая точка находится ближе всего?» для каждой точки в пространстве. Каждая область отвечает на вопрос: «К какой точке относится эта территория?». Границы отмечают места, где ближайшей становится уже другая точка. А каждая вершина представляет собой уникальную геометрическую взаимосвязь между несколькими областями.

Суть диаграммы Вороного можно выразить одной фразой: дайте мне набор точек, и я разделю всё пространство на части в зависимости от того, какая из этих точек находится ближе всего к любому заданному месту. Здесь нет ни сложной рекурсии, ни загадочных формул, ни искусственно созданных конструкций — только точки, расстояние и близость. И всё же, если применить эти простые правила ко всей плоскости, возникает сложный и прекрасный геометрический мир.

Исследуем мир математики через понятие «близости»

Диаграммы Вороного наглядно показывают, как расстояние формирует пространство.

Вы также можете изучить треугольник Серпинского: здесь обычный треугольник преобразуется путем многократного «вырезания» из него частей, что создает бесконечно рекурсивную структуру.

Или взгляните на снежинку Коха — пример того, как простая прямая линия может превратиться в бесконечно сложную снежинку благодаря постоянному изменению её границ.

Ещё один интересный объект — кривая Гильберта: благодаря бесконечной рекурсии она постепенно заполняет собой всё двумерное пространство.

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

Диаграммы Вороного устроены совсем иначе. В их основе нет бесконечной рекурсии; они отвечают лишь на один простой вопрос: «Что находится ближе всего к данной точке?» Этот единственный, предельно ясный вопрос позволяет превратить всё пространство в удивительную математическую карту.

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