Комментарии 49
Контрпример: постройте диаграмму Воронова для квадрата
Например, когда точки — пиксели.
Даже если не изображения, сетка часто бывает дискретной. А когда результат работы алгоритма зависит от рандома — это ну очень странно.
А то, что я про случайные точки написал — это её доказательство, по сути.
Это не означает, что её можно применять только к случайно набросанным точкам, просто для точек на сетке она оказывается немного неверна (число вариантов расстановки конечно, из них есть не удовлетворяющие условию — те же точки в вершинах квадрата).
Можно наложить условие «никакие 4 точки не должны лежать на одной окружности». Тогда теорема будет справедлива. Но это условие избыточно.
Реально полезная информация — это выпуклость полученных кластеров.
Для случайных точек на плоскости можно использовать формулировку «вершины диаграммы имеют степень не более 3 с вероятностью 1».
Дискретная сетка с произвольными точками ни к одному из этих вариантов условия не подходит (там есть точки на одной окружности и используется не вся плоскость).
Вспомнил, как первый раз реализовал алгоритм Форчуна, тогда это было для меня достижением и улыбка не слезала с лица очень долго.
Однако в тексте отмечено, что он фактически является диаграммой, поскольку сходство очевидно, и наличие нескольких линий, делающих многоугольники рисунка невыпуклыми, этого факта не отменяют.
Ссылка на реализацию 3d на JS с помощью WebGL http://wwwmpa.mpa-garching.mpg.de/~dnelson/webgl/vormesh3.htm, в свое время пришлось долго разбираться, данная статья будет отличным пособием.
Теперь на диаграмме процессов у меня есть тактическая раскраска показывающая какая часть диаграммы исполнена (зелёная), какая активна (красная), а какая пассивна (без окраски) вполне удобно и на схеме эффектно смотрится.
Но не менее важно упомянуть и дискретный случай, когда вершины могут находиться только в узлах непрерывной сетки, например — пиксели изображений. В этом случае операция называется «Euclidean Distance Transform» (EDT).
При этом есть возможность построить алгоритм с меньшей сложностью — O(N) вместо O(N * log N) для общего случая. Кому интересно — вот статья. Алгоритмы там совсем несложные — до алгоритма Mejster я додумался сам. Также существуют методы приближённого вычисления EDT, ориентированные на GPU.
Примеры применений EDT — быстрое вычисление операций математической морфологии с круговым сруктурным элементом произвольного радиуса, скелетизация.
Есть (спорно) более простой метод построения диаграммы за O(N^2 log N). Все, почти как у вас, только полуплоскости пересекаются по-другому. Не надо пересекать выпуклые многоугольники, можно так и работать с полуплоскостями.
Сначала их надо отсортировать по углу наклона (при чем ориентировать полуплоскости так, чтобы центр локуса был слева от прямой). В этом случае сортируем против часовой стрелки. Потом добавляем плоскости по одной, отсекая от текущей границы ненужные отрезки. Очень удобно текущую границу представить в виде стека отрезков — первый не замкнут слева, остальные замкнутые, но последний не замкнут справа. Когда добавляем новую прямую, пересекаем ее с отрезком вершиной стека. Если пересечение левее левой границы отрезка, просто выбрасываем его и повторяем операцию. В конце мы получим этакую петлю образованную прямыми. Надо будет ее обрезать с двух концов — это тоже просто. Пересекаем 2 прямые, первую и последнюю в стеке. Если точка пересечения левее левого конца на последней, то выкидываем ее из стека. Иначе если точка пересечения правее правого конца на первой прямой, выкидываем ее. В противном случае замыкаем точной пересечения первую и последнюю прямые. Вот мы и получили весь локус.
Нужно только уметь пересекать прямые параметрически, и сортировать их по углу. Отрезки хранятся в виде прямой и допустимого отрезка параметров на ней. В самом конце надо выбрасывать элементы с начала стека, что по идее требует дека, но если реализовать стек массивом, то можно просто двигать указатель на начало и потом в конце уже сдвинуть все элементы в начало.
Жесть какая это ваше полярное преобразование! Есть ли у вас хорошие ссылки, где про это прочитать?
Обычная инверсия, это еще понятно, но тут точке сопоставляется прямая и наоборот. И главное, совсем-совсем непонятно, почему прямая через образы двух прямых соответствует образу точки пересечения. И почему выпуклая оболочка будет внутренней границей всех пересечений тоже непонятно в таком преобразовании.
Блин, вы абсолютно правы! Полярное преобразование — просто гениальная вещь! У вас нет ли примеров хороших задачек, где это преобразование еще можно применить?
Читайте первоисточники и учите термины на русском языке. Сама работа Вороного 2008г. не очень поможет, она на французском), но есть обзор работ Вороного, который сделал Борис Николаевич Делоне в книге «Петербургская школа теории чисел», 1947г. Еще есть работа Делоне, Сандаковой по теории стереоэдров. Там используется правильная терминология. Также очень советую разобраться с историей вопроса «подъема точек на параболоид» (lifting). А также историю вопроса «метода оборачивания подарка» (gift wrapping). Кто и сколько раз это переоткрывал. А придумал Вороной в 1908г.
А в целом статья хорошая.
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 степени свободы.
Смысл в добавлении степени свободы — избавиться от дорогостоящих операций (sin, cos, sqrt).
С работой этих алгоритмов в 2D все понятно и достаточно просто представить. Но когда пытаешься перейти в 3D начинается взрыв мозга.
Причем в большинстве материалов первыми идут строки, вроде: «будем рассматривать 2-мерное пространство, для 3-мерного все аналогично».
Было бы очень интересно прочесть про построение диаграммы в 3D, ND с визуализацией
Алгоритм такой:
1. Применяем обычный 2D алгоритм к каждой из плоскостей XY.
2. Далее для каждой из точек XY рассматриваем прямую, перпендикулярную XY.
3. Вращение ближайших точек, найденных на 1 шаге, не влияет на результат => вращаем так, чтобы они все оказались в одной плоскости.
4. Применяем 2D алгоритм.
И так для каждой последующей размерности.
Использовал диаграмму Вороного и теорию графов для вычисления Medial axis (центральной линии) 2D-объектов (для 3D объектов, заданных сеткой, тоже можно). По сути — это построение скелета. Кратчайший путь через диаграмму Вороного для 2D-случая как раз даёт центральную линию. Правда пришлось немного помудрить в случае самопересечений объекта.
Вы пишете, что дерево является сбалансированным: "у узла либо два сына, либо ноль". Но это лишь говорит о том, что дерево двоичное. Балансировка всё равно необходима.
Диаграмма Вороного и её применения