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

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

  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)

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

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

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

14
задан pdusen 25 February 2012 в 03:45
поделиться