java - 随机生成约束边以生成约束 delaunay 三角剖分

Question

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

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

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

提前致谢。

Answer 1

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

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

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

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

Triangle软件包中包含几个可能在这方面有用的基准几何图形。

希望这对您有所帮助。