algorithm - Chazelle三角剖分算法的实现

Question

有一个algorithm for triangulating a polygon in linear time由于 Chazelle (1991)，但是，AFAIK，在一般数学软件库中没有任何标准实现他的算法。

有人知道这样的实现吗？

Answer 1

查看此 answer问题Powerful algorithms too complex to implement :

According to Skiena (author of The Algorithm Design Manual), "[the] algorithm is quite hopeless to implement."

我之前曾寻找过一种实现方式，但找不到。我认为可以肯定的是，由于它的复杂性，没有人实现过它，而且我认为它还有一个相当大的常数因子，因此不能很好地对抗 O(n lg n) 算法具有更小的常数因子。