检查一个点从 2d 凸包的面上是否可见
我正在尝试实现 Bowyer-Watson 算法来生成平面上一组点的 Delaunay 三角剖分。该算法假设存在边界超三角形，但也提到了一些替代方案，例如维护点集的凸包。
因此，当我们决定通过在增量算法中假设凸包来生成点的德劳内三角剖分时，如果一个点位于凸包之外，我们应该从该点绘制顶点到构成面的凸包上的所有顶点从该点可见的船体。
我想知道如何解决这个问题？我是否应该首先生成所有点的凸包，或者像增量方法中每次添加一个点一样，我是否应该以 DCEL 的形式维护凸包？
编辑：在上图中，如果我的点 P 位于平面上一组点的凸包之外，我需要计算该点可见的包的边缘。 [船体的绿色边缘] 
我希望该图片有助于澄清问题。
提前致谢
I am trying to implement the Bowyer-Watson algorithm for generating a Delaunay Triangulation of a set of points in a plane. The algorithm assumes a presence of a bounding super-triangle, but some alternatives like maintaining the convex hull of the set of points have also been mentioned.
Thus, when we decide to produce a delaunay triangulation of points by assuming a convex hull in an incremental algorithm, if a point lies outside the convex hull, we should draw vertices from the point to all the vertices on the convex hull which comprise the faces of the hull from which the point is visible.
I was wondering how could I approach this problem? Should I initially generate a convex hull of all the points or like in the incremental approach where points are added one at a time, should i maintain a convex hull in the form of a DCEL?
EDIT: In the image above, if I have the point P which is outside the convex hull of a set of points in a plane, I need to calculate the edges of the hull from which the point is visible. [The green edge of the hull]
I hope the image helps in clarifying the question.
Thanks in advance
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
看到 P 的边是当船体逆时针移动时与 P 形成顺时针三角形的边（计算有符号面积）。
The edges that see P are those that form a clockwise triangle with P when the hull is traversed counterclockwise (compute the signed area).