确定哪个Delaunay边是Gabriel边

Question

确定哪个Delaunay边是Gabriel边

3

我的目的是实现一个算法来检查Delaunay边是否为Gabriel边。

根据定义，如果Delaunay三角划分边的直径圆为空，则其被称为Gabriel边。因此，要检查它是否是Gabriel边，我们需要扫描所有Delaunay中的有限顶点以检查是否有任何一个位于该直径圆内，或者我们只需要检查其两个相邻的三角形。哪一种选项更准确呢？

- marcterenzi

相邻的两个顶点就足够了，你肯定不需要检查图中的每个顶点。请参阅Wikipedia文章。将Delaunay三角剖分转换为其Gabriel图的性能应该是O（N）。 - Nuclearman

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alex · Accepted Answer

你只需要检查相邻的两个三角形。假设相邻三角形中的第三个顶点不在边界球的直径内（即暗示该边可能具有Gabriel属性）。该三角形的空圆（根据Delaunay属性）包含对应于Gabriel球体的半圆（下面是灰色的）。如果你检查连接到一条边的两个Delaunay三角形，则知道Gabriel球体的两半都为空。