检查点是否从二维凸包的面上可见

Question

我正在尝试实现Bowyer-Watson算法来生成平面中一组点的Delaunay三角剖分。该算法假设存在一个有边界的超三角形，但也提到了一些替代方案，如保持点集的凸包。

因此，当我们决定在增量算法中通过假设凸壳来产生点的delaunay三角剖分时，如果一个点位于凸壳之外，我们应该绘制从该点到凸壳上的所有顶点的顶点，这些顶点包括从凸壳上可以看到该点的面。

我想知道我该如何处理这个问题？我应该最初生成所有点的凸包，或者像增量方法一样，一次添加一个点，是否应该以DCEL的形式维护一个凸包？

编辑:在上面的图像中，如果我有一个点P，它在平面中一组点的凸包之外，我需要计算从那里可以看到该点的壳的边。船体的绿色边缘

​

我希望这张图片有助于澄清这个问题。

提前感谢

Answer 1

看到P的边是那些在逆时针穿越船体时与P形成顺时针三角形的边(计算有符号的面积)。