Как я могу получить словарь ячеек из данных диаграммы Voronoi?
Используя библиотеку генерации диаграммы voronoi/delaunay, найденную в этой программе, которая основана на оригинальной реализации Fortune его алгоритма, со случайным набором точек в качестве входных данных, я могу получить следующие выходные данные:
- Список ребер из триангуляции Delaunay, что означает, что для каждой входной точки я могу видеть, какие точки входа являются ее соседями, Они, похоже, не в каком-то определенном порядке.
- Список пар вершин из Диаграмма Вороного, который я могу использовать для рисования диаграммы Вороного по одной строке за раз. Опять же, видимо, в определенном порядке.
- Неименованный список пар точек, который, кажется, только тот же список, что и 2, но в другом порядке.
- Список вершин, образованных на диаграмме Вороного, также явно не в определенном порядке.
Ниже приведен пример данных из тестового запуска моей программы с использованием этой библиотеки:
Input points:
0 (426.484, 175.16)
1 (282.004, 231.388)
2 (487.891, 353.996)
3 (50.8574, 5.02996)
4 (602.252, 288.418)
Vertex Pairs:
0 (387.425, 288.533) (277.142, 5.15565)
1 (387.425, 288.533) (503.484, 248.682)
2 (277.142, 5.15565) (0, 288.161)
3 (387.425, 288.533) (272.213, 482)
4 (503.484, 248.682) (637.275, 482)
5 (503.484, 248.682) (642, 33.7153)
6 (277.142, 5.15565) (279.477, 0)
Voronoi lines?:
0 (279.477, 0) (277.142, 5.15565)
1 (642, 33.7153) (503.484, 248.682)
2 (503.484, 248.682) (637.275, 482)
3 (387.425, 288.533) (272.213, 482)
4 (277.142, 5.15565) (0, 288.161)
5 (387.425, 288.533) (503.484, 248.682)
6 (277.142, 5.15565) (387.425, 288.533)
Delaunay Edges:
0 (282.004, 231.388) (487.891, 353.996)
1 (602.252, 288.418) (487.891, 353.996)
2 (426.484, 175.16) (487.891, 353.996)
3 (426.484, 175.16) (602.252, 288.418)
4 (50.8574, 5.02996) (282.004, 231.388)
5 (426.484, 175.16) (282.004, 231.388)
6 (50.8574, 5.02996) (426.484, 175.16)
Vertices:
0 (277.142, 5.15565)
1 (503.484, 248.682)
2 (387.425, 288.533)
3 (0, 288.161)
4 (272.213, 482)
5 (637.275, 482)
6 (642, 33.7153)
7 (279.477, 0)
Хотя приведенные выше данные являются достаточными, если все, что мне нужно, это рисовать диаграммы Вороного и Делоне, недостаточно информации для фактической работы, которую я пытаюсь сделать с этими диаграммами. Мне нужен словарь многоугольников, образованных вершинами Вороного, проиндексированный входной точкой, вокруг которой образовался каждый многоугольник. Предпочтительно, для каждого многоугольника эти точки будут отсортированы по часовой стрелке. p >
С приведенной выше информацией я мог бы неявно назначать данные для каждого региона, при необходимости назначать данные по углам, указывать, в каких регионах обмениваются ребрами (с использованием границ Delaunay), и соответственно анализировать.
Итак, , как я могу использовать доступные мне данные, чтобы собрать словарь, в котором ключ является одной из входных точек, а данные, проиндексированные этим ключом, представляют собой список верунов Вороного, которые формировать окружающий многоугольник? Или, альтернативно, это информация где-то неявная в данных, которые мне даны?
Ответы
Ответ 1
Алгоритм удачи - O (n log n) - но ваш код будет O (n ^ 2), если вы попытаетесь восстановить способ грубой силы клеток, предложенный Alink.
Отправной точкой для моего ответа является то, что то, что вы используете для создания ячеек, не является библиотекой, а скорее просто класс, написанный для аккуратного переноса код, первоначально представленный самим Fortune, а не на самом деле зрелая библиотека. Таким образом, автор на самом деле не ожидал ваших нужд, и хотя запрошенная вами информация была рассчитана, она недоступна.
Внутренне ваши входные точки хранятся как экземпляры структуры "Site", и алгоритм продолжает создавать половинные края, каждый из которых поддерживает ссылочную "вершину", которая является указателем на Участок, который она охватывает. Шагая по полуребрам, вы, естественно, крутите вокруг закрытого Сайта - именно то, что вам нужно.
Чтобы получить доступ к этим данным, я предложил изменить или расширить класс VoronoiDiagramGenerator; Я бы сделал это, создав хеш-таблицу с указателями Site в качестве ключа и одного указателя HalfEdge в качестве значения. Затем измените метод generateVoroni, вставив ваш новый код сразу же после вызова voronoi:
For each HalfEdge in ELHash
Get table entry for current half edge Site
If site in table has null HalfEdge reference
set current HalfEdge reference
End If
End For each
... и есть ваш словарь. Этот односторонний край позволит вам "пройти" по периметру многоугольника, охватывающего связанный сайт, который, я думаю, является тем, о чем вы просили. Ваша следующая проблема будет заключаться в том, чтобы эффективно обнаружить, какой полигон охватывает новую точку данных, - но это еще один вопрос:-). Надеюсь, вы подумаете о том, чтобы поделиться своим завершенным классом - он должен быть значительно более полезным, чем базовый класс.
Изменить:
Вот отличная презентация, описывающая все сказанное выше на фотографиях: http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt:
- определение диаграммы Вороного
- дерево полуребер (см. рис. ниже)
- Алгоритм Fortunes в изображениях
И вот реализация С#, которая могла бы помочь вам найти словарь, как было предложено выше: http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C
![Slide 31]()
![Slide 32]()
![Slide 33]()
![Slide 34]()
Ответ 2
Ваш список ребер каким-то образом неполным, вам нужно добавить те, которые находятся на границе содержащего прямоугольника, предоставленного в библиотечный вызов (здесь здесь 642,482). Технически подразделение Вороного должно использовать некоторые бесконечные ребра, но все они конечны. Я предполагаю, что вы также хотите, чтобы эти "открытые" полигоны располагались вблизи этой границы, поскольку в вашем примере все они похожи.
Добавление этих пограничных границ кажется не сложным, а утомительным. Вероятно, что-то вроде, для каждой стороны главного прямоугольника, найти все вершины на нем (игнорируя углы), сортировать их (по x для горизонтального, по y для вертикали) и разделять эту сторону, используя эти значения. Это генерирует недостающие края, но не добавляет их непосредственно в ваш основной список, потому что они являются особыми, поскольку они являются единственными, которые не разделяют две ячейки.
Итак, для самого вопроса я бы пошел так:
В вашем основном списке ребер (предоставляемых библиотекой) каждое ребро разделяет две ячейки, и если мы найдем их, то мы можем просто назначить это ребро для каждой из этих ячеек. Поскольку ячейка эквивалентна входной точке, у нас будет необходимый словарь, за исключением списка ребер вместо вершин, но который легко преобразовать.
Теперь, чтобы получить эти 2 ячейки:
Вычислите среднюю точку ребра и оттуда найдите две ближайшие точки входа, просто перебирая список, сохраняя 2 наименьших расстояния. По свойствам структуры Вороного эти два являются теми, которые образуют две клетки. Обратите внимание, что эти два расстояния должны быть равны, но неточность поплавка, вероятно, будет иметь небольшую разницу.
Чтобы закончить, добавьте граничные границы, которые мы сгенерировали вдоль основного прямоугольника, но для них просто используйте первую ближайшую точку ввода, так как они только соседствуют с одной ячейкой.
Наконец, мы можем преобразовать каждый список ребер в список вершин (сбрасываем каждую точку конца в набор). Если вы хотите отсортировать их по часовой стрелке, обратите внимание, что это выпуклый многоугольник с входной точкой внутри. Таким образом, вы можете просто сгенерировать вектор, идущий от входной точки к каждой вершине, вычислить ее угол от одной оси (используйте std:: atan2 (x, y)) и используйте этот угол в качестве значения компаратора для сортировки (см. Std:: вид).
Ответ 3
Я использовал пакет Triangle для генерации триангуляции Dalaunay: http://www.cs.cmu.edu/~quake/triangle.html
Он работает в двух режимах: a) как утилита triangulate.exe и b) как библиотека C
Чтобы скомпилировать его как утилиту, вам просто нужно скомпилировать triangle.c и запустить:
triangulate -vZ input.poly
#v -voronoy, Z - starting from 0 index
чтобы получить диаграмму voronoi (см. руководство по . poly format)
Я сделал эксперимент с вашими входными данными в таком файле .poly:
# <# of vertices> <dimension (must be 2)> <# of attributes> <# of boundary markers (0 or 1)>
5 2 0 0
# Following lines: <vertex #> <x> <y> [attributes] [boundary marker]
0 426.484 175.16
1 282.004 231.388
2 487.891 353.996
3 50.8574 5.02996
4 602.252 288.418
#One line: <# of segments> <# of boundary markers (0 or 1)>
5 0
#Following lines: <segment #> <endpoint> <endpoint> [boundary marker]
0 0 1
1 1 2
2 2 3
3 3 4
4 4 0
Но он просто сообщает об ошибках входных данных.
- Работая с этим пакетом, я бы сказал, что он часто не работает с данными ïnput, сообщающими об ошибке. Он принимает только входные многоугольники (не случайные точки), и проблема здесь в том, что у вас есть самопересекающийся входной многоугольник.
- Он не отвечает на ваш вопрос, сообщая только о множестве точек, а не о словаре
Ответ 4
Вы можете просто использовать треугольник: http://www.cs.cmu.edu/~quake/triangle.html
Ответ 5
http://svn.osgeo.org/qgis/trunk/qgis/python/plugins/fTools/tools/voronoi.py
Эта реализация python от Carson Farmer дает вам топологическую информацию