보로 노이 세포 인접성 결정 및 보관

Question

나는 수천 개의 점 집합으로 작업 할 것입니다. Fortune 알고리즘의 기존 구현을 구현하거나 사용하여 포인트의 보로 노이 다이어그램을 생성 할 수 있지만, 애플리케이션에 각 보로 노이 셀에 대한 인접성을 알 필요가 있습니다.

더 구체적으로 말하면, 어떤 보로 노이 셀에 대해서 나는 이것에 인접한 셀을 알아야합니다. 이 시점에서 필자는 출력이나 저장 방법에 신경 쓰지 않을 것입니다.

누구나 알고리즘을 인식하고 있습니까? 아니면 셀 인접성 결정을 수행 할 수있는 구현 알고리즘을 더 잘 알고 있습니까? 내가 할 일은 파이썬이지만 코드를 쉽게 번역 할 수 있으면 좋을 것입니다.

감사합니다.

Answer 1

리니어 프로그래밍 방식을 사용하는 here 가능한 알고리즘을 사용할 수 있습니다.

펄프는 MPS 또는 LP 파일을 생성하고 GLPK, COIN, CPLEX 및 GUROBI 선형 문제를 해결하기 위해 호출 할 수 있습니다.

PuLP은 파이썬으로 작성된 LP 모델러로 파이썬에서이 선형 프로그램을 모델링 한 다음 GLPK을 사용하여 해결할 수 있습니다.

Answer 2

몇 가지 방법으로이 작업을 수행 할 수 있습니다.

Voronoi 다이어그램에 액세스 할 수있는 경우 셀간에 공유되는 가장자리 세그먼트를 찾을 수 있습니다. Voronoi 엣지 세그먼트를 공유하는 두 개의 셀을 발견하면 인접한 셀을 의미합니다. 전체 데이터 세트에 대한 인접성 정보를 구축하는 효율적인 방법은 Voronoi 셀 목록을 스캔하여 에지의 해시 테이블을 작성하는 것입니다.

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

이전 질문이지만, 나는 동일한 것을 찾고 있었고 그 대답이 여전히 누군가에게 도움이 될 수 있다고 생각했습니다. 하나는 scipy 모듈의 Delaunay을 사용할 수 있습니다.

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()