随机生成约束条件以生成约束Delaunay三角剖分

Question

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

现在使用通用的策略，我想请从组n顶点的随机点，然后选择第二个随机点，并有因为我从一个约束德劳的定义理解它们之间的边缘可能无法正常工作三角剖分是约束边是平面直线图的边。因此它们不相交。如果随机选择点，则可能必须执行检查以确定它们不会产生相交约束。这种方法可能效率不高。

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

在此先感谢。

Answer 1

你可以尝试两个阶段：

• 产生一个小的组随机点，构建一个非约束Delaunay三角。然后，您可以从这个小三角形的边缘内随机选择，形成一组约束边。显然，由于边缘来自三角测量，所以它们将不相交。

• 向数据集添加一组附加的随机点并构造全集的约束Delaunay三角剖分，强加先前找到的约束边。

虽然我相信这个方法是建立一个不相交，随机约束数据三角码设置，更好的方法可能是使用真实数据来测试一种有效的方式。

Triangle包装包括几个基准几何形状，在这方面可能很有用。

希望这会有所帮助。