我希望有人能够以较低级的伪代码向我介绍Fortune算法生成Delaunay三角剖分！我在维基百科上读到了一个版本，但它有点混乱，看起来很高级，而我找到的任何一段代码都有原始C实现的不便之处。
我想用C++实现它，但输出结果需要以我自己定义的类形式（顶点、边和三角形作为对象）呈现。所以我需要完全理解它，并从头开始实现它。
我也阅读了算法的描述，知道它是什么以及如何工作，但对我来说还是太抽象了。然而，如果有一个类似的描述进入（实现）细节，我也会很高兴的，它不必像代码一样！
查找Fortune算法的伪代码
15
- Vincent
2
1不使用CGAL有什么好的理由吗？德劳内三角剖分非常棘手，很难正确实现：您肯定会遇到舍入误差，这将破坏任何不使用自适应精度算法的实现。 - Alexandre C.
1唯一的原因是我以前从未听说过它 :) 除了商业用途的商业许可证之外，这看起来非常有前途，但我想这没关系。我会稍微试用一下，看看它是否足够满足我的需求，但如果没有人提供一个好的伪代码，并且实现起来真的很难，你可能需要将其重复作为我可以标记为最佳答案的答案！ - Vincent
1个回答
23
我花了大约一个月的时间才完全理解Fortune算法，并且我写了我的研究论文。一旦你懂了，它看起来非常容易 :)
这是我对Fortune算法的介绍，包括命令式伪代码和实现细节。
- Ivan
2
非常感谢，这正是我要找的！我很快会仔细看一下，但我相信这就是答案，所以我会将其标记为答案 :) - Vincent
1@Ivan 我知道这是加密评论，但这让我发疯...我读了 Steven Fortune 在他 87 年的论文中提到的原始算法，它与几乎所有其他地方描述和实现的算法都不同，包括你的页面。Fortune 的论文没有用拱线形成的海滩线，而是概念上处理一系列双曲线弧 (尽管没有必要显式存储它)。我怀疑 "通常" 的解释是后来被其他人找到的 (例如 de Berg、Cheong、van Kreveld 和 Overmars 中的一个或多个) 作为等价物。但我想听听你的意见！ - polettix
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接