寻找邻居

Question

我需要在一组点中找到"附近"的邻居.

上图中有10个点.红线是Delaunay三角剖分的边缘,黑色星标记边缘的中线,蓝线是Voronoi镶嵌.点1具有三个"近"邻居,即4,6和7,但不是2和3,它们几乎与边缘1-7一致,但距离更远.

识别近邻(或"好"边缘)的好方法是什么？看看这个图,在我看来,要么选择中点落在与Voronoi线交叉点的边缘,要么考虑作为"近"邻居那些触摸Voronoi单元的边缘可能是一个很好的解决方案(3-5的分类)可以去任何一种方式).有没有一种有效的方法来实现Matlab中的任何一个解决方案(我很乐意得到一个好的通用算法,然后我可以转换为Matlab,顺便说一下)？

Answer 1

您可以选择实现其边中点落在交叉口通过利用的维诺线的第一个想法DelaunayTri类及其edges和nearestNeighbor方法.这是一个包含10个随机对x和y值的示例:

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矩阵,其中每一行包含的索引成x和y一个边缘限定"近"的连接.下图说明了Delaunay三角剖分(红线),Voronoi图(蓝线),三角剖分边缘的中点(黑色星号)以及剩余的"良好"边缘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

这个怎么运作...

Voronoi图由一系列Voronoi多边形或单元组成.在上图中,每个单元表示给定三角测量顶点周围的区域,该区域包围空间中比任何其他顶点更靠近该顶点的所有点.因此,当您有2个顶点不接近任何其他顶点(如图像中的顶点6和8)时,连接这些顶点的线的中点落在Voronoi单元格之间的分隔线上顶点.

然而,当存在接近连接2个给定顶点的线的第三顶点时,第三顶点的Voronoi单元可以在2个给定顶点之间延伸,穿过连接它们的线并将该线包围在中点.因此,该第三顶点可以被认为是2个给定顶点的"更近"邻居,而不是2个顶点彼此相邻.在您的图像中,顶点7的Voronoi单元格延伸到顶点1和2(以及1和3)之间的区域,因此顶点7被认为是顶点1的顶点比顶点2(或3)更近.

在某些情况下,即使它们的Voronoi单元接触,该算法也可能不会将两个顶点视为"近"邻居.图像中的顶点3和5就是这样的一个例子,其中顶点2被认为是顶点3或5的近似邻居,而顶点3或5彼此相邻.