Chazelle的内三角算法

Question

实施

没有为三角测量线性时间，由于Chazelle（1991）多边形的算法，但AFAIK有没有他的一般数学软件库算法的任何标准实现。有没有人知道我通过谷歌搜索找不到这样的实现？

Answer 1

看到这个answer to "Powerful Algorithms too complex to implement"：

根据Skienna（算法设计手册的作者），“那里的算法相当无望实现。”

我查找过一个实现，但找不到一个。我认为可以肯定的是，由于它的复杂性，没有人实现它，我认为它也有相当大的不变系数，所以对于具有较小常数因子的算法不会很好。