寻找邻居
 

我需要在一组要点中找到“附近”的邻居。

[IMG]https://i.stack.imgur.com/fR5pn.png[/IMG]

上图中有10点。红线是[URL="http://www.mathworks.com/help/techdoc/ref/delaunay.html"]Delaunay三角剖分的[/URL]边缘，黑星是边缘的中线，蓝线是[URL="http://www.mathworks.com/help/techdoc/ref/voronoi.html"]Voronoi镶嵌[/URL] 。点1具有三个“近”邻居，即4、6和7，但不是2和3，它们几乎与边1-7对齐，但距离更远。

识别附近邻居（或“良好”边缘）的好方法是什么？从图中可以看出，在我看来，选择中点落在与Voronoi线相交的边上，或将具有接触Voronoi单元格的边视为“近邻”可能是一个很好的解决方案（3-5级可以任意选择）。有没有一种在Matlab中实现这两种解决方案的有效方法（我很乐意获得一个好的通用算法，然后可以将其翻译成Matlab）？



[B]回答：[/B]

您可以通过使用[URL="http://www.mathworks.com/help/techdoc/ref/delaunaytriclass.html"]DelaunayTri类[/URL]及其[URL="http://www.mathworks.com/help/techdoc/ref/trirep.edges.html"]edges[/URL]和[URL="http://www.mathworks.com/help/techdoc/ref/delaunaytri.nearestneighbor.html"]nearestNeighbor[/URL]方法来实现选择中点落在与Voronoi线相交处的边的第一个想法。这是一个带有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 [IMG]https://i.stack.imgur.com/lchJw.png[/IMG]

[B]怎么运行的... [/B]

Voronoi图由一系列Voronoi多边形或单元组成。在上图中，每个像元代表一个给定的三角剖分顶点周围的区域，该区域包围了空间中所有比所有其他顶点更近的点。因此，当您有2个顶点与其他任何顶点都不接近时（例如图像中的顶点6和8），则连接这些顶点的线的中点就落在了Voronoi单元之间的分隔线上顶点。

但是，当第三个顶点靠近连接2个给定顶点的线时，则第三个顶点的Voronoi单元可以在2个给定顶点之间延伸，穿过连接它们的线，并将该线围成中点。因此，该第三个顶点可以被认为是两个给定顶点的“近”邻居，而不是两个顶点彼此相邻。在您的图像中，顶点7的Voronoi单元延伸到顶点1和2（以及1和3）之间的区域，因此，顶点7被认为比顶点2（或3）更接近顶点1。

在某些情况下，即使Voronoi单元接触，该算法也可能不会将两个顶点视为“附近”的邻居。图像中的顶点3和5是这种情况的一个示例，其中顶点2被认为是顶点3或5与顶点3或5彼此之间更近的邻居。



[url=https://stackoverflow.com/questions/4953017]更多&回答...[/url]