查找近邻

Question

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

​

​

上图中有10个点。红色线条是Delaunay Triangulation的边缘，黑色星形标记边缘的中线，蓝色线条是Voronoi tesselation。点1有三个“近”邻居，即4、6和7，但不是2和3，它们几乎与边1-7一致，但更远。

识别近邻(或“好”边)的好方法是什么？从图中看，在我看来，要么选择中点落在Voronoi线交叉点上的边，要么将那些接触Voronoi单元的边视为“近邻”，这可能是一个很好的解决方案( 3-5的分类可以是任何一种方式)。有没有一种有效的方法在Matlab中实现这两种解决方案(我很乐意得到一个很好的通用算法，然后我可以将其翻译成Matlab，顺便说一句)？

Answer 1

您可以通过使用DelaunayTri class及其edges和nearestNeighbor方法来实现您的第一个想法，即选择其中点位于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

​

​

它是如何工作的..。

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

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

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

Answer 2

我同意共享单元边缘是一个很好的邻居标准(基于这个例子)。如果您使用的是面向网格的数据结构(类似于Gts中的内容)，那么识别共享边将是微不足道的。

另一方面，Matlab使这变得更“有趣”。假设voronoi单元被存储为补丁，您可以尝试获取“Faces”补丁属性(请参阅this reference)。这应该会返回一些类似于邻接矩阵的东西，它可以识别连接的顶点。由此(还有一点魔力)，你应该能够确定共享顶点，然后推断出共享边。根据我的经验，这种“搜索”问题不太适合Matlab --如果可能的话，我建议转移到一个更适合于网格连接查询的系统。

Answer 3

另一种比创建三角剖分或voronoi图更简单的可能性是使用邻域矩阵。

首先把你所有的点放到一个2D方阵中。然后，您可以运行完全或部分空间排序，因此点将在矩阵中排序。

具有小Y的点可以移动到矩阵的顶行，同样，具有大Y的点将移动到底行。具有较小X坐标的点也会发生同样的情况，这些点应该移动到左侧的列中。对称地，具有较大X值的点将转到右侧列。

在进行空间排序之后(有许多方法可以实现这一点，无论是串行算法还是并行算法)，您只需访问点P实际存储在邻域矩阵中的相邻单元格，就可以查找给定点P的最近点。

你可以在下面的文章中阅读更多关于这个想法的细节(你可以在网上找到它的PDF副本)：基于紧急行为的GPU上的超大规模人群模拟。

排序步骤为您提供了有趣的选择。您可以只使用本文中描述的奇偶转置排序，它的实现非常简单(即使在CUDA中也是如此)。如果你只运行一次，它会给你一个部分排序，如果你的矩阵是近似排序的，这可能已经很有用了。也就是说，如果你的点移动得很慢，它将为你节省大量的计算。

如果您需要完整排序，您可以多次运行这种奇偶转置传递(如以下维基百科页面所述)：

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort