最近，我写了一个算法来获得一个随机点集的delaunay三角剖分$I=[-10,10]$x通过将这些点投影到 3 维抛物面上，计算凸包，然后将下包投影回。我已经验证了我的凸包算法产生了正确的结果。因此，我确信问题在于我获得下壳的方法。 $[-10,10] \subset R^2$$z=x^2+y^2$$R^2$

我的下壳提取算法类似于生成凸包的增量构造算法。也就是说，如果我们选择一个负无穷远的点并从该点向上照射船体，我们应该能够看到整个下部船体并能够完全提取它。当然，在计算上，我们不能真正使用负无穷大作为数字。但是在船体下方必须有一个最佳点，整个下部船体应该是可见的。（注意：此处的可见性由带符号的方向确定）。

在我的问题中，由于点集接近原点 (x,y)=(0,0)，因此我选择沿负 z 轴寻找最佳视点。我认为由于下壳上的点在抛物面上，我们可以利用抛物面随着 (x,y) 输入坐标沿径向移动而单调递增的事实从原点 (0,0)。因此，点集中 x,y 坐标离原点 (0,0) 最远的点不仅在抛物面上具有最高的 z 坐标，而且具有最陡的切平面。此外，这个切平面与负 z 轴相交的地方应该是可以看到整个下船体的最佳点。 $z=x^2 + y^2$

当我尝试这个算法时，它似乎并不完美。也就是说，它能够提取下船体的几乎所有方面。上）非常薄且位于 2D 外壳（即外边界三角形）上的刻面时遇到问题。在这些情况下，我不得不将我的初始视点降低多达或更多，这取决于二维 delaunay 三角剖分外边界上三角形的薄度。$R^2$$10^5$

我知道还有其他方法可以获得下壳，但我真的更感兴趣的是了解我的原始算法中的缺陷在哪里。由于抛物面是单调向上凹的，因此最佳视点不应该位于 z 轴上的切平面撞击 z 轴的点上，其中是从给定点集（在中）投影到抛物面（在中，其 (x,y) 坐标离原点最远的点？ $(x^*,y^*,z^*)$$(x^*,y^*,z^*)$$R^2$$R^3$