algorithm - 凸壳误解？

Question

我写了一个格雷厄姆扫描凸包算法的实现，对于测试数据，我使用了这些点

[(2.0,2.0),(4.0,2.0),(0.5,2.5),(3.0,3.5),(1.0,4.0),(0.0,4.0),(1.0,1.0),(3.0,2.5),(4.0,4.0),(3.5,1.5),(0.5,1.0)]

根据我的程序，凸包是

[(0.0,4.0),(1.0,4.0),(4.0,4.0),(3.0,2.5),(4.0,2.0),(3.5,1.5),(1.0,1.0),(0.5,1.0)]

但是，我希望凸包是

[(0.0,4.0),(1.0,4.0),(4.0,4.0),(4.0,2.0),(3.5,1.5),(1.0,1.0),(0.5,1.0)]

我也用https://github.com/shadwstalkr/GrahamScanDemo/尝试了我的一组点，这也给出了相同的解决方案。经过多次抱怨和抱怨后，我在维基百科上读到“如果对象内的每一对点，连接它们的直线段上的每个点也在对象内，则该对象是凸的。”

在画出我的观点和船体之后。看来我的程序在该定义内生成了一个对象，但这是否意味着仅按角度排序就会给出一个凸包，而在包中没有任何点？

我是否不了解凸包实际上是什么并且我正在解决一个不同的问题，或者我的实现和 shadwstalkr 都不正确？

Answer 1

通过使用wolframalpha Polygon{}命令，您可以看到您的解决方案与真实解决方案之间的差异：
您的：

真实的：

所以你的多边形既不是convex，因为根据凸多边形的定义，多边形内的所有点对必须形成仅包含来自该多边形的点的线段。例如，从{4,4}到的线{4,2}形成了多边形之外的线段。其次 - 你的多边形既不是convex hull因为橡胶不能弯曲到多边形内部来指向{3., 2.5}。所以你需要修复你的算法。

Answer 2

您的直观解决方案是正确的，只是它有一点太多：(1, 4). 凸包通常定义为最小凸集。包括(1, 4)，集合是凸的，但它不是最小的，因为它位于(1, 4)集合中其他两个点之间的线上：(0,4)和(4,4)。如果去掉(1, 4)，假想的橡皮筋的形状不会改变。

看起来您的程序中存在错误。