寻找附近的邻居

发布于 2024-10-17 03:19:03 字数 580 浏览 7 评论 0 原文

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

pointSet

上图中有 10 个点。红线是 Delaunay 三角剖分的边缘，黑色星星标记中间边缘线，蓝线是 Voronoi 细分。点 1 有三个“近”邻居，即 4、6 和 7，但没有 2 和 3，它们几乎与边 1-7 对齐，但距离更远。

识别近邻（或“好”边缘）的好方法是什么？看图，在我看来，要么选择中点落在与 Voronoi 线相交的边，要么将那些接触 Voronoi 单元的边视为“近”邻居，可能是一个很好的解决方案（3-5 的分类）可以选择任何一种方式）。有没有一种有效的方法可以在 Matlab 中实现任一解决方案（顺便说一句，我很高兴获得一个好的通用算法，然后可以将其转换为 Matlab）？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

顾挽 2024-10-24 03:19:03

您可以通过使用 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×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 个给定顶点之间延伸，穿过连接它们的线并包围该线的中点。因此，与这两个给定顶点之间的距离相比，第三个顶点可以被认为是与这两个给定顶点“更近”的邻居。在图像中，顶点 7 的 Voronoi 单元延伸到顶点 1 和 2（以及 1 和 3）之间的区域，因此顶点 7 被认为比顶点 2（或 3）更靠近顶点 1。

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

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

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

enter image description here

How it works...

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.

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.

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.

回复收藏 0 原文