4

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

より具体的には、ボロノイセルについては、これに隣接するセルを知る必要があります。この時点では、実装をマッサージして自分に有利に働く可能性があるため、出力方法や保存方法については気にしません。

誰かがアルゴリズムを知っていますか、またはセル隣接の決定を達成できる実装されたアルゴリズムをもっとよく知っていますか？私が行う作業はPythonですが、コードを簡単に翻訳できるので、何でも素晴らしいでしょう。

ありがとう！

4

3 に答える 3

11

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

ここに画像の説明を入力

于 2013-05-28T12:51:27.560 に答える
3

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

ボロノイ図にアクセスできる場合は、セル間の共有エッジ セグメントを探すことができます。ボロノイ エッジ セグメントを共有する 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パッケージは広く使用されています。

お役に立てれば。

于 2012-03-11T09:42:26.227 に答える
1

線形計画法のアプローチを使用する可能なアルゴリズムがここにあります。

PuLPは、MPSまたはLPファイルを生成し、 GLPK、COIN、CPLEX、およびGUROBIを呼び出して、線形問題を解決できます。

PuLPはPythonで記述されたLPモデラーであり、Pythonでこの線形計画法をモデル化し、GLPKを使用して解くために使用できます。

于 2012-03-11T08:00:33.367 に答える