Delaunay 三角剖分、分而治之算法
我在DT Lee 和 BJ Schachter 所著的“构建 Delaunay 三角剖分的两种算法”中读到了有关该算法的内容，国际计算机与信息科学杂志，第 1 卷。 9，第 3 期，1980 年。我不太明白如何在合并阶段实现该部分，您需要找到两半之间的公共下切线和上切线。我是否需要为两个半部构造一个凸包，其中顶点按顺时针或逆时针顺序排序，如果是这样，我如何才能做到这一点，同时递归计算 Delaunay 三角剖分而不超过 O(nlogn)时间。是否有可能以递归方式同时执行这两项操作，我走在正确的道路上吗？
I've read about the algorithm in "Two algorithms for constructing a Delaunay triangulation" by D. T. Lee and B. J. Schachter, International Journal of Computer and Information Sciences, Vol. 9, No. 3, 1980. I don't quite understand how to implement the part in the merging stage where you need to find the common lower and upper tangent between the two halves. Do I need to construct a convex hull for both halves, where the vertices are sorted in clockwise or counter-clockwise order, and if so how can I manage to do that whilst recursively computing the Delaunay triangulation without exceeding O(nlogn) time. Is it maybe possible to do both simultaneously in a recursive manner, am I on the right path?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论