一連のポイントの中から「近くの」隣人を見つける必要があります。
上の画像には10個のポイントがあります。赤い線はドロネー三角形分割からのエッジであり、黒い星はエッジの正中線を示し、青い線はボロノイテッセレーションです。ポイント1には、3つの「近い」ネイバー、つまり4、6、および7がありますが、2と3はありません。これらは、エッジ1〜7とほぼ一致していますが、はるかに離れています。
近くの隣人（または「良い」エッジ）を識別するための良い方法は何ですか？図を見ると、中点がボロノイ線との交点に当たるエッジを選択するか、ボロノイセルに接触しているエッジを「近く」と見なすのが良い解決策であると思われます（3〜5の分類）。どちらにでも行くことができます）。Matlabでいずれかのソリューションを実装する効率的な方法はありますか（Matlabに変換できる優れた一般的なアルゴリズムを入手できれば幸いです）？
DelaunayTriクラスedgesとそのnearestNeighborメソッドを使用して、中点がボロノイ線との交点にあるエッジを選択するという最初のアイデアを実装できます。xとy値のランダムなペアが10個ある例を次に示します。
x = rand(10,1); %# Random x data
y = rand(10,1); %# Random y data
dt = DelaunayTri(x,y); %# Compute the Delaunay triangulation
edgeIndex = edges(dt); %# Triangulation edge indices
midpts = [mean(x(edgeIndex),2) ... %# Triangulation edge midpoints
mean(y(edgeIndex),2)];
nearIndex = nearestNeighbor(dt,midpts); %# Find the vertex nearest the midpoints
keepIndex = (nearIndex == edgeIndex(:,1)) | ... %# Find the edges where the
(nearIndex == edgeIndex(:,2)); %# midpoint is not closer to
%# another vertex than it is
%# to one of its end vertices
edgeIndex = edgeIndex(keepIndex,:); %# The "good" edges
そして今edgeIndexはN行2列の行列であり、各行には「近くの」接続を定義する1つのエッジへのインデックスxと1つのエッジのインデックスが含まれています。y次のプロットは、ドロネー三角形分割（赤い線）、ボロノイ図（青い線）、三角形分割エッジの中点（黒いアスタリスク）、および残っている「良好な」エッジedgeIndex（太い赤い線）を示しています。
triplot(dt,'r'); %# Plot the Delaunay triangulation
hold on; %# Add to the plot
plot(x(edgeIndex).',y(edgeIndex).','r-','LineWidth',3); %# Plot the "good" edges
voronoi(dt,'b'); %# Plot the Voronoi diagram
plot(midpts(:,1),midpts(:,2),'k*'); %# Plot the triangulation edge midpoints
ボロノイ図は、一連のボロノイポリゴンまたはセルで構成されています。上の画像では、各セルは、他のどの頂点よりもその頂点に近い空間内のすべてのポイントを囲む、特定の三角形分割頂点の周囲の領域を表しています。この結果、他の頂点に近くない2つの頂点（画像の頂点6と8など）がある場合、それらの頂点を結ぶ線の中点は、Voronoiセル間の分離線になります。頂点。
ただし、2つの指定された頂点を結ぶ線に近い3番目の頂点がある場合、3番目の頂点のボロノイセルは2つの指定された頂点の間に伸び、それらを結ぶ線と交差し、その線を中点で囲みます。したがって、この3番目の頂点は、2つの頂点が互いに隣接しているよりも、指定された2つの頂点に「近い」隣接と見なすことができます。画像では、頂点7のボロノイセルが頂点1と2（および1と3）の間の領域に拡張されているため、頂点7は頂点2（または3）よりも頂点1に近いと見なされます。
場合によっては、このアルゴリズムは、ボロノイセルが接触していても、2つの頂点を「近い」隣接頂点と見なさない場合があります。画像の頂点3と5はこの例であり、頂点2は、頂点3または5が互いに隣接しているよりも、頂点3または5に近接していると見なされます。
共有セルエッジが（この例に基づく）適切な隣接基準であることに同意します。メッシュ指向のデータ構造（Gtsのものなど）を使用している場合、共有エッジを識別するのは簡単です。
一方、Matlabは、これをより「興味深い」ものにします。ボロノイセルがパッチとして保存されていると仮定すると、「Faces」パッチプロパティを取得してみてください（このリファレンスを参照）。これにより、接続された頂点を識別する隣接行列のようなものが返されます。それ（そして少しの魔法）から、共有された頂点を決定し、共有されたエッジを推測できるはずです。私の経験では、この種の「検索」問題はMatlabにはあまり適していません。可能であれば、メッシュ接続のクエリにより適したシステムに移行することをお勧めします。
三角測量やボロノイ図を作成するよりも簡単な別の可能性は、近傍行列を使用することです。
まず、すべてのポイントを2D正方行列に配置します。次に、完全または部分的な空間ソートを実行できるため、ポイントはマトリックス内で順序付けられます。
Yが小さいポイントはマトリックスの一番上の行に移動でき、同様に、Yが大きいポイントは一番下の行に移動します。X座標が小さいポイントでも同じことが起こり、左側の列に移動するはずです。そして対称的に、X値が大きいポイントは右側の列に移動します。
空間ソートを実行した後（シリアルアルゴリズムまたは並列アルゴリズムの両方でこれを実現する方法は多数あります）、ポイントPが実際に近傍行列に格納されている隣接セルにアクセスするだけで、特定のポイントPの最も近いポイントを検索できます。
このアイデアの詳細については、次の論文を参照してください（PDFコピーはオンラインで入手できます）：EmergentBehaviorに基づくGPUでの超大規模群集シミュレーション。
並べ替えの手順では、興味深い選択肢が得られます。ペーパーで説明されている奇偶転置ソートだけを使用できます。これは、実装が非常に簡単です（CUDAでも）。これを1回実行するだけで、部分的な並べ替えが可能になります。これは、行列がほぼ並べ替えられている場合にすでに役立ちます。つまり、ポイントの移動が遅い場合は、計算量を大幅に節約できます。
フルソートが必要な場合は、このような奇偶転置パスを数回実行できます（次のウィキペディアのページで説明されています）。