为什么 Matlab 的 delaunayn() 中的 delaunay 边将点与不相邻的 Voronoi 区域连接起来？
我试图在给定的数据集中找到与边缘相邻的 Voronoi 区域的点。我是计算几何的新手，但从在线阅读来看，使用 Delaunay 曲面细分似乎是实现此目的的一种简单方法。 此 PDF 特别是有一个引理指出
引理 2.4 S 的两个点由 Delaunay 边连接当且仅当它们的 Voronoi 区域 边缘相邻。
因此，我发现数据集的 delaunay 细分为：
dt = delaunay(dataset); %using delaunayn() since dataset can be multidimensional
但是现在，当我将其与该数据集的 voronoi 图一起绘制时，我发现 delaunay 边返回的连接点的区域实际上并不与边相邻。
这是我用来一起绘制 Voronoi 和 Delaunay 的代码：
voronoi(dataset(:, 1),dataset(:, 2));
hold on;
dt = delaunayn(dataset);
triplot(dt, dataset(:, 1), dataset(:, 2), 'red');
这是输出： 
作为示例问题，请参见图右端的 X 点与左下角附近的 Y 点相连。
另一个例子是这个SO问题 - 点1连接到2和3，即使它们' re 不相邻，而且即使扩展到无穷大，1 和 2 似乎也无法共享一条边。这个问题实际上促使我使用上面的代码测试 delaunayn 输出。
为什么会发生这种情况，以及如何真正获得我需要的边缘相邻的邻居区域？
注意：要查看完整尺寸和清晰度的图像，请右键单击并选择“查看图像”或类似选项。
I am trying to find the points with edge-adjacent Voronoi regions in a given dataset. I'm new to computational geometry, but from reading up online, it appeared that using the Delaunay tessellation would be an easy way to do this. This PDF in particular even has a lemma that states
Lemma 2.4 Two points of S are joined by a Delaunay edge iff their Voronoi regions
are edge-adjacent.
So, I found the delaunay tessellation of my dataset as
dt = delaunay(dataset); %using delaunayn() since dataset can be multidimensional
But now, when I plot this along with the voronoi diagram for this dataset, I find that the delaunay edges returned connect points whose regions are not actually edge-adjacent.
Here is the code I used to plot Voronoi and Delaunay together:
voronoi(dataset(:, 1),dataset(:, 2));
hold on;
dt = delaunayn(dataset);
triplot(dt, dataset(:, 1), dataset(:, 2), 'red');
And here is the output:
As an example of the problem, see the point X on the right end of the figure connected to point Y near the lower left corner.
Another example is in this SO question - the point 1 is connected to 2 and 3, even though they're not adjacent, and there doesn't seem to be any way 1 and 2 could share an edge even if extended to infinity. This question is actually what prompted me to test the delaunayn output with the above code.
Why is this happening, and how do I actually get the edge-adjacent neighbour regions that I need?
Note: For seeing the image in full size and clarity, please right click and choose 'View image' or similar.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
据我所知（图表的质量不太好），X 和 Y 的区域应该在绘制部分的下方相邻。如果你缩小得足够远，你应该可以看到它们。
即 X 和 Y 相交的边存在，但只是未显示在绘图上。
下图不是显示绘图区域之外的voronoi图，而是如何找到上面描述的交点（注意，这里没有显示平分线）：
As far as I can see (the quality of the diagram is not so good), the regions for X and Y should be adjacent below the plotted part. If you zoom out far enough, you should see them.
I.e. the edge where X and Y meet exists, but is just not shown on the plot.
The following diagram does not show the voronoi diagram outside of the plotting area, but how to find the intersection point described above (note, the bisector is not shown here):
