私が解決したい問題は、指定された入力ポイントとして指定されたブルー ノード (ソース ノード) で指定されたマップをテッセレーションすることです。これができたら、各セル内にいくつのブラック ノード (デマンド ノード) があるかを確認したいと思います。そのセルに関連付けられた青色ノードに割り当てます。
フォーチュンのアルゴリズムを使用せずにこれを行う簡単な方法があるかどうかを知りたいのですが、Mahotas.segmentation.gvoronoi(image) sourceと呼ばれるこの関数に出会いました。しかし、これで問題が解決するかどうかはわかりません。
また、このセグメンテーションを行うより良い方法があれば教えてください (ボロノイ テッセレーション以外)。クラスタリング アルゴリズムが適切な選択であるかどうかはわかりません。私はプログラミング初心者です。
ボロノイ分割を使用する別の方法を次に示します。
ソース ノード上に kd ツリーを構築します。次に、デマンド ノードごとに、kd ツリーを使用して最も近いソース ノードを見つけ、その近くのソース ノードに関連付けられたカウンターをインクリメントします。
http://code.google.com/p/python-kdtree/にある kd ツリーの実装が役立つはずです。
私はちょうど同じものを探していて、これを見つけました：
https://stackoverflow.com/users/1062447/wye-bee（たとえば、kd-tree）による空間インデックスの回答が、問題の最も簡単な解決策だと思います。
さらに、フォーチュンのアルゴリズムに代わるより簡単な方法があるかどうかも尋ねました。その特定の質問については、次のように説明します。ボロノイ図の実装が最も簡単なアルゴリズムですか。
ダイアグラムには多くのポイントがありません。これは、デマンド ノードごとに、すべてのソース ノードを繰り返し処理し、最も近いノードを見つけることができることを示唆しています。
おそらくこれ：
def distance(a, b):
return sum((xa - xb) ** 2 for (xa, xb) in zip(a, b))
def clusters(sources, demands):
result = dict((source, []) for source in sources)
for demand in demands:
nearest = min(sources, key=lambda s: distance(s, demand))
result[nearest].append(demand)
return result
このコードは、他のどのノードよりもそのソース ノードに近いすべてのデマンド ノードのリストにソース ノードをマッピングする辞書を提供します。
これは特に効率的ではありませんが、非常に簡単です。
Run this code in Mathematica. It's spectacular! (Yes, I know it is not Python, but ...)
pts3 = RandomReal[1, {50, 3}];
ListDensityPlot[pts3,
InterpolationOrder -> 0, ColorFunction -> "SouthwestColors", Mesh -> All]
