algorithm - 浅析凸包的格雷厄姆扫描算法

Question

我编写了一个代码来实现凸包的格雷厄姆扫描算法。我通过生成一些测试用例来测试程序。在所有情况下，它都会给出准确的结果。但我的问题是，当程序可能无法给出完美的凸包作为输出时，是否有可能生成一些棘手的测试用例？产生这种情况的过程是怎样的？

Answer 1

正如 Sascha 在评论中回答的那样，如果不知道您是如何实现算法的，就不可能帮助您生成棘手的测试用例或知道这是否可行。

算法本身当然被证明是正确的并且能够解决问题。因此，这只是关于测试您的实现是否按照算法所说的那样进行。

我建议尝试向自己证明您的实现 - 证明您得到的起点是正确的，证明您为排序所做的计算为什么按角度给出正确的排序顺序，证明计算所依据的决定丢一分或继续是基于等价于(或直接算出)右转或左转的问题，并证明算法的每一步都在你的实现中执行。

所有这些证明都可以进行两次 - 理论上进行一次，然后使用针对特定问题的测试代码以及​​为它们构建的测试用例(例如检查右转/左转计算是否正确完成你不需要算法的其余部分 - 只需针对已知的正确结果测试许多可能的星座的 3 点集，以测试您使用的计算是否给出正确答案)。