Открыть список
Как стать автором
Обновить

Комментарии 49

> Есть теорема, в которой говорится, что вершина диаграммы Вороного всегда лежит на пересечении ровно трёх рёбер диаграммы

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

Можно наложить условие «никакие 4 точки не должны лежать на одной окружности». Тогда теорема будет справедлива. Но это условие избыточно.

Реально полезная информация — это выпуклость полученных кластеров.
Математическая теорема не бывает «немного неверна». У нее есть вполне конкретное условие — если никакие 4 точки не лежат на одной окружности.

Для случайных точек на плоскости можно использовать формулировку «вершины диаграммы имеют степень не более 3 с вероятностью 1».

Дискретная сетка с произвольными точками ни к одному из этих вариантов условия не подходит (там есть точки на одной окружности и используется не вся плоскость).
Еще более контрпример — постройте диаграмму для произвольно наброшенных точек на окружности.
Спасибо за публикацию. С удовольствием прочитал. Еще частое применение — биоинформатика. Анализ распределения клеток и структур на фотографии, определение соседей и регионов.
Добавлю, что алгоритм применяется в флюоресцентной микроскопии (фотографии клеток) для определения границ клеточной мембраны. За центры берут клеточные ядра. Применяются диаграммы Вороного, правда, не потому что очень хорошо работают, а потому что это — простой алгоритм. Но на самом деле клеточные мембраны не ведут себя в соответствии с алгоритмом Вороного и в некоторых случаях различия столь значительны, что приходится вручную указывать границы клеток.
Спасибо за статью.

Вспомнил, как первый раз реализовал алгоритм Форчуна, тогда это было для меня достижением и улыбка не слезала с лица очень долго.
Аналогично, для определения прискваженных участков сочинял алгоритм раздувающихся кругов.
Был самодоволен.
О том, что это диаграмма Вороного узнал значительно позже.
Невооруженным глазом нашел на теле жирафа невыпуклое пятно. Не надо приплетать, пожалуйста.
Вы правы, у жирафов рисунок не всегда в точности является диаграммой, тем более, что у всех жирафов он разный.
Однако в тексте отмечено, что он фактически является диаграммой, поскольку сходство очевидно, и наличие нескольких линий, делающих многоугольники рисунка невыпуклыми, этого факта не отменяют.
Забавно, что Вы опровергаете наблюдаемый факт словом «фактически».
Пятна на коже жирафа и других животных более корректно моделируются клеточными автоматами.
Если присмотреться к фото, то видно что ранее такие пятна были разбиты на выпуклые, но границы между ними стали очень тонкие и теперь почти не видны. Похоже пигментация шкуры начинается с неких случайных зёрен которые растут пока не встретятся на границе.
Автор, отличная статья, большое спасибо!
Ссылка на реализацию 3d на JS с помощью WebGL http://wwwmpa.mpa-garching.mpg.de/~dnelson/webgl/vormesh3.htm, в свое время пришлось долго разбираться, данная статья будет отличным пособием.
У меня в приложении возникла похожая задача: для диаграммы с прямоугольными объектами в разном состоянии нужно найти разбиение на области примыкающие к прямоугольнику. То есть как диаграмма Вороного, но с прямоугольниками вместо точек. Точное решение я заменил упрощённым алгоритмом, получилось удачно, с артефактами только в особых на критичных случаях, но быстро, так что можно разбиение перестраивать по мере редактирования схемы.

Теперь на диаграмме процессов у меня есть тактическая раскраска показывающая какая часть диаграммы исполнена (зелёная), какая активна (красная), а какая пассивна (без окраски) вполне удобно и на схеме эффектно смотрится.
image
Если, вдруг, кому надо, могу дать рабочий проект WInForms
Сразу видно, что статью писал математик — рассматриваются только непрерывные случаи.

Но не менее важно упомянуть и дискретный случай, когда вершины могут находиться только в узлах непрерывной сетки, например — пиксели изображений. В этом случае операция называется «Euclidean Distance Transform» (EDT).

При этом есть возможность построить алгоритм с меньшей сложностью — O(N) вместо O(N * log N) для общего случая. Кому интересно — вот статья. Алгоритмы там совсем несложные — до алгоритма Mejster я додумался сам. Также существуют методы приближённого вычисления EDT, ориентированные на GPU.

Примеры применений EDT — быстрое вычисление операций математической морфологии с круговым сруктурным элементом произвольного радиуса, скелетизация.
FYI, для ознакомления http://www.cgal.org/, конкретно по диаграммам Вороного http://doc.cgal.org/latest/Manual/packages.html#PartVoronoiDiagrams

Есть (спорно) более простой метод построения диаграммы за O(N^2 log N). Все, почти как у вас, только полуплоскости пересекаются по-другому. Не надо пересекать выпуклые многоугольники, можно так и работать с полуплоскостями.


Сначала их надо отсортировать по углу наклона (при чем ориентировать полуплоскости так, чтобы центр локуса был слева от прямой). В этом случае сортируем против часовой стрелки. Потом добавляем плоскости по одной, отсекая от текущей границы ненужные отрезки. Очень удобно текущую границу представить в виде стека отрезков — первый не замкнут слева, остальные замкнутые, но последний не замкнут справа. Когда добавляем новую прямую, пересекаем ее с отрезком вершиной стека. Если пересечение левее левой границы отрезка, просто выбрасываем его и повторяем операцию. В конце мы получим этакую петлю образованную прямыми. Надо будет ее обрезать с двух концов — это тоже просто. Пересекаем 2 прямые, первую и последнюю в стеке. Если точка пересечения левее левого конца на последней, то выкидываем ее из стека. Иначе если точка пересечения правее правого конца на первой прямой, выкидываем ее. В противном случае замыкаем точной пересечения первую и последнюю прямые. Вот мы и получили весь локус.


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

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

Жесть какая это ваше полярное преобразование! Есть ли у вас хорошие ссылки, где про это прочитать?


Обычная инверсия, это еще понятно, но тут точке сопоставляется прямая и наоборот. И главное, совсем-совсем непонятно, почему прямая через образы двух прямых соответствует образу точки пересечения. И почему выпуклая оболочка будет внутренней границей всех пересечений тоже непонятно в таком преобразовании.

Блин, вы абсолютно правы! Полярное преобразование — просто гениальная вещь! У вас нет ли примеров хороших задачек, где это преобразование еще можно применить?

Локус, сайт… Потому что пудинг — очень вкусный блюдинг…
Читайте первоисточники и учите термины на русском языке. Сама работа Вороного 2008г. не очень поможет, она на французском), но есть обзор работ Вороного, который сделал Борис Николаевич Делоне в книге «Петербургская школа теории чисел», 1947г. Еще есть работа Делоне, Сандаковой по теории стереоэдров. Там используется правильная терминология. Также очень советую разобраться с историей вопроса «подъема точек на параболоид» (lifting). А также историю вопроса «метода оборачивания подарка» (gift wrapping). Кто и сколько раз это переоткрывал. А придумал Вороной в 1908г.

А в целом статья хорошая.
Меня удивило, что в библиотеке SplashGeom 2D-линия задается всего тремя числами. Я всегда считал, что необходимо четыре. Может кто-нибудь пояснить, за счет чего достинута такая «экономия».
Четыре числа нужно для записи отрезка в 2D. А вот прямая параметризуется всего двумя числами (a, d):

x cos a + y sin a = d

Но так как работать с синусами и косинусами неудобно, то представляют в виде:

A x + B y = C

и иногда нормализуют (A^2 + B^2 = 1).
Спасибо. Исчерпывающий ответ.

Просто уравнение прямой A*x+B*y+C=0. Но тут есть одна степень свободы, на самом деле достаточно 2х чисел (y=kx+b, или cos(a)*x+sin(a)*y+c=0). 4 числа нужно, если задавать прямую 2-мя точками, но при этом тут 2 степени свободы.

Вариант y = kx + b обычно не используют из-за невозможности представления вертикальных прямых.
Смысл в добавлении степени свободы — избавиться от дорогостоящих операций (sin, cos, sqrt).
И тут я замер… вспоминая во скольких программах у меня используется такое уравнение прямой.
можно использовать y=tg(a)*x+b
В свое время (года 2-3 назад) тоже занимался построением этой диаграммы, а потом и триангуляцией по этой диаграмме.
С работой этих алгоритмов в 2D все понятно и достаточно просто представить. Но когда пытаешься перейти в 3D начинается взрыв мозга.
Причем в большинстве материалов первыми идут строки, вроде: «будем рассматривать 2-мерное пространство, для 3-мерного все аналогично».
Было бы очень интересно прочесть про построение диаграммы в 3D, ND с визуализацией
Согласен, в 3D всё будет уже не так интуитивно понятно и просто. В будущем, возможно, я напишу статью и на эту тему (однако сначала реализация алгоритма Форчуна).
При переходе в 3D используется сведение задачи к 2D с помощью теоремы Пифагора.

Алгоритм такой:
1. Применяем обычный 2D алгоритм к каждой из плоскостей XY.
2. Далее для каждой из точек XY рассматриваем прямую, перпендикулярную XY.
3. Вращение ближайших точек, найденных на 1 шаге, не влияет на результат => вращаем так, чтобы они все оказались в одной плоскости.
4. Применяем 2D алгоритм.
И так для каждой последующей размерности.

Использовал диаграмму Вороного и теорию графов для вычисления Medial axis (центральной линии) 2D-объектов (для 3D объектов, заданных сеткой, тоже можно). По сути — это построение скелета. Кратчайший путь через диаграмму Вороного для 2D-случая как раз даёт центральную линию. Правда пришлось немного помудрить в случае самопересечений объекта.


Картинки

Вы пишете, что дерево является сбалансированным: "у узла либо два сына, либо ноль". Но это лишь говорит о том, что дерево двоичное. Балансировка всё равно необходима.

Локус — по-русски геометрическое место точек (гмт) ;-)
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.