Определение и сохранение смещения ячеек Вороного

Question

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

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

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

Спасибо!

Answer 1

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

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

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

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 

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

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

Answer 3

Хотя это старый вопрос, я искал его и думал, что ответ может быть полезен для кого-то. Можно использовать 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()