Как я могу получить словарь ячеек из этих данных диаграммы Вороного?

Question

Используя библиотеку генерации диаграмм Вороного / Делоне, найденную в этой программе , которая основана на оригинальной реализации Fortune его алгоритма со случайным набором точек в качестве входных данных, I могу получить следующие выходные данные:

1. Список ребер из Триангуляция Делоне , означающий, что для каждой входной точки я могу видеть, какие входные точки являются ее соседями. Похоже, они не в каком-то определенном порядке.
2. Список пар вершин из Диаграммы Вороного , которые я могу использовать для рисования диаграммы Вороного по одной линии за раз. Опять же, по-видимому, в определенном порядке.
3. неназванный список пар точек , который, кажется, представляет собой тот же список, что и 2, но в другом порядке.
4. Список вершин, сформированных на диаграмме Вороного , также, по-видимому, в произвольном порядке.

Вот пример данных из тестового прогона моей программы с использованием этой библиотеки:

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)

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

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

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

Answer 1

Алгоритм Фортуны O (n log n), но ваш код будет O (n ^ 2), если вы попытаетесь реконструировать клетки методом "грубой силы", как предложено Alink.

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

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

Чтобы получить доступ к этим данным, я предложил изменить или расширить класс VoronoiDiagramGenerator;Я бы сделал это, создав хеш-таблицу с указателями сайта в качестве ключа и одним указателем HalfEdge в качестве значения.Затем измените метод generateVoroni, вставив новый код сразу после вызова voronoi:

For each HalfEdge in ELHash
         Get table entry for current half edge's 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:

• определение диаграммы Вороного
• дерево полуголов (см. Фото ниже)
• Алгоритм удачи в картинках

А вот иРеализация C #, которая может помочь вам получить словарь, как предложено выше: http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C

Answer 2

Ваш список ребер как-то неполон, вам нужно добавить те, что на границе содержащего прямоугольника, предоставленного для вызова библиотеки (здесь, кажется, 642 482).Технически подразделение Вороного должно использовать некоторые бесконечные ребра, но все они конечны.Я предполагаю, что вы также хотите, чтобы эти «открытые» многоугольники были рядом с этой границей, поскольку в вашем примере они все такие.

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

Итак, для самого вопроса я бы сказал так:this: в вашем основном списке ребер (предоставленных библиотекой) каждое ребро разделяет две ячейки, и если мы найдем, какие из них, мы можем просто назначить это ребро каждой из этих ячеек.Поскольку ячейка эквивалентна входной точке, нам понадобится словарь, за исключением списка ребер вместо вершин, но его легко конвертировать.

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

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

Наконец, мы можем преобразовать каждый список ребер в список вершин (сбросить каждую конечную точку в набор).Если вы хотите отсортировать их по часовой стрелке, обратите внимание, что это выпуклый многоугольник с точкой ввода внутри.Таким образом, вы можете просто сгенерировать вектор, идущий от входной точки к каждой вершине, вычислить его угол от одной оси (используйте std :: atan2 (x, y)) и использовать этот угол в качестве значения компаратора для их сортировки (см. Std ::вид).

Answer 3

Я использовал пакет Triangle для генерации триангуляции Далаунея: http://www.cs.cmu.edu/~quake/triangle.html

Работает в 2 режимах: а) как утилита triangulate.exe и б) как библиотека Си Чтобы скомпилировать его как утилиту, вам просто нужно скомпилировать triangle.c и запустить:

   triangulate -vZ input.poly 
   #v -voronoy, Z - starting from 0 index

чтобы получить диаграмму вороного (см. Руководство о .poly формате ) Я провел эксперимент с вашими входными данными в таком файле .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

Но он просто сообщает об ошибке ввода данных.

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

Answer 4

http://svn.osgeo.org/qgis/trunk/qgis/python/plugins/fTools/tools/voronoi.py

Эта реализация Python от Carson Farmer дает вам топологическую информацию

Answer 5

Вы можете просто использовать треугольник: http://www.cs.cmu.edu/~quake/triangle.html