我需要一种快速算法来找到大型简单封闭多边形的凸包。
Lee 的算法（如此处第 2.1 节所述）在大多数情况下都很好，但不是所有情况。例如，顺时针多边形 (3,3)-(1,2)-(2,1)-(2,2)-(3,0)-(0,1)-(0,3)-(3 ,3) 将得到解决方案 (3,3)-(2,1)-(0,1)-(0,3)-(3,3) - 它不包括所有顶点。
错误是 (2,2) 被放入堆栈。我看不出如何修改 Lee 的算法来纠正这个问题。你能？
当然，我可以改用 Melkman 的算法，但 Lee 的算法利用了我的条件，使它更简单、更快速，如果可能的话，我更喜欢它。此外，我很惊讶文献中的 Lee 算法据说是正确的。