在邻居附近寻找 [英] Finding near neighbors

问题描述

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

I need to find "near" neighbors among a set of points.

上图中有10点.红线是 Delaunay三角剖分的边缘，黑色星号表示中间的-边缘的蓝色线是 Voronoi镶嵌.点1具有三个近"邻居，即4、6和7，但没有2和3，它们几乎与边1-7对齐，但距离更远.

There are 10 points in the above image. Red lines are edges from the Delaunay Triangulation, black stars mark the mid-lines of the edges, blue lines are the Voronoi tesselation. Point 1 has three "near" neighbors, i.e. 4, 6, and 7, but not 2 and 3, who are almost in line with the edge 1-7, but much further away.

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

What is a good way to identify the near neighbors (or "good" edges)? Looking at the figure, it seems to me that either selecting edges whose mid-point falls onto the intersection with the Voronoi lines, or considering as "near" neighbors those with touching Voronoi cells could be a good solution (the classification of 3-5 can go either way). Is there an efficient way of implementing either of the solutions in Matlab (I'd be happy to get a good general algorithm that I can then translate to Matlab, btw)?

推荐答案

您可以通过使用

You can implement your first idea of selecting edges whose mid-points fall on the intersection with the Voronoi lines by making use of the DelaunayTri class and its edges and nearestNeighbor methods. Here's an example with 10 random pairs of x and y values:

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中保留的良好"边线(粗红线):

And now edgeIndex is an N-by-2 matrix where each row contains the indices into x and y for one edge that defines a "near" connection. The following plot illustrates the Delaunay triangulation (red lines), Voronoi diagram (blue lines), midpoints of the triangulation edges (black asterisks), and the "good" edges that remain in edgeIndex (thick red lines):

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单元之间的分隔线上顶点.

The Voronoi diagram is comprised of a series of Voronoi polygons, or cells. In the above image, each cell represents the region around a given triangulation vertex which encloses all the points in space that are closer to that vertex than any other vertex. As a result of this, when you have 2 vertices that aren't close to any other vertices (like vertices 6 and 8 in your image) then the midpoint of the line joining those vertices falls on the separating line between the Voronoi cells for the vertices.

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

However, when there is a third vertex that is close to the line joining 2 given vertices then the Voronoi cell for the third vertex may extend between the 2 given vertices, crossing the line joining them and enclosing that lines midpoint. This third vertex can therefore be considered a "nearer" neighbor to the 2 given vertices than the 2 vertices are to each other. In your image, the Voronoi cell for vertex 7 extends into the region between vertices 1 and 2 (and 1 and 3), so vertex 7 is considered a nearer neighbor to vertex 1 than vertex 2 (or 3) is.

在某些情况下，即使它们的Voronoi细胞接触，该算法也可能不会将两个顶点视为近邻".图像中的顶点3和5就是一个例子，其中顶点2被认为比顶点3或5与顶点3或5更近.

In some cases, this algorithm may not consider two vertices as "near" neighbors even though their Voronoi cells touch. Vertices 3 and 5 in your image are an example of this, where vertex 2 is considered a nearer neighbor to vertices 3 or 5 than vertices 3 or 5 are to each other.

这篇关于在邻居附近寻找的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！