2

我已经实现了 Domiter 和 Zalik 使用的扫描线方法，以在 Java 中为 2D 空间中的一组点生成约束 Delaunay 三角剖分。我想确保我开发的代码真正适用于n随机生成的点和k其中的约束边。

现在使用通用策略，我想从一组n顶点中选择一个随机点，然后选择第二个随机点并在它们之间有一条边可能不起作用，因为我从受约束的 Delaunay 三角剖分的定义中了解到约束边是平面直线图的边。因此它们是不相交的。如果这些点是随机选择的，则可能必须执行检查以确定它们不会产生相交约束。这种方法可能根本没有效率。

因此，我想知道是否有人知道随机生成约束的有效策略。

提前致谢。

4

1 回答 1

3

您可以尝试两个阶段的过程：

  • 生成一小组随机点并构建不受约束的 Delaunay 三角剖分。然后，您可以从这个小三角剖分的边缘中随机选择以形成一组约束边缘。显然，由于边缘来自三角剖分，它们将不相交。

  • 将一组额外的随机点附加到数据集并构建完整集的约束 Delaunay 三角剖分，施加先前找到的约束边。

虽然我相信这种方法是为三角测量代码构建非相交、随机约束数据集的有效方法，但更好的方法可能是使用真实数据进行测试。

Triangle包包括几个在这方面可能有用的基准几何图形。

希望这可以帮助。

于 2012-03-22T06:00:13.063 回答