确定哪个Delaunay边是Gabriel？

Question

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

根据定义，如果一条Delaunay三角边的对圆是空的，就可以说它是一条Gabriel边。因此，为了检查它是否是加布里埃尔边，我们需要进行以下操作 扫描Delaunay的所有有限顶点，检查是否有顶点在该对角线圆内。 或者我们只需要 检验其相邻的两个三角形. 哪个是准确的方案？

Answer 1

你只需要检查相邻的两个三角形。假设其中一个相邻三角形上的第三个顶点不在边的对圆球内（即表明该边可能具有加百列属性）。这个三角形的空（由Delaunay属性）圆周（下图虚线）包含一个与Gabriel球对应的半圆（下图灰色）。如果你检查连接在一条边上的两个Delaunay三角形，就知道加百列球的两半都是空的。