我需要在一组点中找到“近”邻居。
上图中有 10 个点。红线是Delaunay 三角剖分的边缘，黑色星星标记边缘的中线，蓝线是Voronoi 镶嵌。点 1 有 3 个“近”邻居，即 4、6 和 7，但不是 2 和 3，它们几乎与边缘 1-7 一致，但距离更远。
什么是识别近邻（或“好”边缘）的好方法？看这个图，在我看来，要么选择中点落在与 Voronoi 线相交的边缘，要么将那些与 Voronoi 细胞接触的边缘视为“近”邻居，这可能是一个很好的解决方案（3-5 的分类）可以去任何一种方式）。是否有一种在 Matlab 中实现任一解决方案的有效方法（我很高兴得到一个好的通用算法，然后我可以将其转换为 Matlab，顺便说一句）？
DelaunayTri您可以通过使用类及其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 多边形或单元组成。在上图中，每个单元表示给定三角剖分顶点周围的区域，该区域包含空间中比任何其他顶点更接近该顶点的所有点。因此，当您有 2 个顶点不靠近任何其他顶点（如图像中的顶点 6 和 8）时，连接这些顶点的线的中点落在 Voronoi 单元之间的分隔线上顶点。
但是，当有第三个顶点靠近连接 2 个给定顶点的线时，则第三个顶点的 Voronoi 单元可能在 2 个给定顶点之间延伸，穿过连接它们的线并包围该线的中点。因此，这第三个顶点可以被认为是 2 个给定顶点的“更近”邻居，而不是 2 个顶点彼此之间的距离。在您的图像中，顶点 7 的 Voronoi 单元延伸到顶点 1 和 2（以及 1 和 3）之间的区域，因此顶点 7 被认为比顶点 2（或 3）更接近顶点 1。
在某些情况下，即使两个顶点的 Voronoi 单元相接触，该算法也可能不会将两个顶点视为“近”邻居。图像中的顶点 3 和 5 就是一个例子，其中顶点 2 被认为是顶点 3 或 5 比顶点 3 或 5 彼此更接近的邻居。
我同意共享单元边缘是一个很好的邻居标准（基于这个例子）。如果您使用的是面向网格的数据结构（如 Gts 中的某些东西），那么识别共享边将是微不足道的。
另一方面，Matlab 使这更“有趣”。假设 voronoi 单元存储为补丁，您可以尝试获取“Faces”补丁属性（请参阅此参考）。这应该返回类似识别连接顶点的邻接矩阵。由此（还有一点魔法），您应该能够确定共享顶点，然后推断共享边。根据我的经验，这种“搜索”问题不太适合 Matlab - 如果可能，我建议转移到更适合查询网格连接的系统。
比创建三角剖分或 voronoi 图更简单的另一种可能性是使用邻域矩阵。
首先将所有点放入二维方阵中。然后您可以运行完整或部分空间排序，因此点将在矩阵内变得有序。
Y 小的点可以移动到矩阵的顶行，同样，Y 大的点会移动到矩阵的底行。具有较小 X 坐标的点也会发生同样的情况，这些点应该移动到左侧的列。并且对称地，具有大 X 值的点将进入右列。
完成空间排序后（有很多方法可以通过串行或并行算法实现这一点），您可以通过访问点 P 实际存储在邻域矩阵中的相邻单元来查找给定点 P 的最近点。
您可以在以下论文中阅读有关此想法的更多详细信息（您可以在线找到它的 PDF 副本）：基于紧急行为的 GPU 上的超大规模人群模拟。
排序步骤为您提供了有趣的选择。您可以只使用论文中描述的奇偶转置排序，它实现起来非常简单（即使在 CUDA 中也是如此）。如果你只运行一次，它会给你一个部分排序，如果你的矩阵是接近排序的，这可能已经很有用了。也就是说，如果您的点移动缓慢，它将为您节省大量计算。
如果你需要一个完整的排序，你可以多次运行这样的奇偶转置传递（如下面的维基百科页面所述）：