1

我试图在给定的数据集中找到边缘相邻的 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');

这是输出：Voronoi Delaunay 情节

作为问题的一个例子，看图右端的点 X 连接到左下角附近的点 Y。

另一个例子是在这个 SO question - 点 1 连接到 2 和 3，即使它们不相邻，而且即使扩展到无穷大，1 和 2 似乎也没有任何方式可以共享一条边。这个问题实际上是促使我用上面的代码测试 delaunayn 输出的原因。

为什么会发生这种情况，我如何真正获得我需要的边缘相邻区域？

注意：要查看完整尺寸和清晰度的图像，请右键单击并选择“查看图像”或类似选项。

4

1 回答 1

2

据我所见（图表的质量不太好），X 和 Y 的区域应该在绘图部分下方相邻。如果你缩小得足够远，你应该会看到它们。

即 X 和 Y 相交的边缘存在，但只是没有显示在图上。

下图并没有显示绘图区域之外的voronoi图，而是如何找到上面描述的交点（注意，这里没有显示平分线）： 扩展的voronoi图

于 2011-11-24T07:23:02.033 回答