您可以使用DelaunayTri类及其边和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-by-2矩阵，其中每一行都包含定义“近”连接的一条边的xy的索引。下图显示了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

How it works...

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

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

在某些情况下，该算法可能不会将两个顶点视为“近”邻居，即使它们的Voronoi单元接触。图像中的顶点3和5就是一个例子，其中顶点2被认为是与顶点3或5的邻居，而不是与顶点3或者5的邻居。

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

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

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

首先将所有点放置在二维正方形矩阵中。然后你可以运行完全或部分空间排序，这样点就会在矩阵中有序排列。

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

在进行空间排序后（有很多方法可以实现这一点，既可以通过串行算法也可以通过并行算法），您可以通过访问点P实际存储在邻域矩阵中的相邻单元来查找给定点P的最近点。

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

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

如果你需要一个完整的排序，你可以多次运行这种奇偶换位传递（如以下维基百科页面所述）：

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