凸包误解？

Question

我编写了一个 Graham 扫描凸包算法的实现，测试数据使用了这些点。

[(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都是错误的？

- Ra is dead

---

你从哪里获取期望点数的？ - Blender

这就是我的直觉和“橡皮筋”比喻所产生的结果。 - Ra is dead

Answer 1

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

真实的：

因此，您的多边形既不是凸多边形，因为按照凸多边形的定义，多边形内的所有点对必须形成仅包含该多边形中的点的线段。例如，从{4,4}到{4,2}的线段超出了多边形。 其次，您的多边形也不是凸包，因为橡皮无法弯曲到多边形内部的点{3., 2.5}。 所以您需要修复您的算法。

- Agnius Vasiliauskas

---

凸包不应该是最小的吗？也就是说，（1,4）不应该是它的一部分吗？ - Christofer Ohlsson

Answer 2

你的直觉解决方案是正确的，只是多了一个点：(1, 4)。凸包通常被定义为最小凸集。包括(1, 4)，这个集合是凸的，但它不是最小的，因为(1, 4)在集合中另外两个点(0,4)和(4,4)之间的线上。如果你移除(1, 4)，那么想象中的橡皮筋的形状不会改变。

看起来你的程序有一个bug。

- zoo

---

False - OP（原帖作者）的解决方案既不是“凸”也不是“凸包”。请见我的答案。 - Agnius Vasiliauskas

True - Graham扫描算法的OP解决方案是错误的，但他凭直觉得出的解决方案是正确的。 - zoo

是的，我只评论了他的实现输出。 - Agnius Vasiliauskas