Определение и сохранение соседства клеток Вороного

Question

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

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

Кто-нибудь знает об алгоритме или, еще лучше, знает о реализованном алгоритме, который может выполнять определение смежности ячеек? Работа, которую я буду выполнять, написана на python, но все было бы здорово, так как я легко могу перевести код.

Спасибо!

Answer 1

Хотя это старый вопрос, я искал тот же вопрос и подумал, что ответ может все же быть полезным для кого-то. Можно использовать Delaunay из scipy модуля.

from scipy.spatial import Delaunay
from collections import defaultdict
import itertools

points=[[0.0, 0.0], [0.0, 1.0], [0.2, 0.5], [0.3, 0.6], [0.4, 0.5], [0.6, 0.3], [0.6, 0.5], [1.0, 0.0], [1.0, 1.0]]
tri = Delaunay(points)
neiList=defaultdict(set)
for p in tri.vertices:
    for i,j in itertools.combinations(p,2):
        neiList[i].add(j)
        neiList[j].add(i)

for key in sorted(neiList.iterkeys()):
    print("%d:%s" % (key,','.join([str(i) for i in neiList[key]])))

0:1,2,5,7
1:0,8,2,3
2:0,1,3,4,5
3:8,1,2,4,6
4:2,3,5,6
5:0,2,4,6,7
6:8,3,4,5,7
7:8,0,5,6
8:1,3,6,7

# This is for visualization
from scipy.spatial import Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt
vor = Voronoi(points)
voronoi_plot_2d(vor)
for i,p in enumerate(x):
    plt.text(p[0], p[1], '#%d' % i, ha='center')
plt.show()

Answer 2

Вы можете сделать это несколькими различными способами.

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

for (all cells in voronoi diagram)
    for (all edges in current cell)
        if (matching edge found in hash table)
            // the current cell is adjacent to the cell that added
            // the matching edge segment to the hash table
        else
            // push current edge segment onto hash table and mark with 
            // current cell index
        endif
    endfor
endfor

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

Надеюсь, это поможет.

Answer 3

Возможный алгоритм доступен здесь который использует подход линейного программирования.

PuLP может генерировать файлы MPS или LP и вызывать GLPK , COIN , CPLEX и GUROBI для решения линейных задач.

PuLP - это модельер LP, написанный на Python, и его можно использовать для моделирования этой линейной программы на Python, а затем решить, используя GLPK .