Voronoiセル隣接関係の決定と保存

Question

私は数千点のセットを扱います。 Fortuneアルゴリズムの実装を実装したり使用したりして、ポイントのボロノイ図を作成することができますが、私のアプリケーションでは、各ボロノイセルに関する隣接関係を知る必要があります。

より具体的には、任意のVoronoiセルについて、これに隣接するセルを知る必要があります。現時点では、出力や保存の方法には関心がありません。私の好みに合わせて実装をマッサージすることができます。

アルゴリズムを認識している人はいますか、セルの隣接判定を行うことができる実装済みアルゴリズムを知っている方がいますか？私がやる作業はPythonですが、コードを簡単に翻訳できるのですばらしいことがあります。

ありがとうございます！

Answer 1

here 可能なアルゴリズムは、リニアプログラミングアプローチを使用しています。

パルプはMPSやLPファイルを生成し、線形問題を解決するためにGLPK、COIN、CPLEX、およびGUROBIを呼び出すことができます。

PuLPはPythonで書かれたLPモデラーで、この線形プログラムをPythonでモデル化してからGLPKを使って解くことができます。

Answer 2

いくつかの方法でこれを行うことができます。

Voronoiダイアグラムにアクセスするだけであれば、セル間で共有されるエッジセグメントを探すことができます。ボロノイのエッジセグメントを共有する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

これは古い質問ですが、私は同じことを探していましたが、回答がまだ誰かにとって役立つかもしれないと考えました。 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()