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

Question

Использование Вороного/Делоне библиотеки поколения схема нашла in this program, которая основана на оригинальной реализации Фортуне из his algorithm, со случайным набором точек в качестве входных данных, я могу получить следующие выходные данные:

1. Список ребер из Delaunay Triangulation, что означает, что для каждой входной точки я могу видеть, какие точки входа являются ее соседями. Они, похоже, не в каком-то определенном порядке.
2. Список вершинных пар из Voronoi Diagram, который я могу использовать для рисования диаграммы Вороного по одной линии за раз. Опять же, по-видимому, в каком-то определенном порядке.
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) 

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

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

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

Answer 1

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

Отправной точкой для моего ответа является то, что то, что вы используете для создания ячеек, не является библиотекой, а скорее всего a class written to neatly wrap up the code originally presented by Fortune himself, а не фактически зрелой библиотекой. Таким образом, автор на самом деле не ожидал ваших нужд, и хотя запрошенная вами информация была рассчитана, она недоступна.

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

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

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 

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

Edit: Вот замечательная презентация descibing все сказанное выше в картинках: http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt:

• определение Вороной Диаграмма
• дерева полуребер (см рис.ниже)
• Fortunes алгоритм в картинках

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

Answer 2

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

к получить диаграммы Вороного (Обратитесь к инструкции о .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, сообщающими об ошибке. Он принимает только входные многоугольники (не случайные точки), и проблема здесь в том, что у вас есть самопересекающийся входной многоугольник.
• Он не отвечает на вопрос, отчетность только множество точек, не словарь

Answer 5

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

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