分析凸包的Graham扫描算法

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

只需生成一些随机测试用例并检查您的解决方案。对于大型实例，检查它是否包含所有点很容易。为了检查它是否是最小的壳体，可以生成小的测试用例并与穷举搜索进行比较。没有您的算法知识，就无法生成硬实例。你也可以实现一个函数，在你知道最佳解决方案的地方生成实例（通过构造）。但它会更加偏向。 – sascha

当点共线时，凸壳代码有时会破裂，特别是在船体上。 –

压力测试是通过让所有站点在水平/垂直或斜线上共线。还重复了顶点。如果您使用了基于极坐标的实现，请尝试使用站点与中心对齐的配置。 –

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

该算法本身当然被证明是正确的，并解决问题。所以它只是测试你的实现是否执行算法所说的。

我会建议试图向自己证明你的实现 - 证明你正确的作为出发点，证明你为排序做的计算是按照角度给出正确的排序顺序，证明计算结果决定放弃还是继续是基于等同于（或直接找出）右转或左转问题，并证明算法的每一步都在您的实现中执行。

所有这些证明都可以进行两次 - 理论上一次，然后使用测试代码将测试代码定位到为其构建的测试用例（例如，检查右转/左转计算是否正确完成您不需要算法的其余部分 - 只需测试大量3点集合，并根据已知的正确结果对每个星座进行测试，以测试您使用的计算是否给出正确的答案）。

2016-09-17 23:16:16

回答